提出新方法，让随机近端算法在更宽松条件下实现最优收敛速度。
Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms
- 放松方差有界假设，提升算法适用性
- 证明最后迭代点收敛率达~O(1/√T)，接近理论最优
- 适用于多任务和联邦学习中的图引导正则化问题
我们分析了两类经典算法：用于处理光滑项与非光滑正则项之和的凸优化问题的近端随机梯度法，以及针对正则项为多个非光滑函数之和时采用随机增量近端方法。重点是放宽通常严格但常见的有界方差假设，以获得最后迭代点的收敛率。在分量凸性和光滑性条件下，证明了两种算法的最后迭代点均达到$ ilde{O}(1/ oot{T})$的收敛率，该速率在对数因子范围内为最优。结果可直接应用于多任务和联邦学习中出现的图引导正则化问题，其中正则项可分解为协作图上各边的和。
原文摘要 · Abstract (English)
We analyze two classical algorithms for solving additively composite convex optimization problems where the objective is the sum of a smooth term and a nonsmooth regularizer: proximal stochastic gradient method for a single regularizer; and the randomized incremental proximal method, which uses the proximal operator of a randomly selected function when the regularizer is given as the sum of many nonsmooth functions. We focus on relaxing the bounded variance assumption that is common, yet stringent, for getting last iterate convergence rates. We prove the $\widetilde{O}(1/\sqrt{T})$ rate of convergence for the last iterate of both algorithms under componentwise convexity and smoothness, which is optimal up to log terms. Our results apply directly to graph-guided regularizers that arise in multi-task and federated learning, where the regularizer decomposes as a sum over edges of a collaboration graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。