一種基於新的信賴區間更新規則之高效牛頓法於大規模線性分類

Abstract

線性分類的一個主要任務是解決最小化問題。雖然有很多最優化技術可以方便地運用，但是對於大規模資料需要有特殊的演算法改進。典型的無規則最優化演算法迭代地進行兩個過程：尋找一個好的下降方向，然後調整合適的步長。過去的線性分類發展主要集中在尋找下降方向，而很少考慮調整步長。在這篇論文中，我們提出了一種新穎的調整信賴區間大小的方法來間接地調整步長。這個設定嵌於一個針對邏輯迴歸和L2損失支援向量機的信賴區間牛頓法中。實驗證明我們的新方法極大地領先現有的大規模線性分類方法。

The main task in training a linear classification is to solve an unconstrained minimization problem. While many optimization techniques can be conveniently applied, special algorithmic development and implementation tricks are needed to handle large scale data sets. Typically, an unconstrained optimization method iteratively conduct two procedures of finding a good direction and then deciding a suitable step size. Past developments for linear classification focus on finding the direction, but little attention has been paid on adjusting the step size. In this work, we develop novel techniques to adjust the trust-region size that indirectly decides the step length. The setting is embedded into a trust region Newton method for logistic regression and L2-loss SVM. Experiments indicate that our new settings significantly outperform existing implementations for large-scale linear classification.