On Distributed Nonconvex Optimization: Projected Subgradient Method for Weakly Convex Problems in Networks

• 成果类型: Article
• 署名作者: Chen, Shixiang; Garcia, Alfredo; Shahrampour, Shahin
• 署名单位: Texas A&M University System; Texas A&M University College Station
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2021.3056535
• 发表日期: 2022
• 页码: 662-675
• 关键词: convergence; optimization; Machine Learning; Convex functions; Stochastic processes; gradient methods; training; distributed optimization; multiagent systems; Nonconvex Optimization; projected stochastic subgradient method

摘要

The stochastic subgradient method is a widely used algorithm for solving large-scale optimization problems arising in machine learning. Often, these problems are neither smooth nor convex. Recently, Davis et al., 2018 characterized the convergence of the stochastic subgradient method for the weakly convex case, which encompasses many important applications (e.g., robust phase retrieval, blind deconvolution, biconvex compressive sensing, and dictionary learning). In practice, distributed implementations of the projected stochastic subgradient method (stoDPSM) are used to speed up risk minimization. In this article, we propose a distributed implementation of the stochastic subgradient method with a theoretical guarantee. Specifically, we show the global convergence of stoDPSM using the Moreau envelope stationarity measure. Furthermore, under a so-called sharpness condition, we show that deterministic DPSM (with a proper initialization) converges linearly to the sharp minima, using geometrically diminishing step size. We provide numerical experiments to support our theoretical analysis.