📉Variational Analysis Unit 8 – Monotone Operators & Proximal Algorithms

Key Concepts and Definitions

• Monotone operators generalize the concept of monotone functions to the setting of operators between Hilbert spaces
• A Hilbert space $H$ is a complete inner product space where the inner product $\langle \cdot, \cdot \rangle$ induces a norm $\|\cdot\|$ and a metric $d(x,y) = \|x-y\|$
• An operator $T: H \to H$ is monotone if $\langle Tx - Ty, x - y \rangle \geq 0$ for all $x,y \in H$
  • Intuitively, monotone operators preserve the order relation induced by the inner product
• The subdifferential $\partial f(x)$ of a convex function $f$ at $x$ is the set of all subgradients $v$ such that $f(y) \geq f(x) + \langle v, y-x \rangle$ for all $y$
  • The subdifferential is a monotone operator when $f$ is convex
• The proximal operator $\operatorname{prox}_{\lambda f}(x)$ of a convex function $f$ with parameter $\lambda > 0$ is defined as $\operatorname{argmin}_{y} \left\{ f(y) + \frac{1}{2\lambda}\|y-x\|^2 \right\}$
  • It generalizes the projection operator onto a convex set

Monotone Operators: Basics and Properties

• Monotone operators can be classified based on the strength of the monotonicity property
• An operator $T$ is strictly monotone if $\langle Tx - Ty, x - y \rangle > 0$ for all $x \neq y$
• $T$ is strongly monotone with parameter $\mu > 0$ if $\langle Tx - Ty, x - y \rangle \geq \mu\|x-y\|^2$ for all $x,y$
  • Strong monotonicity implies strict monotonicity
• The resolvent $J_{\lambda T} = (I + \lambda T)^{-1}$ of a monotone operator $T$ with parameter $\lambda > 0$ is a single-valued operator
  • It is firmly nonexpansive, i.e., $\|J_{\lambda T}(x) - J_{\lambda T}(y)\|^2 \leq \langle x-y, J_{\lambda T}(x) - J_{\lambda T}(y) \rangle$ for all $x,y$
• The graph of a monotone operator $T$ is the set $\operatorname{gra} T = \{(x,y) \in H \times H : y \in Tx\}$
  • The graph is a monotone subset of $H \times H$

Types of Monotone Operators

• Maximal monotone operators are monotone operators whose graph is not properly contained in the graph of any other monotone operator
  • They generalize the concept of continuous functions to the setting of set-valued operators
• The subdifferential of a proper, lower semicontinuous, convex function is maximal monotone
• The normal cone operator $N_C(x)$ of a nonempty, closed, convex set $C$ is maximal monotone
  • It is defined as $N_C(x) = \{v : \langle v, y-x \rangle \leq 0 \text{ for all } y \in C\}$ if $x \in C$ and $\emptyset$ otherwise
• Cocoercive operators $T$ satisfy $\langle Tx - Ty, x - y \rangle \geq \frac{1}{L}\|Tx-Ty\|^2$ for some $L > 0$ and all $x,y$
  • They are a subclass of monotone operators with Lipschitz continuous gradient
• Monotone operators can be composed and remain monotone under certain conditions
  • The sum of two monotone operators is monotone
  • The composition of a monotone operator with a linear, self-adjoint, positive semidefinite operator is monotone

Introduction to Proximal Algorithms

• Proximal algorithms are a class of iterative methods for solving optimization problems involving nonsmooth functions
• They are based on the idea of replacing a nonsmooth function with a sequence of smooth approximations using the proximal operator
• The basic structure of a proximal algorithm involves alternating between a proximal step and a gradient step
  • The proximal step minimizes a regularized version of the original function
  • The gradient step moves in the direction of the negative gradient of the smooth part
• Proximal algorithms can handle composite objective functions of the form $f(x) + g(x)$ where $f$ is smooth and $g$ is nonsmooth
  • The proximal operator of $g$ is used to handle the nonsmooth part
• Convergence of proximal algorithms can be established under various assumptions on the functions and the algorithm parameters
  • Sublinear, linear, and superlinear convergence rates are possible depending on the setting

Proximal Point Method

