Metric Subregularity and the Proximal Point Method

Introduction

Let $\mathcal{H}$ be a real Hilbert space and let T:\mathcal{H}\;{\lower 1.0pt\hbox{\rightarrow}}\kern-12.0pt\hbox{\raise 2.8pt\hbox{\rightarrow}}\;\mathcal{H} be a set-valued mapping. Two common problems that arise in several branches of applied mathematics are to

where $I$ is some index set. Specifically, these problems correspond to finding a zero of an operator and, more generally, a common zero of multiple operators.

Suppose that the operators under consideration are monotone, meaning that

For $\lambda>0$, the mappings $J_{\lambda T}:=(I+\lambda T)^{-1}$ are the resolvents of $T$, which were shown to be at most single-valued in . One proposed method for solving Problem 1.1 is the proximal point algorithm, considered originally in and more thoroughly explored by , given by, for $k=0,1,2,\ldots,$

Our goal is to examine how appropriate regularity assumptions on the operators $T$ (or $T_{1},\ldots,T_{m}$, respectively) affect the speed of convergence of variants of the proximal point algorithm. In order to do so, the remainder of this paper is organized as follows. In Section 2, we provide notation and basic facts about monotone operators, metric regularity and subregularity, and the geometry of convex sets. Then, in Section 3, we show how assumptions of metric subregularity can be used to demonstrate linear convergence of both the proximal point algorithm for Problem 1.1 and a randomized proximal point algorithm for Problem 1.2.

Background and Notation

A single-valued operator $U$ is firmly non-expansive if

It was shown in that an operator $T$ is monotone if and only if its resolvents are firmly non-expansive. The domain of $T$ is $\{x\in\mathcal{H}:T(x)\neq\emptyset\}$ and the inverse operator, $T^{-1}$, is defined by $T^{-1}(y)=\{x:y\in T(x)\}$. It is known that (see , for example) $T$ is monotone if and only if $T^{-1}$ is monotone and, if $T$ is maximal monotone, meaning the graph of $T$ is not strictly contained in the graph of another monotone operator, then both $T$ and $T^{-1}$ are closed and convex-valued and the domain of the resolvents of $T$ is $\mathcal{H}$.

We are interested in how certain regularity conditions affect local rates of convergence. One prominent condition is the idea of metric regularity of set-valued mappings. We say the set-valued mapping $\Phi$ is metrically regular at $\bar{x}$ for $\bar{b}\in\Phi(\bar{x})$ if there exists $\gamma>0$ such that

Further, the modulus of regularity is the infimum of all constants $\gamma$ such that Inequality 2.2 holds.

A slightly weaker condition is that of metric subregularity. We say the set-valued mapping $\Phi$ is metrically subregular at $\bar{x}$ for $\bar{b}\in\Phi(\bar{x})$ if there exists $\gamma>0$ such that

Further, the modulus of subregularity is the infimum of all constants $\gamma$ such that Equation 2.3 holds. Note that for metric subregularity, the reference vector $\bar{b}$ is fixed in Inequality 2.3 but not in Inequality 2.2. It is clear from the definitions that metric regularity implies metric subregularity; hence, the modulus of subregularity is no larger than the modulus of regularity, using the convention that the modulus of (sub)regularity is infinite if the mapping fails to be metrically (sub)regular.

The property of metric regularity is connected with other ideas in variational analysis. The simplest connection, as shown in [11, Ex. 1.1], is that metric regularity generalizes the Banach open mapping principle, essentially saying that a bounded and linear mapping is metrically regular if and only if it is surjective; in such a case, the modulus of regularity is simply $\sup_{y\in B}\{d(0,A^{-1}(y))\}$ where $B$ is the unit ball. If the mapping $\Phi$ has a closed-convex graph, the Robinson-Ursescu Theorem says that $\Phi$ is metrically regular at $\bar{x}$ for $\bar{y}$ if and only if $\bar{y}$ is in the interior of the range of $\Phi$. Metric regularity is also known to be equivalent to several others in variational analysis, namely the Aubin property of $\Phi^{-1}$ and the openness at linear rate of $\Phi$. Additionally, metric regularity has been shown to be a generalization of the Eckart-Young result from matrix analysis on the distance to singularity of a matrix. Further, a result originating with Lyusternik and Graves (, ) and extended by others (for example, ,, ) show that metric regularity is determined by the first-order behavior of a mapping and is preserved by sufficiently small first-order perturbations. Additional information about metric regularity and its relationship to other concepts in variational analysis can be found in , , and , among others.

A central tool frequently appearing in variational analysis is that of the normal cone of a closed, convex set, $S$. Specifically, the normal cone of $S$ at $\bar{x}\in S$ can be defined as

and $N_{S}(\bar{x})=\emptyset$ if $\bar{x}\not\in S$. Let $d(x,S)$ denote the distance from $x$ to $S$, given by $d(x,S):=\inf_{s\in S}\|x-s\|$. Further, let $P_{S}(x)$ be the projection operator onto $S$, i.e., the set of such minimizers. If $S$ is closed, convex and non-empty, then $P_{S}$ is single-valued everywhere. Further, the projection operator is firmly non-expansive ([9, Thm 5.5]) and can be characterized by

