A unified approach to error bounds for structured convex optimization problems

By Zirui Zhou, Anthony Man-Cho So. 2015

200 citations recorded by the source corpus.

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. We believe that our approach will find further applications in the study of error bounds for structured convex optimization problems.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition (2016, methodology): “…holds for other problems where a linear convergence rate has been show like group L1-regularization [Tseng, 2010], sparse group L1-regularization [Zhang et al., 2013], nuclear-norm regularization [Hou et al., 2013], and other classes of functions [Zhou and So, 2015, Drusvyatskiy and Lewis, 2016].”
Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods (2016, methodology): “Recently, the authors of [33] proved that the error bound condition holds under very mild assumptions, thereby explaining asymptotic linear converge of the proximal gradient method often observed in practice.”