A Unified Approach to Error Bounds for Structured Convex Optimization Problems

Introduction

It has long been recognized that many convex optimization problems can be put into the form

where $\mathcal{E}$ is a finite-dimensional Euclidean space, $f:\mathcal{E}\rightarrow(-\infty,+\infty]$ is a proper convex function that is continuously differentiable on $\mbox{int}(\mbox{dom}(f))$, and $P:\mathcal{E}\rightarrow(-\infty,+\infty]$ is a closed proper convex function. On one hand, the constrained minimization problem

where $C\subseteq\mathcal{E}$ is a closed convex set, is an instance of Problem (1) with $P$ being the indicator function of $C$; i.e.,

On the other hand, various data fitting problems in machine learning, signal processing, and statistics can be formulated as Problem (1), where $f$ is a loss function measuring the deviation of a solution from the observations and $P$ is a regularizer intended to induce certain structure in the solution. With the advent of the big data era, instances of Problem (1) that arise in contemporary applications often involve a large number of variables. This has sparked a renewed interest in first-order methods for solving Problem (1) in recent years; see, e.g., and the references therein. From a theoretical point of view, a fundamental issue concerning these methods is to determine their convergence rates. It is well known that various first-order methods for solving Problem (1) will converge at the sublinear rate of $O(1/k^{2})$, where $k\geq 1$ is the number of iterations; see, e.g., . Moreover, the $O(1/k^{2})$ convergence rate is optimal when the functions $f$ and $P$ are given by first-order oracles . However, in many applications, both $f$ and $P$ are given explicitly and have very specific structure. It has been observed numerically that first-order methods for solving structured instances of Problem (1) converge at a much faster rate than that suggested by the theory; see, e.g., . Thus, it is natural to ask whether the structure of the problem can be exploited in the convergence analysis to yield sharper convergence rate results.

where $d(x,\mathcal{X}):=\inf_{z\in\mathcal{X}}\|z-x\|_{2}$ denotes the Euclidean distance from the vector $x\in\mathcal{E}$ to the set $\mathcal{X}\subseteq\mathcal{E}$; cf. . Conceptually, the error bound (2) provides a handle on the structure of the objective function $F$ of Problem (1) in the neighborhood $T$ of the optimal solution set $\mathcal{X}$ via the residual function $r$. For the purpose of analyzing the convergence rates of first-order methods, one particularly useful choice of the residual function is $r_{\rm prox}(x):=\|R(x)\|_{2}$, where $R:\mathcal{E}\rightarrow\mathcal{E}$ is the residual map defined by

and $\mbox{prox}_{P}:\mathcal{E}\rightarrow\mathcal{E}$ is the proximal map associated with $P$; i.e.,

Indeed, by comparing the optimality conditions of (1) and (4), it is immediate that $x\in\mathcal{X}$ if and only if $r_{\rm prox}(x)=0$. Moreover, it is known that many first-order methods for solving Problem (1) have update rules that aim at reducing the value of the residual function; see, e.g., . This leads to the following instantiation of (2):

Error Bound with Proximal Map-Based Residual Function. For any $\zeta\geq v^{*}:=\min_{x\in\mathcal{E}}F(x)$, there exist constants $\kappa>0$ and $\epsilon>0$ such that

The usefulness of the error bound (EBP) comes from the fact that whenever it holds, a host of first-order methods for solving Problem (1), such as the proximal gradient method, the extragradient method, and the coordinate (gradient) descent method, can be shown to converge linearly; see and the references therein. Thus, an important research issue is to identify conditions on the functions $f$ and $P$ under which the error bound (EBP) holds. Nevertheless, despite the efforts of many researchers over a long period of time, the repertoire of instances of Problem (1) that are known to possess the error bound (EBP) is still rather limited. Below are some representative scenarios in which (EBP) has been shown to hold:

In many applications, such as regression problems, the function $f$ of interest is not strongly convex but has the structure described in scenarios (S2) and (S3). However, a number of widely used structure-inducing regularizers $P$—most notably the nuclear norm regularizer—are not covered by these scenarios. One of the major difficulties in establishing the error bound (EBP) for regularizers other than those described in scenarios (S2) and (S3) is that they typically have non-polyhedral epigraphs. Moreover, existing approaches to establishing the error bound (EBP) are quite ad hoc in nature and cannot be easily generalized. Thus, in order to identify more scenarios in which the error bound (EBP) holds, some new ideas would seem to be necessary.

In this paper, we present a new analysis framework for studying the error bound property (EBP) associated with Problem (1). The framework applies to the setting where $f$ has the form described in scenario (S2) and $P$ is any closed proper convex function. In particular, it applies to all the scenarios (S1)–(S3). Our first contribution is to elucidate the relationship between the error bound property (EBP) and various notions in set-valued analysis. This allows us to utilize powerful tools from set-valued analysis to elicit the key properties of Problem (1) that can guarantee the validity of (EBP). Specifically, we show that the problem of establishing the error bound (EBP) can be reduced to that of checking the calmness of a certain set-valued mapping $\Gamma$ induced by the optimal solution set $\mathcal{X}$ of Problem (1); see Corollary 1. Furthermore, using the fact that $\mathcal{X}$ can be expressed as the intersection of a polyhedron and the inverse of the subdifferential of $P$ at a certain point $-\bar{g}\in\mathcal{E}$ (see Proposition 1), we show that the calmness of $\Gamma$ is in turn implied by (i) the bounded linear regularity of the two intersecting sets and (ii) the calmness of $(\partial P)^{-1}$ at $-\bar{g}$; see Theorem 2. These results provide a concrete starting point for verifying the error bound property (EBP) and make it possible to simplify the analysis substantially. We remark that when $P$ has a polyhedral epigraph, the early works of Luo and Tseng have already pointed out a connection between (EBP) and the calmness of certain polyhedral multi-function. However, such an idea has not been further explored in the literature to tackle more general forms of $P$.

To demonstrate the power of our proposed framework, we apply it to scenarios (S1)–(S3) and show that the error bound results in can be recovered in a unified manner; see Sections 4.1–4.3. It is worth noting that scenario (S3) involves the non-polyhedral grouped LASSO regularizer, and the existing proof of the validity of the error bound (EBP) in this scenario employs a highly intricate argument . By contrast, our approach leads to a much simpler and more transparent proof. Motivated by the above success, we proceed to apply our framework to the following scenario, which again involves a non-polyhedral regularizer and arises in the context of low-rank matrix optimization:

