Fast Margin Maximization via Dual Acceleration
This work provides a faster method for margin maximization in machine learning, which is incremental as it builds on existing momentum and dual techniques.
The paper tackles the problem of training linear classifiers with exponentially-tailed losses on separable data, achieving a margin maximization rate of O~(1/t^2), which is faster than standard gradient descent's O(1/log(t)) and normalized gradient descent's O(1/t).
We present and analyze a momentum-based gradient method for training linear classifiers with an exponentially-tailed loss (e.g., the exponential or logistic loss), which maximizes the classification margin on separable data at a rate of $\widetilde{\mathcal{O}}(1/t^2)$. This contrasts with a rate of $\mathcal{O}(1/\log(t))$ for standard gradient descent, and $\mathcal{O}(1/t)$ for normalized gradient descent. This momentum-based method is derived via the convex dual of the maximum-margin problem, and specifically by applying Nesterov acceleration to this dual, which manages to result in a simple and intuitive method in the primal. This dual view can also be used to derive a stochastic variant, which performs adaptive non-uniform sampling via the dual variables.