# A Unified Approach to Error Bounds for Structured Convex Optimization Problems

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

## Key facts

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

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

- [Nonsmooth Nonconvex-Nonconcave Minimax Optimization: Primal-Dual Balancing and Iteration Complexity Analysis](https://mlsanity.com/paper/2209.10825/) (2022)
- [A Convergent Single-Loop Algorithm for Relaxation of Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2303.06595/) (2023)
- [No Wrong Turns: The Simple Geometry Of Neural Networks Optimization Paths](https://mlsanity.com/paper/2306.11922/) (2023)
- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Orthogonal Group Synchronization with Incomplete Measurements: Error Bounds and Linear Convergence of the Generalized Power Method](https://mlsanity.com/paper/2112.06556/) (2021)
- [FAStEN: An Efficient Adaptive Method for Feature Selection and Estimation in High-Dimensional Functional Regressions](https://mlsanity.com/paper/2303.14801/) (2023)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [A Complete Loss Landscape Analysis of Regularized Deep Matrix Factorization](https://mlsanity.com/paper/2506.20344/) (2025)
- [WARPd: A linearly convergent first-order method for inverse problems with approximate sharpness conditions](https://mlsanity.com/paper/2110.12437/) (2021)
- [Distributed Sparse Regression via Penalization](https://mlsanity.com/paper/2111.06530/) (2021)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [Decentralized Weakly Convex Optimization Over the Stiefel Manifold](https://mlsanity.com/paper/2303.17779/) (2023)
- [Error Bound Analysis for the Regularized Loss of Deep Linear Neural Networks](https://mlsanity.com/paper/2502.11152/) (2025)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Stability of Primal-Dual Gradient Flow Dynamics for Multi-Block Convex Optimization Problems](https://mlsanity.com/paper/2408.15969/) (2024)
- [ℓ1-norm rank-one symmetric matrix factorization has no spurious second-order stationary points](https://mlsanity.com/paper/2410.05025/) (2024)
- [A Randomized Linearly Convergent Frank-Wolfe-type Method for Smooth Convex Minimization over the Spectrahedron](https://mlsanity.com/paper/2503.01441/) (2025)
- [Efficient Group Lasso Regularized Rank Regression with Simulation-Based Tuning](https://mlsanity.com/paper/2510.11546/) (2025)
- [Bilevel Models for Adversarial Learning and A Case Study](https://mlsanity.com/paper/2510.25121/) (2025)
- [Dynamic Proximal Gradient Algorithms for Schatten-p Quasi-Norm Regularized Problems](https://mlsanity.com/paper/2603.00333/) (2026)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)

## Abstract (arXiv)

Error bounds, which refer to inequalities that bound the distance of vectors in a test set to a given set by a residual function, have proven to be extremely useful in analyzing the convergence rates of a host of iterative methods for solving optimization problems. In this paper, we present a new framework for establishing error bounds for a class of structured convex optimization problems, in which the objective function is the sum of a smooth convex function and a general closed proper convex function. Such a class encapsulates not only fairly general constrained minimization problems but also various regularized loss minimization formulations in machine learning, signal processing, and statistics. Using our framework, we show that a number of existing error bound results can be recovered in a unified and transparent manner. To further demonstrate the power of our framework, we apply it to a class of nuclear-norm regularized loss minimization problems and establish a new error bound for this class under a strict complementarity-type regularity condition. We then complement this result by constructing an example to show that the said error bound could fail to hold without the regularity condition. Consequently, we obtain a rather complete answer to a question raised by Tseng. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.