Metric sub-regularity is a local property of set-valued operators which turns out to be a key enabler for linear convergence in several operator-based algorithms. However, conditions are often stated for the fixed-point residual operator and become rather difficult to verify in practice. In this post we state sufficient metric sub-regularity conditions for a monotone inclusion which are easier to verify and we focus on the preconditioned proximal point method (P3M).
Let us first provide some necessary mathematical preliminaries and definitions.
Let use denote by the set of extended real numbers, that is . Functions which map into are called extended-real-valued and are often used in optimisation to encode constraints.
Let be a real Hilbert space. For a function , its domain is the set .
We call proper if it is not everywhere equal to infinity, that is .
We say that is closed (or lower semicontinuous) if . This is equivalent to requiring that the epigraph of , that is the set , is closed.
The convex conjugate of a proper convex function , is the function . The convex conjugate plays a central role in Fenchel duality theory.
The proximal operator of a proper, closed, convex function with parameter is the mapping . The proximal operator of is also the resolvent of the operator . In general, for an operator , its resolvent is the operator , where is the identity operator.
The subdifferential of a proper, convex function at is .
For two Hilbert spaces and we denote by the direct sum of the two spaces equipped with the inner product .
We define three important classes of operators on Hilbert spaces. We call nonexpansive if . We call –averaged if it can be written as , where is the identity operator and is nonexpansive. We say that is firmly nonexpansive if it is -averaged.
We say that a set-valued operator is a monotone operator if for every and for every and , it is . For any proper function , is monotone.
We say that is maximally monotone if it is monotone and its graph cannot be extended to the graph of another monotone operator – in other words, if for every for which for all with , it is . As an example, skew-symmetric bounded linear operators are maximally monotone. Moreoever, the subdifferential of a convex, proper, closed function is maximally monotone.
Last, for a convex set , we define its core to be the set , where is the conic hull. The strong relative interior of a set is the set (here span stands for the set of linear combinations and the overline denotes the topological closure). The strong relative interior is a recurring notion in infinite dimensional spaces and it appears in results related to strong duality (such as the Attouch-Brézis Theorem).
For an operator , the set of its fixed points is defined as .
The inverse of an operator is defined as . The set of zeros of is
Preconditioned Proximal Point Method
Optimization problems can be stated as monotone inclusions:
where is a maximally monotone operator. The classical proximal point method (P2M) is
where is the resolvent of with parameter . More often than not, however, cannot be evaluated as it requires the solution of another optimisation problem.
The preconditioned proximal point method (P3M) consists in replacing in P2M with where is a bounded invertible linear operator on . The modified algorithm reads
An appropriate choice of may lead to steps which are easier to evaluate as we shall see in the following section.
Primal-Dual Optimality Conditions
Consider the following optimisation problem
where and are proper, convex, closed functions and is a bounded linear operator whose adjoint is denoted by .
We assume that , that is, the above optimisation problem has a nonempty feasible domain.
The optimality conditions of this problem are
and provided that , the optimality conditions become
Equivalently, the optimality conditions are satisfied if and only if there is a and a so that
Using the well-known property that (as it easily follows from the definitions of the subdifferential and the convex conjugate), the optimality conditions become simply.
Naturally, we define the operator as
We are now looking for a primal-dual point which satisfies the monotone inclusion .
The Chambolle-Pock Method
The Chambolle-Pock method is an instance of the P3M method for solving using the following linear operator as a preconditioner
Using its Schur complement it can be verified that this is positive definite provided that (where is the operator norm of ).
This linear operator is used to define a modified inner product on as which in turn induces the norm . In what follows, will be taken with respect to this inner product.
Using this preconditioner, P3M boils down to the following recursion:
This is easy to verify starting from the basic P3M iteration described above, which is where .
This defines the following operator
which we shall refer to as the Chambolle-Pock operator. The fixed points of , that is, points such that are exactly the solutions of the monotone inclusion .
Operator is firmly nonexpansive in with the modified inner product introduced above.
We further define the fixed-point residual operator as
The notion of metric subregularity is of key importance in establishing linear convergence rates for several algorithms. Let us first state the definition:
Definition. A set-valued function defined on a Hilbert space is said to be metrically subregular at a for a if there is a constant and a neighbourhood for so that
for all .
Metric subregularity is equivalent to the calmness of the inverse mapping. It is a property which is weaker than metric regularity, bounded linear regularity for single-valued mappings and the popular Aubin property.
A common assumption which is used to establish linear rate of convergence is that the fixed-point residual is metrically subregular at a solution for , that is, there is a neighbourhood of so that
where is the set of fixed-points of . This condition is, however, difficult to verify in practice. Instead, we may use the following condition in conjunction with P3M. We state the following proposition which is not specific to the Chambolle-Pock algorithm.
Proposition. Let be a P3M step and let be the corresponding fixed-point residual. If is metrically sub-regular at for with modulus , then is metrically sub-regular at for with modulus .
Proof. For given take so that .
For , define for which we know that .
Equivalently, satisfies .
Note that and . Using the triangle inequality for the distance-to-set mapping, for
which completes the proof.
Shen and Pan (Prop. 3.1) provide conditions under which operators in the form are metrically sub-regular at a . A condition which is also mentioned in the book of Dontchev and Rockafellar requires to be an affine map and to have a polyhedral graph.
The condition of the above proposition is that for , there is a and a neighbourhood of so that
for all . The right hand side of this last inequality can be written as