# RSG: Beating Subgradient Method without Smoothness and Strong Convexity

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Dec 2015.

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

- [Large-scale Stochastic Optimization of NDCG Surrogates for Deep Learning with Provable Convergence](https://mlsanity.com/paper/2202.12183/) (2022)
- [Faster Rates of Private Stochastic Convex Optimization](https://mlsanity.com/paper/2108.00331/) (2021)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [Minimax risk classifiers with 0-1 loss](https://mlsanity.com/paper/2201.06487/) (2022)
- [Direct Prediction Set Minimization via Bilevel Conformal Classifier Training](https://mlsanity.com/paper/2506.06599/) (2025)
- [Federated Learning on Adaptively Weighted Nodes by Bilevel Optimization](https://mlsanity.com/paper/2207.10751/) (2022)
- [On the Initialization for Convex-Concave Min-max Problems](https://mlsanity.com/paper/2103.00284/) (2021)
- [Adaptive proximal gradient methods are universal without approximation](https://mlsanity.com/paper/2402.06271/) (2024)
- [Beyond O(√T) Regret: Decoupling Learning and Decision-making in Online Linear Programming](https://mlsanity.com/paper/2501.02761/) (2025)
- [Decoupling Learning and Decision-Making: Breaking the O(√T) Barrier in Online Resource Allocation with First-Order Methods](https://mlsanity.com/paper/2402.07108/) (2024)
- [Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for Linear Programming](https://mlsanity.com/paper/2111.05530/) (2021)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [Transfer Learning through Enhanced Sufficient Representation: Enriching Source Domain Knowledge with Target Data](https://mlsanity.com/paper/2502.20414/) (2025)
- [Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth](https://mlsanity.com/paper/2108.04482/) (2021)
- [Some Primal-Dual Theory for Subgradient Methods for Strongly Convex Optimization](https://mlsanity.com/paper/2305.17323/) (2023)

## Abstract (arXiv)

In this paper, we study the efficiency of a bf Restarted bf Subbf Gradient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an ε-optimal solution with a lower complexity than the SG method. In particular, we first show that RSG can reduce the dependence of SG's iteration complexity on the distance between the initial solution and the optimal set to that between the ε-level set and the optimal set multiplied by a logarithmic factor. Moreover, we show the advantages of RSG over SG in solving three different families of convex optimization problems. (a) For the problems whose epigraph is a polyhedron, RSG is shown to converge linearly. (b) For the problems with local quadratic growth property in the ε-sublevel set, RSG has an O(frac1εlog(frac1ε)) iteration complexity. (c) For the problems that admit a local Kurdyka-L ojasiewicz property with a power constant of β∈[0,1), RSG has an O(frac1ε2βlog(frac1ε)) iteration complexity. The novelty of our analysis lies at exploiting the lower bound of the first-order optimality residual at the ε-level set. It is this novelty that allows us to explore the local properties of functions (e.g., local quadratic growth property, local Kurdyka-L ojasiewicz property, more generally local error bound conditions) to develop the improved convergence of RSG.  We also develop a practical variant of RSG enjoying faster convergence than the SG method, which can be run without knowing the involved parameters in the local error bound condition. We demonstrate the effectiveness of the proposed algorithms on several machine learning tasks including regression, classification and matrix completion.