The validity of the error bound (EBP) in this scenario was left as an open question in and to date is still unresolved.It was claimed in that the error bound (EBP) holds in scenario (S4). However, there is a critical flaw in the proof. Specifically, contrary to what was claimed in [13, Supplementary Material, Section C], the matrices $U^{k}$ and $V^{k}$ that satisfy displayed equations (37) and (38) need not satisfy displayed equation (35). The erroneous claim was due to an incorrect application of [35, Lemma 4.3]. We thank Professor Defeng Sun and Ms. Ying Cui for bringing this issue to our attention. As our second contribution in this work, we show that under a strict complementarity-type regularity condition on the optimal solution set $\mathcal{X}$ of Problem (1), the error bound (EBP) holds in scenario (S4); see Proposition 12. This is achieved by verifying conditions (i) and (ii) mentioned in the preceding paragraph. Specifically, we first show that condition (i) is satisfied under the said regularity condition. Then, we prove that $(\partial\|\cdot\|_{*})^{-1}$ is calm everywhere, which implies that condition (ii) is always satisfied; see Proposition 11. We note that to the best of our knowledge, this last result is new and could be of independent interest. To further understand the role of the regularity condition, we demonstrate via a concrete example that without such condition, the error bound (EBP) could fail to hold; see Section 4.4.4. Consequently, we obtain a rather complete answer to the question raised by Tseng .

Preliminaries

Consider the optimization problem (1). Recall that its optimal value and optimal solution set are denoted by $v^{*}$ and $\mathcal{X}$, respectively. We shall make the following assumptions in our study:

(Structural Properties of the Objective Function)

The function $f:\mathcal{E}\rightarrow(-\infty,+\infty]$ takes the form

where $\mathcal{A}:\mathcal{E}\rightarrow\mathcal{T}$ is a linear operator, $c\in\mathcal{E}$ is a given vector, and $h:\mathcal{T}\rightarrow(-\infty,+\infty]$ is a convex function with the following properties:

The effective domain ${\rm dom}(h)$ of $h$ is non-empty and open, and $h$ is continuously differentiable on ${\rm dom}(h)$.

For any compact convex set $V\subseteq{\rm dom}(h)$, the function $h$ is strongly convex and its gradient $\nabla h$ is Lipschitz continuous on $V$.

The function $P:\mathcal{E}\rightarrow(-\infty,+\infty]$ is convex, closed, and proper.

(Properties of the Optimal Solution Set) The optimal solution set $\mathcal{X}$ is non-empty and compact. In particular, $v^{*}>-\infty$.

The above assumptions yield several useful consequences. First, Assumption 1(a-i) implies that $\mbox{dom}(f)=\mathcal{A}^{-1}(\mbox{dom}(h))=\left\{x\in\mathcal{E}\mid\mathcal{A}(x)\in\mbox{dom}(h)\right\}$ is also non-empty and open, and $f$ is continuously differentiable on $\mbox{dom}(f)$. Second, under Assumption 1(a-ii), if the Lipschitz constant of $\nabla h$ on the compact convex set $V\subseteq\mbox{dom}(h)$ is $L_{h}(V)$, then the Lipschitz constant of $\nabla f$ on $\mathcal{A}^{-1}(V)$ is at most $L_{h}(V)\|\mathcal{A}\|^{2}$, where $\|\mathcal{A}\|$ is the spectral norm of $\mathcal{A}$. Third, Assumption 1 implies that $F$ is a closed proper convex function. Together with Assumption 2 and [30, Corollary 8.7.1], we conclude that for any $\zeta\geq v^{*}$, the level set $L(\zeta):=\left\{x\in\mathcal{E}\mid F(x)\leq\zeta\right\}$ is a compact subset of $\mathcal{E}$.

2 A Characterization of the Optimal Solution Set 𝒳𝒳\mathcal{X}

Since Problem (1) is an unconstrained convex optimization problem, its first-order optimality condition is both necessary and sufficient for optimality. Hence, we have

The following proposition shows that under Assumptions 1 and 2, the optimal solution set $\mathcal{X}$ admits an alternative, more explicit characterization. Such a characterization will be central to our analysis of the error bound property associated with Problem (1).

Consider the optimization problem (1). Under Assumptions 1 and 2, there exists a $\bar{y}\in\mathcal{T}$ such that

where $\bar{g}=\mathcal{A}^{*}\nabla h(\bar{y})+c\in\mathcal{E}$. In particular, we have

Proof The proof of (8) is rather standard; cf. . For completeness’ sake, we include the proof here. For arbitrary $x_{1},x_{2}\in\mathcal{X}$, let $y_{1}=\mathcal{A}(x_{1})$ and $y_{2}=\mathcal{A}(x_{2})$. Note that the line segment between $y_{1}$ and $y_{2}$ is a compact convex subset of $\mbox{dom}(h)$. By Assumption 1(a-ii), the function $h$ is strongly convex on this set. Thus, there exists a $\sigma>0$ such that

Upon adding the above two inequalities and using $x_{1},x_{2}\in\mathcal{X}$, we have

This implies that $y_{1}=y_{2}$, for otherwise the above inequality contradicts the fact that $v^{*}$ is the optimal value of Problem (1). Consequently, the map $x\mapsto\mathcal{A}(x)$ is invariant over $\mathcal{X}$; i.e., there exists a $\bar{y}\in\mathcal{T}$ such that $\mathcal{A}(x)=\bar{y}$ for all $x\in\mathcal{X}$. Now, using (5) and Assumption 1(a-i), we compute $\nabla f(x)=\mathcal{A}^{*}\nabla h(\mathcal{A}(x))+c$. Since $\mathcal{A}(x)=\bar{y}$ for all $x\in\mathcal{X}$, we have $\nabla f(x)=\mathcal{A}^{*}\nabla h(\bar{y})+c=\bar{g}$ for all $x\in\mathcal{X}$. This completes the proof of (8).

To establish (9), we first observe that by (7) and (8), every $x\in\mathcal{X}$ belongs to the set on the right-hand side of (9). Now, for any $x\in\mathcal{E}$ satisfying $\mathcal{A}(x)=\bar{y}$ and $-\bar{g}\in\partial P(x)$, we can use the relationships $\bar{g}=\mathcal{A}^{*}\nabla h(\bar{y})+c$ and $\nabla f(x)=\mathcal{A}^{*}\nabla h(\mathcal{A}(x))+c$ to get $\mathbf{0}\in\nabla f(x)+\partial P(x)$. This, together with (7), implies that $x\in\mathcal{X}$, as desired. \sqcup\hbox to0.0pt{\hss\sqcap}

3 Tools from Set-Valued Analysis

