2020/10/18 by Loris Cannelli, Cannelli, Loris, Francisco Facchinei +5
Computer Science · Engineering · #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2010.09057
openalex publication_date 2020/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider convex and nonconvex constrained optimization with a partially\nseparable objective function: agents minimize the sum of local objective\nfunctions, each of which is known only by the associated agent and depends on\nthe variables of that agent and those of a few others. This partitioned setting\narises in several applications of practical interest. We propose what is, to\nthe best of our knowledge, the first distributed, asynchronous algorithm with\nrate guarantees for this class of problems. When the objective function is\nnonconvex, the algorithm provably converges to a stationary solution at a\nsublinear rate whereas linear rate is achieved when the objective satisfies\nunder the renowned Luo-Tseng error bound condition (which is less stringent\nthan strong convexity). Numerical results on matrix completion and LASSO\nproblems show the effectiveness of our method.\n