linear regularity – Optimization Online

Two Spectral Gaps: Decentralized Optimization over Intersections of Local Convex Sets

Published: 2026/08/27

Sarvagya Jha

Convex Optimization, Nonsmooth Optimization, Parallel Algorithms convex feasibility, decentralized optimization, friedrichs angle, Gossip algorithms, linear regularity, oracle complexity

We study decentralized minimization of an average of strongly convex, smooth local objectives over an intersection of agent-private closed convex sets, where each agent knows only its own objective and its own set and agents communicate over a gossip network. We show that the complexity is controlled by a single geometric scalar, which we call … Read more

Tight global linear convergence rate bounds for operator splitting methods

Published: 2016/03/10, Updated: 2019/01/18

Convex Optimization, Linear Programming averaged operator, composite convex optimization, error bound, friedrichs angle, global linear convergence, linear programming, linear regularity, operator splitting

In this paper we establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding … Read more