Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
Variance Reduction via Primal-Dual Accelerated Dual Averaging for Nonsmooth Convex Finite-Sums
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Chaobing Song;Stephen J. Wright;Jelena Diakonikolas
中科院分区：
文献类型：
--
作者：
Chaobing Song;Stephen J. Wright;Jelena Diakonikolas
我们研究了在机器学习应用中广泛出现的结构化非光滑凸有限和优化，包括支持向量机和最小绝对偏差。对于该问题的原始对偶公式，我们提出了一种新的算法，称为\emph{通过原始对偶加速对偶平均的方差减少（\vrpda）}。在非光滑和一般凸设置中，\vrpda就原始-对偶间隙而言具有总体复杂性$O(nd\log\min \{1/\epsilon, n\} + d/\epsilon )$，其中$n$表示样本数量，$d$表示原始变量的维度，$\epsilon$表示所需的精度。在非光滑和强凸设置下，\vrpda的总体复杂性在原对偶间隙和迭代与最优解之间的距离方面变为$O(nd\log\min\{1/\epsilon, n\} + d/\sqrt{\epsilon})$。对于\vrpda，这两个结果都以一种更简单和直接的方式显著提高了最先进的复杂性估计，对于非光滑和一般凸设置为$O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\epsilon)$，对于非光滑和强凸设置为$O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\sqrt{\epsilon})$。此外，这两种复杂性都优于缺乏我们所考虑的特殊（共同）结构的一般凸有限和的\emph{下界}。我们的理论结果得到了数值实验的支持，这证实了\vrpda与最先进的产品相比的竞争性能。
We study structured nonsmooth convex finite-sum optimization that appears widely in machine learning applications, including support vector machines and least absolute deviation. For the primal-dual formulation of this problem, we propose a novel algorithm called \emph{Variance Reduction via Primal-Dual Accelerated Dual Averaging (\vrpda)}. In the nonsmooth and general convex setting, \vrpda~has the overall complexity $O(nd\log\min \{1/\epsilon, n\} + d/\epsilon )$ in terms of the primal-dual gap, where $n$ denotes the number of samples, $d$ the dimension of the primal variables, and $\epsilon$ the desired accuracy. In the nonsmooth and strongly convex setting, the overall complexity of \vrpda~becomes $O(nd\log\min\{1/\epsilon, n\} + d/\sqrt{\epsilon})$ in terms of both the primal-dual gap and the distance between iterate and optimal solution. Both these results for \vrpda~improve significantly on state-of-the-art complexity estimates, which are $O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\epsilon)$ for the nonsmooth and general convex setting and $O(nd\log \min\{1/\epsilon, n\} + \sqrt{n}d/\sqrt{\epsilon})$ for the nonsmooth and strongly convex setting, in a much more simple and straightforward way. Moreover, both complexities are better than \emph{lower} bounds for general convex finite sums that lack the particular (common) structure that we consider. Our theoretical results are supported by numerical experiments, which confirm the competitive performance of \vrpda~compared to state-of-the-art.