A method of characterizing regularity of closed sets $S_{1},\ldots,S_{m}$ is by considering regularity properties of a related set-valued mapping. Given a Hilbert space, $\mathcal{H}$, consider the product space $\mathcal{H}^{m}$ with the induced inner product defined by

and consider the set-valued mapping given by $\Phi(x)=[S_{1}-x,\ldots,S_{m}-x]^{T}$. Note that $0\in\Phi(x)$ if and only if $x\in\cap_{i}S_{i}$. Using metric regularity as a starting point, suppose $\Phi(x)$ is metrically regular at $\bar{x}$ for 0. From the definition, metric regularity of $\Phi$ at $\bar{x}$ for 0 is equivalent to the strong metric inequality, examined in and , among others, defined by the existence of $\beta,\delta>0$ such that, for $i=1,\ldots,m$,

Characterizing this in terms of normal cones, it was shown in [19, Thm. 1, Prop. 10, Cor. 2] that this is equivalent to the existence of a constant $k>0$ such that

By using the formula in [32, Thm 9.43] for expressing the modulus of regularity in terms of coderivatives, it was shown in that the modulus of regularity of $\Phi$ at $\bar{x}$ for 0 equals

with this value being infinite being equivalent to a lack of metric regularity of $\Phi$.

Consider a relaxed variant of the strong metric inequality, known simply as the metric inequality as studied in , and among others, defined to hold at $\bar{x}$ if there exists $\beta>0$ such that

If Inequality 2.8 is valid for $\delta=\infty$, we obtain the property of linear regularity and if it holds for all $\delta>0$, it is equivalent to the property of bounded linear regularity, as studied in , , , , and others, often in an algorithmic context. It is easy to show that the existence of a $\delta>0$ such that Inequality 2.8 holds is equivalent to the previously defined mapping $\Phi$ being metrically subregular at $\bar{x}$ for 0.

Our focus for the remainder of this paper will involve metric subregularity. Unfortunately, several of the stability properties and some of the geometric intuition that accompanies metric regularity—especially that relating to normal cones of sets—fails to have a natural equivalent for metric subregularity; some examples of this phenomenon are given in . However, since metric regularity implies metric subregularity, the intuition provided by metric regularity can be applied to the following results when that property does, in fact, hold. Additionally, if the monotone operators under consideration are actually subdifferentials of convex functions, characterization of both metric regularity and subregularity in terms of the underlying function was shown in , providing additional intuition.

Metric Regularity and Linear Convergence

We now return to Problem 1.1, the problem of finding a zero of a maximal monotone operator. Variants of proximal point algorithms for solving this and related problems have been considered by a wide variety of authors, including , ,,, and others.

Many authors consider an algorithmic framework much more general than the one considered in this paper. Some of the better-studied variants allow for a varying proximal parameter $\lambda$, allow approximate computation of the proximal iteration, allow over- or under-relaxation in the proximal step or incorporate an additional projective framework. These ideas have often proven worthwhile both for designing a computationally practical and efficient algorithm as well as for improving the convergence analysis. However, in this paper, we will only consider algorithms in their “classical” form, assuming exact computation of the resolvent with a fixed proximal parameter. Our particular interest is in exploring how naturally occurring constants—for example, the modulus of subregularity of the mappings themselves and of the mapping associated with the solution sets—govern the local rate of convergence and, further, how randomization as an analytical tool can emphasize this connection. To begin, consider the basic proximal point algorithm given by 1.3, where $x_{k+1}=J_{\lambda T}(x_{k})$. Under an assumption of metric subregularity, we obtain the following initial result.

Suppose $T$ is maximal monotone and metrically subregular at $\bar{x}\in T^{-1}(0)$ for 0 with regularity modulus $\gamma$. Let $\bar{\gamma}>\gamma$ and suppose $x_{0}$ is sufficiently near $\bar{x}$. Then the iterates given by Algorithm 1.3 are linearly convergent to $T^{-1}(0),$ the zero-set of $T$, satisfying

Proof Let $\hat{x}\in T^{-1}(0)$ and note that $J_{\lambda T}(\hat{x})=\hat{x}.$ Since the resolvent of a monotone operator is firmly non-expansive, it follows from Inequality 2.1 that, for any $x$,

However, by definition of $J_{\lambda T}$,

Now, note that since the resolvents and projection operators are firmly non-expansive, if $x_{0}$ has the property of being sufficiently close to $\bar{x}$ such that Inequality 2.3 holds with constant $\bar{\gamma}$, then $x_{j}$ and $P_{T^{-1}(0)}(x_{j})$ do as well for each $j\geq 0$. Therefore, it follows that

Further observe that by considering a sequence $\{\lambda_{k}\}$ such that $\lambda_{k}\rightarrow\infty$ instead of a fixed $\lambda$ in the above algorithm, we obtain superlinear convergence.