Proposition 1 reveals that the optimal solution set $\mathcal{X}$ of Problem (1) is completely characterized by the vectors $\bar{y}\in\mathcal{T}$ and $\bar{g}\in\mathcal{E}$. Thus, in order to estimate $d(x,\mathcal{X})$ for some $x\in\mathcal{E}\setminus\mathcal{X}$, a natural idea is to take $y=\mathcal{A}(x)$ and an arbitrary $-g\in\partial P(x)$ and establish a relationship between $d(x,\mathcal{X})$ and $\|(y,g)-(\bar{y},\bar{g})\|_{2}$. Intuitively, if $\mathcal{X}$ is “nice” (e.g., satisfies certain regularity condition), then one should be able to control the (local) growth of $d(x,\mathcal{X})$ by that of a “nice” function of $\|(y,g)-(\bar{y},\bar{g})\|_{2}$. Such an idea can be formalized using tools from set-valued analysis, which we now introduce.

Let $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ be finite-dimensional Euclidean spaces. We say that a mapping $\Gamma$ is a multi-function (or set-valued mapping) from $\mathcal{E}_{1}$ to $\mathcal{E}_{2}$ (denoted by $\Gamma:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$) if it assigns a subset $\Gamma(u)$ of $\mathcal{E}_{2}$ to each vector $u\in\mathcal{E}_{1}$. The graph and domain of $\Gamma$ are defined by

respectively. The inverse mapping of $\Gamma$, denoted by $\Gamma^{-1}$, is the multi-function from $\mathcal{E}_{2}$ to $\mathcal{E}_{1}$ defined by

Before we proceed further, let us briefly illustrate some of the concepts above.

Let $P:\mathcal{E}\rightarrow(-\infty,+\infty]$ be a closed proper convex function. Its subdifferential $\partial P$ is a multi-function from $\mathcal{E}$ to $\mathcal{E}$. Moreover, by [30, Corollary 23.5.1], we have $(\partial P)^{-1}=\partial P^{*}$, where $P^{*}$ is the conjugate of $P$. \sqcup\hbox to0.0pt{\hss\sqcap}

Next, we introduce two regularity notions regarding set-valued mappings.

A multi-function $\Gamma:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$ is said to be calm at $\bar{u}\in\mathcal{E}_{1}$ for $\bar{v}\in\mathcal{E}_{2}$ if $(\bar{u},\bar{v})\in{\rm gph}(\Gamma)$ and there exist constants $\kappa,\epsilon>0$ such that

A multi-function $\Lambda:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$ is said to be metrically sub-regular at $\bar{u}\in\mathcal{E}_{1}$ for $\bar{v}\in\mathcal{E}_{2}$ if $(\bar{u},\bar{v})\in{\rm gph}(\Lambda)$ and there exist constants $\kappa,\epsilon>0$ such that

The notions of calmness and metric sub-regularity have played a central role in the study of error bounds; see, e.g., and the references therein. To see what these notions would yield in the context of Problem (1), consider the multi-function $\Gamma:\mathcal{T}\times\mathcal{E}\rightrightarrows\mathcal{E}$ given by

Suppose that $\Gamma$ is calm at $(\bar{y},\bar{g})\in\mathcal{T}\times\mathcal{E}$ for $\bar{x}\in\mathcal{E}$, where $\bar{y}$ and $\bar{g}$ are given in Proposition 1. Note that $\mathcal{X}=\Gamma(\bar{y},\bar{g})$ and $\bar{x}\in\mathcal{X}$. Hence, by (10), there exist constants $\kappa,\epsilon>0$ such that

The error bound (14) shows that under a calmness assumption on the multi-function $\Gamma$ given in (12), the local growth of $d(x,\mathcal{X})$ is on the order of $\|(y,g)-(\bar{y},\bar{g})\|_{2}$, where $y=\mathcal{A}(x)$ and $-g\in\partial P(x)$ is arbitrary. This realizes the idea mentioned at the beginning of this sub-section. However, we are ultimately interested in establishing the error bound (EBP), which is concerned with the test set $\left\{x\in\mathcal{E}\mid F(x)\leq\zeta,\,\|R(x)\|_{2}\leq\epsilon\right\}$ (where $\zeta\geq v^{*}$ is arbitrary and $\epsilon=\epsilon(\zeta)$ depends on $\zeta$) and residual function $x\mapsto\|R(x)\|_{2}$. At first sight, it is not clear whether the error bounds (EBP) and (14) are compatible. Indeed, the former involves only easily computable quantities (i.e., $F(x)$ and $\|R(x)\|_{2}$), while the latter involves quantities that are generally not known a priori (i.e., $\bar{x}\in\mathcal{E}$, $\bar{y}\in\mathcal{T}$, and $\bar{g}\in\mathcal{E}$). Nevertheless, as we shall demonstrate in Section 3, the latter can be used to establish the former under some mild conditions.

Before we leave this section, let us record two useful results regarding the notions of calmness and metric sub-regularity. The first is a well-known equivalence between the calmness of a multi-function and the metric sub-regularity of its inverse. One direction of the equivalence has already manifested in our discussion above.

(see, e.g., [8, Theorem 3H.3]) For a multi-function $\Gamma:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$, let $(\bar{u},\bar{v})\in{\rm gph}(\Gamma)$. Then, $\Gamma$ is calm at $\bar{u}$ for $\bar{v}$ if and only if its inverse $\Gamma^{-1}$ is metrically sub-regular at $\bar{v}$ for $\bar{u}$.

The second result concerns a multi-function $\Gamma:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$ that is calm at $\bar{u}\in\mathcal{E}_{1}$ for a set of points $\bar{V}\subseteq\Gamma(\bar{u})$. It shows that if $\bar{V}$ is compact, then the neighborhoods around each $\bar{v}\in\bar{V}$ in the definition of calmness can be made uniform.

For a multi-function $\Gamma:\mathcal{E}_{1}\rightrightarrows\mathcal{E}_{2}$, let $\bar{u}\in{\rm dom}(\Gamma)$ and suppose that $\bar{V}\subseteq\Gamma(\bar{u})$ is compact. Then, the following statements are equivalent:

$\Gamma$ is calm at $\bar{u}$ for any $\bar{v}\in\bar{V}$.

There exist constants $\kappa,\epsilon>0$ such that

Proof It is clear that (b) implies (a). Hence, suppose that (a) holds. By (10), given any $\bar{v}\in\bar{V}$, there exist constants $\kappa(\bar{v}),\epsilon(\bar{v})>0$ such that

Since $\bar{V}$ is compact and $\{v_{k}\}_{k\geq 1}\subseteq\bar{V}$, by passing to a subsequence if necessary, we may assume that $v_{k}\rightarrow v$ for some $v\in\bar{V}$. Then, we have

which shows that $w_{k}\rightarrow v$. On the other hand, since $v\in\bar{V}$, there exists an index $i\in\{1,\ldots,N\}$ such that $\|v-\bar{v}_{i}\|_{2}=\delta<\epsilon(\bar{v}_{i})$. This implies that

for $k=1,2,\ldots,$ which contradicts the fact that $w_{k}\rightarrow v$. Thus, the claim is established.

