optimized cutting plane alg. for large-scale risk minimization, JMLR.

• binary svm without bias term なら kernel化は(形式的には)できます。問題の設定から、bias項についてはもともと考えていない。もちろん、入力を拡張して bias を入れることはできるが、regularization term が少しだけ異なるため、svm そのものではなくなります。
• 計算量については、sub-gradient のところで Gram matrix との掛け算が出てくるので、sparse でないなら O(m^2), m: #samples. 著者らは conclusion で、カーネル化についても考えたいと言っているが、この計算量を気にしているのでしょうか?
  • line search のために計算しておく係数達にどのくらいの計算時間が必要か、linear-kernel と non-linear kernel で order が異なるのかもしれません。要確認 → 計算量は同じ。単に represeneter theorem から得られる primal でアルゴリズムを実行すればいいのでは?
• convergence rate の導出に differential eq. を使っています。これは online learning で learning rate も学習するときの convergence rate の導出に似ています。大雑把に言えば、sub-differential+line search と stochastic gradient+adaptive learning rate は、最適解の近くでほとんど同じ挙動を示す、ということのようです。