Our primary interest in Theorem 3.1 is as a tool in proving the following result, Theorem 3.5. However, we note that Theorem 3.1 is similar to some previously known results. For example, linear convergence was shown in and , under a framework that permitted error in evaluating the resolvent, with a slightly stronger regularity assumption. In particular, as a limiting case with no such error in evaluating the resolvent, an identical convergence rate was obtained in . The result by Solodov and Svaiter in , however, corresponds to a hybrid proximal-projection algorithm.

We wish to generalize this result to that of Problem 1.2, finding a common zero among a group of maximal monotone operators, $T_{1},\ldots,T_{m}$. Variants of proximal point algorithms for this problem have been considered by a variety of authors, including , , , , among others. In what follows, consider the following randomized variant of a proximal point algorithm: for $k=0,1,2,\ldots,$

The maximal monotone operators $T_{i}$, $i=1,\ldots,m$, are metrically subregular at $\bar{x}\in\cap_{j}T_{j}^{-1}(0)$ for 0 with modulus $\gamma_{i}$.

The mapping $\Phi(x)=[T_{1}^{-1}(0)-x,\ldots,T_{m}^{-1}(0)-x]^{T}$ is metrically subregular at $\bar{x}$ for 0 with modulus $\kappa$.

$\bar{\gamma}>\max\{\gamma_{1},\ldots,\gamma_{m}\}$ and $\bar{\kappa}>\kappa$.

Then for $x_{0}$ sufficiently close to $\bar{x}$, Algorithm 3.4 satisfies

Proof If $x_{0}$ is sufficiently close to $\bar{x}$ such that Inequality 2.3 holds with constant $\bar{\gamma}$ for each mapping $T_{i}$, it follows from the firm non-expansivity of the resolvents and the projection operator that each iterate $x_{k}$ and the projection of each iterate onto the common zero set, $P_{\cap_{j}T_{j}^{-1}(0)}(x_{k})$, are sufficiently close to $\bar{x}$ as well. Additionally, this implies the first conclusion of the theorem.

Suppose that at iteration $k$, the resolvent $J_{\lambda T_{i}}$ is chosen by the algorithm. Then it follows that

The first inequality comes from the fact that $x_{k}-P_{T_{i}^{-1}(0)}(x_{k})\in N_{T_{i}^{-1}(0)}(P_{T_{i}^{-1}(0)}(x_{k}))$ so Inequality 2.4 can be applied from the definition of the normal cone. The second inequality is an application of the Cauchy-Schwartz inequality. The rest follows from the definition of the projection operator, followed by applying Theorem 3.1, the previous linear convergence result. Putting this together, we obtain

where the last inequality follows from the metric subregularity of the mapping $\Phi(x)=[T_{1}^{-1}(0)-x,\ldots,T_{m}^{-1}(0)-x]^{T}$. $\Box$

Note that the last assumption in Theorem 3.5 is so that the convergence rate is less than 1. Additionally, this type of convergence result implies that $d(x_{k},\cap_{j}T_{j}^{-1}(0))\rightarrow 0$ almost surely (cf. ).

One particularly simple way of de-randomizing Algorithm 3.4 is by considering averaged resolvents or, in the terminology of , the barycentric proximal method. Specifically, given maximal monotone operators $T_{i},~i=1,\ldots,m$ with respective resolvents $J_{\lambda T_{i}},~i=1,\ldots,m$, consider the algorithm described such that, for $k=0,1,2,\ldots,$

The following proposition, found in , provides the necessary connection.

If $\bar{x}\in\cap_{i}T_{i}^{-1}(0)$, then $\bar{x}$ is a solution to Problem 3.7. Further, if $\cap_{i}T_{i}^{-1}(0)\neq\emptyset$, the fixed points of Problem 3.7 are common fixed points of all the $T_{i}$’s.

Considering the example where each operator $T_{i}$ is the normal cone mapping for some closed, convex set, it follows that Algorithm 3.6 is simply the averaged projections algorithm studied by , , , , and , among others. More generally, we can use the result of Theorem 3.5 to generalize a result on averaged projections found in [21, Thm 5.8] to the barycentric proximal method.

Suppose the assumptions of Theorem 3.5 hold. Then the conclusions of Theorem 3.5 hold for Algorithm 3.6 as well.

Proof Let $x_{k}$ be the current iterate, $x_{k+1}^{BP}$ be the new iterate in the barycentric proximal method, Algorithm 3.6, and let $x_{k+1}^{RP}$ be the new iterate in the randomized proximal point method, Algorithm 3.4. First, note that since each set $T_{i}^{-1}(0)$ is convex, the distance function $d(~\cdot~,\cap_{j}T_{j}^{-1}(0))$ is as well, and

Let $\alpha=\Big(1-\frac{1}{m\bar{\kappa}^{2}}+\frac{2}{m\bar{\kappa}^{2}}\Big(\frac{\bar{\gamma}^{2}}{\lambda^{2}+\bar{\gamma}^{2}}\Big)^{\frac{1}{2}}\Big)$ and observe that the function $d(~\cdot~,\cap_{j}T_{j}^{-1}(0))^{2}$ is also convex. Noting that

from an application of Jensen’s Inequality. $\Box$

In particular, the barycentric proximal method converges at least as quickly as the randomized proximal point method.

References