Now, upon setting $\kappa=\max_{i=1,\ldots,N}\kappa(\bar{v}_{i})$, we obtain

Sufficient Conditions for the Validity of the Error Bound (EBP)

Following our discussion in Section 2.3, we now show that under Assumptions 1 and 2, the error bound (EBP) is implied by certain calmness property of the multi-function $\Gamma$ given in (12). This is achieved by exploring the relationships between error bounds defined using different test sets and residual functions. For the sake of convenience, we shall refer to the multi-function $\Gamma$ given in (12) as the solution map associated with Problem (1) in the sequel.

To begin, recall that the error bound (EBP) involves the test set $\left\{x\in\mathcal{E}\mid F(x)\leq\zeta,\,\|R(x)\|_{2}\leq\epsilon\right\}$, where $\zeta\geq v^{*}$ is arbitrary and $\epsilon>0$ depends on $\zeta$. The following proposition shows that under Assumptions 1 and 2, we can replace the test set by a neighborhood of $\mathcal{X}$. This would facilitate our analysis of the relationship between the error bound (EBP) and the calmness of the solution map $\Gamma$, as the latter is also defined in terms of a neighborhood of $\mathcal{X}$.

Consider the optimization problem (1). Under Assumptions 1 and 2, the error bound (EBP) holds if there exist constants $\kappa,\rho>0$ such that

Proof To establish the error bound (EBP), it suffices to show that for any $\zeta\geq v^{*}$, there exists an $\epsilon>0$ such that

Suppose that this does not hold. Then, there exist a scalar $\zeta\geq v^{*}$ and a sequence $\{x_{k}\}_{k\geq 1}$ in $\mathcal{E}$ such that $F(x_{k})\leq\zeta$ for $k=1,2,\ldots$ and $\|R(x_{k})\|_{2}\rightarrow 0$, but $d(x_{k},\mathcal{X})>\rho$ for $k=1,2,\ldots$. Since $\left\{x\in\mathcal{E}\mid F(x)\leq\zeta\right\}$ is compact by Assumption 2, by passing to a subsequence if necessary, we may assume that $x_{k}\rightarrow\bar{x}$ for some $\bar{x}\in\mathcal{E}$. Using the fact that $\mbox{prox}_{P}$ is 1-Lipschitz continuous on $\mathcal{E}$ (see, e.g., [6, Lemma 2.4]) and $\nabla f$ is continuous on $\mbox{dom}(f)$ (Assumption 1(a-i)), we see that $R$ is continuous on $\mbox{dom}(f)$. This, together with the fact that $\|R(x_{k})\|_{2}\rightarrow 0$, implies that $\|R(\bar{x})\|_{2}=0$; i.e., $\bar{x}\in\mathcal{X}$. However, this contradicts the fact that $d(x_{k},\mathcal{X})>\rho$ for $k=1,2,\ldots$, and the proof is completed. \sqcup\hbox to0.0pt{\hss\sqcap}

Before we proceed, two remarks are in order. First, the reverse implication in Proposition 3 is also true if, in addition to Assumptions 1 and 2, the optimal solution set $\mathcal{X}$ of Problem (1) is contained in the relative interior of $\mbox{dom}(F)$. However, since we will mostly focus on sufficient conditions for the error bound (EBP) to hold, we will not indulge in proving this here. Second, for those instances of Problem (1) that do not satisfy Assumption 2, one or both of the error bounds (EBP) and (EBN) could fail to hold. The following example demonstrates such possibility.

which shows that the level sets of $F$ are closed but not bounded. It follows that $F$ is a closed proper convex function with $\mbox{dom}(F)=C$ and

Next, we determine the residual map $R$ on $\mbox{dom}(F)$. Recall that

Since $P$ is the indicator function of $C$, it is easy to see that $\mbox{prox}_{P}$ is the projection operator onto $C$. Note that for each $y\geq 0$, the function

is decreasing in $x\in(-\infty,0]$. Moreover, it can be verified that $y-(1+1/y)\exp(-1/y)\geq 0$ for all $y\geq 0$. It follows that

In particular, we have $r(x,y)=\|R(x,y)\|_{2}=\|\nabla f(x,y)\|_{2}$ for all $(x,y)\in\mbox{dom}(F)$.

Now, observe that for any $\zeta>v^{*}=0$, if $(\bar{x},\bar{y})\notin\mathcal{X}$ satisfies $F(\bar{x},\bar{y})\leq\zeta$, then $F(x,\bar{y})\leq\zeta$ for any $x\leq\bar{x}$. However, we have $d((x,\bar{y}),\mathcal{X})=\|\bar{y}\|_{2}\neq 0$ for any $x\leq 0$ and $\lim_{x\rightarrow-\infty}\|R(x,\bar{y})\|_{2}=0$. It follows that there do not exist constants $\kappa,\epsilon>0$ such that (EBP) holds. Similarly, for any $\rho>0$, we have

Since $\lim_{x\rightarrow-\infty}\|R(x,y)\|_{2}=0$ for any $y\geq 0$, there does not exist a constant $\kappa>0$ such that (EBN) holds. In fact, the same arguments show that the instance in question does not possess a Hölderian error bound; i.e., the error bounds (EBP) and (EBN) fail to hold even if one replaces the inequality $d(x,\mathcal{X})\leq\kappa\|R(x)\|_{2}$ by $d(x,\mathcal{X})\leq\kappa\|R(x)\|_{2}^{\alpha}$ for any $\alpha\in(0,1)$. \sqcup\hbox to0.0pt{\hss\sqcap}

2 Error Bound with Alternative Residual Function

where $\kappa,\rho>0$ are constants and $\bar{y}\in\mathcal{T}$, $\bar{g}\in\mathcal{E}$ are given in Proposition 1. Our interest in the error bound (EBR) stems from the following result, which reveals that it is closely related to certain calmness property of the solution map $\Gamma$:

Suppose that Problem (1) satisfies Assumptions 1 and 2. Let $\bar{y}\in\mathcal{T}$ and $\bar{g}\in\mathcal{E}$ be as in Proposition 1. Then, the error bound (EBR) holds if and only if the solution map $\Gamma:\mathcal{T}\times\mathcal{E}\rightrightarrows\mathcal{E}$ is calm at $(\bar{y},\bar{g})$ for any $\bar{x}\in\Gamma(\bar{y},\bar{g})$.

Conversely, suppose that $\Gamma$ is calm at $(\bar{y},\bar{g})$ for any $\bar{x}\in\Gamma(\bar{y},\bar{g})$. Since $\mathcal{X}=\Gamma(\bar{y},\bar{g})$ is compact by Assumption 2, Proposition 2 implies the existence of $\kappa,\rho>0$ such that

