SDCA without Duality
Shai Shalev-Shwartz School of Computer Science and Engineering, The Hebrew University, Jerusalem, Israel
Abstract
Stochastic Dual Coordinate Ascent is a popular method for solving regularized loss minimization for the case of convex losses. In this paper we show how a variant of SDCA can be applied for non-convex losses. We prove linear convergence rate even if individual loss functions are non-convex as long as the expected loss is convex.
中文速览
随机对偶坐标上升法（Stochastic Dual Coordinate Ascent，SDCA）在凸损失函数下已被广泛用于求解正则化经验风险最小化问题，但当单个损失函数非凸时，其对偶问题失去意义，原有理论无法直接适用。本文提出一种"无对偶"的SDCA变体，仅利用各损失函数的梯度信息进行更新，将SDCA重新解释为一种方差递减的随机梯度下降，从而彻底绕开对偶框架。在此基础上，作者证明：即便每个单独的损失函数非凸，只要其平均值是凸函数，算法仍能以线性速率收敛，同时对经典的全凸情形也给出了更简洁的直接证明。这一结果为将SDCA推广到深度学习等非凸优化场景提供了理论支撑，也为理解方差缩减类算法在非凸设置下的行为奠定了基础。
原文 arXiv:1502.06177;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1502.06177v1