High-Dimensional Nonconvex Stochastic Optimization by Doubly Stochastic Successive Convex Approximation
High-Dimensional Nonconvex Stochastic Optimization by Doubly Stochastic Successive Convex Approximation
复制标题
DOI：
10.1109/tsp.2020.3033354
复制
发表时间：
2020
影响因子：
5.4
通讯作者：
Aryan Mokhtari;Alec Koppel
中科院分区：
文献类型：
--
作者：
Aryan Mokhtari;Alec Koppel
在本文中，我们考虑了对培训集的监督学习问题，在培训集中，训练示例的数量和特征向量的维度都很大。我们关注的情况下，损失函数定义了我们希望估计的参数的质量可能是非凸的，但也具有凸正则化。我们提出了一个双重随机连续的凸近似方案（DSSC），能够处理非凸式的预期风险最小化。该方法通过将决策变量分解为块并在每个步骤的块的随机子集上运行（通过将随机近似的优点与块坐标方法融合在一起），然后实现连续的凸近似值。与许多随机凸方法相反，在非凸面设置中无法确保其几乎确定的行为，DSSC几乎可以确保收敛到问题的固定解决方案。此外，我们表明所提出的DSSC算法以$ {\ Mathcal O}的速率达到平稳性。在LASSO回归问题的非凸变体上进行的数值实验表明，DSSC在这种情况下表现出色。然后，我们将此方法应用于从地面机器人收集的高维视觉数据的字典学习任务中，并观察到难以置信的非convex随机程序的可靠收敛行为。
In this paper, we consider supervised learning problems over training sets in which the number of training examples and the dimension of feature vectors are both large. We focus on the case where the loss function defining the quality of the parameter we wish to estimate may be non-convex, but also has a convex regularization. We propose a Doubly Stochastic Successive Convex approximation scheme (DSSC) able to handle non-convex regularized expected risk minimization. The method operates by decomposing the decision variable into blocks and operating on random subsets of blocks at each step (fusing the merits of stochastic approximation with block coordinate methods), and then implements successive convex approximation. In contrast to many stochastic convex methods whose almost sure behavior is not guaranteed in non-convex settings, DSSC attains almost sure convergence to a stationary solution of the problem. Moreover, we show that the proposed DSSC algorithm achieves stationarity at a rate of ${\mathcal O}((\log t)/{t^{1/4}})$. Numerical experiments on a non-convex variant of a lasso regression problem show that DSSC performs favorably in this setting. We then apply this method to the task of dictionary learning from high-dimensional visual data collected from a ground robot, and observe reliable convergence behavior for a difficult non-convex stochastic program.