Now, let $x\in\mathcal{E}$ be such that $d(x,\mathcal{X})\leq\rho$ and $\partial P(x)\not=\emptyset$. Using (16) and the inequality $\sqrt{a^{2}+b^{2}}\leq a+b$, which is valid for all $a,b\geq 0$, we have

It follows that the error bound (EBR) holds. \sqcup\hbox to0.0pt{\hss\sqcap}

Since our goal is to link the error bound (EBP) and the calmness of the solution map $\Gamma$, in view of Propositions 3 and 4, it remains to understand the relationship between the error bounds (EBN) and (EBR). Towards that end, we prove the theorem, which constitutes the first main result of this paper:

Consider the optimization problem (1). Under Assumptions 1 and 2, the error bound (EBN) holds if and only if the error bound (EBR) holds.

The proof of Theorem 1 relies on the following technical result:

Suppose that Problem (1) satisfies Assumptions 1 and 2. Then, there exists a constant $\rho_{0}>0$ such that $N_{\rho}:=\left\{x\in\mathcal{E}\mid d(x,\mathcal{X})\leq\rho\right\}\subseteq{\rm dom}(f)$ for all $\rho\in(0,\rho_{0}]$. Moreover, there exist constants $L_{A},L_{R}>0$, which depend on $\rho_{0}$, such that for all $x\in N_{\rho_{0}}$, we have

where $\bar{y}\in\mathcal{T}$ and $\bar{g}\in\mathcal{E}$ are given in Proposition 1.

Proof Recall from the discussion in Section 2.1 that $\mbox{dom}(f)$ is open. On the other hand, the optimal solution set $\mathcal{X}$ is compact by Assumption 2. Since $\mathcal{X}\subseteq\mbox{dom}(f)$, a standard argument shows that $N_{\rho_{0}}\subseteq\mbox{dom}(f)$ for some $\rho_{0}>0$. Moreover, we have $N_{\rho}\subseteq N_{\rho^{\prime}}$ whenever $0<\rho<\rho^{\prime}$.

Clearly, the set $N_{\rho_{0}}$ is compact. This implies that $\mathcal{A}(N_{\rho_{0}})=\left\{\mathcal{A}(x)\in\mathcal{T}\mid x\in N_{\rho_{0}}\right\}\subseteq\mbox{dom}(h)$ is also compact. By Assumption 1(a-ii), $\nabla h$ is Lipschitz continuous on $\mathcal{A}(N_{\rho_{0}})$. Hence, for any $x\in N_{\rho_{0}}$, there exists an $L_{A}>0$ such that

Now, let $\bar{x}$ be the projection of $x$ onto $\mathcal{X}$. Then, we have $\bar{y}=\mathcal{A}(\bar{x})$ and $\nabla f(\bar{x})=\bar{g}$ by Proposition 1 and $R(\bar{x})=\mathbf{0}$. This, together with the 1-Lipschitz continuity of $\mbox{prox}_{P}$ on $\mathcal{E}$, implies that

where $L_{R}=L_{A}\|\mathcal{A}\|+2>0$. This completes the proof. \sqcup\hbox to0.0pt{\hss\sqcap}

Proof of Theorem 1 Suppose that the error bound (EBN) holds. Then, there exist constants $\kappa_{0},\rho>0$ such that

By decreasing $\rho$ if necessary, we may assume that $\{x\in\mathcal{E}\mid d(x,\mathcal{X})\leq\rho\}\subseteq\mbox{dom}(f)$, so that Lemma 1 applies. Let $x\in\mathcal{E}$ be such that $d(x,\mathcal{X})\leq\rho$ and suppose that $-g\in\partial P(x)$. Using the definition of the proximity operator $\mbox{prox}_{P}$ in (4), it is straightforward to verify that $x=\mbox{prox}_{P}(x-g)$. This, together with (17) and the definition of the residual map $R$ in (3), leads to

where (3.2) follows from the 1-Lipschitz continuity of $\mbox{prox}_{P}$ on $\mathcal{E}$, (3.2) follows from Lemma 1, and $\kappa=\kappa_{0}\cdot\max\{L_{A},1\}>0$. Since $-g\in\partial P(x)$ is arbitrary, we conclude that the error bound (EBR) holds.

Conversely, suppose that the error bound (EBR) holds. Then, there exist constants $\kappa_{0},\rho_{0}>0$ such that

By Lemma 1, there exists a constant $\rho_{1}>0$ such that $\left\{x\in\mathcal{E}\mid d(x,\mathcal{X})\leq\rho_{1}\right\}\subseteq\mbox{dom}(f)$. Set $\rho=\min\{\rho_{0},\rho_{1}\}/(L_{R}+1)>0$ and let $x\in\mathcal{E}$ be such that $d(x,\mathcal{X})\leq\rho$, where $L_{R}>0$ is given in Lemma 1. Using the definition of the proximity operator $\mbox{prox}_{P}$ in (4) and the residual map $R$ in (3), we have $\mathbf{0}\in R(x)+\nabla f(x)+\partial P(x+R(x))$, or equivalently,

In addition, the property of projection onto $\mathcal{X}$, the triangle inequality, and Lemma 1 imply

It follows from (20)–(22) and Lemma 1 that

Now, let $V=\{\mathcal{A}(x)\in\mathcal{T}\mid d(x,\mathcal{X})\leq\rho\}\subseteq\mbox{dom}(h)$. Since $\mathcal{X}$ is compact, $V$ is also compact. By Assumption 1(a-ii), the function $h$ is strongly convex on $V$. Hence, there exists a $\sigma>0$ such that for any $x\in\mathcal{E}$ satisfying $d(x,\mathcal{X})\leq\rho$, we have

where $\bar{x}$ is the projection of $x$ onto $\mathcal{X}$. Using the convexity of $P$ and the fact that $-\bar{g}\in\partial P(\bar{x})$ and $-g(x)\in\partial P(x+R(x))$, we have

for some constant $L_{f}>0$, where we use the fact that $\nabla f$ is Lipschitz continuous on the compact set $\{x\in\mathcal{E}\mid d(x,\mathcal{X})\leq\rho\}$ in the last inequality (see the discussion in Section 2.1). Since $\|R(x)\|_{2}^{2}\geq 0$ for all $x\in\mathcal{E}$, we conclude from (23)–(25) that

where $\kappa_{2}=2\kappa_{1}^{2}\cdot\max\{(L_{f}+1)/\sigma,1\}$. Solving the above quadratic inequality yields

where $\kappa=\left(\kappa_{2}+\sqrt{\kappa_{2}(\kappa_{2}+4)}\right)/2$. This completes the proof. \sqcup\hbox to0.0pt{\hss\sqcap}

Upon combining Propositions 3, 4 and Theorem 1, we obtain the following sufficient condition for the error bound (EBP) to hold:

