# Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization

arXiv: https://arxiv.org/abs/2206.14981 · HTML: https://mlsanity.com/paper/2206.14981/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 30 Jun 2022.

## Builds on (most cited first, 17 of 17)

- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Efficiency of minimizing compositions of convex functions and smooth maps](https://mlsanity.com/paper/1605.00125/) (2016)
- [Stochastic Methods for Composite and Weakly Convex Optimization Problems](https://mlsanity.com/paper/1703.08570/) (2017)
- [Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization](https://mlsanity.com/paper/1409.3257/) (2014)
- [Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrieval](https://mlsanity.com/paper/1705.02356/) (2017)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [Asynchronous Stochastic Coordinate Descent: Parallelism and Convergence Properties](https://mlsanity.com/paper/1403.3862/) (2014)
- [Convergence Rates for Deterministic and Stochastic Subgradient Methods Without Lipschitz Continuity](https://mlsanity.com/paper/1712.04104/) (2017)
- ["Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent](https://mlsanity.com/paper/1710.04718/) (2017)
- [Stochastic Block Mirror Descent Methods for Nonsmooth and Stochastic Optimization](https://mlsanity.com/paper/1309.2249/) (2013)
- [Regret Bounds without Lipschitz Continuity: Online Learning with Relative-Lipschitz Losses](https://mlsanity.com/paper/2010.12033/) (2020)
- [Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization](https://mlsanity.com/paper/1509.01404/) (2015)
- ["Efficient" Subgradient Methods for General Convex Optimization](https://mlsanity.com/paper/1605.08712/) (2016)
- [Radial Subgradient Method](https://mlsanity.com/paper/1703.09280/) (2017)
- [Linear Convergence of Randomized Primal-Dual Coordinate Method for Large-scale Linear Constrained Convex Programming](https://mlsanity.com/paper/2008.12946/) (2020)

## Built on by (most cited first, 1 of 1)

- [A Unified Analysis on the Subgradient Upper Bounds for the Subgradient Methods Minimizing Composite Nonconvex, Nonsmooth and Non-Lipschitz Functions](https://mlsanity.com/paper/2308.16362/) (2023)

## Abstract (arXiv)

Coordinate-type subgradient methods for addressing nonsmooth optimization problems are relatively underexplored due to the set-valued nature of the subdifferential. In this work, our study focuses on nonsmooth composite optimization problems, encompassing a wide class of convex and weakly convex (nonconvex nonsmooth) problems. By utilizing the chain rule of the composite structure properly, we introduce the Randomized Coordinate Subgradient method (RCS) for tackling this problem class. To the best of our knowledge, this is the first coordinate subgradient method for solving general nonsmooth composite optimization problems. In theory, we consider the linearly bounded subgradients assumption for the objective function, which is more general than the traditional Lipschitz continuity assumption, to account for practical scenarios. We then conduct convergence analysis for RCS in both convex and weakly convex cases based on this generalized Lipschitz-type assumption. Specifically, we establish the widetildeO(1/√k) convergence rate in expectation and the tilde o(1/√k) almost sure asymptotic convergence rate in terms of the suboptimality gap when f is convex. For the case when f is weakly convex and its subdifferential satisfies the global metric subregularity property, we derive the O(varepsilon-4) iteration complexity in expectation. We also establish an asymptotic convergence result. To justify the global metric subregularity property utilized in the analysis, we establish this error bound condition for the concrete (real-valued) robust phase retrieval problem. We also provide a convergence lemma and the relationship between the global metric subregularity properties of a weakly convex function and its Moreau envelope. Finally, we conduct several experiments to demonstrate the possible superiority of RCS over the subgradient method.