Fast Margin Maximization via Dual Acceleration
Fast Margin Maximization via Dual Acceleration
复制标题
DOI：
--
复制
发表时间：
2021-07
期刊：
影响因子：
--
通讯作者：
Ziwei Ji;N. Srebro;Matus Telgarsky
中科院分区：
文献类型：
--
作者：
Ziwei Ji;N. Srebro;Matus Telgarsky
我们提出并分析了一种基于动量的梯度方法，用于训练具有指数尾损失的线性分类器（例如，指数或逻辑损失），它以$\widetilde{\mathcal{O}}（1/t^2）$的速率最大化可分离数据的分类边际。这与标准梯度下降的$\mathcal{O}（1/\log（t））$和归一化梯度下降的$\mathcal{O}（1/t）$的速率形成对比。这种基于动量的方法是通过最大边际问题的凸对偶导出的，特别是通过将Nesterov加速应用于该对偶，从而在原始中产生简单直观的方法。这种对偶视图也可以用于导出随机变量，其通过对偶变量执行自适应非均匀采样。
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.