Source-linked AI summary
A Unified Approach to Error Bounds for Structured Convex Optimization Problems
Zirui Zhou, Anthony Man-Cho So
TL;DR
The paper addresses the limited range of structured convex optimization problems known to satisfy error bounds, which help analyze first-order-method convergence rates. It develops a set-valued-analysis framework, recovers existing results uniformly, and establishes an error bound for nuclear-norm regularized loss minimization under strict complementarity-type regularity, while showing failure without that condition.
Problem
Known error-bound instances for structured convex optimization remain limited, despite their usefulness for analyzing convergence rates of first-order methods.
Method
The paper develops a set-valued-analysis framework for error bounds when the objective combines a smooth convex function with any closed proper convex function.
Results
Under a strict complementarity-type regularity condition, nuclear-norm regularized loss minimization problems possess the error-bound property, while existing results are recovered in a unified manner.
Takeaways & Limitations
The framework provides a unified and transparent way to establish error bounds across structured convex optimization settings.
Takeaways & Limitations
Without the strict complementarity-type regularity condition, the error bound can fail, including failure of a Hölderian error bound in the constructed instance.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper frames structured convex optimization through proximal-map error bounds, which can establish linear convergence for several first-order methods. It develops a unified set-valued-analysis framework and applies it to existing scenarios and nuclear-norm regularization.
- Problem setting: Many applications use a smooth loss and a closed proper convex regularizer, including constrained minimization and structured data-fitting problems.The formulation covers machine learning, signal processing, and statistics.
- Motivation: Error bounds relate distance to the optimal solution set X to a residual function on a test set.The proximal residual is especially useful because it vanishes exactly at optimal solutions.
- Motivation: When the proximal-map error bound holds, proximal gradient, extragradient, and coordinate descent methods can converge linearly.Identifying conditions that guarantee this bound is therefore a central research issue.
- Research gap: Existing error-bound scenarios include strongly convex losses, polyhedral regularizers, and grouped LASSO, but nuclear-norm regularization is not covered.Non-polyhedral epigraphs make broader error-bound analyses difficult, while prior approaches are often ad hoc.
- Framework: The proposed framework reduces error-bound verification to calmness of a solution-induced mapping, supported by bounded linear regularity and inverse-subdifferential calmness.It applies when f has the scenario (S2) structure and P is any closed proper convex function, covering scenarios (S1)–(S3).
- Applications: The framework recovers prior results transparently and establishes the nuclear-norm error bound under a strict complementarity-type regularity condition.Without that condition, a constructed example shows the bound can fail, addressing Tseng’s open question.
2 Preliminaries
The paper studies structured convex optimization under assumptions on the objective and optimal solution set, then connects optimality to set-valued analysis and error bounds.
- Basic setup: The objective uses a structured convex formulation with a linear operator, a convex function h, and a closed proper convex regularizer P.The assumptions require h to have a nonempty open effective domain, be continuously differentiable there, be strongly convex on compact convex subsets, and have Lipschitz gradient; P is convex, closed, and proper.
- Basic setup: The optimal solution set X is assumed non-empty and compact, which ensures finite optimal value and compact objective level sets.Under the structural assumptions, every level set L(ζ) for ζ ≥ v∗ is a compact subset of E.
- Characterization of X: Proposition 1 characterizes X using a common image vector ȳ and subgradient vector ġ, so all optimal solutions share A(x)=ȳ and ∇f(x)=ġ.This characterization reduces the analysis of distance to X to relationships between A(x), subgradients of P, and the pair (ȳ, ġ).
- Tools from Set-Valued Analysis: Set-valued mappings are used to formulate regularity conditions, including calmness and metric sub-regularity.The mapping Γ(y,g) collects points satisfying A(x)=y and −g ∈ ∂P(x), with X=Γ(ȳ,ġ).
- Tools from Set-Valued Analysis: Calmness of Γ yields a local distance bound from x to X in terms of deviations of (y,g) from (ȳ,ġ).This produces an error bound with residual based on the inverse mapping, and the inverse Γ^-1 is metrically sub-regular at optimal pairs.
- Tools from Set-Valued Analysis: The framework connects this set-valued error bound to the proximal-map residual used in convergence analysis under additional mild conditions.The proximal residual vanishes exactly on X and is targeted by many first-order methods.
3 Sufficient Conditions for the Validity of the Error Bound (EBP)
The paper reduces establishment of the error bound property to calmness of a solution map, using equivalent residual formulations and neighborhood arguments. This framework yields sufficient conditions while also exposing examples where error bounds fail.
- Neighborhood reduction: The EBP can be replaced by a neighborhood condition when compact level sets and continuity of the residual map are available.The proof uses compactness of level sets, continuity of ∇f, and the 1-Lipschitz property of proxP.
- Failure example: An example shows that without suitable boundedness, residuals can approach zero while points remain separated from the optimal solution set.For the constructed instance, both EBP and EBN fail, even for a Hölderian residual bound.
- Alternative residual: The framework links distance estimates to perturbations in A(x) and subdifferential values through the alternative error bound (EBR).This relation is then connected to calmness and metric sub-regularity of set-valued mappings.
- Equivalent error bounds: Theorem 1 establishes that the neighborhood-based error bound (EBN) holds if and only if the alternative-residual error bound (EBR) holds.This connects distance to the solution set with both the proximal residual and subdifferential-based residual descriptions.
- Solution-map framework: Calmness of the solution map Γ is sufficient for the error bound property (EBP) under Assumptions 1 and 2.The reduction proceeds through equivalence between neighborhood-based and alternative-residual error bounds.
4 Applications to Structured Convex Optimization
The framework is applied to four structured convex optimization classes, recovering three existing error-bound results and resolving the nuclear-norm case under regularity.
- Applications: Four classes of structured convex optimization problems are shown to possess the calmness property needed for EBP.The approach provides a unified and more transparent treatment of several known cases.
- Applications: The nuclear-norm regularized class satisfies EBP under a strict complementarity-type regularity condition.This resolves an open question raised by Tseng.
- Applications: The objective model uses f as a loss function and P as a regularizer unless stated otherwise.This terminology covers the structured formulations considered in the applications.
4.1 Strongly Convex Loss Function
When the linear operator is the identity, the loss is strongly convex with Lipschitz continuous gradient on compact convex subsets, and EBP holds whenever the solution set is non-empty.
- Strongly Convex Loss Function: Identity A makes the loss function strongly convex with Lipschitz continuous gradient on every compact convex set V contained in dom(f).Conversely, any loss with these properties can be represented using the identity operator.
- Strongly Convex Loss Function: Under this setting, X is either empty or a singleton, so non-emptiness is equivalent to the relevant existence assumption.The solution map is calm at the unique solution, which yields EBP through Corollary 1.
- Strongly Convex Loss Function: The error bound property holds under the identity-map setting whenever the optimal solution set X is non-empty.This is stated as Proposition 5 under Assumptions 1 and 2.
4.2 Polyhedral Convex Regularizer
Polyhedral convex regularizers, including LASSO and the ℓ∞ norm, satisfy EBP through polyhedrality, bounded linear regularity, and metric sub-regularity.
- Polyhedral Convex Regularizer: Polyhedral convex regularizers include the LASSO regularizer ∥x∥1 and the ℓ∞-norm regularizer ∥x∥∞.The framework treats these cases by decomposing the solution map into loss and regularizer components.
- Polyhedral Convex Regularizer: Polyhedrality of the relevant solution sets implies bounded linear regularity, satisfying condition (C1).The loss-side solution set is polyhedral because it is defined by a linear system.
- Polyhedral Convex Regularizer: The inverse subdifferential of a polyhedral regularizer is calm, which implies metric sub-regularity and condition (C2).Robinson’s result supplies calmness for the polyhedral multifunction.
- Polyhedral Convex Regularizer: The error bound property therefore holds for problems with a polyhedral convex regularizer.This conclusion is stated in Proposition 6 under Assumptions 1 and 2.
- Polyhedral Convex Regularizer: The framework gives an alternative proof of earlier results, while removing the boundedness requirement on X requires exploiting polyhedrality directly.The paper distinguishes the framework’s boundedness-based argument from prior polyhedral analyses.
4.3 Grouped LASSO Regularizer
The grouped LASSO regularizer is non-polyhedral but still satisfies the error bound under the paper’s general framework, recovering Tseng’s result with a more transparent proof.
- Regularizer structure: The grouped LASSO regularizer sums weighted Euclidean norms over a partition of variables, encouraging group-level sparsity.Each group J contributes ωJ∥xJ∥2, with nonnegative weights ωJ.
- Relation to prior work: The result recovers Tseng’s theorem while providing a more transparent alternative to his delicate and tedious proof.The authors emphasize that the framework clarifies why grouped LASSO behaves differently from many other non-polyhedral regularizers.
- Structural properties: Its solution-map components ΓP,J(g) are polyhedral convex sets despite the regularizer itself generally being non-polyhedral.This structural property supports bounded linear regularity of the relevant solution-map sets.
- Error-bound result: The framework verifies both required regularity conditions and therefore establishes the error bound for grouped LASSO problems.The two conditions are bounded linear regularity of solution-map sets and metric sub-regularity of the subdifferential.
- Regularity verification: The subdifferential of each positive-weight group norm is metrically sub-regular, and this property extends to the grouped regularizer.The proof treats each group separately and combines the resulting constants across groups.
4.4 Nuclear Norm Regularizer
For nuclear-norm regularized problems, the paper characterizes the relevant solution map and proves subdifferential metric sub-regularity. These results yield the error bound under strict complementarity, while a constructed example shows failure without that condition.
- Problem setting: The nuclear norm regularizer is the sum of singular values and is widely used in convex relaxations of low-rank matrix optimization.The section considers P(X)=∥X∥∗ on rectangular matrix spaces.
- Failure without regularity: A concrete example demonstrates that the error bound can fail when the strict complementarity-type regularity condition is absent.The example has a unique optimal solution, while the regularity condition fails.
- Solution-map characterization: The solution map ΓP(G) is characterized through the singular-value structure of −G, separating singular values equal to one, strictly between zero and one, and zero.Proposition 10 provides the resulting explicit characterization.
- Metric sub-regularity: The subdifferential of the nuclear norm is metrically sub-regular at every graph point.This is stated as Proposition 11 and is identified as crucial for analyzing the error bound.
- Validity of the error bound: Under a strict complementarity-type regularity condition at an optimal solution X⋆, the nuclear-norm regularized problem satisfies the error bound.The condition ensures the required relative-interior intersection and bounded linear regularity.
- Alternative analysis: Existing linear-matrix-inequality error-bound machinery is less suitable for rectangular nonsymmetric decision variables and can obscure the underlying insight.The authors note that even in the symmetric case, the corresponding argument is tedious.
5 Conclusion
The paper develops a set-valued-analysis framework that unifies error-bound results and applies it to nuclear-norm regularization. The nuclear-norm error bound holds under strict complementarity but may fail without it.
- Conclusion: The paper develops a new framework for establishing error bounds in structured convex optimization.The framework uses tools from set-valued analysis.
- Conclusion: The framework recovers several existing error-bound results in a unified and transparent manner.This demonstrates applicability beyond the paper’s nuclear-norm case.
- Conclusion: For nuclear-norm regularized loss minimization, the error bound holds under a strict complementarity-type regularity condition but can fail without it.This provides a rather complete answer to a question raised by Tseng.