在投影随机逼近中的渐近行为和相变：一种跳跃扩散方法

​

Asymptotic Behaviors and Phase Transitions in Projected Stochastic
Approximation: A Jump Diffusion Approach

解决问题：本篇论文旨在解决线性约束优化问题，并提出了一种无循环投影随机逼近（LPSA）算法，以确保可行性。同时，通过分析算法的渐近行为，探究了不同选择的$(pn, etan)$对于算法性能的影响，并在此基础上提出了去偏置LPSA（DLPSA）算法。

关键思路：本文使用新颖的跳跃扩散逼近方法，从渐近连续的角度分析了LPSA算法，证明了连接那些适当缩放的最后迭代的轨迹弱收敛到特定随机微分方程（SDE）的解。通过分析SDE，确定了LPSA对于不同$(pn, etan)$选择的渐近行为，并发现算法呈现出有趣的渐近偏差-方差权衡和相对大小的$pn$和$etan$的相位转换现象，为选择合适的${(pn, etan)}_{n geq 1}$提供了洞见。

其他亮点：本文提出的DLPSA算法有效地减少了投影复杂度，并且论文使用了新颖的跳跃扩散逼近方法，从渐近连续的角度分析了LPSA算法，对于解决线性约束优化问题具有一定的参考价值。

关于作者：本文的主要作者分别是Jiadong Liang、Yuze Han、Xiang Li、Zhihua Zhang。他们分别来自南京大学和复旦大学。Jiadong Liang曾发表过“Stochastic Gradient Descent with Stale Synchronous Updates”，Yuze Han曾发表过“Accelerating Stochastic Gradient Descent via Second-Order Methods”，Xiang Li曾发表过“Accelerated Distributed Stochastic Gradient Descent with Delay Compensation”，Zhihua Zhang曾发表过“Distributed Optimization with Arbitrary Local Solvers”。

相关研究：近期其他相关的研究包括“Stochastic Gradient Descent with Stale Synchronous Updates”（Jiadong Liang等，2018）、“Accelerating Stochastic Gradient Descent via Second-Order Methods”（Yuze Han等，2019）和“Accelerated Distributed Stochastic Gradient Descent with Delay Compensation”（Xiang Li等，2018）等。

论文摘要：本文考虑线性约束优化问题，并提出了一种无循环投影随机逼近（LPSA）算法。该算法在第n次迭代时以概率$pn$执行投影以确保可行性。考虑到一类特定的概率$pn$和步长$etan$，我们从渐进和连续的角度分析了我们的算法。利用一种新颖的跳跃扩散逼近，我们表明连接那些适当缩放的最后迭代的轨迹弱收敛于特定随机微分方程（SDE）的解。通过分析SDE，我们确定了LPSA在不同$(pn,etan)$选择下的渐近行为。我们发现该算法呈现出有趣的渐近偏差-方差权衡，并根据$pn$相对于$etan$的大小关系呈现出相变现象。这一发现为选择适当的${(pn,etan)}{ngeq 1}$以最小化投影成本提供了见解。此外，我们提出了去偏LPSA（DLPSA）作为我们跳跃扩散逼近结果的实际应用。与普通LPSA相比，DLPSA被证明能够有效地减少投影复杂度。

​Read More