• The proximal point method is a basic proximal algorithm for finding a zero of a maximal monotone operator $T$
• It generates a sequence $(x_k)$ starting from an initial point $x_0$ by applying the resolvent of $T$: $x_{k+1} = J_{\lambda_k T}(x_k) = (I + \lambda_k T)^{-1}(x_k)$
  • The sequence of parameters $(\lambda_k)$ is positive and bounded away from zero
• The proximal point method can be interpreted as a implicit discretization of the continuous-time gradient flow $\dot{x}(t) \in -Tx(t)$
• When $T = \partial f$ for a convex function $f$, the method minimizes $f$ and the iterates satisfy $f(x_{k+1}) \leq f(x_k)$
  • The method converges to a minimizer of $f$ if one exists
• The proximal point method has a linear convergence rate when $T$ is strongly monotone
  • It has a sublinear rate $O(1/k)$ in the general case
• Inexact variants of the method allow for approximate computation of the resolvent
  • They require the error to decrease at a sufficient rate to maintain convergence

Proximal Gradient Method

• The proximal gradient method is a proximal algorithm for minimizing composite objective functions $f(x) + g(x)$
  • $f$ is smooth with Lipschitz continuous gradient and $g$ is nonsmooth but has an easy-to-compute proximal operator
• The method alternates between a gradient step for $f$ and a proximal step for $g$: $x_{k+1} = \operatorname{prox}_{\lambda_k g}(x_k - \lambda_k \nabla f(x_k))$
  • The parameter $\lambda_k$ is a step size that can be fixed or determined by a line search
• The proximal gradient method generalizes the gradient descent method and the projected gradient method
  • It reduces to gradient descent when $g = 0$ and to projected gradient when $g$ is the indicator function of a convex set
• The method has a sublinear convergence rate $O(1/k)$ in the general case
  • It has a linear convergence rate when $f$ is strongly convex or when the objective satisfies a error bound condition
• Accelerated versions of the method achieve a faster sublinear rate $O(1/k^2)$ in the general case
  • They use momentum terms to speed up convergence
• Stochastic and incremental variants of the method are suitable for large-scale problems
  • They use stochastic gradients or process the data in smaller batches to reduce the computational cost per iteration

Applications in Optimization

• Proximal algorithms have been widely applied to various optimization problems in machine learning, signal processing, and other fields
• In sparse optimization, the $\ell_1$ norm is used as a regularizer to promote sparsity in the solution
  • The proximal operator of the $\ell_1$ norm is the soft-thresholding operator, which can be computed efficiently
• In matrix completion, the goal is to recover a low-rank matrix from a subset of its entries
  • The nuclear norm is used as a convex surrogate for the rank and its proximal operator is the singular value thresholding operator
• In image processing, total variation regularization is used to preserve edges while removing noise
  • The proximal operator of the total variation norm involves solving a denoising subproblem
• In distributed optimization, proximal algorithms can be implemented in a decentralized manner over a network of agents
  • Each agent performs local computations and communicates with its neighbors to reach consensus on the solution
• Proximal algorithms can be combined with other techniques such as splitting methods and coordinate descent to handle more complex problem structures
  • Splitting methods decompose the problem into simpler subproblems that can be solved efficiently
  • Coordinate descent methods update one variable at a time while keeping the others fixed

Advanced Topics and Extensions

• Proximal algorithms can be extended to handle more general problem settings beyond convex optimization
• Monotone inclusion problems involve finding a point in the intersection of the graphs of two monotone operators
  • They generalize variational inequality problems and can be solved by splitting methods that alternate between the two operators
• Saddle point problems involve finding a point that is a minimum in one variable and a maximum in another variable
  • They can be formulated as monotone inclusion problems and solved by primal-dual proximal algorithms
• Nonconvex optimization problems can be addressed by proximal algorithms under certain conditions
  • The Kurdyka-Łojasiewicz (KL) property is a generalization of convexity that ensures the convergence of proximal algorithms to stationary points
• Bregman proximal algorithms replace the Euclidean distance in the proximal operator with a Bregman distance induced by a convex function
  • They can handle non-Euclidean geometries and adapt to the problem structure
• Inexact and approximate proximal algorithms allow for errors in the computation of the proximal operator
  • They can reduce the computational cost while maintaining convergence guarantees
• Proximal algorithms can be combined with other optimization techniques such as interior-point methods and Newton-type methods
  • They can also be integrated with machine learning frameworks such as deep learning and kernel methods