Proximal Point Method - Polyak-type step size
This note shows that the proximal point method can converge linearly when we choose the proximal parameter according to the function value gap \(f(x_k) - f^\star\) and the distance \(\|x_k - x^\star\|\).
Theorem. Let \(f:\mathbb{R}^n \to \mathbb{R}\) be a proper, closed, convex function with minimum value \(f^\star\) and nonempty solution set \(X^\star := \arg\min f\). Consider the proximal point method \(\begin{align*} x_{k+1} = \arg\min_{x} \left\{ f(x) + \frac{1}{2\lambda_k}\|x - x_k\|^2 \right\}, \end{align*}\) where the stepsize is chosen as \(\begin{align*} \lambda_k = \frac{\|x_k - x^\star\|^2}{f(x_k) - f^\star} \end{align*}\) for some fixed \(x^\star \in X^\star\), provided \(f(x_k) > f^\star\). Then the sequence \(\{x_k\}\) satisfies the linear convergence rate \(\begin{align*} f(x_{k+1}) - f^\star \leq \frac{1}{2} \bigl(f(x_k) - f^\star\bigr), \end{align*}\) and consequently \(\begin{align*} f(x_k) - f^\star \leq 2^{-k} \bigl(f(x_0) - f^\star\bigr). \end{align*}\)
Proof. By optimality of \(x_{k+1}\), we have for any \(x \in \mathbb{R}^n\)
\[\begin{align*} f(x_{k+1}) + \frac{1}{2\lambda_k}\|x_{k+1} - x_k\|^2 \leq f(x) + \frac{1}{2\lambda_k}\|x - x_k\|^2. \end{align*}\]Taking \(x = x^\star \in X^\star\), we obtain
\[\begin{align*} f(x_{k+1}) + \frac{1}{2\lambda_k}\|x_{k+1} - x_k\|^2 \leq f^\star + \frac{1}{2\lambda_k}\|x^\star - x_k\|^2. \end{align*}\]Dropping the nonnegative term \(\frac{1}{2\lambda_k}\|x_{k+1} - x_k\|^2\) from the left-hand side yields
\[\begin{align*} f(x_{k+1}) - f^\star \leq \frac{1}{2\lambda_k}\|x_k - x^\star\|^2. \end{align*}\]Substituting the choice of \(\lambda_k\), we obtain
\[\begin{align*} f(x_{k+1}) - f^\star \leq \frac{1}{2} \bigl(f(x_k) - f^\star\bigr). \end{align*}\]Iterating this inequality gives
\[\begin{align*} f(x_k) - f^\star \leq 2^{-k} \bigl(f(x_0) - f^\star\bigr), \end{align*}\]which completes the proof.