Under the setting of Theorem 1, the error bound (EBP) holds if the solution map $\Gamma:\mathcal{T}\times\mathcal{E}\rightrightarrows\mathcal{E}$ is calm at $(\bar{y},\bar{g})$ for any $\bar{x}\in\Gamma(\bar{y},\bar{g})$.

3 Verifying the Calmness of the Solution Map ΓΓ\Gamma

Corollary 1 reduces the problem of establishing the error bound (EBP) for those instances of Problem (1) that satisfy Assumptions 1 and 2 to that of checking certain calmness property of the solution map $\Gamma$. The upshot of this reduction is that the latter problem can be tackled using a wide array of tools in set-valued analysis. As an illustration, let us develop a simple sufficient condition for the calmness property stated in Corollary 1 to hold.

To motivate our approach, observe that the solution map $\Gamma$ has a separable structure. Specifically, we have

where $\Gamma_{f}:\mathcal{T}\rightrightarrows\mathcal{E}$ and $\Gamma_{P}:\mathcal{E}\rightrightarrows\mathcal{E}$ are multi-functions defined by

Intuitively, if $x\in\mathcal{E}\setminus\mathcal{X}$ is close to both $\Gamma_{f}(\bar{y})$ and $\Gamma_{P}(\bar{g})$, then it should be close to $\Gamma_{f}(\bar{y})\cap\Gamma_{P}(\bar{g})=\mathcal{X}$. This suggests that it may be possible to estimate $d(x,\mathcal{X})$ by separately estimating $d(x,\Gamma_{f}(\bar{y}))$ and $d(x,\Gamma_{P}(\bar{g}))$. Such idea can be formalized using the notion of bounded linear regularity of a collection of closed convex sets. We begin with the definition.

(see, e.g., [3, Definition 5.6]) Let $C_{1},\ldots,C_{N}$ be closed convex subsets of $\mathcal{E}$ with a non-empty intersection $C$. We say that the collection $\{C_{1},\ldots,C_{N}\}$ is boundedly linearly regular if for every bounded subset $B$ of $\mathcal{E}$, there exists a constant $\kappa>0$ such that

Naturally, we are interested in the collection $\mathcal{C}=\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$. It is obvious that both $\Gamma_{f}(\bar{y})$ and $\Gamma_{P}(\bar{g})$ are convex, and that the former is closed. Using the fact that $P$ is a closed proper convex function (Assumption 1(b)) and [30, Theorem 24.4], we see that $\Gamma_{P}(\bar{g})$ is closed as well. In addition, we have $\Gamma_{f}(\bar{y})\cap\Gamma_{P}(\bar{g})=\mathcal{X}$, which is non-empty by Assumption 2. Thus, the collection $\mathcal{C}$ satisfies the hypothesis of Definition 2. The following result highlights the relevance of the notion of bounded linear regularity in establishing the calmness property stated in Corollary 1.

Suppose that Problem (1) satisfies Assumptions 1 and 2. Let $\bar{y}\in\mathcal{T}$ and $\bar{g}\in\mathcal{E}$ be as in Proposition 1. Consider the collection $\mathcal{C}=\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$, where the multi-functions $\Gamma_{f}:\mathcal{T}\rightrightarrows\mathcal{E}$ and $\Gamma_{P}:\mathcal{E}\rightrightarrows\mathcal{E}$ are defined in (26). Suppose that the following two conditions hold:

(C1). The collection $\mathcal{C}$ is boundedly linearly regular.

(C2). For any $\bar{x}\in\mathcal{X}$, the subdifferential $\partial P:\mathcal{E}\rightrightarrows\mathcal{E}$ is metrically sub-regular at $\bar{x}$ for $-\bar{g}$.

Then, the solution map $\Gamma:\mathcal{T}\times\mathcal{E}\rightrightarrows\mathcal{E}$ is calm at $(\bar{y},\bar{g})$ for any $\bar{x}\in\Gamma(\bar{y},\bar{g})$.

Proof Condition (C2) and Fact 1 imply that $(\partial P)^{-1}:\mathcal{E}\rightrightarrows\mathcal{E}$ is calm at $-\bar{g}$ for any $\bar{x}\in\mathcal{X}$. Since $\mathcal{X}$ is compact by Assumption 2, Proposition 2 implies the existence of constants $\kappa_{0},\epsilon>0$ such that

It is clear that $\Gamma(y,g)\subseteq\Gamma_{P}(g)=(\partial P)^{-1}(-g)$ for any $(y,g)\in\mathcal{T}\times\mathcal{E}$. Thus, the above inclusion leads to

On the other hand, observe that $\Gamma_{f}(\bar{y})$ is the set of solutions to a linear system. Thus, by the Hoffman bound , there exists a constant $\kappa_{1}>0$ such that

where $\kappa=\kappa_{2}\cdot\max\{\kappa_{0},\kappa_{1}\}$. This implies that $\Gamma$ is calm at $(\bar{y},\bar{g})$ for any $\bar{x}\in\Gamma(\bar{y},\bar{g})$, as desired. \sqcup\hbox to0.0pt{\hss\sqcap}

As seen from Theorem 2, the bounded linear regularity of the collection $\mathcal{C}$ can potentially simplify the task of verifying the calmness property stated in Corollary 1 and hence of establishing the error bound (EBP). Thus, it is natural to ask when the collection $\mathcal{C}$ is boundedly linearly regular. The following fact provides a simple answer.

([4, Corollary 3]) Let $C_{1},\ldots,C_{N}$ be closed convex subsets of $\mathcal{E}$, where $C_{r+1},\ldots,C_{N}$ are polyhedral for some $r\in\{0,1,\ldots,N\}$. Suppose that

Then, the collection $\{C_{1},\ldots,C_{N}\}$ is boundedly linearly regular.

Although Fact 2 only gives a sufficient condition for the collection $\mathcal{C}$ to be boundedly linearly regular, it is already very useful for studying the error bound property (EBP) associated with Problem (1). This will be elaborated in the next section.

Applications to Structured Convex Optimization

So far our investigation has focused on deriving conditions that can imply the error bound (EBP) for the structured convex optimization problem (1). However, we have yet to exhibit instances of Problem (1) that would satisfy those conditions. As it turns out, such instances abound in applications. In this section, we will consider four classes of instances of Problem (1) and show that they all possess the calmness property stated in Corollary 1. Consequently, they all have the error bound property (EBP). Although previous works have already established the error bound property for three of the four classes of instances mentioned above, we shall see that our approach provides a unified and more transparent treatment of the existing results. More interestingly, our approach allows us to resolve the validity of the error bound (EBP) for the fourth class of instances, which comprises of structured convex optimization problems with nuclear norm regularization. This answers an open question raised by Tseng .

