Monteiro-Svaiter A-HPE method
Introduction
A note on the Monteiro-Svaiter A-HPE method [1], which generalizes the early work of Solodov and Svaiter (the hybrid proximal/extragradient method) using Nesterov's acceleration approach. The original paper has been very hard to read for me. Here, I will try to make it more readable.
Background. The A-HPE method originates from the monotone inclusion problem, find $x$ such that
$$0 \in T(x), \quad x \in \mathbb{E},$$
where $T$ is a maximal monotone operator. The proximal point algorithm (PPA) is a first-order method for this problem. It updates the iterates by
$$x_{k+1} = (\lambda_{k+1} T + \mathbf{I})^{-1}(x_k).$$
In the special case $T = \partial f$ for a closed proper convex $f$, the resolvent reduces to the proximal operator,
$$x_{k+1} = (\lambda_{k+1} \partial f + \mathbf{I})^{-1}(x_k) = \mathrm{prox}_{\lambda_{k+1} f}(x_k) = \underset{x \in \mathbb{E}}{\mathrm{argmin}} \left\{ f(x) + \tfrac{1}{2\lambda_{k+1}} \|x - x_k\|^2 \right\},$$
so each PPA step minimizes $f$ regularized by a quadratic proximity term. Equivalently, writing the Moreau envelope $f_\lambda(x) = \min_u \lbrace f(u) + \tfrac{1}{2\lambda}|u - x|^2 \rbrace$, whose gradient is $\nabla f_\lambda(x) = \tfrac{1}{\lambda}(x - \mathrm{prox}_{\lambda f}(x))$, the update is exactly a gradient step on the (smooth) envelope,
$$x_{k+1} = x_k - \lambda_{k+1} \nabla f_{\lambda_{k+1}}(x_k).$$
That is, PPA on $f$ is gradient descent on its Moreau envelope.
A-HPE: Accelerated Hybrid Proximal Extragradient Method
Consider $f$ to be a proper convex function.
$$\min_{x\in\mathbb{E}} f(x)$$
We have the A-HPE algorithm (Algorithm 1).
- Input: $x_0\in\mathbb{E}, y_0\in\mathbb{E}, A_0=0, \sigma \in [0, 1]$.
- For $k=0,1,2,\ldots$:
- Find $\lambda_{k+1}$, compute extrapolation
$$\begin{align*} a_{k+1} &= \tfrac{\lambda_{k+1}+ \sqrt{\lambda_{k+1}^2 + 4\lambda_{k+1}A_k}}{2}\\ \tilde x_{k} &= \tfrac{A_k}{A_k + a_{k+1}}y_k + \tfrac{a_{k+1}}{A_k + a_{k+1}}x_k \end{align*}$$
- Get $(y_{k+1}, v_{k+1}) \in \mathscr{S'}_{(\varepsilon_{k+1},\sigma)}(\tilde x_k, \lambda_{k+1})$.
- Update,
$$\begin{align*} A_{k+1} &= A_k + a_{k+1} \\ x_{k+1} &= x_k - a_{k+1} v_{k+1} \end{align*}$$
- Find $\lambda_{k+1}$, compute extrapolation
- Consider the following "exact" proximal iteration,
$$y:= \mathrm{prox}_{\lambda_{k+1}f} (\tilde x_k) = \underset{x \in \mathbb{E}}{\mathrm{argmin}} ~ \left\{ f(x) + \tfrac{1}{2\lambda_{k+1}} \|x - \tilde x_k\|^2 \right\} \tag{1}$$
whose optimality condition is$$y - \tilde x_k = - \lambda_{k+1} v, \quad v \in \partial f(y).$$
- The exact minimization is as hard as the original problem, so we use an approximation.
- The choice $\sigma$: the RHS error.
- The choice $\varepsilon_{k+1}$ — error for enlargement of subdifferential.
- This will be designated in different ways. The solution is given from a mapping $\mathscr{S'}$:
$$\begin{align*} &\mathscr{S'}_{(\varepsilon_{k+1},\sigma)}(\tilde x_k, \lambda_{k+1}) = \left\{ (y_{k+1}, v_{k+1}) \in \mathbb{E}^2 : (y_{k+1}, v_{k+1})\quad\text{satisfying} \quad (3) \right\} \tag{2} \\ &\left\{\begin{array}{l} v_{k+1} \in \partial_{\varepsilon_{k+1}} f(y_{k+1}) \\ \|y_{k+1} - \tilde x_k + \lambda_{k+1}v_{k+1}\|^2 + 2\lambda_{k+1}\varepsilon_{k+1} \leq \sigma^2\|y_{k+1} - \tilde x_k\|^2 \end{array}\right. \tag{3} \end{align*}$$
- The prox mapping is hard to compute, so, we need an "implementable" version of mapping $\mathscr{S'}$.
Basic properties of A-HPE
Inexact condition
In this section the relative error may vary by iteration. Write
$$\sigma_{k+1} \in [0,1)$$
for the error used in the step that produces $(y_{k+1},v_{k+1})$. The fixed-error A-HPE method is the special case $\sigma_{k+1}\equiv\sigma$. The per-step inexact condition is
$$\begin{align*} & v_{k+1} \in \partial_{\varepsilon_{k+1}} f(y_{k+1}) \\ & \|y_{k+1} - \tilde x_k + \lambda_{k+1}v_{k+1}\|^2 + 2\lambda_{k+1}\varepsilon_{k+1} \leq \sigma_{k+1}^2\|y_{k+1} - \tilde x_k\|^2. \end{align*} \tag{4}$$
$$\begin{align*} & \|y - \tilde x + \lambda v\|^2 + 2\lambda \varepsilon \leq \eta^2 \|y - \tilde x\|^2 \tag{5} \\ \Longleftrightarrow \quad ~ & \min_{x \in \mathbb{E}} ~ \langle v, x-y \rangle - \varepsilon + \tfrac{1}{2\lambda} \|x - \tilde x\|^2 \ge \tfrac{1-\eta^2}{2\lambda}\|y - \tilde x\|^2 \tag{6} \end{align*}$$
That is, if the step $(y_{k+1}, v_{k+1})$ satisfies the per-step condition with error $\sigma_{k+1}$,$$\left(\min_{x \in \mathbb{E}} ~ \ell_{k+1}(x) + \tfrac{1}{2\lambda_{k+1}} \|x - \tilde x_k\|^2\right) - f(y_{k+1}) \ge \tfrac{1-\sigma_{k+1}^2}{2\lambda_{k+1}} \|y_{k+1} - \tilde x_k\|^2 \tag{7}$$
Note that by the optimal condition of (6),
$$\begin{align*} (6) \quad \Leftrightarrow \quad \boxed{\lambda v + x - \tilde x = 0} & \quad \Leftrightarrow \quad 0 \le ~ \langle v, \tilde x-\lambda v - y \rangle - \varepsilon + \tfrac{\lambda}{2} \|v\|^2 - \tfrac{1-\eta^2}{2\lambda}\|y - \tilde x\|^2 \\ \Rightarrow \quad & 2\lambda \langle v, y - \tilde x \rangle + \lambda^2 \|v\|^2 + \|y- \tilde x\|^2 + 2\lambda \varepsilon \le \eta^2 \|y-\tilde x\|^2 \\ \Rightarrow \quad & \|y- \tilde x + \lambda v\|^2 + 2 \lambda \varepsilon \le \eta^2 \|y-\tilde x\|^2. \end{align*}$$
Applying this equivalence with $(y,v,\tilde x,\lambda,\varepsilon,\eta)=(y_{k+1},v_{k+1},\tilde x_k,\lambda_{k+1},\varepsilon_{k+1},\sigma_{k+1})$ gives
$$(5) \quad \Leftrightarrow \quad \underbrace{\min_{x \in \mathbb{E}} ~ \langle v_{k+1}, x-y_{k+1} \rangle - \varepsilon_{k+1} + \tfrac{1}{2\lambda_{k+1}} \|x - \tilde x_k\|^2}_{\text{find a prox update.}} \ge \tfrac{1-\sigma_{k+1}^2}{2\lambda_{k+1}}\|y_{k+1} - \tilde x_k\|^2 \Leftrightarrow (4) \approx (1)$$
The estimating sequence
Now define the sequence $(\ell_k, L_k)$; note that $\lbrace a_k\rbrace_{k=0}^\infty$ is a sequence of positive numbers but dependent on $\lambda_k$.
$$\begin{align*} \ell_k(x) &= f(y_{k}) + \langle x - y_{k}, v_k \rangle - \varepsilon_{k} & v_k \in \partial_{\varepsilon_{k}} f(y_{k}) \\ L_{k}(x) & = L_{k-1}(x) + a_{k} \ell_{k}(x), & L_0(x) = 0 \\ \varphi_k(x) & = L_k(x) + \tfrac{1}{2} \|x - x_0\|^2 \end{align*}$$
We have the following algebraic relation.
$$\begin{align*} \lambda_{k+1} A_{k+1} &= a_{k+1}^2 \quad\text{and}\quad a_{k+1}^2 - \lambda_{k+1}a_{k+1} - \lambda_{k+1}A_k = 0 \tag{8} \\ \ell_k(x) &\le f(x), \quad\text{and}\quad L_k(x) \le A_k f(x), \quad \forall x\in\mathbb{E} \tag{9} \\ x_k &= \underset{x\in\mathbb{E}}{\mathrm{argmin}} ~\varphi_k(x) \quad\text{and}\quad \varphi_k(x) = \varphi_k(x_k) + \tfrac{1}{2} \|x - x_k\|^2 \quad \forall x\in\mathbb{E} \tag{10} \end{align*}$$
(8) and (9) are obvious. For (10), let $k=0$, it is trivial. Suppose it holds for $k$, By induction, for $k+1$, the optimal condition is,
$$\begin{align*} 0 &= \nabla \varphi_{k+1}(x) = \nabla L_{k+1}(x) + (x - x_0) \\ &= \nabla L_k(x) + a_{k+1}\nabla \ell_{k+1}(x) + (x - x_0) \\ &= (x_0 - x_k) + a_{k+1} v_{k+1} + x-x_0. \end{align*}$$
That is, $x = x_{k+1}$. Note that $\nabla \varphi_k(x_k) = 0$, so
$$\varphi_k(x) = \varphi_k(x_k) + \langle \nabla \varphi_k(x_k), (x - x_k) \rangle + \tfrac{1}{2} \nabla^2 \varphi_k(x_k)[x - x_k, x - x_k],$$
this completes the proof.
This is saying that $\lbrace x_k\rbrace_{k=0}^\infty$ are from "global underestimates"; it belongs to a "linear span" of carefully chosen points $\lbrace y_k\rbrace_{k=0}^\infty$ and their gradients $\lbrace v_k\rbrace_{k=0}^\infty$; $y_k$ is computed by some "local overestimate" model.
Main convergence proof
We have the following result.
$$\beta_k = \inf_{x \in \mathbb{E}} \varphi_k(x) - A_k f(y_k)$$
Then,(a) $\beta_0 = 0$, and for $k \ge 0$,
$$\beta_{k+1} \ge \beta_k + \tfrac{1-\sigma_{k+1}^2}{2}\tfrac{A_{k+1}}{\lambda_{k+1}}\|y_{k+1} - \tilde x_k\|^2 \tag{11}$$
(b) Thus,$$\tfrac{1}{2}\textstyle\sum_{j=1}^k (1-\sigma_j^2)\tfrac{A_j}{\lambda_j}\|y_j - \tilde x_{j-1}\|^2 + \tfrac{1}{2}\|x-x_k\|^2 \le \varphi_k(x) - A_kf(y_k) \tag{12}$$
For (11). For $k=0$, it holds trivially. Note that,
$$\begin{align*} \beta_k &= \inf_{x\in\mathbb{E}} \varphi_k(x) - A_k f(y_k) \\ &= \inf_{x\in\mathbb{E}} L_k(x) + \tfrac{1}{2} \|x - x_0\|^2 - A_k f(y_k) \\ &= \varphi_k(x_k) - A_k f(y_k). \end{align*}$$
Given $x \in \mathbb{E}$, consider the extrapolation,
$$\tilde x = \tfrac{A_k}{A_{k+1}} y_k + \tfrac{a_{k+1}}{A_{k+1}} x$$
Then, because $\ell_{k+1}$ is a linear function, we have,
$$\begin{align*} \ell_{k+1}(\tilde x) &= \ell_{k+1}(\tfrac{A_k}{A_{k+1}} y_k + \tfrac{a_{k+1}}{A_{k+1}} x) = \tfrac{A_k}{A_{k+1}} \ell_{k+1}(y_k) + \tfrac{a_{k+1}}{A_{k+1}} \ell_{k+1}(x) \\ \tilde x - \tilde x_k &= \tfrac{a_{k+1}}{A_{k+1}} (x - x_k). \end{align*}$$
Therefore,
$$\begin{align*} \forall x \in \mathbb{E}, ~ \underbrace{L_{k+1}(x)+\tfrac{1}{2}\left\|x-x_0\right\|^2}_{\varphi_{k+1}(x)} & = a_{k+1} \ell_{k+1}(x)+ \underbrace{L_k(x)+\tfrac{1}{2}\left\|x-x_0\right\|^2}_{\varphi_k(x)} \\ & \stackrel{(10)}{=} a_{k+1} \ell_{k+1}(x)+ \varphi_k(x_k) + \tfrac{1}{2}\left\|x-x_k\right\|^2 \\ & = a_{k+1} \ell_{k+1}(x)+A_k f\left(y_k\right)+\beta_k+\tfrac{1}{2}\left\|x-x_k\right\|^2 \\ &\stackrel{(9)}{\ge} a_{k+1} \ell_{k+1}(x)+A_k \ell_{k+1}(y_k) + \beta_k+\tfrac{1}{2}\left\|x-x_k\right\|^2 \\ &= A_{k+1} \ell_{k+1}(\tilde x) + \beta_k + \tfrac{1}{2}\tfrac{A_{k+1}^2}{a_{k+1}^2}\|\tilde x-\tilde x_k\|^2 \\ &\stackrel{(8)}{=} A_{k+1} \ell_{k+1}(\tilde x) + \beta_k + \tfrac{1}{2}\tfrac{A_{k+1}}{\lambda_{k+1}}\|\tilde x-\tilde x_k\|^2. \end{align*}$$
Thus, minimizing over $x$ (equivalently over $\tilde x$, since $x \mapsto \tilde x$ is a bijection of $\mathbb{E}$), we have,
$$\begin{align*} \beta_{k+1} &= \inf_{x\in\mathbb{E}} \varphi_{k+1}(x) - A_{k+1} f(y_{k+1}) \\ & \ge \beta_k + A_{k+1} \left(\min_{\tilde x \in \mathbb{E}}\left\{\ell_{k+1}(\tilde x) + \tfrac{1}{2\lambda_{k+1}}\|\tilde x-\tilde x_k\|^2\right\} - f(y_{k+1})\right) \\ &\stackrel{(7)}{\ge} \beta_k + \tfrac{1-\sigma_{k+1}^2}{2}\tfrac{A_{k+1}}{\lambda_{k+1}}\|y_{k+1} - \tilde x_k\|^2. \end{align*}$$
For (12). By (11), we have,
$$\beta_k \ge \beta_0 + \textstyle\sum_{j=1}^k \tfrac{1-\sigma_j^2}{2}\tfrac{A_{j}}{\lambda_{j}}\|y_{j} - \tilde x_{j-1}\|^2.$$
That is,
$$\varphi_k(x) - A_k f(y_k) - \tfrac{1}{2}\|x-x_k\|^2 = \varphi_k(x_k) - A_k f(y_k) = \beta_k \ge \underbrace{\beta_0}_{=0} + \textstyle\sum_{j=1}^k \tfrac{1-\sigma_j^2}{2}\tfrac{A_{j}}{\lambda_{j}}\|y_{j} - \tilde x_{j-1}\|^2$$
We have the following key result.
$$\tfrac{1}{2}\|x_k - x^\ast\|^2 + A_k( f(y_k) - f^\ast ) + \tfrac{1}{2}\textstyle\sum_{j=1}^k (1-\sigma_j^2)\tfrac{A_j}{\lambda_j}\|y_j - \tilde x_{j-1}\|^2 \le \tfrac{1}{2} \delta_0^2. \tag{13}$$
Consequently,$$f(y_k) - f^\ast \le \tfrac{\delta_0^2}{2A_k}, \quad \|x_k - x^\ast\| \le \delta_0, \tag{14}$$
and$$\textstyle\sum_{j=1}^k (1-\sigma_j^2)\tfrac{A_j}{\lambda_j}\|y_j - \tilde x_{j-1}\|^2 \le \delta_0^2. \tag{15}$$
By (12), take $x = x^\ast$, we have,
$$\begin{align*} \textstyle\sum_{j=1}^k \tfrac{1-\sigma_j^2}{2}\tfrac{A_{j}}{\lambda_{j}}\|y_{j} - \tilde x_{j-1}\|^2 &\le \varphi_k(x^\ast) - A_k f(y_k) - \tfrac{1}{2}\|x^\ast-x_k\|^2 \\ &= L_k(x^\ast) + \tfrac{1}{2}\|x^\ast-x_0\|^2 - A_k f(y_k) - \tfrac{1}{2}\|x^\ast-x_k\|^2 \\ &\le A_k f(x^\ast) + \tfrac{1}{2}\|x^\ast-x_0\|^2 - A_k f(y_k) - \tfrac{1}{2}\|x^\ast-x_k\|^2. \end{align*}$$
Rearranging gives (13); dropping nonnegative terms gives (14) and (15).
We will need the following result.
$$A_k \ge \tfrac{1}{4} \left(\textstyle\sum_{j=1}^k\sqrt{\lambda_j}\right)^2 \tag{16}$$
Recall $a_{k+1} = \tfrac{1}{2}\left(\lambda_{k+1} + \sqrt{\lambda_{k+1}^2 + 4\lambda_{k+1}A_k}\right)$. Hence,
$$\begin{align*} A_{k+1} &= A_k + a_{k+1} \\ &= A_k + \tfrac{\lambda_{k+1}}{2} + \tfrac{1}{2}\sqrt{\lambda_{k+1}^2 + 4\lambda_{k+1}A_k} \\ &\ge A_k + \tfrac{\lambda_{k+1}}{4} + \sqrt{\lambda_{k+1}A_k} \\ &= \left(\sqrt{A_k} + \tfrac{1}{2}\sqrt{\lambda_{k+1}}\right)^2, \end{align*}$$
so that $\sqrt{A_{k+1}} \ge \sqrt{A_k} + \tfrac{1}{2}\sqrt{\lambda_{k+1}}$; telescoping from $A_0 = 0$ gives $\sqrt{A_k} \ge \tfrac{1}{2}\textstyle\sum_{j=1}^k \sqrt{\lambda_j}$.
Second-order A-HPE
Now consider,
$$\min_{x\in\mathbb{E}} f(x) = \min_{x\in\mathbb{E}} g(x) + h(x)$$
while $g$ has second-order derivatives and $h$ is proper closed convex. We consider an implementable solution mapping $\mathscr{S'}$, taking advantage of a second-order model,
$$\begin{align*} y & = \underset{y \in \mathbb{E}}{\mathrm{argmin}} ~ \left\{ \mathcal{T}_x(y) + h(y) + \tfrac{1}{2\lambda} \|y - x\|^2 \right\} \\ \mathcal{T}_x(y) & = g(x) + \langle y - x, \nabla g(x) \rangle + \tfrac{1}{2}{\nabla^2 g(x)[y-x,y-x]}. \end{align*} \tag{17}$$
We hope to find an approximate solution to (1) in the following way,
- Find a $\sigma_T$-approximate solution$\sigma_T = 0$ if it is solved exactly. to (17):
$$\begin{align*} & u_{k+1} \in \nabla \mathcal{T}_{\tilde x_{k}}(y_{k+1}) + \partial_{\varepsilon_{k+1}} h(y_{k+1})\\ & \|y_{k+1} - \tilde x_k + \lambda_{k+1}u_{k+1}\|^2 + 2\lambda_{k+1}\varepsilon_{k+1} \leq \sigma_T^2 \|y_{k+1} - \tilde x_k\|^2. \end{align*} \tag{18}$$
- For example, if $f$ is smooth, then $h=0, \varepsilon_{k+1}=0$, and we have
$$\begin{align*} & u_{k+1} = \mathcal{T}_{\tilde x_{k}}(y_{k+1}) \\ & \|y_{k+1} - \tilde x_k + \lambda_{k+1}u_{k+1}\| \leq \sigma_T\|y_{k+1} - \tilde x_k\| \end{align*}$$
implying the usual inexact Newton condition,$$\left\|\nabla g(\tilde x_k) + \left(\nabla^2 g(\tilde x_k)+\tfrac{1}{\lambda_{k+1}}\mathbf{I}\right)d_{k+1}\right\| \le \tfrac{\sigma_T}{\lambda_{k+1}}\|d_{k+1}\|$$
- Then, define
$$\begin{align*} v_{k+1} &= \nabla g(y_{k+1}) + u_{k+1} - \nabla \mathcal{T}_{\tilde x_{k}}(y_{k+1}) \\ &= \nabla g(y_{k+1}) + \partial_{\varepsilon_{k+1}} h(y_{k+1}) \\ \sigma_{k+1} &= \sigma_T + \tfrac{M}{2}\lambda_{k+1} \|y_{k+1} - \tilde x_k\|. \end{align*}$$
Then, one can show that $(y_{k+1}, v_{k+1}) \in \mathscr{S'}_{(\varepsilon_{k+1},\sigma_{k+1})}(\tilde x_k, \lambda_{k+1})$. - Let us put the above together, see Algorithm 2.
- Input: $x_0\in\mathbb{E}, y_0\in\mathbb{E}, A_0=0, \sigma \in [0, 1]$.
- Choose $0 < \sigma_\ell < \sigma_u < 1$, and some $\sigma_T$, to ensure
$$\sigma_T + \sigma_u < 1, \quad \sigma_\ell < \tfrac{1+\sigma_T}{1-\sigma_T} \cdot \sigma_u$$
- For $k=0,1,2,\ldots$:
- Find $\lambda_{k+1}$, compute extrapolation
$$\begin{align*} a_{k+1} &= \tfrac{\lambda_{k+1}+ \sqrt{\lambda_{k+1}^2 + 4\lambda_{k+1}A_k}}{2}\\ \tilde x_{k} &= \tfrac{A_k}{A_k + a_{k+1}}y_k + \tfrac{a_{k+1}}{A_k + a_{k+1}}x_k \end{align*}$$
- Get $(y_{k+1}, u_{k+1}) \in \mathscr{S'}_{(\varepsilon_{k+1},\sigma_T)}(\tilde x_k, \lambda_{k+1})$, until,
$$\tfrac{2\sigma_\ell}{M}\le \lambda_{k+1} \|y_{k+1} - \tilde x_k\|\le \tfrac{2\sigma_u}{M}$$
- Set $(y_{k+1}, A_{k+1}, x_{k+1})$,
$$\begin{align*} v_{k+1} &= \nabla g(y_{k+1}) + \partial_{\varepsilon_{k+1}} h(y_{k+1})\\ A_{k+1} &= A_k + a_{k+1} \\ x_{k+1} &= x_k - a_{k+1} v_{k+1} \end{align*}$$
- Find $\lambda_{k+1}$, compute extrapolation
The standard A-HPE method will keep $\sigma_{k+1}$ within a specific range in $\Theta(1)$; that is,
$$\lambda_{k+1} \|y_{k+1} - \tilde x_k\| = \Theta(1).$$
So $\lambda_{k+1}$ needs justification handled a posteriori — it takes a search process to find $\lambda_{k+1}$. To achieve this, a specific realization of Algorithm 2 needs a proper strategy to work with a second-order oracle; see, for example, the $p$-order regularized oracle [2][3]. There are also many recent techniques that may possibly help to achieve this, see Mishchenko [4] using only second-order regularization.
Cubic-regularized A-HPE
Here, we present the analysis using cubic oracle as a special case of high-order A-HPE [3], assuming $f$ is smooth (i.e., $\varepsilon_k = 0$). Consider the cubic regularization oracle to use in A-HPE; specifically, we consider the "proximal" cubic oracle as,
$$T_\lambda(x) := \underset{y \in \mathbb{E}}{\mathrm{argmin}}~\underbrace{\langle \nabla f(x), y-x \rangle + \tfrac{1}{2}\nabla^2 f(x)[y-x, y-x] + \tfrac{M}{6}\|y-x\|^3}_{\mathcal{T}_x(y)} + \tfrac{1}{2\lambda}\|y-x\|^2 \tag{19}$$
In the following we write $T := T_\lambda(x)$ when $\lambda$ and $x$ are clear from the context. Note that,
$$\begin{align*} \nabla \mathcal{T}_x(T) &= \nabla f(x) + \nabla^2 f(x)[T-x] + \tfrac{M}{2}\|T-x\|(T-x)\\ \|\nabla f(T) - \nabla \mathcal{T}_x(T)\| &= \|\nabla f(T) - \nabla f(x) - \nabla^2 f(x)[T-x] - \tfrac{M}{2}\|T-x\|(T-x)\|\\ &\le \tfrac{M+L_2}{2}\|T-x\|^2. \end{align*}$$
Find a $\sigma_T$-approximate solution of the proximal cubic oracle,Note: this is not just minimizing $\mathcal{T}_x(y)$ but also the proximal term $\tfrac{1}{2\lambda}|y-x|^2$; but, it is still a cubic oracle.
$$\|\lambda \nabla \mathcal{T}_x(T) + (T-x)\| \le \sigma_T \|T-x\|.$$
Thus,
$$\begin{align*} \|T - x + \lambda \nabla f(T)\| &\le \|T - x + \lambda \nabla \mathcal{T}_x(T)\| + \lambda \|\nabla f(T) - \nabla \mathcal{T}_x(T)\| \\ &\le \sigma_T \|T-x\| + \tfrac{M+L_2}{2}\lambda\|T-x\|^2 \\ &= \left(\sigma_T + \tfrac{M+L_2}{2} (\lambda\|T-x\|)\right)\|T-x\|. \end{align*}$$
We could run a cubic oracle with parameter $M$, define $y_{k+1} = T_{\lambda_{k+1}}(\tilde x_k), v_{k+1} = \nabla f(y_{k+1})$, we search for some $\lambda_{k+1}$ so that,
$$\tfrac{2\sigma_l}{M+L_2} \le \lambda_{k+1}\|y_{k+1} - \tilde x_k\| \le \tfrac{2\sigma_u}{M+L_2}. \tag{20}$$
The induced A-HPE error is therefore the per-step quantity
$$\sigma_{k+1} := \sigma_T + \tfrac{M+L_2}{2}\lambda_{k+1}\|y_{k+1} - \tilde x_k\| \le \sigma_T + \sigma_u =: \sigma < 1. \tag{21}$$
The analysis below is conditional on the existence, at every iteration, of a $\lambda_{k+1}$ satisfying the band (20), which is located by a line search on $\lambda$ (we do not prove termination of this search here). Thus,
$$\begin{align*} \|y_{k+1} - \tilde x_k + \lambda_{k+1} v_{k+1}\| &\le \left(\sigma_T + \tfrac{M+L_2}{2} (\lambda_{k+1}\|y_{k+1} - \tilde x_k\|)\right)\|y_{k+1} - \tilde x_k\| \\ &= \sigma_{k+1}\|y_{k+1} - \tilde x_k\| \le \sigma \|y_{k+1} - \tilde x_k\|. \end{align*}$$
So, this is an A-HPE oracle with per-step errors uniformly bounded by $\sigma$. The following theorem holds.
$$A_k \ge \tfrac{1}{4} C^{-\tfrac{2p}{q}}\left( \textstyle\sum_{j=1}^k {A_j^{\tfrac{1}{q}}} \right)^{2p}, \quad q = 7, ~ p=\tfrac{7}{6}, ~ C = \tfrac{\delta_0^2}{1-\left(\sigma_T+\sigma_u\right)^2}\left(\tfrac{2\sigma_l}{L_2+M}\right)^{-2}. \tag{22}$$
that is,$$A_k \ge \tfrac{1}{4} C^{-\tfrac{1}{3}}\left( \textstyle\sum_{j=1}^k {A_j^{\tfrac{1}{7}}} \right)^{\tfrac{7}{3}}. \tag{23}$$
and thus,$$A_k \ge \left(\tfrac{1}{2}\right)^3 \tfrac{2\sigma_l}{L_2+M}\left(\tfrac{1-\sigma^2}{\delta_0^2}\right)^{\tfrac{1}{2}}\left(\tfrac{2}{3}\right)^{\tfrac{7}{2}} k^{\tfrac{7}{2}}. \tag{24}$$
For (22). By the large-step condition (20),
$$\tfrac{A_j}{\lambda_j}\|y_j - \tilde x_{j-1}\|^2 = \tfrac{A_j}{\lambda_j^3}\left(\lambda_j \|y_j - \tilde x_{j-1}\|\right)^2 \ge \left(\tfrac{2\sigma_l}{L_2+M}\right)^2 \tfrac{A_j}{\lambda_j^3},$$
Since $\sigma_j \le \sigma$ by (21), (15) gives,
$$\textstyle\sum_{j=1}^k \tfrac{A_j}{\lambda_j^3} \le \tfrac{\delta_0^2}{1-\sigma^2}\left(\tfrac{2\sigma_l}{L_2+M}\right)^{-2} = C. \tag{25}$$
Write $b_j := A_j \lambda_j^{-3}$, so that $\sqrt{\lambda_j} = A_j^{1/6} b_j^{-1/6}$. By the Hölder inequality with exponents $(\tfrac{7}{6}, 7)$,
$$\begin{align*} \textstyle\sum_{j=1}^k A_j^{1/7} &= \textstyle\sum_{j=1}^k \left(A_j^{1/6} b_j^{-1/6}\right)^{6/7} b_j^{1/7} \\ &\le \left(\textstyle\sum_{j=1}^k A_j^{1/6} b_j^{-1/6}\right)^{6/7}\left(\textstyle\sum_{j=1}^k b_j\right)^{1/7} \\ &\stackrel{(25)}{\le} \left(\textstyle\sum_{j=1}^k \sqrt{\lambda_j}\right)^{6/7} C^{1/7}, \end{align*}$$
i.e., $\textstyle\sum_{j=1}^k \sqrt{\lambda_j} \ge C^{-1/6} \left(\textstyle\sum_{j=1}^k A_j^{1/7}\right)^{7/6}$. Substituting into (16),
$$A_k \ge \tfrac{1}{4}\left(\textstyle\sum_{j=1}^k \sqrt{\lambda_j}\right)^2 \ge \tfrac{1}{4} C^{-1/3}\left(\textstyle\sum_{j=1}^k A_j^{1/7}\right)^{7/3},$$
which is (23), i.e., (22) with $q = 7$, $p = \tfrac{7}{6}$, $\tfrac{2p}{q} = \tfrac{1}{3}$.
For (24). Let $S_k := \textstyle\sum_{j=1}^k A_j^{1/7}$ and $\theta := 4^{-1/7} C^{-1/21}$, so (23) reads $A_k^{1/7} \ge \theta S_k^{1/3}$. Since $t \mapsto t^{2/3}$ is concave and $S_k - S_{k-1} = A_k^{1/7}$,
$$S_k^{2/3} - S_{k-1}^{2/3} \ge \tfrac{2}{3} S_k^{-1/3}\left(S_k - S_{k-1}\right) = \tfrac{2}{3} S_k^{-1/3} A_k^{1/7} \ge \tfrac{2}{3}\theta.$$
Telescoping from $S_0 = 0$ gives $S_k^{2/3} \ge \tfrac{2\theta}{3} k$, i.e., $S_k \ge \left(\tfrac{2\theta}{3}\right)^{3/2} k^{3/2}$. Substituting back into (23),
$$A_k \ge \tfrac{1}{4} C^{-1/3} S_k^{7/3} \ge \tfrac{1}{4} C^{-1/3} \left(\tfrac{2\theta}{3}\right)^{7/2} k^{7/2} = \tfrac{1}{4} \cdot 4^{-1/2} \left(\tfrac{2}{3}\right)^{7/2} C^{-1/2} k^{7/2} = \left(\tfrac{1}{2}\right)^3 \left(\tfrac{2}{3}\right)^{7/2} C^{-1/2} k^{7/2},$$
and $C^{-1/2} = \tfrac{2\sigma_l}{L_2+M}\left(\tfrac{1-\sigma^2}{\delta_0^2}\right)^{1/2}$ gives (24).
Nesterov's optimal method
Nesterov presents an optimal cubic-regularized method with a $\mathcal{O}(\tfrac{1}{k^{3.5}})$ rate of convergence in [2] (§4.3.2), which simplifies the analysis of A-HPE. Again, consider the cubic oracle,
$$T(x) := \underset{y \in \mathbb{E}}{\mathrm{argmin}}~\underbrace{\langle \nabla f(x), y-x \rangle + \tfrac{1}{2}\nabla^2 f(x)[y-x, y-x] + \tfrac{M}{6}\|y-x\|^3}_{\mathcal{T}_x(y)}.$$
Here, we will not use the proximal term $\tfrac{1}{2\lambda}|y-x|^2$; cf. (19). Again, the optimal condition is,
$$\nabla \mathcal{T}_x(T) = \nabla f(x) + \nabla^2 f(x)[T-x] + \tfrac{M}{2}\|T-x\|(T-x) = 0.$$
So,
$$\langle \nabla f(T), x-T \rangle \ge \tfrac{1}{M\|T-x\|^2} \|\nabla f(T)\|^2 + \tfrac{M-L_2}{4M}{\|T-x\|^3}.$$
if $M \ge \tfrac{1}{\sigma}L_2$, then,
$$\langle \nabla f(T), x-T \rangle \ge \tfrac{1}{M\|T-x\|^2} \|\nabla f(T)\|^2 + \tfrac{(1-\sigma^2)M}{4}{\|T-x\|^3}.$$
The method is quite different from A-HPE.To be consistent with the text, the extrapolation point is denoted as $y$.
- Input: $x_0\in\mathbb{E}, y_0\in\mathbb{E}, A_0=0, \sigma \in [0, 1], \gamma > 1, M = \tfrac{1}{\sigma}L_2, \varphi_0(x) = \tfrac{1}{2}\|x-x_0\|^2$.
- For $k=0,1,2,\ldots$:
- Compute $v_k = \underset{v \in \mathbb{E}}{\mathrm{argmin}}~\varphi_k(x)$.
- Choose $\rho_{k}>0$ and solve,
$$\begin{align*} a_{k+1}^2 &= \tfrac{2(A_{k} + a_{k+1})}{M\rho_k} \\ A_{k+1} &= A_k + a_{k+1} \\ y_{k+1} &= \tfrac{A_k}{A_{k+1}}x_k + \tfrac{a_{k+1}}{A_{k+1}}v_k \end{align*}$$
- Compute $x_{k+1} = T(y_{k+1})$.
- If $\rho_k$ satisfies (30), update the model
$$\varphi_{k+1}(x) = \varphi_k(x) + a_{k+1} \big[f(x_{k+1}) + \langle \nabla f(x_{k+1}), x-x_{k+1} \rangle\big].$$
Else, go back to the choice of $\rho_k$.
We note the lemma below for convenience.
(a) For any $x \in \mathbb{E}$,
$$\varphi_k(x) = \varphi_k(v_k) + \tfrac{1}{2}\|x-v_k\|^2. \tag{26}$$
(b) For any $k \ge 0$,$$\varphi_{k+1}(x^\ast) \le A_{k+1} f(x^\ast) + \tfrac{1}{2}\|x^\ast-x_0\|^2. \tag{27}$$
(c) For any $k \ge 0$,$$v_{k+1} = x_0 - \textstyle\sum_{j=1}^k a_j \nabla f(x_j) \tag{28}$$
For (26). Note that, $\nabla\varphi_k(v_k) = 0$, and so,
$$\varphi_k(x) - \varphi_k(v_k) = \tfrac{1}{2}\|x-v_k\|^2.$$
For (27).
$$\begin{align*} \varphi_{k+1}(x^\ast) = \textstyle\sum_{j=1}^{k+1} a_j \left(f(x_j) + \langle \nabla f(x_j), x^\ast-x_j \rangle\right) + \tfrac{1}{2}\|x^\ast-x_0\|^2 \\ \le \textstyle\sum_{j=1}^{k+1} a_j f(x^\ast) + \tfrac{1}{2}\|x^\ast-x_0\|^2 \le A_{k+1} f(x^\ast) + \tfrac{1}{2}\|x^\ast-x_0\|^2. \end{align*}$$
For (28). Note that the model-minimization step of Algorithm 3,
$$\begin{align*} v_{k+1} &= \underset{v \in \mathbb{E}}{\mathrm{argmin}}~\varphi_{k+1}(x) \\ &=\underset{v \in \mathbb{E}}{\mathrm{argmin}}~\tfrac{1}{2}\|x-x_0\|^2 + \textstyle\sum_{j=1}^k a_j \left(f(x_j) + \langle \nabla f(x_j), x-x_j \rangle\right) \\ &=\underset{v \in \mathbb{E}}{\mathrm{argmin}}~\tfrac{1}{2}\|x-x_0\|^2 + \langle \textstyle\sum_{j=1}^k a_j \nabla f(x_j), x-x_j \rangle \end{align*}$$
and so
$$v_{k+1} - x_0 + \textstyle\sum_{j=1}^k a_j \nabla f(x_j) = 0 ~\Longrightarrow~ v_{k+1} = x_0 - \textstyle\sum_{j=1}^k a_j \nabla f(x_j).$$
$$A_kf(x_k) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 \le \varphi_k^\ast = \varphi_k(v_k).$$
We prove by induction. Clearly $k=0$ it holds. Assume it holds for $k$, we need to show it for $k+1$, that is,
$$\begin{align*} \varphi_{k+1}(x) &= \varphi_k(x) + a_{k+1} \big[f(x_{k+1}) + \langle \nabla f(x_{k+1}), x-x_{k+1} \rangle\big] \\ &= \varphi_k^\ast + \tfrac{1}{2}\|x-v_k\|^2 + a_{k+1} \big[f(x_{k+1}) + \langle \nabla f(x_{k+1}), x-x_{k+1} \rangle\big] \\ &\ge A_kf(x_k) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 + \tfrac{1}{2}\|x-v_k\|^2 + a_{k+1} \big[f(x_{k+1}) + \langle \nabla f(x_{k+1}), x-x_{k+1} \rangle\big] \\ &\ge A_kf(x_{k+1}) + A_k\langle \nabla f(x_{k+1}), x_k-x_{k+1} \rangle \\ & \qquad + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 + \tfrac{1}{2}\|x-v_k\|^2 + a_{k+1} \big[f(x_{k+1}) + \langle \nabla f(x_{k+1}), x-x_{k+1} \rangle\big] \\ &= A_{k+1}f(x_{k+1}) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 + \tfrac{1}{2}\|x-v_k\|^2 \\ & \qquad + \langle \nabla f(x_{k+1}), a_{k+1}(x-x_{k+1}) + A_k(x_k-x_{k+1}) \rangle. \end{align*}$$
Consider
$$\inf_{x \in \mathbb{E}} \left\{\tfrac{1}{2}\|x-v_k\|^2 + \langle \nabla f(x_{k+1}), a_{k+1}(x-x_{k+1}) + A_k(x_k-x_{k+1}) \rangle\right\} \tag{29}$$
The optimal condition is,
$$x - v_k + a_{k+1}\nabla f(x_{k+1}) = 0 ~\Longrightarrow~ x = v_k - a_{k+1}\nabla f(x_{k+1}) = v_{k+1}.$$
Thus,
$$\begin{align*} (29) &= \tfrac{1}{2}\|a_{k+1}\nabla f(x_{k+1})\|^2 + \langle \nabla f(x_{k+1}), a_{k+1}(v_k - a_{k+1}\nabla f(x_{k+1}) - x_{k+1}) + A_k(x_k - x_{k+1}) \rangle \\ &= - \tfrac{1}{2}\|a_{k+1}\nabla f(x_{k+1})\|^2 + \langle \nabla f(x_{k+1}), A_{k+1}(y_{k+1} - x_{k+1}) \rangle. \end{align*}$$
Combining,
$$\begin{align*} \varphi_{k+1}(v_{k+1}) &\ge A_{k+1}f(x_{k+1}) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 \\ & \qquad - \tfrac{1}{2}\|a_{k+1}\nabla f(x_{k+1})\|^2 + \langle \nabla f(x_{k+1}), A_{k+1}(y_{k+1} - x_{k+1}) \rangle \\ &\ge A_{k+1}f(x_{k+1}) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 - \tfrac{1}{2}\|a_{k+1}\nabla f(x_{k+1})\|^2\\ & \qquad + \tfrac{A_{k+1}}{M\|y_{k+1} - x_{k+1}\|} \|\nabla f(x_{k+1})\|^2 + \tfrac{(1-\sigma^2)MA_{k+1}}{4}\|y_{k+1} - x_{k+1}\|^3 \\ &= A_{k+1}f(x_{k+1}) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k+1}A_j\|x_{j}-y_{j}\|^3 + \tfrac{A_{k+1}}{M} \|\nabla f(x_{k+1})\|^2 \left(\|y_{k+1} - x_{k+1}\| - \tfrac{1}{\rho_k}\right). \end{align*}$$
This completes the induction.
$$\gamma\|x_{k+1} - y_{k+1}\| \ge \rho_k \ge \|x_{k+1} - y_{k+1}\|, \tag{30}$$
then, for any $k \ge 1$,$$A_k \ge \tfrac{1}{4} \gamma^{-1.5} \tfrac{\sqrt{1-\sigma^2}}{M\|x_0 - x^\ast \|} \left(\tfrac{k+0.5}{1.5}\right)^{3.5}.$$
By the recursion of $A_k$,
$$A_{k+1}^{0.5} - A_k^{0.5} = \tfrac{a_{k+1}}{A_{k+1}^{0.5}+A_k^{0.5}} = \tfrac{1}{A_{k+1}^{0.5}+A_k^{0.5}}\sqrt{\tfrac{2A_{k+1}}{M\rho_k}} \ge \boxed{\sqrt{\tfrac{1}{2M\rho_k}}}.$$
So this gives a lower bound,
$$A_{k} \ge \tfrac{1}{2M} \left(\textstyle\sum_{j=0}^{k-1} \rho_j^{-0.5}\right)^2 \ge \boxed{\tfrac{1}{2M\gamma}\left(\textstyle\sum_{j=0}^{k-1} \|x_{j+1} - y_{j+1}\|^{-0.5}\right)^2}.$$
Note that by Lemma 6,
$$A_kf(x_k) + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\|x_{j}-y_{j}\|^3 \le \varphi_k^\ast \le A_k f(x^\ast) + \tfrac{1}{2}\|x^\ast - x_0\|^2.$$
Let $\xi_j = |x_j - y_j|^{1/2}$, then, this gives,
$$\begin{align*} A_k\left[f(x_k) - f(x^\ast)\right] + \tfrac{1-\sigma^2}{4}M \textstyle\sum_{j=1}^{k}A_j\xi_j^6 &\le \tfrac{1}{2}\|x^\ast - x_0\|^2 \\ A_k &\ge \tfrac{1}{2M\gamma}\left(\textstyle\sum_{j=1}^{k} \tfrac{1}{\xi_j}\right)^2. \end{align*}$$
The rest follows similarly as done in A-HPE.
- [1] An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM Journal on Optimization. 23(2), 1092–1125 (2013). http://epubs.siam.org/doi/10.1137/110833786
- [2] Lectures on Convex Optimization. Springer Optimization and Its Applications, vol. 137. Springer International Publishing, Cham (2018). http://link.springer.com/10.1007/978-3-319-91578-4
- [3] An optimal high-order tensor method for convex optimization. Mathematics of Operations Research. 46(4), 1390–1412 (2021). https://pubsonline.informs.org/doi/10.1287/moor.2020.1103
- [4] Regularized Newton method with global $\mathcal{O}(1/k^2)$ convergence. SIAM Journal on Optimization. 33(3), 1440–1462 (2023). https://epubs.siam.org/doi/10.1137/22M1488752