For notational simplicity, in what follows, we shall refer to $f$ as the loss function and $P$ as the regularizer. Moreover, unless otherwise stated, Assumptions 1 and 2 will be in force.

As a warm-up, suppose that the linear operator $\mathcal{A}$ in Assumption 1 is the identity; i.e., $\mathcal{E}=\mathcal{T}$ and $\mathcal{A}(x)=x$ for all $x\in\mathcal{E}$. This gives rise to instances of Problem (1) in which the loss function $f$ is strongly convex and has a Lipschitz continuous gradient on any compact convex set $V\subseteq\mbox{dom}(f)$. Conversely, any such loss function can be put into the form (5) by letting $\mathcal{A}$ to be the identity map, $h=f$, and $c=\mathbf{0}$. It is well known that in this case the error bound (EBP) holds whenever the optimal solution set $\mathcal{X}$ is non-empty; see, e.g., [25, Theorem 3.1]. To recover this result using the machinery developed in Section 3, we first observe that the solution map $\Gamma$ is given by

Now, note that $\mathcal{X}$ is either empty or a singleton. Thus, the non-emptiness of $\mathcal{X}$ is equivalent to Assumption 2. In particular, we have $\mathcal{X}=\Gamma(\bar{y},\bar{g})=\{\bar{x}\}$, where $\bar{x}=\bar{y}\in\mathcal{E}$ and $\bar{g}=\nabla h(\bar{x})+c\in\mathcal{E}$ with $-\bar{g}\in\partial P(\bar{x})$. This, together with (30), implies that

which in turn implies that $\Gamma$ is calm at $(\bar{y},\bar{g})$ for $\bar{x}\in\Gamma(\bar{y},\bar{g})$. The desired conclusion then follows from Corollary 1.

Suppose that Problem (1) satisfies Assumptions 1 and 2. Suppose further that $\mathcal{A}$ is the identity map, so that the loss function $f$ is strongly convex and has a Lipschitz continuous gradient on any compact convex set $V\subseteq\mbox{dom}(f)$. Then, the error bound (EBP) holds.

2 Polyhedral Convex Regularizer

is polyhedral convex. As $\Gamma_{f}(\bar{y})$ is also polyhedral convex (it is the set of solutions to a linear system), we conclude from Fact 2 that the collection $\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$ is boundedly linearly regular; i.e., condition (C1) is satisfied.

Now, by [28, Proposition 3], $\partial P^{*}=(\partial P)^{-1}$ is a polyhedral multi-function; i.e., $\mbox{gph}(\partial P^{*})$ is the union of a finite (possibly empty) collection of polyhedral convex sets (see for an alternative proof of this result). Hence, we can invoke a celebrated result of Robinson to conclude that $(\partial P)^{-1}$ is calm at $-\bar{g}$ for any $\bar{x}\in\mathcal{X}$; see [8, Proposition 3H.1]. This, together with Fact 1, implies that for any $\bar{x}\in\mathcal{X}$, $\partial P$ is metrically sub-regular at $\bar{x}$ for $-\bar{g}$; i.e., condition (C2) is satisfied.

Suppose that Problem (1) satisfies Assumptions 1 and 2 with $P$ being a polyhedral convex regularizer. Then, the error bound (EBP) holds.

Modulo the boundedness assumption on $\mathcal{X}$ (see Assumption 2), our argument above leads to an alternative proof of Theorem 2.1 in Luo and Tseng and a part of Theorem 4 in Tseng and Yun . It is worth noting that one can use the machinery developed in Section 3 to establish the error bound (EBP) without assuming the boundedness of $\mathcal{X}$. However, one needs to exploit the polyhedrality of $P$, just as it was done in . Since our original motivation is to develop an analysis framework that can tackle non-polyhedral regularizers $P$, we choose not to pursue a separate, more refined analysis for the polyhedral case, so as to streamline the presentation.

3 Grouped LASSO Regularizer

To begin, recall that for any $x\in\mathcal{F}$, where $\mathcal{F}$ is a finite-dimensional Euclidean space, we have

The following result provides an explicit characterization of $\Gamma_{P,J}(g)$, where $J\in\mathcal{J}$:

On the other hand, if $\omega_{J}>0$, then

Consequently, $\Gamma_{P,J}(g)$ is a polyhedral convex set.

Proof The case where $\omega_{J}=0$ is trivial. Thus, let us focus on the case where $\omega_{J}>0$. Using (31), it is clear that $\Gamma_{P,J}(g)=\emptyset$ (resp. $\Gamma_{P,J}(g)=\{\mathbf{0}\}$) when $\|g_{J}\|_{2}>\omega_{J}$ (resp. $\|g_{J}\|_{2}<\omega_{J}$). Now, suppose that $\|g_{J}\|_{2}=\omega_{J}$ and $x\in\Gamma_{P,J}(g)$. By (31) and the Cauchy-Schwarz inequality, we have $\|x\|_{2}=\langle-g_{J}/\omega_{J},x\rangle\leq\|x\|_{2}$, which implies that $x$ is a non-negative multiple of $-g_{J}/\omega_{J}$. Conversely, it is easy to see that $a\cdot g_{J}\in\Gamma_{P,J}(g)$ for any $a\leq 0$. This completes the proof. \sqcup\hbox to0.0pt{\hss\sqcap}

From (32) and Proposition 7, we see that $\Gamma_{P}(\bar{g})$ is a polyhedral convex set. Thus, by Fact 2, the collection $\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{g})\}$ is boundedly linearly regular; i.e., condition (C1) in Theorem 2 is satisfied.

Since $(\bar{x},-\bar{g})\in{\rm gph}(\partial P)$, Proposition 7 implies that $\bar{g}_{J}=\mathbf{0}$ whenever $\omega_{J}=0$, where $J\in\mathcal{J}$. This in turn implies that

To proceed, we prove the following result, which would allow us to bound each summand in (33) by the corresponding summand in (34).

The multi-function $\partial\|\cdot\|_{2}:\mathcal{F}\rightrightarrows\mathcal{F}$ is metrically sub-regular at any $x\in\mathcal{F}$ for any $s\in\mathcal{F}$ such that $(x,s)\in{\rm gph}(\partial\|\cdot\|_{2})$.

Proof Let $(x_{0},s_{0})\in{\rm gph}(\partial\|\cdot\|_{2})$ be arbitrary. By (31), we have $\|s_{0}\|_{2}\leq 1$. Consider first the case where $\|s_{0}\|_{2}<1$. We have $x_{0}=\mathbf{0}$ and $(\partial\|\cdot\|_{2})^{-1}(s_{0})=\{\mathbf{0}\}$. It follows that for any $x\in\mathcal{F}$,

On the other hand, set $\epsilon=\min\{\|y-s_{0}\|_{2}\mid\|y\|_{2}=1\}$. Since $\|s_{0}\|_{2}<1$, we have $\epsilon>0$. Moreover, for any $x\in\mathcal{F}\setminus\{\mathbf{0}\}$, we have $d(s_{0},\partial\|x\|_{2})=\|s_{0}-(x/\|x\|_{2})\|_{2}\geq\epsilon$. Thus, we obtain

Next, consider the case where $\|s_{0}\|_{2}=1$. Let $\epsilon>0$ be arbitrary and set $\kappa=\|x_{0}\|_{2}+\epsilon>0$. We claim that

as desired. \sqcup\hbox to0.0pt{\hss\sqcap}

From Proposition 8 and the fact that $(\bar{x}_{J},-\bar{g}_{J})\in{\rm gph}(\omega_{J}\partial\|\cdot\|_{2})$ for $J\in\mathcal{J}$, we deduce that for each $J\in\mathcal{J}$ with $\omega_{J}>0$, there exist constants $\kappa_{J},\epsilon_{J}>0$ such that

It then follows from (33), (34), and (35) that

In other words, $\partial P$ is metrically sub-regular at $\bar{x}$ for $-\bar{g}$.

Finally, by invoking Theorem 2 and Corollary 1, we recover the following result of Tseng [38, Theorem 2]:

Suppose that Problem (1) satisfies Assumptions 1 and 2 with $P$ being the grouped LASSO regularizer. Then, the error bound (EBP) holds.

4 Nuclear Norm Regularizer

where $I_{r}$ is the $r\times r$ identity matrix.

Although the matrices $\Sigma(X)$ and $\Sigma_{+}(X)$ are uniquely determined by $X$, there could be multiple pairs of orthogonal matrices $(U,V)$ that decompose $X$ into the form (36). Let

be the set of all such pairs of orthogonal matrices. Furthermore, let $\bar{\sigma}_{1}(X)>\bar{\sigma}_{2}(X)>\cdots>\bar{\sigma}_{s}(X)$ be the distinct non-zero singular values of $X$. Then, we can define the index sets

The following result explains the relationship between different SVDs of $X$:

To facilitate our study of the local behavior of the solution map $\Gamma$, we will also need the following matrix perturbation results:

Suppose that $\Gamma_{P}(G)\not=\emptyset$. Then, we have $\|-G\|\leq 1$ by Fact 3. This allows us to divide the singular values of $-G$ into the following three groups:

where $\bar{r}=\mbox{rank}(-G)$. In particular, every SVD of $-G$ can be put into the form

Suppose that $-G$ admits the SVD (37). Then, we have

Since $Z\succeq\mathbf{0}$, the diagonal entries of $\Lambda$ are non-negative. It follows that

is an SVD of $X$. This, together with Fact 3 and the fact that $\|\bar{\Sigma}_{(0,1)}\|<1$, implies

Upon observing that $QQ^{T}=I_{\bar{s}}$ and using (37), we conclude that $-G\in\partial\|X\|_{*}$, or equivalently, $X\in\Gamma_{P}(G)$, as desired.

Note that since $\|W^{\prime}\|\leq 1$, we have $\sigma_{i}(W^{\prime})\in(0,1]$ for $i=1,\ldots,r^{\prime}$, where $r^{\prime}=\mbox{rank}(W^{\prime})$. Now, let

Upon comparing (37) and (38) and noting that $I_{\bar{r}-\bar{s}}\succ\bar{\Sigma}_{(0,1)}$ and $I_{r^{\prime}}\succeq\Sigma_{+}(W^{\prime})$, we have $r\leq\bar{s}$ and

where (41) follows from the SVD of $X$ in (36); (42) follows from (39), (40), and the fact that

4.3 Metric Sub-Regularity of ∂P𝑃\partial P

This result, which could be of independent interest, is crucial to understanding the validity of the error bound (EBP) for Problem (1) when $P$ is the nuclear norm regularizer. Note that by a standard argument (see, e.g., [8, Exercise 3H.4]), it suffices to establish the existence of constants $\kappa_{0},\epsilon_{0},\delta_{0}>0$ such that

4.4 Validity of the Error Bound (EBP)

Theorem 2 and Proposition 11 imply that in order to establish the error bound (EBP) for the nuclear norm-regularized problem (1), it suffices to show that the collection $\mathcal{C}=\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{G})\}$, where $\bar{y}=\mathcal{A}(X)$ and $\bar{G}=\nabla f(X)$ for any $X\in\mathcal{X}$ (recall Proposition 1), is boundedly linearly regular. Since Proposition 10 suggests that the set $\Gamma_{P}(\bar{G})$ is not polyhedral in general, we can invoke Fact 2 to conclude that the collection $\mathcal{C}$ is boundedly linearly regular if the regularity condition $\Gamma_{f}(\bar{y})\cap\mbox{ri}(\Gamma_{P}(\bar{G}))\not=\emptyset$ holds. However, such condition is not entirely satisfactory, as it reveals very little about the structure of the optimal solution set $\mathcal{X}$. This motivates us to develop an alternative regularity condition, which leads to the third main result of this paper:

Suppose that Problem (1) satisfies Assumptions 1 and 2 with $P$ being the nuclear norm regularizer. Suppose further that there exists an $X^{\star}\in\mathcal{X}$ satisfying

Proof Recall from (9) that $-\bar{G}\in\partial\|X\|_{*}$ for any $X\in\mathcal{X}$. Hence, we have $\|-\bar{G}\|\leq 1$ by Fact 3. In particular, we may assume that $-\bar{G}$ admits the SVD (37). Since $X^{\star}\in\mathcal{X}$ satisfies (49), we have $-\nabla f(X^{\star})=-\bar{G}\in\mbox{ri}(\partial\|X^{\star}\|_{*})$. This, together with (37) and Fact 3, implies that $\mbox{rank}(X^{\star})=\bar{s}$. Now, observe that $X^{\star}\in\Gamma_{P}(\bar{G})$, as $-\bar{G}\in\partial\|X^{\star}\|_{*}$. Since $\mbox{rank}(X^{\star})=\bar{s}$, Proposition 10 yields $X^{\star}\in\mbox{ri}(\Gamma_{P}(\bar{G}))$. Since we also have $X^{\star}\in\Gamma_{f}(\bar{y})$, we conclude that $\Gamma_{f}(\bar{y})\cap\mbox{ri}(\Gamma_{P}(\bar{G}))\not=\emptyset$. Hence, by Fact 2, the collection $\{\Gamma_{f}(\bar{y}),\Gamma_{P}(\bar{G})\}$ is boundedly linearly regular. Upon combining this with Proposition 11 and then invoking Theorem 2, the desired result follows. \sqcup\hbox to0.0pt{\hss\sqcap}