Introduction
Inexact gradient information affects both the progress of an optimization method and the accuracy of its output. Relative errors scale with the magnitude of the true gradient and therefore diminish as the gradient vanishes, whereas an absolute error component may persist near a minimizer. When the smoothness constant or the error parameters are unknown, the algorithm must also determine suitable step sizes from the information available during the iteration. The purpose of this paper is to study these issues within a common deterministic error model and to develop adaptive gradient methods with explicit convergence guarantees.
We consider the unconstrained minimization problem:
min x ∈ R n f ( x ) , (1) \min_{x \in\mathbb{R}^n} f(x), \tag*{(1)} x ∈ R n min f ( x ) , (1)
where f : R n → R f : \mathbb{R}^n \to\mathbb{R} f : R n → R is differentiable. We assume that the minimum is attained and write f ∗ = min x ∈ R n f ( x ) f^* = \min_{x \in\mathbb{R}^n} f(x) f ∗ = min x ∈ R n f ( x ) . Given an initial point x 0 x^0 x 0 , let x ∗ x^* x ∗ be a minimizer closest to x 0 x^0 x 0 in the Euclidean norm, and set R = ∥ x 0 − x ∗ ∥ 2 R = \lVert x^0 - x^* \rVert_2 R = ∥ x 0 − x ∗ ∥ 2 . Throughout, ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ and ∥ ⋅ ∥ 2 \lVert\cdot\rVert_2 ∥ ⋅ ∥ 2 denote the Euclidean inner product and norm, respectively. For a differentiable function, convexity is characterized by
( ∀ x , y ∈ R n ) f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ ≤ f ( y ) . (2) (\forall x,y \in\mathbb{R}^{n})\qquad f(x) + \langle\nabla f(x),y-x\rangle\leq f(y). \tag*{(2)} ( ∀ x , y ∈ R n ) f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ ≤ f ( y ) . (2)
We express L L L -smoothness, with L > 0 L > 0 L > 0 , through the quadratic upper model
( ∀ x , y ∈ R n ) f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + L 2 ∥ x − y ∥ 2 2 . (3) (\forall x,y \in\mathbb{R}^{n})\qquad f(y) \leq f(x) + \langle\nabla f(x),y-x\rangle+ \frac{L}{2}\lVert x-y\rVert_{2}^{2}. \tag*{(3)} ( ∀ x , y ∈ R n ) f ( y ) ≤ f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + 2 L ∥ x − y ∥ 2 2 . (3)
For the analysis of the intermediate method, we additionally assume that f f f is μ \mu μ -strongly convex, with μ > 0 \mu> 0 μ > 0 :
( ∀ x , y ∈ R n ) f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + μ 2 ∥ x − y ∥ 2 2 ≤ f ( y ) . (4) (\forall x,y \in\mathbb{R}^{n})\qquad f(x) + \langle\nabla f(x),y-x\rangle+ \frac{\mu}{2}\lVert x-y\rVert_{2}^{2} \leq f(y). \tag*{(4)} ( ∀ x , y ∈ R n ) f ( x ) + ⟨ ∇ f ( x ) , y − x ⟩ + 2 μ ∥ x − y ∥ 2 2 ≤ f ( y ) . (4)
In this case the minimizer is unique. Some of our gradient descent results instead use the Polyak–Łojasiewicz (PL) condition with parameter μ > 0 \mu> 0 μ > 0 :
( ∀ x ∈ R n ) 1 2 μ ∥ ∇ f ( x ) ∥ 2 2 ≥ f ( x ) − f ∗ . (5) (\forall x \in\mathbb{R}^{n})\qquad\frac{1}{2\mu}\lVert\nabla f(x)\rVert_{2}^{2} \geq f(x)-f^{*}. \tag*{(5)} ( ∀ x ∈ R n ) 2 μ 1 ∥ ∇ f ( x ) ∥ 2 2 ≥ f ( x ) − f ∗ . (5)
We consider gradient-based first-order methods; standard treatments of this class are given in [2 , 3 , 6 , 7 , 8 , 9 ] . When gradients are queried at the iterates, the usual linear-span restriction takes the form
x N + 1 ∈ x 0 + span { ∇ ~ f ( x 0 ) , ∇ ~ f ( x 1 ) , … , ∇ ~ f ( x N ) } , (6) x^{N+1} \in x^{0} + \operatorname{span}\left\{ \widetilde{\nabla} f(x^{0}),\widetilde{\nabla} f(x^{1}),\ldots,\widetilde{\nabla} f(x^{N}) \right\}, \tag*{(6)} x N + 1 ∈ x 0 + span { ∇ f ( x 0 ) , ∇ f ( x 1 ) , … , ∇ f ( x N ) } , (6)
where ∇ ~ f ( x k ) \widetilde{\nabla} f(x^{k}) ∇ f ( x k ) is an approximation for ∇ f ( x k ) \nabla f(x^{k}) ∇ f ( x k ) .
The exact gradient is assumed to be unavailable. Instead, an inexact oracle returns ∇ ~ f ( x ) \widetilde{\nabla} f(x) ∇ f ( x ) satisfying the composite error condition
( ∀ x ∈ R n ) ∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 2 ≤ α ∥ ∇ f ( x ) ∥ 2 2 + δ , 0 ≤ α < 1 , 0 ≤ δ . (7) (\forall x \in\mathbb{R}^{n})\qquad\lVert\widetilde{\nabla} f(x)-\nabla f(x)\rVert_{2}^{2} \leq\alpha\lVert\nabla f(x)\rVert_{2}^{2}+\delta,\qquad0 \leq\alpha< 1, 0 \leq\delta. \tag*{(7)} ( ∀ x ∈ R n ) ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 2 ≤ α ∥ ∇ f ( x ) ∥ 2 2 + δ , 0 ≤ α < 1 , 0 ≤ δ . (7)
Both adaptive procedures use exact function values to evaluate their acceptance conditions. Thus, the inexactness considered here concerns the gradient, not the function values. The proposed methods can also be run using exact specifications of the function and the error, in which case the function values themselves need not be used.
Various models of inexact first-order information have been studied in [1 , 4 , 5 , 6 , 9 , 11 ] . Our analysis is formulated directly in terms of the norm bound (7). To make its two components explicit, define ζ ( x ) = ∇ ~ f ( x ) − ∇ f ( x ) \zeta(x)=\widetilde{\nabla} f(x)-\nabla f(x) ζ ( x ) = ∇ f ( x ) − ∇ f ( x ) . By Lemma A.5, condition (7) is equivalent to the existence of a decomposition
ζ ( x ) = ∇ ~ f ( x ) − ∇ f ( x ) = ζ a ( x ) + ζ r ( x ) , ∥ ζ a ( x ) ∥ 2 ≤ δ , ∥ ζ r ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 . (8) \zeta(x)=\widetilde{\nabla} f(x)-\nabla f(x)=\zeta_{a}(x)+\zeta_{r}(x),\qquad\lVert\zeta_{a}(x)\rVert_{2}\leq\delta,\qquad\lVert\zeta_{r}(x)\rVert_{2}\leq\alpha\lVert\nabla f(x)\rVert_{2}. \tag*{(8)} ζ ( x ) = ∇ f ( x ) − ∇ f ( x ) = ζ a ( x ) + ζ r ( x ) , ∥ ζ a ( x ) ∥ 2 ≤ δ , ∥ ζ r ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 . (8)
The purely relative model is obtained by setting δ = 0 \delta=0 δ = 0 :
( ∀ x ∈ R n ) ∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 2 ≤ α ∥ ∇ f ( x ) ∥ 2 2 . (9) (\forall x \in\mathbb{R}^{n})\qquad\lVert\widetilde{\nabla} f(x)-\nabla f(x)\rVert_{2}^{2}\leq\alpha\lVert\nabla f(x)\rVert_{2}^{2}. \tag*{(9)} ( ∀ x ∈ R n ) ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 2 ≤ α ∥ ∇ f ( x ) ∥ 2 2 . (9)
The purely absolute model corresponds to α = 0 \alpha= 0 α = 0 :
( ∀ x ∈ R n ) ∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 ≤ δ . (10) (\forall x \in\mathbb{R}^{n}) \qquad\lVert\widetilde{\nabla} f(x) - \nabla f(x) \rVert_{2} \le\delta. \tag*{(10)} ( ∀ x ∈ R n ) ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 ≤ δ . (10)
Contributions. We develop two adaptive procedures with different information requirements. The first is a gradient descent method that allows adaptation of the smoothness estimate and of both error estimates. Separate switches determine which quantities are updated, while a shared backtracking index controls the active estimations. We obtain convergence for smooth and PL objectives. Regularization technique yields result for convex problems with purely relative gradient error. The second procedure is the Algorithm 2 (CE-AIGM). For strongly convex objectives, it adapts the smoothness estimate while keeping the strong convexity parameter and the error bounds fixed and known. In the fixed-smoothness setting, the accelerated convergence is retained when α = O ( ( μ / L ) 1 / 4 ) \alpha= O((\mu/L)^{1/4}) α = O (( μ / L ) 1/4 ) , larger admissible relative errors lead to intermediate guarantees (see Theorem 3.1 ).
Organization. § 2 presents adaptive gradient descent and its stationarity, PL, and regularization-based guarantees. § 3 introduces CE-AIGM and explains its accelerated and intermediate regimes. Auxiliary inequalities, regularization lemmas, and the proofs for the two algorithms are collected in Appendix § 5 -D.
Adaptive gradient descent
We first consider gradient descent when the smoothness constant and the parameters of the composite error model are not necessarily known. Algorithm 1 uses a computable backtracking condition to select a step together with the error estimates needed to accept it. It also provides options F α F_{\alpha} F α , F δ F_{\delta} F δ , and F L F_{L} F L that enable or disable the corresponding adaptivity. The active parameters nevertheless share a single search index, rather than being estimated through three independent searches. An estimate whose adaptation is disabled must already be a guaranteed upper bound on the corresponding parameter:
F α = false ⇒ α 0 ≥ α , F δ = false ⇒ δ 0 ≥ δ , F L = false ⇒ L 0 ≥ L . F_{\alpha} = \text{false} \Rightarrow\alpha_{0} \ge\alpha,\quad F_{\delta} = \text{false} \Rightarrow\delta_{0} \ge\delta,\quad F_{L} = \text{false} \Rightarrow L_{0} \ge L. F α = false ⇒ α 0 ≥ α , F δ = false ⇒ δ 0 ≥ δ , F L = false ⇒ L 0 ≥ L .
For the maxima defining the search bounds below, we use the conventions 0 / 0 = 1 0/0 = 1 0/0 = 1 and log 2 0 = − ∞ \log_{2} 0 = -\infty log 2 0 = − ∞ .
Algorithm 1 Adaptive Gradient Descent (x 0 x^0 x 0 , N N N , α 0 \alpha_0 α 0 , F α F_\alpha F α , δ 0 \delta_0 δ 0 , F δ F_\delta F δ , L 0 L_0 L 0 , F L F_L F L )
1: Input: Starting point x 0 x^0 x 0 , number of steps N ≥ 1 N \ge1 N ≥ 1 . 2: Input: 0 ≤ α 0 < 1 0 \le\alpha_0 < 1 0 ≤ α 0 < 1 - initial estimation of relative error, 3: Input: F α ∈ { false , true } F_\alpha\in\{\text{false},\text{true}\} F α ∈ { false , true } - whether to adapt the relative error. 4: Input: δ 0 ≥ 0 \delta_0 \ge0 δ 0 ≥ 0 - initial estimation of absolute error, 5: Input: F δ ∈ { false , true } F_\delta\in\{\text{false},\text{true}\} F δ ∈ { false , true } - whether to adapt the absolute error. 6: Input: L 0 > 0 L_0 > 0 L 0 > 0 - initial estimation of smoothness, 7: Input: F L ∈ { false , true } F_L \in\{\text{false},\text{true}\} F L ∈ { false , true } - whether to adapt the smoothness. 8: Set J 0 = 0 J_0 = 0 J 0 = 0 . 9: for k = 0 … N − 1 k = 0 \ldots N - 1 k = 0 … N − 1 do 10: α ^ k , δ ^ k , L ^ k , θ k , x k + 1 = Step ( J k , x k , α 0 , F α , δ 0 , F δ , L 0 , F L ) \hat{\alpha}_k,\hat{\delta}_k,\hat{L}_k,\theta_k,x^{k+1} = \operatorname{Step}(J_k,x^k,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L) α ^ k , δ ^ k , L ^ k , θ k , x k + 1 = Step ( J k , x k , α 0 , F α , δ 0 , F δ , L 0 , F L ) . 11: while f ( x k + 1 ) > f ( x k ) − θ k ∥ ∇ f ( x k ) ∥ 2 2 + 1 4 ( 1 + α ^ k ) 2 L ^ k δ ^ k 2 f(x^{k+1}) > f(x^k) - \theta_k\lVert\nabla f(x^k)\rVert_2^2 + \frac{1}{4(1+\hat{\alpha}_k)^2\hat{L}_k}\hat{\delta}_k^2 f ( x k + 1 ) > f ( x k ) − θ k ∥ ∇ f ( x k ) ∥ 2 2 + 4 ( 1 + α ^ k ) 2 L ^ k 1 δ ^ k 2 do 12: J k = J k + 1 J_k = J_k + 1 J k = J k + 1 . 13: α ^ k , δ ^ k , L ^ k , θ k , x k + 1 = Step ( J k , x k , α 0 , F α , δ 0 , F δ , L 0 , F L ) \hat{\alpha}_k,\hat{\delta}_k,\hat{L}_k,\theta_k,x^{k+1} = \operatorname{Step}(J_k,x^k,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L) α ^ k , δ ^ k , L ^ k , θ k , x k + 1 = Step ( J k , x k , α 0 , F α , δ 0 , F δ , L 0 , F L ) . 14: end while 15: J k + 1 = max { 0 , J k − 1 } J_{k+1} = \max\{0,J_k - 1\} J k + 1 = max { 0 , J k − 1 } . 16: end for 17: Output: x N x^N x N . 19: function Step ( t , x , α 0 , F α , δ 0 , F δ , L 0 , F L ) \operatorname{Step}(t,x,\alpha_0,F_\alpha,\delta_0,F_\delta,L_0,F_L) Step ( t , x , α 0 , F α , δ 0 , F δ , L 0 , F L ) 20: α ^ = 1 − 1 − α 0 2 t \hat{\alpha} = 1 - \frac{1-\alpha_0}{2^t} α ^ = 1 − 2 t 1 − α 0 If (F α F_\alpha F α is true) else α 0 \alpha_0 α 0 . 21: δ ^ = 2 t δ 0 \hat{\delta} = 2^t\delta_0 δ ^ = 2 t δ 0 If (F δ F_\delta F δ is true) else δ 0 \delta_0 δ 0 . 22: L ^ = 2 t L 0 \hat{L} = 2^tL_0 L ^ = 2 t L 0 If (F L F_L F L is true) else L 0 L_0 L 0 . 23: h = 1 − α ^ 4 L ^ ( 1 + α ^ ) 2 h = \frac{1-\hat{\alpha}}{4\hat{L}(1+\hat{\alpha})^2} h = 4 L ^ ( 1 + α ^ ) 2 1 − α ^ . 24: θ = 1 32 L ^ ( 1 + α ^ ) 4 \theta= \frac{1}{32\hat{L}(1+\hat{\alpha})^4} θ = 32 L ^ ( 1 + α ^ ) 4 1 . 25: y = x − h ∇ ^ f ( x ) y = x - h\widehat{\nabla}f(x) y = x − h ∇ f ( x ) . 26: return ( α ^ , δ ^ , L ^ , θ , y ) (\hat{\alpha},\hat{\delta},\hat{L},\theta,y) ( α ^ , δ ^ , L ^ , θ , y ) . 27: end function
The first result controls the smallest true-gradient norm among the first N N N iterates. It applies without convexity, although the true gradient norm is used only as an analytical measure and is not required by the algorithm.
Theorem 2.1. Let the function f f f be L L L -smooth (3) , ∇ ^ f \widehat{\nabla}f ∇ f satisfies composite error condition (7) . Then Algorithm 1 provides convergence:
min 0 ≤ k ≤ N − 1 ∥ ∇ f ( x k ) ∥ 2 2 ≤ 1024 M ∗ 3 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 f ( x 0 ) − f ( x ∗ ) N + 512 M ∗ 5 δ 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 \min_{0 \le k \le N-1}\lVert\nabla f(x^k)\rVert_2^2 \le1024\frac{M_*^3L_0}{(1-\alpha_0)^2(1-\alpha)^2}\frac{f(x^0)-f(x^*)}{N}
+512\frac{M_*^5\delta_0^2}{(1-\alpha_0)^2(1-\alpha)^2} 0 ≤ k ≤ N − 1 min ∥ ∇ f ( x k ) ∥ 2 2 ≤ 1024 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 3 L 0 N f ( x 0 ) − f ( x ∗ ) + 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 5 δ 0 2 where
J ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L L 0 ) , log 2 ( δ δ 0 ) } ⌉ , J_*=\left\lceil\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L}{L_0}\right),\log_2\left(\frac{\delta}{\delta_0}\right)\right\}\right\rceil, J ∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L ) , log 2 ( δ 0 δ ) } ⌉ , M ∗ = 2 J ∗ , assuming 0 0 = 1. M_* = 2^{J_*},\quad\text{assuming }\frac{0}{0}=1. M ∗ = 2 J ∗ , assuming 0 0 = 1.
and the total number of inexact gradient ∇ ~ f \widetilde{\nabla} f ∇ f calls is bounded by 2 N + J ∗ − 1 2N + J_* - 1 2 N + J ∗ − 1 .
The factor M ∗ M_* M ∗ quantifies the scale of the initial underestimation of the parameters. Because the active estimates share a search index, underestimating one parameter may also enlarge the others. The stationarity statement concerns a best iterate in gradient norm, not necessarily the returned point x N x^N x N . Under the PL condition, the same one-step inequality yields a bound on the last iterate in objective value.
Theorem 2.2. Let the function f f f be L L L -smooth (3) and satisfies PL condition (5) , ∇ ~ f \widetilde{\nabla} f ∇ f satisfies composite error condition (7) . Then Algorithm 1 ensures the following convergence rate:
f ( x N ) − f ∗ ≤ ( 1 − 1 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ M ∗ − 3 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 256 M ∗ 5 ( 1 − α 0 ) 2 ( 1 − α ) 2 δ 0 2 μ , f(x^N) - f^* \le\left(1 - \frac{1}{512}(1-\alpha_0)^2(1-\alpha)^2 \cdot M_*^{-3}\frac{\mu}{L_0}\right)^N (f(x^0)-f^*)
+ 256\frac{M_*^5}{(1-\alpha_0)^2(1-\alpha)^2}\frac{\delta_0^2}{\mu}, f ( x N ) − f ∗ ≤ ( 1 − 512 1 ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ M ∗ − 3 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + 256 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 5 μ δ 0 2 , where
J ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L L 0 ) , log 2 ( δ δ 0 ) } ⌉ , J_* = \left\lceil\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L}{L_0}\right),\log_2\left(\frac{\delta}{\delta_0}\right)\right\}\right\rceil, J ∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L ) , log 2 ( δ 0 δ ) } ⌉ , M ∗ = 2 J ∗ , assuming 0 0 = 1. M_* = 2^{J_*},\quad\text{assuming }\frac{0}{0}=1. M ∗ = 2 J ∗ , assuming 0 0 = 1. and the total number of inexact gradient ∇ ~ f \widetilde{\nabla} f ∇ f calls is bounded by 2 N + J ∗ − 1 2N + J_* - 1 2 N + J ∗ − 1 .
Theorem 2.3. Let the function f f f be L L L -smooth (3) and satisfies PL condition (5) , ∇ ~ f \widetilde{\nabla} f ∇ f satisfies composite error condition (7) . Then Algorithm 1 with α = α 0 \alpha= \alpha_0 α = α 0 , L 0 = L L_0 = L L 0 = L , δ 0 = δ \delta_0 = \delta δ 0 = δ , F α = F δ = F L = false F_\alpha= F_\delta= F_L = \textbf{false} F α = F δ = F L = false ensures the following convergence rate:
f ( x N ) − f ∗ ≤ ( 1 − 1 512 ( 1 − α ) 4 μ L ) N ( f ( x 0 ) − f ∗ ) + 256 δ 2 ( 1 − α ) 4 μ . f(x^N) - f^* \le\left(1-\frac{1}{512}(1-\alpha)^4\frac{\mu}{L}\right)^N (f(x^0)-f^*) + 256\frac{\delta^2}{(1-\alpha)^4\mu}. f ( x N ) − f ∗ ≤ ( 1 − 512 1 ( 1 − α ) 4 L μ ) N ( f ( x 0 ) − f ∗ ) + 256 ( 1 − α ) 4 μ δ 2 .
For a convex objective that need not satisfy the PL condition, we apply the method to the regularized function f μ ( x ∣ x 0 ) = f ( x ) + μ 2 ∥ x − x 0 ∥ 2 f_\mu(x|x^0) = f(x) + \frac{\mu}{2}\lVert x-x^0\rVert^2 f μ ( x ∣ x 0 ) = f ( x ) + 2 μ ∥ x − x 0 ∥ 2 . Lemma B.3 explains the correctness of using the Algorithm 1 for such function.
Theorem 2.4. Let the function f f f be L L L -smooth (3) and convex (2) , ∇ ~ f \widetilde{\nabla} f ∇ f satisfies relative error condition (9) . Consider an arbitrary 0 < μ , 0 < R 0 0 < \mu, 0 < R_0 0 < μ , 0 < R 0 , then Algorithm 1 ensures the following convergence rate:
f ( x N ) − f ∗ ≤ ( 1 − 1 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 256 M ∗ 5 μ R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 + μ R 2 2 , f(x^N) - f^* \le\left(1-\frac{1}{512}(1-\alpha_0)^2(1-\alpha)^2M_*^{-3}\frac{\mu}{L_0}\right)^N(f(x^0)-f^*)
+ 256\frac{M_*^5\mu R_0^2}{(1-\alpha_0)^2(1-\alpha)^2}+\frac{\mu R^2}{2}, f ( x N ) − f ∗ ≤ ( 1 − 512 1 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + 256 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 5 μ R 0 2 + 2 μ R 2 , where
J ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L + μ L 0 ) , log 2 ( α R R 0 ) } ⌉ , M ∗ = 2 J ∗ . J_* = \left\lceil\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L+\mu}{L_0}\right),\log_2\left(\alpha\frac{R}{R_0}\right)\right\}\right\rceil,\quad M_* = 2^{J_*}. J ∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L + μ ) , log 2 ( α R 0 R ) } ⌉ , M ∗ = 2 J ∗ .
and the total number of inexact gradient ∇ ~ f \widetilde{\nabla} f ∇ f calls is bounded by 2 N + J ∗ − 1 2N + J_* - 1 2 N + J ∗ − 1 . And one can solve problem f ( x N ) − f ∗ ≤ ε f(x^N) - f^* \le\varepsilon f ( x N ) − f ∗ ≤ ε , where ε > 0 \varepsilon> 0 ε > 0 , choosing:
μ = ε R ^ 2 , \mu= \frac{\varepsilon}{\widehat{R}^{2}}, μ = R 2 ε ,
then after:
N = max { 0 , ⌈ 512 M ∗ ∗ 3 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 R ^ 2 ε ln ( 3 ( f ( x 0 ) − f ∗ ) ε ) ⌉ } N = \max\left\{0,\left\lceil\frac{512M_{**}^{3}}{(1-\alpha_0)^2(1-\alpha)^2}\frac{L_0\widehat{R}^{2}}{\varepsilon}\ln\left(\frac{3(f(x^0)-f^*)}{\varepsilon}\right)\right\rceil\right\} N = max { 0 , ⌈ ( 1 − α 0 ) 2 ( 1 − α ) 2 512 M ∗∗ 3 ε L 0 R 2 ln ( ε 3 ( f ( x 0 ) − f ∗ ) ) ⌉ }
iterations method will provide f ( x N ) − f ∗ ≤ ε f(x^N) - f^* \le\varepsilon f ( x N ) − f ∗ ≤ ε , where
R ^ 2 = max { 3 R 2 2 , 768 M ∗ 0 5 R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 } , \widehat{R}^{2} = \max\left\{\frac{3R^2}{2},\frac{768M_{*0}^{5}R_0^2}{(1-\alpha_0)^2(1-\alpha)^2}\right\}, R 2 = max { 2 3 R 2 , ( 1 − α 0 ) 2 ( 1 − α ) 2 768 M ∗ 0 5 R 0 2 } ,
J ∗ ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( 2 L L 0 ) , log 2 ( α R R 0 ) } ⌉ , M ∗ ∗ = 2 J ∗ ∗ . J_{**} = \left\lceil\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{2L}{L_0}\right),\log_2\left(\alpha\frac{R}{R_0}\right)\right\}\right\rceil,\quad M_{**}=2^{J_{**}}. J ∗∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 2 L ) , log 2 ( α R 0 R ) } ⌉ , M ∗∗ = 2 J ∗∗ .
Remark 2.1. It follows from the Theorem 2.1 -Theorem 2.3 that, if δ 0 = 0 \delta_0 = 0 δ 0 = 0 is chosen, the inner loop may fail to terminate when δ > 0 \delta> 0 δ > 0 . Therefore, the choice δ 0 = 0 \delta_0 = 0 δ 0 = 0 should be made only when it is known that there is no absolute error component in (10) .
The proofs in Appendix C establish a one-step inequality for every accepted update and then use telescoping or the PL condition, respectively. The finite backtracking bound follows from the existence of a search level at which all active estimates are conservative.
Adaptive intermediate method
We now turn to strongly convex objectives and seek faster convergence when the relative gradient error is sufficiently small. The Algorithm 2 (CE-AIGM) combines extrapolation with a gradient step and a computable acceptance test. Its convergence bound interpolates between accelerated and non-accelerated condition-number dependence as the relative error parameter increases. Unlike Algorithm 1, CE-AIGM adapts only the smoothness estimation, the parameter of strong-convexity μ \mu μ is also known, whereas L L L need not be.
Algorithm 2 CE-AIGM (Composite Error Adaptive Intermediate Gradient Method).
Input: Starting point x 0 x^0 x 0 , number of steps N ≥ 1 N \ge1 N ≥ 1 .
Input: μ \mu μ - strongly-convexity constant of function f f f .
Input: α \alpha α - relative error of gradient,
Input: δ \delta δ - absolute error of gradient,
Input: L 0 ≥ μ L_0 \ge\mu L 0 ≥ μ - initial estimation of smoothness,
Set J 0 = 0 J_0=0 J 0 = 0 , c 0 = f ( x 0 ) c_0=f(x^0) c 0 = f ( x 0 ) , u 0 = x 0 u^0=x^0 u 0 = x 0 , A 0 = 0 A_0=0 A 0 = 0 .
for k = 0 … N − 1 k=0\ldots N-1 k = 0 … N − 1 do
y k y^k y k , u k + 1 u^{k+1} u k + 1 , x k + 1 x^{k+1} x k + 1 , c k + 1 c_{k+1} c k + 1 , A k + 1 = Step ( J k , u k , x k , c k , A k , μ , α , δ , L 0 ) A_{k+1}=\operatorname{Step}(J_k,u^k,x^k,c_k,A_k,\mu,\alpha,\delta,L_0) A k + 1 = Step ( J k , u k , x k , c k , A k , μ , α , δ , L 0 ) .
while f ( x k + 1 ) > c k + 1 + A k + 1 f(x^{k+1})>c_{k+1}+A_{k+1} f ( x k + 1 ) > c k + 1 + A k + 1 do
J k = J k + 1 J_k=J_k+1 J k = J k + 1 .
y k y^k y k , u k + 1 u^{k+1} u k + 1 , x k + 1 x^{k+1} x k + 1 , c k + 1 c_{k+1} c k + 1 , A k + 1 = Step ( J k , u k , x k , c k , A k , μ , α , δ , L 0 ) A_{k+1}=\operatorname{Step}(J_k,u^k,x^k,c_k,A_k,\mu,\alpha,\delta,L_0) A k + 1 = Step ( J k , u k , x k , c k , A k , μ , α , δ , L 0 ) .
end while
J k + 1 = max { 0 , J k − 1 } J_{k+1}=\max\{0,J_k-1\} J k + 1 = max { 0 , J k − 1 } .
end for
Output: x N x^N x N . 16.
function Step ( t , u , x , c , A , μ , α , δ , L 0 ) \operatorname{Step}(t,u,x,c,A,\mu,\alpha,\delta,L_0) Step ( t , u , x , c , A , μ , α , δ , L 0 )
L ^ = 2 t L 0 \widehat L=2^tL_0 L = 2 t L 0
h = 1 − α ( 1 + α ) 2 1 4 L ^ h=\dfrac{1-\alpha}{(1+\alpha)^2}\dfrac{1}{4\widehat L} h = ( 1 + α ) 2 1 − α 4 L 1
s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q = ( 1 − α ) 4 ( 1 + α ) 4 μ 32 L ^ s=1-2\alpha+3\alpha^2,\quad m=1-2\alpha-\alpha^2,\quad q=\dfrac{(1-\alpha)^4}{(1+\alpha)^4}\dfrac{\mu}{32\widehat L} s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q = ( 1 + α ) 4 ( 1 − α ) 4 32 L μ
ω = ( m − s ) + ( s − m ) 2 + 4 m q 2 m \omega=\dfrac{(m-s)+\sqrt{(s-m)^2+4mq}}{2m} ω = 2 m ( m − s ) + ( s − m ) 2 + 4 m q
y = ω u + x 1 + ω , g ~ = ∇ ~ f ( y ) , x ^ = y − h g ~ , u ^ = ( 1 − ω ) u + ω y − 2 ω μ g ~ y=\dfrac{\omega u+x}{1+\omega},\quad\widetilde g=\widetilde{\nabla}f(y),\quad\widehat x=y-h\widetilde g,\quad\widehat u=(1-\omega)u+\omega y-\dfrac{2\omega}{\mu}\widetilde g y = 1 + ω ω u + x , g = ∇ f ( y ) , x = y − h g , u = ( 1 − ω ) u + ω y − μ 2 ω g
A ^ = ( 1 − ω ) A + ω δ 2 4 ( 1 + α ) 2 L ^ + 4 δ 2 ( 1 − α ) 2 μ \widehat A=(1-\omega)A+\omega\dfrac{\delta^2}{4(1+\alpha)^2\widehat L}+\dfrac{4\delta^2}{(1-\alpha)^2\mu} A = ( 1 − ω ) A + ω 4 ( 1 + α ) 2 L δ 2 + ( 1 − α ) 2 μ 4 δ 2
c ^ = ( 1 − ω ) c + ω ( f ( y ) − s ( 1 − α ) 2 μ ∥ ∇ ~ f ( y ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ ) + ω ( 1 − ω ) μ 4 ∥ y − u − 2 μ ∇ ~ f ( y ) ∥ 2 2 \widehat c=(1-\omega)c+\omega\left(f(y)-\dfrac{s}{(1-\alpha)^2\mu}\lVert\widetilde{\nabla}f(y)\rVert_2^2-\dfrac{2\delta^2}{(1-\alpha)^2\mu}\right)+\dfrac{\omega(1-\omega)\mu}{4}\left\lVert y-u-\dfrac{2}{\mu}\widetilde{\nabla}f(y)\right\rVert_2^2 c = ( 1 − ω ) c + ω ( f ( y ) − ( 1 − α ) 2 μ s ∥ ∇ f ( y ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 ) + 4 ω ( 1 − ω ) μ y − u − μ 2 ∇ f ( y ) 2 2
return ( y , u ^ , x ^ , c ^ , A ^ ) (y,\widehat u,\widehat x,\widehat c,\widehat A) ( y , u , x , c , A ) .
end function
Theorem 3.1. Let f f f be an L L L -smooth and μ \mu μ -strongly convex function, ∇ ~ f \widetilde{\nabla}f ∇ f satisfies composite error condition (7), α ∈ [ 0 ; 1 / 3 ] \alpha\in[0;1/3] α ∈ [ 0 ; 1/3 ] . Then Algorithm 2 with L 0 ≥ μ L_0\ge\mu L 0 ≥ μ generates x N x^N x N , s.t.
f ( x N ) − f ∗ ≤ exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 57 δ 2 μ . f(x^N)-f^*\le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right)\left(f(x^0)-f^*+\frac{\mu}{4}R^2\right)+57\frac{\delta^2}{\mu}. f ( x N ) − f ∗ ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 57 μ δ 2 .
where:
R : = ∥ x 0 − x ∗ ∥ 2 , γ ∗ = min { 1 4 , log μ L ∗ ( 3 α ) } , if μ = L ∗ or α = 0 , then γ ∗ = 1 4 . R := \lVert x^{0} - x^{*} \rVert_{2},\ \gamma^{*} = \min\left\{\frac{1}{4}, \log_{\frac{\mu}{L_{*}}}(3\alpha)\right\},\quad\text{if }\mu= L_{*}\text{ or }\alpha= 0,\ \text{then }\gamma^{*} = \frac{1}{4}. R := ∥ x 0 − x ∗ ∥ 2 , γ ∗ = min { 4 1 , log L ∗ μ ( 3 α ) } , if μ = L ∗ or α = 0 , then γ ∗ = 4 1 .
L ∗ = max 0 ≤ k ≤ N − 1 L ~ k ≤ max { L 0 , 2 L } , L_{*} = \max_{0 \le k \le N-1} \widetilde{L}_{k} \le\max\{L_{0},2L\}, L ∗ = 0 ≤ k ≤ N − 1 max L k ≤ max { L 0 , 2 L } ,
J ∗ = ⌈ max { 0 , log 2 ( L L 0 ) } ⌉ . J_{*} = \left\lceil\max\left\{0,\log_{2}\left(\frac{L}{L_{0}}\right)\right\}\right\rceil. J ∗ = ⌈ max { 0 , log 2 ( L 0 L ) } ⌉ .
The total number of iterations of the inner loop can be estimated as N + J ∗ − 1 N + J_{*} - 1 N + J ∗ − 1 a and the total number of inexact gradient ∇ ~ f \widetilde{\nabla}f ∇ f evaluations over N N N iterations of Algorithm 2 is estimated as 2 N + J ∗ − 1 2N + J_{*} - 1 2 N + J ∗ − 1 .
Theorem 3.2. Let f f f be an L L L -smooth and μ \mu μ -strongly convex function, ∇ ~ f \widetilde{\nabla}f ∇ f satisfies composite error condition (7), α ∈ [ 0 ; 1 / 3 ] \alpha\in[0;1/3] α ∈ [ 0 ; 1/3 ] . Then Algorithm 2 with L 0 = L L_{0}=L L 0 = L generates x N x^{N} x N , s.t.
f ( x N ) − f ∗ ≤ exp ( − 1 250 ( μ L ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 57 δ 2 μ . f(x^{N}) - f^{*} \le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L}\right)^{1-2\gamma^{*}}N\right)\left(f(x^{0}) - f^{*} + \frac{\mu}{4}R^{2}\right) + 57\frac{\delta^{2}}{\mu}. f ( x N ) − f ∗ ≤ exp ( − 250 1 ( L μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 57 μ δ 2 . where:
R : = ∥ x 0 − x ∗ ∥ 2 , γ ∗ = min { 1 4 , log μ L ( 3 α ) } , if μ = L or α = 0 , then γ ∗ = 1 4 . R := \lVert x^{0} - x^{*} \rVert_{2},\ \gamma^{*} = \min\left\{\frac{1}{4}, \log_{\frac{\mu}{L}}(3\alpha)\right\},\quad\text{if }\mu= L\text{ or }\alpha= 0,\ \text{then }\gamma^{*} = \frac{1}{4}. R := ∥ x 0 − x ∗ ∥ 2 , γ ∗ = min { 4 1 , log L μ ( 3 α ) } , if μ = L or α = 0 , then γ ∗ = 4 1 .
The dependence on the relative error can be written without logarithms. Set κ ∗ = L ∗ / μ ≥ 1 \kappa_{*} = L_{*}/\mu\ge1 κ ∗ = L ∗ / μ ≥ 1 . The exponent in Theorem 3.1 satisfies the identity
( μ L ∗ ) 1 − 2 γ ∗ = 1 max { κ ∗ , 9 α 2 κ ∗ } , \left(\frac{\mu}{L_{*}}\right)^{1-2\gamma^{*}} = \frac{1}{\max\left\{\sqrt{\kappa_{*}},9\alpha^{2}\kappa_{*}\right\}}, ( L ∗ μ ) 1 − 2 γ ∗ = max { κ ∗ , 9 α 2 κ ∗ } 1 ,
hence the accelerated condition-number dependence is retained when α ≤ 1 3 κ ∗ − 1 / 4 \alpha\le\frac{1}{3}\kappa_{*}^{-1/4} α ≤ 3 1 κ ∗ − 1/4 . Above this scale, the second term in the maximum determines the stated bound. At α = 1 / 3 \alpha= 1/3 α = 1/3 , it equals κ ∗ \kappa_{*} κ ∗ and gives the non-accelerated condition-number dependence. Between these regimes, the estimate reflects the size of the relative error. For example, in the fixed-smoothness setting, with κ = L / μ \kappa= L/\mu κ = L / μ and α = 1 3 κ − β \alpha= \frac{1}{3}\kappa^{-\beta} α = 3 1 κ − β for 0 ≤ β ≤ 1 / 4 0 \le\beta\le1/4 0 ≤ β ≤ 1/4 , the factor governing the iteration count is κ 1 − 2 β \kappa^{1-2\beta} κ 1 − 2 β . The absolute error enters the objective bound through O ( δ 2 / μ ) O(\delta^{2}/\mu) O ( δ 2 / μ ) , uniformly over the admissible range of α \alpha α , there is no additional amplification of this residual by the condition number, in comparison with the results obtained in [11 ] .
Analogously to Theorem 2.4, a solution to the convex problem using a regularization technique can be proposed.
Theorem 3.3. Let the function f f f be L L L -smooth (3) and convex (2), ∇ ~ f \widetilde{\nabla}f ∇ f satisfies relative error condition (9) with α ∈ [ 0 ; 1 / 3 ] \alpha\in[0;1/3] α ∈ [ 0 ; 1/3 ] and constant R = ∥ x 0 − x ∗ ∥ 2 R = \lVert x^{0} - x^{*}\rVert_{2} R = ∥ x 0 − x ∗ ∥ 2 is known. Consider an arbitrary 0 < μ ≤ L 0 0 < \mu\le L_{0} 0 < μ ≤ L 0 , then Algorithm 2 ensures the following convergence rate:
f ( x N ) − f ∗ ≤ exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 39 μ R 2 2 , (11) f(x^{N}) - f^{*} \le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_{*}}\right)^{1-2\gamma^{*}}N\right)\left(f(x^{0}) - f^{*} + \frac{\mu}{4}R^{2}\right) + \frac{39\mu R^{2}}{2}, \tag*{(11)} f ( x N ) − f ∗ ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 2 39 μ R 2 , (11)
where
L ∗ = max 0 ≤ k ≤ N − 1 L ^ k ≤ max { L 0 , 2 ( L + μ ) } , L_* = \max_{0 \leq k \leq N-1} \widehat{L}_k \leq\max\{L_0, 2(L+\mu)\}, L ∗ = 0 ≤ k ≤ N − 1 max L k ≤ max { L 0 , 2 ( L + μ )} ,
γ ∗ = min { 1 4 , log μ L ∗ ( 3 α ) } , if α = 0 or μ = L ∗ , then γ ∗ = 1 4 . \gamma^* = \min\left\{\frac{1}{4}, \log_{\frac{\mu}{L_*}}(3\alpha)\right\}, \quad\text{if } \alpha=0 \text{ or } \mu=L_*, \text{ then } \gamma^*=\frac{1}{4}. γ ∗ = min { 4 1 , log L ∗ μ ( 3 α ) } , if α = 0 or μ = L ∗ , then γ ∗ = 4 1 .
J ∗ = ⌈ max { 0 , log 2 ( L + μ L 0 ) } ⌉ . J_* = \left\lceil\max\left\{0,\log_2\left(\frac{L+\mu}{L_0}\right)\right\}\right\rceil. J ∗ = ⌈ max { 0 , log 2 ( L 0 L + μ ) } ⌉ .
and the total number of inexact gradient ∇ ~ f \widetilde{\nabla}f ∇ f calls is bounded by 2 N + J ∗ − 1 2N+J_*-1 2 N + J ∗ − 1 . And one can solve problem f ( x N ) − f ∗ ≤ ε f(x^N)-f^*\leq\varepsilon f ( x N ) − f ∗ ≤ ε , where 0 < ε ≤ f ( x 0 ) − f ∗ 0<\varepsilon\leq f(x^0)-f^* 0 < ε ≤ f ( x 0 ) − f ∗ , choosing (with L 0 ≥ μ L_0\geq\mu L 0 ≥ μ ):
μ = ε 39 R 2 ⟹ γ ∗ = min { 1 4 , log ε 39 L ∗ R 2 ( 3 α ) } , if α = 0 , then γ ∗ = 1 4 , \mu=\frac{\varepsilon}{39R^2}\Longrightarrow\gamma^*=\min\left\{\frac{1}{4},\log_{\frac{\varepsilon}{39L_*R^2}}(3\alpha)\right\}, \quad\text{if } \alpha=0,\text{ then }\gamma^*=\frac{1}{4}, μ = 39 R 2 ε ⟹ γ ∗ = min { 4 1 , log 39 L ∗ R 2 ε ( 3 α ) } , if α = 0 , then γ ∗ = 4 1 ,
then after:
N = max { 0 , ⌈ 250 ( 39 L ∗ R 2 ε ) 1 − 2 γ ∗ ln ( 157 ( f ( x 0 ) − f ∗ ) 78 ε ) ⌉ } . N=\max\left\{0,\left\lceil250\left(\frac{39L_*R^2}{\varepsilon}\right)^{1-2\gamma^*}\ln\left(\frac{157(f(x^0)-f^*)}{78\varepsilon}\right)\right\rceil\right\}. N = max { 0 , ⌈ 250 ( ε 39 L ∗ R 2 ) 1 − 2 γ ∗ ln ( 78 ε 157 ( f ( x 0 ) − f ∗ ) ) ⌉ } .
iterations method will provide f ( x N ) − f ∗ ≤ ε f(x^N)-f^*\leq\varepsilon f ( x N ) − f ∗ ≤ ε .
Remark 3.1. Using the LongTails framework [10 ] , one can obtain analogous results and even improve upon them. Specifically, in the strongly convex case, this framework yields the convergence (for other method) stated in Theorem 3.2: for α < 1 \alpha<1 α < 1 and ε ≥ 136 δ 2 ( 1 − α ) 2 μ \varepsilon\geq136\frac{\delta^2}{(1-\alpha)^2\mu} ε ≥ 136 ( 1 − α ) 2 μ δ 2 , it ensures that f ( x N ) − f ∗ ≤ ε f(x^N)-f^*\leq\varepsilon f ( x N ) − f ∗ ≤ ε after
N = ⌈ ( 8 L μ ( 1 − α ) + 32 α 2 L μ ( 1 − α ) ) log ( 1 + 2 L R 2 ε ) ⌉ , N=\left\lceil\left(8\sqrt{\frac{L}{\mu(1-\alpha)}}+\frac{32\alpha^2L}{\mu(1-\alpha)}\right)\log\left(1+\frac{2LR^2}{\varepsilon}\right)\right\rceil, N = ⌈ ( 8 μ ( 1 − α ) L + μ ( 1 − α ) 32 α 2 L ) log ( 1 + ε 2 L R 2 ) ⌉ ,
iterations. In the convex case (μ = 0 \mu=0 μ = 0 ), this framework outperforms Theorem 3.3 by reducing the logarithmic factor through a damped linear-coupling method (without regularization). For relative error (9) (α < 1 \alpha<1 α < 1 ), this method guarantees f ( x N ) − f ∗ ≤ ε f(x^N)-f^*\leq\varepsilon f ( x N ) − f ∗ ≤ ε after
N = ⌈ 7 L R 2 ( 1 − α ) ε + 11 α 2 L R 2 ( 1 − α ) ε ⌉ , N=\left\lceil7\sqrt{\frac{LR^2}{(1-\alpha)\varepsilon}}+\frac{11\alpha^2LR^2}{(1-\alpha)\varepsilon}\right\rceil, N = ⌈ 7 ( 1 − α ) ε L R 2 + ( 1 − α ) ε 11 α 2 L R 2 ⌉ ,
iterations. We invite readers to apply this framework to their own problem formulations and to verify for themselves that their convergence results can be improved.
AI Use Statement
The authors used GPT-6 to check the proofs and to improve the English text (spelling and grammar). All ideas and proofs were conceived without the assistance of artificial intelligence. No AI tools were used to generate mathematical content, ideas, or proofs. For information on the possibility of obtaining results using AI, see Remark 3.1 .
Miscellaneous Used Lemmas
Lemma A.1. If u , v ∈ R n u,v\in\mathbb{R}^{n} u , v ∈ R n , then ∀ λ > 0 \forall\lambda>0 ∀ λ > 0 :
⟨ u , v ⟩ ≤ λ 2 ∥ u ∥ 2 2 + 1 2 λ ∥ v ∥ 2 2 . \langle u,v\rangle\leq\frac{\lambda}{2}\lVert u\rVert_{2}^{2}+\frac{1}{2\lambda}\lVert v\rVert_{2}^{2}. ⟨ u , v ⟩ ≤ 2 λ ∥ u ∥ 2 2 + 2 λ 1 ∥ v ∥ 2 2 .
Lemma A.2. If a , b ≥ 0 a,b\geq0 a , b ≥ 0 , then
( a − b ) 2 ≥ 1 2 a 2 − b 2 . (a-b)^{2}\geq\frac{1}{2}a^{2}-b^{2}. ( a − b ) 2 ≥ 2 1 a 2 − b 2 . Proof. Using Fenchel A.1 inequality with λ = 1 2 \lambda=\frac{1}{2} λ = 2 1 .
Lemma A.3. If ∇ ~ f \widetilde{\nabla}f ∇ f satisfies error condition (7) . Following inequalities take place:
( 1 − α ) ∥ ∇ f ( x ) ∥ 2 − δ ≤ ∥ ∇ ~ f ( x ) ∥ 2 ≤ ( 1 + α ) ∥ ∇ f ( x ) ∥ 2 + δ , (1-\alpha)\lVert\nabla f(x)\rVert_{2}-\delta\leq\lVert\widetilde{\nabla}f(x)\rVert_{2}\leq(1+\alpha)\lVert\nabla f(x)\rVert_{2}+\delta, ( 1 − α ) ∥ ∇ f ( x ) ∥ 2 − δ ≤ ∥ ∇ f ( x ) ∥ 2 ≤ ( 1 + α ) ∥ ∇ f ( x ) ∥ 2 + δ , 1 1 + α ( ∥ ∇ ~ f ( x ) ∥ 2 − δ ) ≤ ∥ ∇ f ( x ) ∥ 2 ≤ 1 1 − α ( ∥ ∇ ~ f ( x ) ∥ 2 + δ ) , \frac{1}{1+\alpha}\left(\lVert\widetilde{\nabla}f(x)\rVert_{2}-\delta\right)\leq\lVert\nabla f(x)\rVert_{2}\leq\frac{1}{1-\alpha}\left(\lVert\widetilde{\nabla}f(x)\rVert_{2}+\delta\right), 1 + α 1 ( ∥ ∇ f ( x ) ∥ 2 − δ ) ≤ ∥ ∇ f ( x ) ∥ 2 ≤ 1 − α 1 ( ∥ ∇ f ( x ) ∥ 2 + δ ) , 1 2 ( 1 − α ) 2 ∥ ∇ f ( x ) ∥ 2 2 − δ 2 ≤ ∥ ∇ ~ f ( x ) ∥ 2 2 ≤ 2 ( 1 + α ) 2 ∥ ∇ f ( x ) ∥ 2 2 + 2 δ 2 , \frac{1}{2}(1-\alpha)^{2}\lVert\nabla f(x)\rVert_{2}^{2}-\delta^{2}\leq\lVert\widetilde{\nabla}f(x)\rVert_{2}^{2}\leq2(1+\alpha)^{2}\lVert\nabla f(x)\rVert_{2}^{2}+2\delta^{2}, 2 1 ( 1 − α ) 2 ∥ ∇ f ( x ) ∥ 2 2 − δ 2 ≤ ∥ ∇ f ( x ) ∥ 2 2 ≤ 2 ( 1 + α ) 2 ∥ ∇ f ( x ) ∥ 2 2 + 2 δ 2 , 1 2 ( 1 + α ) 2 ∥ ∇ ~ f ( x ) ∥ 2 2 − 1 ( 1 + α ) 2 δ 2 ≤ ∥ ∇ f ( x ) ∥ 2 2 ≤ 2 ( 1 − α ) 2 ∥ ∇ ~ f ( x ) ∥ 2 2 + 2 ( 1 − α ) 2 δ 2 . \frac{1}{2(1+\alpha)^{2}}\lVert\widetilde{\nabla}f(x)\rVert_{2}^{2}-\frac{1}{(1+\alpha)^{2}}\delta^{2}\leq\lVert\nabla f(x)\rVert_{2}^{2}\leq\frac{2}{(1-\alpha)^{2}}\lVert\widetilde{\nabla}f(x)\rVert_{2}^{2}+\frac{2}{(1-\alpha)^{2}}\delta^{2}. 2 ( 1 + α ) 2 1 ∥ ∇ f ( x ) ∥ 2 2 − ( 1 + α ) 2 1 δ 2 ≤ ∥ ∇ f ( x ) ∥ 2 2 ≤ ( 1 − α ) 2 2 ∥ ∇ f ( x ) ∥ 2 2 + ( 1 − α ) 2 2 δ 2 . Proof. Follows from definition (7) , Lemma A.1 and Lemma A.2 .
Lemma A.4. If ∇ ~ f \widetilde{\nabla} f ∇ f satisfies error condition (7) , then:
∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 ≤ α 1 − α ∥ ∇ ~ f ( x ) ∥ 2 + δ 1 − α . \lVert\widetilde{\nabla} f(x) - \nabla f(x) \rVert_2 \le\frac{\alpha}{1-\alpha}\lVert\widetilde{\nabla} f(x) \rVert_2 + \frac{\delta}{1-\alpha}. ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 ≤ 1 − α α ∥ ∇ f ( x ) ∥ 2 + 1 − α δ .
Proof.
∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 + δ ≤ Lemma A.3 α 1 − α ( ∥ ∇ ~ f ( x ) ∥ 2 + δ ) + δ ≤ α 1 − α ∥ ∇ ~ f ( x ) ∥ 2 + δ 1 − α . \begin{aligned}
\lVert\widetilde{\nabla} f(x) - \nabla f(x) \rVert_2
&\le\alpha\lVert\nabla f(x) \rVert_2 + \delta\\
&\mathrel{\overset{\text{Lemma A.3}}{\le}} \frac{\alpha}{1-\alpha}\left(\lVert\widetilde{\nabla} f(x) \rVert_2 + \delta\right) + \delta\\
&\le\frac{\alpha}{1-\alpha}\lVert\widetilde{\nabla} f(x) \rVert_2 + \frac{\delta}{1-\alpha}.
\end{aligned} ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 + δ ≤ Lemma A.3 1 − α α ( ∥ ∇ f ( x ) ∥ 2 + δ ) + δ ≤ 1 − α α ∥ ∇ f ( x ) ∥ 2 + 1 − α δ .
Lemma A.5. If ζ ( x ) = ∇ ~ f ( x ) − ∇ f ( x ) \zeta(x) = \widetilde{\nabla} f(x) - \nabla f(x) ζ ( x ) = ∇ f ( x ) − ∇ f ( x ) satisfies error condition (7) , then exist two vector fields ζ a , ζ r \zeta_a,\zeta_r ζ a , ζ r :
ζ ( x ) = ζ a ( x ) + ζ r ( x ) , \zeta(x) = \zeta_a(x) + \zeta_r(x), ζ ( x ) = ζ a ( x ) + ζ r ( x ) , which satisfy:
∥ ζ a ( x ) ∥ ≤ δ , ∥ ζ r ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 . \lVert\zeta_a(x) \rVert\le\delta,\qquad\lVert\zeta_r(x) \rVert_2 \le\alpha\lVert\nabla f(x) \rVert_2. ∥ ζ a ( x )∥ ≤ δ , ∥ ζ r ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 .
Proof. Let us define two sets:
S 1 = { ∇ f ( x ) + v , ∥ v ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 } , S 2 = { ∇ ~ f ( x ) + v , ∥ v ∥ 2 ≤ δ } . \begin{aligned}
S_1 &= \{\nabla f(x) + v,\ \lVert v \rVert_2 \le\alpha\lVert\nabla f(x) \rVert_2\},\\
S_2 &= \{\widetilde{\nabla} f(x) + v,\ \lVert v \rVert_2 \le\delta\}.
\end{aligned} S 1 S 2 = { ∇ f ( x ) + v , ∥ v ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 } , = { ∇ f ( x ) + v , ∥ v ∥ 2 ≤ δ } .
Then from condition ∥ ∇ ~ f ( x ) − ∇ f ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 + δ \lVert\widetilde{\nabla} f(x) - \nabla f(x) \rVert_2 \le\alpha\lVert\nabla f(x) \rVert_2 + \delta ∥ ∇ f ( x ) − ∇ f ( x ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 + δ we can draw a conclusion about S 1 ∩ S 2 ≠ ∅ S_1 \cap S_2 \ne\varnothing S 1 ∩ S 2 = ∅ and the existence of two vectors ζ r , ζ a \zeta_r,\zeta_a ζ r , ζ a , described in theorem condition.
Lemma A.6. If ∇ ~ f \widetilde{\nabla} f ∇ f satisfies composite error (7) , then:
( ∀ x ∈ R n ) ⟨ ∇ f ( x ) , ∇ ~ f ( x ) ⟩ ≥ 1 − α 4 ( 1 + α ) ∥ ∇ ~ f ( x ) ∥ 2 2 − δ 2 1 − α . (\forall x \in\mathbb{R}^{n})\quad\langle\nabla f(x),\widetilde{\nabla} f(x)\rangle\ge\frac{1-\alpha}{4(1+\alpha)}\lVert\widetilde{\nabla} f(x) \rVert_2^2 - \frac{\delta^2}{1-\alpha}. ( ∀ x ∈ R n ) ⟨ ∇ f ( x ) , ∇ f ( x )⟩ ≥ 4 ( 1 + α ) 1 − α ∥ ∇ f ( x ) ∥ 2 2 − 1 − α δ 2 .
Proof.
⟨ ∇ f ( x ) , ∇ f ~ ( x ) ⟩ = Lemma A .5 ⟨ ∇ f ( x ) + ζ a ( x ) + ζ r ( x ) , ∇ f ( x ) ⟩ ≥ Lemma A .1 , ( 8 ) ∥ ∇ f ( x ) ∥ 2 2 − α ∥ ∇ f ( x ) ∥ 2 2 − δ 2 2 λ − λ 2 ∥ ∇ f ( x ) ∥ 2 2 ≥ λ = 1 − α 1 − α 2 ∥ ∇ f ( x ) ∥ 2 2 − δ 2 2 ( 1 − α ) ≥ Lemma A .3 1 − α 2 ( 1 2 ( 1 + α ) 2 ∥ ∇ f ~ ( x ) ∥ 2 2 − δ 2 ( 1 + α ) 2 ) − δ 2 2 ( 1 − α ) = 1 − α 4 ( 1 + α ) 2 ∥ ∇ f ~ ( x ) ∥ 2 2 − 1 − α 2 ( 1 + α ) 2 δ 2 − 1 2 ( 1 − α ) δ 2 ≥ 1 − α 1 + α ≤ 1 1 − α 4 ( 1 + α ) 2 ∥ ∇ f ~ ( x ) ∥ 2 2 − δ 2 1 − α . \begin{aligned}
\langle\nabla f(x), \nabla\widetilde{f}(x) \rangle
&\underset{\text{Lemma } A.5}{=}
\langle\nabla f(x)+\zeta_a(x)+\zeta_r(x),\nabla f(x)\rangle\\
&\underset{\text{Lemma } A.1,(8)}{\geq}
\|\nabla f(x)\|_2^2-\alpha\|\nabla f(x)\|_2^2-\frac{\delta^2}{2\lambda}-\frac{\lambda}{2}\|\nabla f(x)\|_2^2 \\
&\underset{\lambda=1-\alpha}{\geq}
\frac{1-\alpha}{2}\|\nabla f(x)\|_2^2-\frac{\delta^2}{2(1-\alpha)} \\
&\underset{\text{Lemma } A.3}{\geq}
\frac{1-\alpha}{2}\left(\frac{1}{2(1+\alpha)^2}\|\nabla\widetilde{f}(x)\|_2^2-\frac{\delta^2}{(1+\alpha)^2}\right)-\frac{\delta^2}{2(1-\alpha)} \\
&=
\frac{1-\alpha}{4(1+\alpha)^2}\|\nabla\widetilde{f}(x)\|_2^2-\frac{1-\alpha}{2(1+\alpha)^2}\delta^2-\frac{1}{2(1-\alpha)}\delta^2 \\
&\underset{\frac{1-\alpha}{1+\alpha}\leq1}{\geq}
\frac{1-\alpha}{4(1+\alpha)^2}\|\nabla\widetilde{f}(x)\|_2^2-\frac{\delta^2}{1-\alpha}.
\end{aligned} ⟨ ∇ f ( x ) , ∇ f ( x )⟩ Lemma A .5 = ⟨ ∇ f ( x ) + ζ a ( x ) + ζ r ( x ) , ∇ f ( x )⟩ Lemma A .1 , ( 8 ) ≥ ∥∇ f ( x ) ∥ 2 2 − α ∥∇ f ( x ) ∥ 2 2 − 2 λ δ 2 − 2 λ ∥∇ f ( x ) ∥ 2 2 λ = 1 − α ≥ 2 1 − α ∥∇ f ( x ) ∥ 2 2 − 2 ( 1 − α ) δ 2 Lemma A .3 ≥ 2 1 − α ( 2 ( 1 + α ) 2 1 ∥∇ f ( x ) ∥ 2 2 − ( 1 + α ) 2 δ 2 ) − 2 ( 1 − α ) δ 2 = 4 ( 1 + α ) 2 1 − α ∥∇ f ( x ) ∥ 2 2 − 2 ( 1 + α ) 2 1 − α δ 2 − 2 ( 1 − α ) 1 δ 2 1 + α 1 − α ≤ 1 ≥ 4 ( 1 + α ) 2 1 − α ∥∇ f ( x ) ∥ 2 2 − 1 − α δ 2 .
Lemma A.7. Let f f f satisfies strong convexity (4), then:
∥ x − x ∗ ∥ 2 2 ≤ 1 μ ∥ ∇ f ( x ) ∥ 2 2 . \|x-x^*\|_2^2\leq\frac{1}{\mu}\|\nabla f(x)\|_2^2. ∥ x − x ∗ ∥ 2 2 ≤ μ 1 ∥∇ f ( x ) ∥ 2 2 .
Proof. From strong convexity and gradient dominance condition (which follows from the strong convexity):
μ 2 ∥ x − x ∗ ∥ 2 2 ≤ f ( x ) − f ∗ ≤ 1 2 μ ∥ ∇ f ( x ) ∥ 2 2 , ∥ x − x ∗ ∥ 2 ≤ 1 μ ∥ ∇ f ( x ) ∥ 2 . \frac{\mu}{2}\|x-x^*\|_2^2\leq f(x)-f^*\leq\frac{1}{2\mu}\|\nabla f(x)\|_2^2,\qquad\|x-x^*\|_2\leq\frac{1}{\mu}\|\nabla f(x)\|_2. 2 μ ∥ x − x ∗ ∥ 2 2 ≤ f ( x ) − f ∗ ≤ 2 μ 1 ∥∇ f ( x ) ∥ 2 2 , ∥ x − x ∗ ∥ 2 ≤ μ 1 ∥∇ f ( x ) ∥ 2 .
Lemma A.8. Let f f f be L L L -smooth (3), ∇ ~ f \widetilde{\nabla} f ∇ f satisfies composite error condition (7). If variables x , y x,y x , y are related by the following relation x = y − h ∇ ~ f ( y ) x=y-h\widetilde{\nabla}f(y) x = y − h ∇ f ( y ) , where:
h = 1 − α ( 1 + α ) 2 1 4 L , (12) h=\frac{1-\alpha}{(1+\alpha)^2}\frac{1}{4L}, \tag*{(12)} h = ( 1 + α ) 2 1 − α 4 L 1 , (12) then:
f ( x ) ≤ f ( y ) − ( 1 − α ) 2 ( 1 + α ) 4 1 32 L ∥ ∇ ~ f ( y ) ∥ 2 2 + δ 2 4 ( 1 + α ) 2 L . f(x)\leq f(y)-\frac{(1-\alpha)^2}{(1+\alpha)^4}\frac{1}{32L}\|\widetilde{\nabla}f(y)\|_2^2+\frac{\delta^2}{4(1+\alpha)^2L}. f ( x ) ≤ f ( y ) − ( 1 + α ) 4 ( 1 − α ) 2 32 L 1 ∥ ∇ f ( y ) ∥ 2 2 + 4 ( 1 + α ) 2 L δ 2 . Proof. Using smoothness of function f f f we get:
f ( x ) ≤ f ( y ) + ⟨ ∇ f ( y ) , x − y ⟩ + L 2 ∥ x − y ∥ 2 2 . f(x)\leq f(y)+\langle\nabla f(y),x-y\rangle+\frac{L}{2}\|x-y\|_2^2. f ( x ) ≤ f ( y ) + ⟨ ∇ f ( y ) , x − y ⟩ + 2 L ∥ x − y ∥ 2 2 .
Let us estimate dot product:
⟨ ∇ f ( y ) , x − y ⟩ = − h ⟨ ∇ f ( y ) , ∇ ~ f ( y ) ⟩ ≤ Lemma A.6 − h ( 1 − α 4 ( 1 + α ) 2 ∥ ∇ ~ f ( y ) ∥ 2 2 − δ 2 1 − α ) . \langle\nabla f(y),x-y\rangle= -h\langle\nabla f(y),\widetilde{\nabla} f(y)\rangle\underset{\text{Lemma A.6}}{\leq} -h\left(\frac{1-\alpha}{4(1+\alpha)^2}\lVert\widetilde{\nabla} f(y)\rVert_2^2-\frac{\delta^2}{1-\alpha}\right). ⟨ ∇ f ( y ) , x − y ⟩ = − h ⟨ ∇ f ( y ) , ∇ f ( y )⟩ Lemma A.6 ≤ − h ( 4 ( 1 + α ) 2 1 − α ∥ ∇ f ( y ) ∥ 2 2 − 1 − α δ 2 ) .
Then:
f ( x ) ≤ f ( y ) − h ( 1 − α 4 ( 1 + α ) 2 ∥ ∇ ~ f ( y ) ∥ 2 2 − δ 2 1 − α ) + L h 2 2 ∥ ∇ ~ f ( y ) ∥ 2 2 = f ( y ) + h ∥ ∇ ~ f ( y ) ∥ 2 2 ( L h 2 − 1 − α 4 ( 1 + α ) 2 ) + h δ 2 1 − α = h d e f i n i t i o n f ( y ) − 1 − α ( 1 + α ) 2 1 4 L 1 − α 8 ( 1 + α ) 2 ∥ ∇ ~ f ( y ) ∥ 2 2 + δ 2 4 ( 1 + α ) 2 L (13) \begin{aligned}
f(x) &\leq f(y)-h\left(\frac{1-\alpha}{4(1+\alpha)^2}\lVert\widetilde{\nabla} f(y)\rVert_2^2-\frac{\delta^2}{1-\alpha}\right)+\frac{Lh^2}{2}\lVert\widetilde{\nabla} f(y)\rVert_2^2\\
&=f(y)+h\lVert\widetilde{\nabla} f(y)\rVert_2^2\left(\frac{Lh}{2}-\frac{1-\alpha}{4(1+\alpha)^2}\right)+h\frac{\delta^2}{1-\alpha}\\
&\underset{h\ \mathrm{definition}}{=}f(y)-\frac{1-\alpha}{(1+\alpha)^2}\frac{1}{4L}\frac{1-\alpha}{8(1+\alpha)^2}\lVert\widetilde{\nabla} f(y)\rVert_2^2+\frac{\delta^2}{4(1+\alpha)^2L} \tag*{(13)}
\end{aligned} f ( x ) ≤ f ( y ) − h ( 4 ( 1 + α ) 2 1 − α ∥ ∇ f ( y ) ∥ 2 2 − 1 − α δ 2 ) + 2 L h 2 ∥ ∇ f ( y ) ∥ 2 2 = f ( y ) + h ∥ ∇ f ( y ) ∥ 2 2 ( 2 L h − 4 ( 1 + α ) 2 1 − α ) + h 1 − α δ 2 h definition = f ( y ) − ( 1 + α ) 2 1 − α 4 L 1 8 ( 1 + α ) 2 1 − α ∥ ∇ f ( y ) ∥ 2 2 + 4 ( 1 + α ) 2 L δ 2 (13)
= f ( y ) − ( 1 − α ) 2 ( 1 + α ) 4 1 32 L ∥ ∇ ~ f ( y ) ∥ 2 2 + δ 2 4 ( 1 + α ) 2 L (14) =f(y)-\frac{(1-\alpha)^2}{(1+\alpha)^4}\frac{1}{32L}\lVert\widetilde{\nabla} f(y)\rVert_2^2+\frac{\delta^2}{4(1+\alpha)^2L} \tag*{(14)} = f ( y ) − ( 1 + α ) 4 ( 1 − α ) 2 32 L 1 ∥ ∇ f ( y ) ∥ 2 2 + 4 ( 1 + α ) 2 L δ 2 (14)
Regularization
Let us consider convex (2) function f f f .
f μ ( x ∣ x 0 ) = f ( x ) + μ 2 ∥ x − x 0 ∥ 2 2 , μ > 0 , x μ ∗ - unique solution for problem: f μ ( ⋅ ∣ x 0 ) → min x ∈ R n , f μ ∗ = f μ ( x μ ∗ ∣ x 0 ) , R μ = ∥ x μ ∗ − x 0 ∥ 2 , L μ = L + μ , ∇ ~ f μ ( x ) = ∇ ~ f ( x ) + μ ( x − x 0 ) . (15) \begin{aligned}
f_\mu(x\mid x^0)&=f(x)+\frac{\mu}{2}\lVert x-x^0\rVert_2^2,\quad\mu>0,\\
x_\mu^*&\text{- unique solution for problem: }f_\mu(\cdot\mid x^0)\to\min_{x\in\mathbb{R}^n},\\
f_\mu^*&=f_\mu(x_\mu^*\mid x^0),\quad R_\mu=\lVert x_\mu^*-x^0\rVert_2,\\
L_\mu&=L+\mu,\quad\widetilde{\nabla} f_\mu(x)=\widetilde{\nabla} f(x)+\mu(x-x^0). \tag*{(15)}
\end{aligned} f μ ( x ∣ x 0 ) x μ ∗ f μ ∗ L μ = f ( x ) + 2 μ ∥ x − x 0 ∥ 2 2 , μ > 0 , - unique solution for problem: f μ ( ⋅ ∣ x 0 ) → x ∈ R n min , = f μ ( x μ ∗ ∣ x 0 ) , R μ = ∥ x μ ∗ − x 0 ∥ 2 , = L + μ , ∇ f μ ( x ) = ∇ f ( x ) + μ ( x − x 0 ) . (15)
Lemma B.1. Let f μ f_\mu f μ be a regularization function for f f f . Then R μ ≤ R R_\mu\leq R R μ ≤ R .
Proof. We have
f μ ∗ + μ 2 R μ 2 ≤ f ( x μ ∗ ) + μ 2 R μ 2 = f μ ∗ ≤ f μ ( x μ ∗ ∣ x 0 ) = f ( x μ ∗ ) + μ 2 R 2 . f_\mu^*+\frac{\mu}{2}R_\mu^2\leq f(x_\mu^*)+\frac{\mu}{2}R_\mu^2=f_\mu^*\leq f_\mu(x_\mu^*\mid x^0)=f(x_\mu^*)+\frac{\mu}{2}R^2. f μ ∗ + 2 μ R μ 2 ≤ f ( x μ ∗ ) + 2 μ R μ 2 = f μ ∗ ≤ f μ ( x μ ∗ ∣ x 0 ) = f ( x μ ∗ ) + 2 μ R 2 . So, R μ 2 ≤ R 2 R_\mu^2\leq R^2 R μ 2 ≤ R 2 .
Lemma B.2. Let f μ f_\mu f μ be a regularization function for f f f . Then ∀ x ∈ R n \forall x\in\mathbb{R}^n ∀ x ∈ R n :
f ( x ) − f ∗ ≤ f μ ( x ∣ x 0 ) − f μ ∗ + μ 2 R 2 . f(x)-f^*\leq f_\mu(x\mid x^0)-f_\mu^*+\frac{\mu}{2}R^2. f ( x ) − f ∗ ≤ f μ ( x ∣ x 0 ) − f μ ∗ + 2 μ R 2 . Proof. We have
f ( x ) − f ∗ ≤ f ( x ) + μ 2 ∥ x − x 0 ∥ 2 2 − f ∗ = f μ ( x ∣ x 0 ) − f ∗ = f μ ( x ∣ x 0 ) − f μ ( x μ ∗ ∣ x 0 ) + μ 2 R 2 ≤ f μ ( x ∣ x 0 ) − f μ ∗ + μ 2 R 2 . \begin{aligned}
f(x)-f^*&\leq f(x)+\frac{\mu}{2}\lVert x-x^0\rVert_2^2-f^*=f_\mu(x\mid x^0)-f^*\\
&=f_\mu(x\mid x^0)-f_\mu(x_\mu^*\mid x^0)+\frac{\mu}{2}R^2\leq f_\mu(x\mid x^0)-f_\mu^*+\frac{\mu}{2}R^2.
\end{aligned} f ( x ) − f ∗ ≤ f ( x ) + 2 μ ∥ x − x 0 ∥ 2 2 − f ∗ = f μ ( x ∣ x 0 ) − f ∗ = f μ ( x ∣ x 0 ) − f μ ( x μ ∗ ∣ x 0 ) + 2 μ R 2 ≤ f μ ( x ∣ x 0 ) − f μ ∗ + 2 μ R 2 .
Lemma B.3. Let f f f be a L L L -smooth (3) , convex (2) function, and ∇ ~ f \widetilde{\nabla} f ∇ f satisfies relative error condition (9) . Then the gradient estimation of regularized function f μ f_\mu f μ satisfies (7) , that is
∥ ∇ ~ f μ ( x ) − ∇ f μ ( x ) ∥ 2 ≤ α ∥ ∇ f μ ( x ) ∥ 2 + α μ R . \lVert\widetilde{\nabla} f_\mu(x)-\nabla f_\mu(x)\rVert_2 \leq\alpha\lVert\nabla f_\mu(x)\rVert_2+\alpha\mu R. ∥ ∇ f μ ( x ) − ∇ f μ ( x ) ∥ 2 ≤ α ∥ ∇ f μ ( x ) ∥ 2 + α μ R . Proof. Since f μ f_\mu f μ is strongly convex:
⟨ ∇ f μ ( x ) , x − x μ ∗ ⟩ ≥ μ ∥ x − x μ ∗ ∥ 2 2 . \langle\nabla f_\mu(x),x-x_\mu^*\rangle\geq\mu\lVert x-x_\mu^*\rVert_2^2. ⟨ ∇ f μ ( x ) , x − x μ ∗ ⟩ ≥ μ ∥ x − x μ ∗ ∥ 2 2 . Then:
∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) ∥ 2 2 = ∥ ∇ f μ ( x ) ∥ 2 2 − 2 μ ⟨ ∇ f μ ( x ) , x − x μ ∗ ⟩ + μ 2 ∥ x − x μ ∗ ∥ 2 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 2 − μ 2 ∥ x − x μ ∗ ∥ 2 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 2 . \begin{aligned}
\lVert\nabla f_\mu(x)-\mu(x-x_\mu^*)\rVert_2^2
&=\lVert\nabla f_\mu(x)\rVert_2^2-2\mu\langle\nabla f_\mu(x),x-x_\mu^*\rangle+\mu^2\lVert x-x_\mu^*\rVert_2^2\\
&\leq\lVert\nabla f_\mu(x)\rVert_2^2-\mu^2\lVert x-x_\mu^*\rVert_2^2\leq\lVert\nabla f_\mu(x)\rVert_2^2.
\end{aligned} ∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) ∥ 2 2 = ∥ ∇ f μ ( x ) ∥ 2 2 − 2 μ ⟨ ∇ f μ ( x ) , x − x μ ∗ ⟩ + μ 2 ∥ x − x μ ∗ ∥ 2 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 2 − μ 2 ∥ x − x μ ∗ ∥ 2 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 2 . That is ∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) ∥ 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 \lVert\nabla f_\mu(x)-\mu(x-x_\mu^*)\rVert_2\leq\lVert\nabla f_\mu(x)\rVert_2 ∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) ∥ 2 ≤ ∥ ∇ f μ ( x ) ∥ 2 . Thus we can provide error bound:
∥ ∇ ~ f μ ( x ) − ∇ f μ ( x ) ∥ 2 = ∥ ∇ ~ f ( x ) + μ ( x − x 0 ) − ∇ f ( x ) − μ ( x − x 0 ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 = α ∥ ∇ f ( x ) + μ ( x − x 0 ) − μ ( x − x 0 ) ∥ 2 = α ∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) + μ ( x 0 − x μ ∗ ) ∥ 2 ≤ α ∥ ∇ f μ ( x ) ∥ 2 + α μ R μ ≤ Lemma B.1 α ∥ ∇ f μ ( x ) ∥ 2 + α μ R . \begin{aligned}
\lVert\widetilde{\nabla} f_\mu(x)-\nabla f_\mu(x)\rVert_2
&=\lVert\widetilde{\nabla} f(x)+\mu(x-x^0)-\nabla f(x)-\mu(x-x^0)\rVert_2\\
&\leq\alpha\lVert\nabla f(x)\rVert_2=\alpha\lVert\nabla f(x)+\mu(x-x^0)-\mu(x-x^0)\rVert_2\\
&=\alpha\lVert\nabla f_\mu(x)-\mu(x-x_\mu^*)+\mu(x_0-x_\mu^*)\rVert_2\\
&\leq\alpha\lVert\nabla f_\mu(x)\rVert_2+\alpha\mu R_\mu
\underset{\text{Lemma B.1}}{\leq}\alpha\lVert\nabla f_\mu(x)\rVert_2+\alpha\mu R.
\end{aligned} ∥ ∇ f μ ( x ) − ∇ f μ ( x ) ∥ 2 = ∥ ∇ f ( x ) + μ ( x − x 0 ) − ∇ f ( x ) − μ ( x − x 0 ) ∥ 2 ≤ α ∥ ∇ f ( x ) ∥ 2 = α ∥ ∇ f ( x ) + μ ( x − x 0 ) − μ ( x − x 0 ) ∥ 2 = α ∥ ∇ f μ ( x ) − μ ( x − x μ ∗ ) + μ ( x 0 − x μ ∗ ) ∥ 2 ≤ α ∥ ∇ f μ ( x ) ∥ 2 + α μ R μ Lemma B.1 ≤ α ∥ ∇ f μ ( x ) ∥ 2 + α μ R .
Adaptivity missing proofs
Lemma C.1. Let f f f is L L L -smooth (3) , ∇ ~ f \widetilde{\nabla} f ∇ f satisfies composite error condition (7) . If 1 > α ^ ≥ α 1>\widehat{\alpha}\geq\alpha 1 > α ≥ α , L ^ ≥ L \widehat{L}\geq L L ≥ L , δ ^ ≥ δ \widehat{\delta}\geq\delta δ ≥ δ and x = y − h ∇ ~ f ( y ) x=y-h\widetilde{\nabla}f(y) x = y − h ∇ f ( y ) , where:
h = 1 − α ^ ( 1 + α ^ ) 2 1 4 L ^ , h=\frac{1-\widehat{\alpha}}{(1+\widehat{\alpha})^2}\frac{1}{4\widehat{L}}, h = ( 1 + α ) 2 1 − α 4 L 1 , then:
f ( x ) ≤ f ( y ) − ( 1 − α ^ ) 2 ( 1 + α ^ ) 4 1 32 L ^ ∥ ∇ ~ f ( y ) ∥ 2 2 + δ ^ 2 4 ( 1 + α ^ ) 2 L ^ . f(x)\leq f(y)-\frac{(1-\widehat{\alpha})^2}{(1+\widehat{\alpha})^4}\frac{1}{32\widehat{L}}\lVert\widetilde{\nabla}f(y)\rVert_2^2+\frac{\widehat{\delta}^2}{4(1+\widehat{\alpha})^2\widehat{L}}. f ( x ) ≤ f ( y ) − ( 1 + α ) 4 ( 1 − α ) 2 32 L 1 ∥ ∇ f ( y ) ∥ 2 2 + 4 ( 1 + α ) 2 L δ 2 . Proof. Observe that if a function f f f satisfies the smoothness condition with parameter L L L , then it also satisfies this condition with any L ^ ≥ L \widehat{L}\geq L L ≥ L , similarly, it satisfies the corresponding conditions for α ^ ≥ α \widehat{\alpha}\geq\alpha α ≥ α and δ ^ ≥ δ \widehat{\delta}\geq\delta δ ≥ δ . Consequently, Lemma A.8 can be applied.
Lemma C.2. Let f f f be L L L -smooth (3) , and let ∇ ~ f \widetilde{\nabla} f ∇ f satisfy the composite error condition (7) . Then, for Algorithm 1 and for all k = 0 , … , N − 1 k=0,\ldots,N-1 k = 0 , … , N − 1 ,
f ( x k + 1 ) ≤ f ( x k ) − 2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 δ 0 2 L 0 . f(x^{k+1}) \leq f(x^k) - 2^{-3J_*-10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2 + 2^{2J_*-1}\frac{\delta_0^2}{L_0}. f ( x k + 1 ) ≤ f ( x k ) − 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 L 0 δ 0 2 . where (assuming 0 0 = 1 \frac{0}{0}=1 0 0 = 1 )
max 0 ≤ k ≤ N − 1 J k ≤ J ∗ = [ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L L 0 ) , log 2 ( δ δ 0 ) } ] , \max_{0\leq k\leq N-1} J_k \leq J_* = \left[\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L}{L_0}\right),\log_2\left(\frac{\delta}{\delta_0}\right)\right\}\right], 0 ≤ k ≤ N − 1 max J k ≤ J ∗ = [ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L ) , log 2 ( δ 0 δ ) } ] , The total number of inexact gradient ∇ ~ f \widetilde{\nabla} f ∇ f evaluations over N N N iterations of Algorithm 1 is estimated as 2 N + J ∗ − 1 2N+J_*-1 2 N + J ∗ − 1 .
Proof. At each iteration of the outer loop of Algorithm 1, a ”while” loop is started and terminates when
f ( x k + 1 ) ≤ f ( x k ) − ( 1 − α ^ k ) 2 ( 1 + α ^ k ) 2 1 32 L ^ k ∥ ∇ ~ f ( x k ) ∥ 2 2 + δ ^ k 2 4 L ^ k ( 1 + α ^ k ) 2 . (16) f(x^{k+1}) \leq f(x^k)-\frac{(1-\widehat{\alpha}_k)^2}{(1+\widehat{\alpha}_k)^2}\frac{1}{32\widehat{L}_k}\lVert\widetilde{\nabla} f(x^k)\rVert_2^2+\frac{\widehat{\delta}_k^2}{4\widehat{L}_k(1+\widehat{\alpha}_k)^2}. \tag*{(16)} f ( x k + 1 ) ≤ f ( x k ) − ( 1 + α k ) 2 ( 1 − α k ) 2 32 L k 1 ∥ ∇ f ( x k ) ∥ 2 2 + 4 L k ( 1 + α k ) 2 δ k 2 . (16) From the definitions α 0 ≤ α ^ k ≤ 1 − 1 − α 0 2 J k \alpha_0\leq\widehat{\alpha}_k\leq1-\frac{1-\alpha_0}{2^{J_k}} α 0 ≤ α k ≤ 1 − 2 J k 1 − α 0 , δ 0 ≤ δ ^ k ≤ 2 J k δ 0 \delta_0\leq\widehat{\delta}_k\leq2^{J_k}\delta_0 δ 0 ≤ δ k ≤ 2 J k δ 0 , and L 0 ≤ L ^ k ≤ 2 J k L 0 L_0\leq\widehat{L}_k\leq2^{J_k}L_0 L 0 ≤ L k ≤ 2 J k L 0 , and from Lemma C.1, it follows that the ”while” loop is guaranteed to terminate once α ^ k ≥ α \widehat{\alpha}_k\geq\alpha α k ≥ α , δ ^ k ≥ δ \widehat{\delta}_k\geq\delta δ k ≥ δ , and L ^ k ≥ L \widehat{L}_k\geq L L k ≥ L , which is equivalent to J k ≥ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L L 0 ) , log 2 ( δ δ 0 ) } J_k\geq\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L}{L_0}\right),\log_2\left(\frac{\delta}{\delta_0}\right)\right\} J k ≥ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L ) , log 2 ( δ 0 δ ) } . Hence J k ≤ J ∗ = [ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L L 0 ) , log 2 ( δ δ 0 ) } ] J_k\leq J_*=\left[\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L}{L_0}\right),\log_2\left(\frac{\delta}{\delta_0}\right)\right\}\right] J k ≤ J ∗ = [ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L ) , log 2 ( δ 0 δ ) } ] . Then, substituting the estimations (and using 1 ≤ 1 + α ^ k ≤ 2 1\leq1+\widehat{\alpha}_k\leq2 1 ≤ 1 + α k ≤ 2 ) of the adaptive parameters into (C1), we obtain
f ( x k + 1 ) ≤ f ( x k ) − 2 − 3 J ∗ − 9 ( 1 − α 0 ) 2 L 0 ∥ ∇ ~ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 2 δ 0 2 L 0 ≤ Lemma A.3 f ( x k ) − 2 − 3 J ∗ − 9 ( 1 − α 0 ) 2 L 0 ( 1 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 − δ 2 ) + 2 2 J ∗ − 2 δ 0 2 L 0 ≤ f ( x k ) − 2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 + 2 − 3 J ∗ − 9 ( 1 − α 0 ) 2 L 0 δ 2 + 2 2 J ∗ − 2 δ 0 2 L 0 ≤ δ ≤ 2 J ∗ δ 0 , 0 ≤ α 0 f ( x k ) − 2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 δ 0 2 L 0 . \begin{aligned}
f(x^{k+1}) &\leq f(x^k)-2^{-3J_*-9}\frac{(1-\alpha_0)^2}{L_0}\lVert\widetilde{\nabla} f(x^k)\rVert_2^2+2^{2J_*-2}\frac{\delta_0^2}{L_0}\\
&\overset{\text{Lemma A.3}}{\leq} f(x^k)-2^{-3J_*-9}\frac{(1-\alpha_0)^2}{L_0}\left(\frac{1}{2}(1-\alpha)^2\lVert\nabla f(x^k)\rVert_2^2-\delta^2\right)+2^{2J_*-2}\frac{\delta_0^2}{L_0}\\
&\leq f(x^k)-2^{-3J_*-10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2+2^{-3J_*-9}\frac{(1-\alpha_0)^2}{L_0}\delta^2+2^{2J_*-2}\frac{\delta_0^2}{L_0}\\
&\underset{\delta\leq2^{J_*}\delta_0,\ 0\leq\alpha_0}{\leq} f(x^k)-2^{-3J_*-10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2+2^{2J_*-1}\frac{\delta_0^2}{L_0}.
\end{aligned} f ( x k + 1 ) ≤ f ( x k ) − 2 − 3 J ∗ − 9 L 0 ( 1 − α 0 ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 2 L 0 δ 0 2 ≤ Lemma A.3 f ( x k ) − 2 − 3 J ∗ − 9 L 0 ( 1 − α 0 ) 2 ( 2 1 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 − δ 2 ) + 2 2 J ∗ − 2 L 0 δ 0 2 ≤ f ( x k ) − 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 − 3 J ∗ − 9 L 0 ( 1 − α 0 ) 2 δ 2 + 2 2 J ∗ − 2 L 0 δ 0 2 δ ≤ 2 J ∗ δ 0 , 0 ≤ α 0 ≤ f ( x k ) − 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 L 0 δ 0 2 . Now we estimate the total number of iterations, taking into account the ”while” loop steps. On the k k k -th iteration of the outer loop, the inner loop takes at most J k + 1 − J k + 1 J_{k+1}-J_k+1 J k + 1 − J k + 1 steps, hence the total number is
J 0 + ∑ k = 0 N − 2 ( J k + 1 − J k + 1 ) ≤ N − 1 + J N − 1 ≤ N − 1 + J ∗ . J_0+\sum_{k=0}^{N-2}(J_{k+1}-J_k+1)\leq N-1+J_{N-1}\leq N-1+J_*. J 0 + k = 0 ∑ N − 2 ( J k + 1 − J k + 1 ) ≤ N − 1 + J N − 1 ≤ N − 1 + J ∗ .
Then the total number of inexact gradient calls estimated as 2 N + J ∗ − 1 2N + J_* - 1 2 N + J ∗ − 1 .
Proof of the Theorem 2.1 . Using Lemma C.2 one can obtain inequality for k = 0 … N − 1 k = 0 \ldots N - 1 k = 0 … N − 1 :
2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 ≤ f ( x k ) − f ( x k + 1 ) + 2 2 J ∗ − 1 δ 0 2 L 0 2^{-3J_* - 10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2 \le f(x^k)-f(x^{k+1})+2^{2J_* - 1}\frac{\delta_0^2}{L_0} 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 ≤ f ( x k ) − f ( x k + 1 ) + 2 2 J ∗ − 1 L 0 δ 0 2
Summing up inequalities above for k = 0 k = 0 k = 0 to k = N − 1 k = N - 1 k = N − 1 :
N min 0 ≤ k ≤ N − 1 ∥ ∇ f ( x k ) ∥ 2 2 ≤ ∑ k = 0 N − 1 ∥ ∇ f ( x k ) ∥ 2 2 ≤ 2 3 J ∗ + 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ( f ( x 0 ) − f ( x N ) + N 2 2 J ∗ − 1 δ 0 2 L 0 ) . \begin{aligned}
N\min_{0\leq k\leq N-1}\lVert\nabla f(x^k)\rVert_2^2 \le\sum_{k=0}^{N-1}\lVert\nabla f(x^k)\rVert_2^2 \\
&\le\frac{2^{3J_*+10}L_0}{(1-\alpha_0)^2(1-\alpha)^2}\left(f(x^0)-f(x^N)+N2^{2J_*-1}\frac{\delta_0^2}{L_0}\right).
\end{aligned} N 0 ≤ k ≤ N − 1 min ∥ ∇ f ( x k ) ∥ 2 2 ≤ k = 0 ∑ N − 1 ∥ ∇ f ( x k ) ∥ 2 2 ≤ ( 1 − α 0 ) 2 ( 1 − α ) 2 2 3 J ∗ + 10 L 0 ( f ( x 0 ) − f ( x N ) + N 2 2 J ∗ − 1 L 0 δ 0 2 ) .
That is:
min 0 ≤ k ≤ N − 1 ∥ ∇ f ( x k ) ∥ 2 2 ≤ 2 3 J ∗ + 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 f ( x 0 ) − f ( x ∗ ) N \min_{0\leq k\leq N-1}\lVert\nabla f(x^k)\rVert_2^2 \le2^{3J_*+10}\frac{L_0}{(1-\alpha_0)^2(1-\alpha)^2}\frac{f(x^0)-f(x^*)}{N} 0 ≤ k ≤ N − 1 min ∥ ∇ f ( x k ) ∥ 2 2 ≤ 2 3 J ∗ + 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 N f ( x 0 ) − f ( x ∗ )
+ 2 5 J ∗ + 9 δ 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 = 1024 M ∗ 3 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 f ( x 0 ) − f ( x ∗ ) N \begin{aligned}
\quad+ 2^{5J_*+9}\frac{\delta_0^2}{(1-\alpha_0)^2(1-\alpha)^2} \\
&= 1024\frac{M_*^3L_0}{(1-\alpha_0)^2(1-\alpha)^2}\frac{f(x^0)-f(x^*)}{N}
\end{aligned} + 2 5 J ∗ + 9 ( 1 − α 0 ) 2 ( 1 − α ) 2 δ 0 2 = 1024 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 3 L 0 N f ( x 0 ) − f ( x ∗ )
+ 512 M ∗ 5 δ 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 . \quad+ 512\frac{M_*^5\delta_0^2}{(1-\alpha_0)^2(1-\alpha)^2}. + 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 5 δ 0 2 .
Total amount of inexact gradient calculations estimated as 2 N + J ∗ − 1 2N + J_* - 1 2 N + J ∗ − 1 by Lemma C.2 .
Proof of the Theorem 2.2 . Using Lemma C.2 one can obtain inequality for k = 0 … N − 1 k = 0 \ldots N - 1 k = 0 … N − 1 :
f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 δ 0 2 L 0 f(x^{k+1})-f^* \le f(x^k)-f^* - 2^{-3J_*-10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2 + 2^{2J_*-1}\frac{\delta_0^2}{L_0} f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 L 0 δ 0 2
Then, using PL condition (5):
f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 10 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 δ 0 2 L 0 ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 9 ( 1 − α 0 ) 2 ( 1 − α ) 2 μ L 0 ( f ( x k ) − f ∗ ) + 2 2 J ∗ − 1 δ 0 2 L 0 = ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 ) ( f ( x k ) − f ∗ ) + 2 2 J ∗ − 1 δ 0 2 L 0 . \begin{aligned}
f(x^{k+1})-f^* \le f(x^k)-f^* - 2^{-3J_*-10}\frac{(1-\alpha_0)^2(1-\alpha)^2}{L_0}\lVert\nabla f(x^k)\rVert_2^2 + 2^{2J_*-1}\frac{\delta_0^2}{L_0} \\
&\le f(x^k)-f^* - 2^{-3J_*-9}\frac{(1-\alpha_0)^2(1-\alpha)^2\mu}{L_0}(f(x^k)-f^*) + 2^{2J_*-1}\frac{\delta_0^2}{L_0} \\
&= \left(1-(1-\alpha_0)^2(1-\alpha)^2\cdot2^{-3J_*-9}\frac{\mu}{L_0}\right)(f(x^k)-f^*) + 2^{2J_*-1}\frac{\delta_0^2}{L_0}.
\end{aligned} f ( x k + 1 ) − f ∗ ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 10 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 ∥ ∇ f ( x k ) ∥ 2 2 + 2 2 J ∗ − 1 L 0 δ 0 2 ≤ f ( x k ) − f ∗ − 2 − 3 J ∗ − 9 L 0 ( 1 − α 0 ) 2 ( 1 − α ) 2 μ ( f ( x k ) − f ∗ ) + 2 2 J ∗ − 1 L 0 δ 0 2 = ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ ) ( f ( x k ) − f ∗ ) + 2 2 J ∗ − 1 L 0 δ 0 2 .
Iterating inequality above, denoting q = 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 q = 1-(1-\alpha_0)^2(1-\alpha)^2\cdot2^{-3J_*-9}\frac{\mu}{L_0} q = 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ , since L 0 2 J ∗ ≥ L ≥ μ L_0 2^{J_*} \ge L \ge\mu L 0 2 J ∗ ≥ L ≥ μ , then:
f ( x N ) − f ∗ ≤ q N ( f ( x 0 ) − f ∗ ) + ∑ k = 0 N − 1 q 2 k 2 J ∗ − 1 δ 0 2 L 0 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) − 2 ( 1 − α ) − 2 ⋅ 2 3 J ∗ + 9 L 0 μ 2 2 J ∗ − 1 δ 0 2 L 0 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 2 5 J ∗ + 8 ( 1 − α 0 ) 2 ( 1 − α ) 2 δ 0 2 μ = ( 1 − 1 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ M ∗ − 3 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 256 M ∗ 5 ( 1 − α 0 ) 2 ( 1 − α ) 2 δ 0 2 μ . \begin{aligned}
f(x^N)-f^* &\le q^N(f(x^0)-f^*)+\sum_{k=0}^{N-1}q^{2k}2^{J_*-1}\frac{\delta_0^2}{L_0}\\
&\le\left(1-(1-\alpha_0)^2(1-\alpha)^2\cdot2^{-3J_*-9}\frac{\mu}{L_0}\right)^N(f(x^0)-f^*)\\
&\quad+(1-\alpha_0)^{-2}(1-\alpha)^{-2}\cdot2^{3J_*+9}\frac{L_0}{\mu}2^{2J_*-1}\frac{\delta_0^2}{L_0}\\
&\le\left(1-(1-\alpha_0)^2(1-\alpha)^2\cdot2^{-3J_*-9}\frac{\mu}{L_0}\right)^N(f(x^0)-f^*)\\
&\quad+\frac{2^{5J_*+8}}{(1-\alpha_0)^2(1-\alpha)^2}\frac{\delta_0^2}{\mu}\\
&=\left(1-\frac{1}{512}(1-\alpha_0)^2(1-\alpha)^2\cdot M_*^{-3}\frac{\mu}{L_0}\right)^N(f(x^0)-f^*)\\
&\quad+256\frac{M_*^5}{(1-\alpha_0)^2(1-\alpha)^2}\frac{\delta_0^2}{\mu}.
\end{aligned} f ( x N ) − f ∗ ≤ q N ( f ( x 0 ) − f ∗ ) + k = 0 ∑ N − 1 q 2 k 2 J ∗ − 1 L 0 δ 0 2 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) − 2 ( 1 − α ) − 2 ⋅ 2 3 J ∗ + 9 μ L 0 2 2 J ∗ − 1 L 0 δ 0 2 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) 2 ( 1 − α ) 2 2 5 J ∗ + 8 μ δ 0 2 = ( 1 − 512 1 ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ M ∗ − 3 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + 256 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ 5 μ δ 0 2 .
The total number of inexact gradient evaluations is estimated as 2 N + J ∗ − 1 2N+J_*-1 2 N + J ∗ − 1 by Lemma C.2.
Proof of the Theorem 2.3. Result follows directly from Theorem 2.2, since J ∗ = 0 J_*=0 J ∗ = 0 and M ∗ = 1 M_*=1 M ∗ = 1 .
Proof of the Theorem 2.4. Let us consider f μ = f ( x ) + μ 2 ∥ x − x 0 ∥ 2 f_\mu=f(x)+\frac{\mu}{2}\lVert x-x^0\rVert^2 f μ = f ( x ) + 2 μ ∥ x − x 0 ∥ 2 . It us known, that f μ f_\mu f μ is μ \mu μ strongly convex (4) and L + μ L+\mu L + μ smooth (3). Corresponding gradient estimation ∇ ~ f μ = ∇ ~ f + μ ( x − x 0 ) \widetilde{\nabla}f_\mu=\widetilde{\nabla}f+\mu(x-x^0) ∇ f μ = ∇ f + μ ( x − x 0 ) satisfies composite error condition with relative error parameter α \alpha α and absolute error α μ R \alpha\mu R α μ R (by Lemma B.3). Let us use δ 0 = μ R 0 \delta_0=\mu R_0 δ 0 = μ R 0 as absolute error initial estimation. Using Theorem 2.2 convergence for f μ f_\mu f μ one can obtain:
f μ ( x N ∣ x 0 ) − f μ ∗ ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 2 5 J ∗ + 8 μ R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 , \begin{aligned}
f_\mu(x^N\mid x^0)-f_\mu^* &\le\left(1-(1-\alpha_0)^2(1-\alpha)^2\cdot2^{-3J_*-9}\frac{\mu}{L_0}\right)^N(f(x^0)-f^*)\\
&\quad+\frac{2^{5J_*+8}\mu R_0^2}{(1-\alpha_0)^2(1-\alpha)^2},
\end{aligned} f μ ( x N ∣ x 0 ) − f μ ∗ ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) 2 ( 1 − α ) 2 2 5 J ∗ + 8 μ R 0 2 ,
where:
J ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( L + μ L 0 ) , log 2 ( α R R 0 ) } ⌉ , M ∗ = 2 J ∗ . J_*=\left\lceil\max\left\{0,\log_2\left(\frac{1-\alpha_0}{1-\alpha}\right),\log_2\left(\frac{L+\mu}{L_0}\right),\log_2\left(\alpha\frac{R}{R_0}\right)\right\}\right\rceil,\quad M_*=2^{J_*}. J ∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 L + μ ) , log 2 ( α R 0 R ) } ⌉ , M ∗ = 2 J ∗ .
Then (since f μ ∗ = f ( x μ ∗ ) + μ 2 ∥ x μ ∗ − x 0 ∥ 2 2 ≥ f ∗ f_{\mu}^{*}=f(x_{\mu}^{*})+\frac{\mu}{2}\lVert x_{\mu}^{*}-x^{0}\rVert_{2}^{2}\ge f^{*} f μ ∗ = f ( x μ ∗ ) + 2 μ ∥ x μ ∗ − x 0 ∥ 2 2 ≥ f ∗ ):
f ( x N ) − f ∗ ≤ L e m m a B .2 f μ ( x N ∣ x 0 ) − f μ ∗ + μ 2 R 2 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 2 5 J ∗ + 8 μ R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 + μ R 2 2 = ( 1 − 1 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 ⋅ μ L 0 ) N ( f ( x 0 ) − f ∗ ) + 256 M ∗ 5 μ R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 + μ R 2 2 ≤ exp ( − 1 512 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 ⋅ μ L 0 N ) ( f ( x 0 ) − f ∗ ) + 256 M ∗ 5 μ R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 + μ R 2 2 . \begin{aligned}
f(x^{N})-f^{*}
&\mathrel{\overset{\mathrm{Lemma\ B.2}}{\le}} f_{\mu}(x^{N}\mid x^{0})-f_{\mu}^{*}+\frac{\mu}{2}R^{2}\\
&\le\left(1-(1-\alpha_{0})^{2}(1-\alpha)^{2}\cdot2^{-3J_{*}-9}\frac{\mu}{L_{0}}\right)^{N}\left(f(x^{0})-f^{*}\right)\\
&\quad+\frac{2^{5J_{*}+8}\mu R_{0}^{2}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}+\frac{\mu R^{2}}{2}\\
&= \left(1-\frac{1}{512}(1-\alpha_{0})^{2}(1-\alpha)^{2}M_{*}^{-3}\cdot\frac{\mu}{L_{0}}\right)^{N}\left(f(x^{0})-f^{*}\right)\\
&\quad+\frac{256M_{*}^{5}\mu R_{0}^{2}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}+\frac{\mu R^{2}}{2}\\
&\le\exp\left(-\frac{1}{512}(1-\alpha_{0})^{2}(1-\alpha)^{2}M_{*}^{-3}\cdot\frac{\mu}{L_{0}}N\right)\left(f(x^{0})-f^{*}\right)\\
&\quad+\frac{256M_{*}^{5}\mu R_{0}^{2}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}+\frac{\mu R^{2}}{2}.
\end{aligned} f ( x N ) − f ∗ ≤ Lemma B.2 f μ ( x N ∣ x 0 ) − f μ ∗ + 2 μ R 2 ≤ ( 1 − ( 1 − α 0 ) 2 ( 1 − α ) 2 ⋅ 2 − 3 J ∗ − 9 L 0 μ ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) 2 ( 1 − α ) 2 2 5 J ∗ + 8 μ R 0 2 + 2 μ R 2 = ( 1 − 512 1 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 ⋅ L 0 μ ) N ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) 2 ( 1 − α ) 2 256 M ∗ 5 μ R 0 2 + 2 μ R 2 ≤ exp ( − 512 1 ( 1 − α 0 ) 2 ( 1 − α ) 2 M ∗ − 3 ⋅ L 0 μ N ) ( f ( x 0 ) − f ∗ ) + ( 1 − α 0 ) 2 ( 1 − α ) 2 256 M ∗ 5 μ R 0 2 + 2 μ R 2 .
Thus, to solve problem f ( x N ) − f ∗ ≤ ε f(x^{N})-f^{*}\le\varepsilon f ( x N ) − f ∗ ≤ ε , where 0 < ε ≤ f ( x 0 ) − f ∗ 0<\varepsilon\le f(x^{0})-f^{*} 0 < ε ≤ f ( x 0 ) − f ∗ one can choose:
μ = ε ⋅ min { 2 3 R 2 , ( 1 − α 0 ) 2 ( 1 − α ) 2 768 M ∗ 5 R 0 2 } . \mu=\varepsilon\cdot\min\left\{\frac{2}{3R^{2}},\frac{(1-\alpha_{0})^{2}(1-\alpha)^{2}}{768M_{*}^{5}R_{0}^{2}}\right\}. μ = ε ⋅ min { 3 R 2 2 , 768 M ∗ 5 R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 } .
Such chose of μ \mu μ guarantee:
μ ≤ 2 ε 3 R 2 ≤ L R 2 3 R 2 ≤ L , \mu\le\frac{2\varepsilon}{3R^{2}}\le\frac{LR^{2}}{3R^{2}}\le L, μ ≤ 3 R 2 2 ε ≤ 3 R 2 L R 2 ≤ L ,
where:
J ∗ ∗ = ⌈ max { 0 , log 2 ( 1 − α 0 1 − α ) , log 2 ( 2 L L 0 ) , log 2 ( α R R 0 ) } ⌉ ≥ J ∗ , M ∗ ∗ = 2 J ∗ ∗ . J_{**}=\left\lceil\max\left\{0,\log_{2}\left(\frac{1-\alpha_{0}}{1-\alpha}\right),\log_{2}\left(\frac{2L}{L_{0}}\right),\log_{2}\left(\alpha\frac{R}{R_{0}}\right)\right\}\right\rceil\ge J_{*},\quad M_{**}=2^{J_{**}}. J ∗∗ = ⌈ max { 0 , log 2 ( 1 − α 1 − α 0 ) , log 2 ( L 0 2 L ) , log 2 ( α R 0 R ) } ⌉ ≥ J ∗ , M ∗∗ = 2 J ∗∗ .
then after:
N = max { 0 , ⌈ 512 M ∗ ∗ 3 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 μ ln ( 3 ( f ( x 0 ) − f ∗ ) ε ) ⌉ } = max { 0 , ⌈ 512 M ∗ ∗ 3 ( 1 − α 0 ) 2 ( 1 − α ) 2 L 0 R ^ 2 ε ln ( 3 ( f ( x 0 ) − f ∗ ) ε ) ⌉ } \begin{aligned}
N
&=\max\left\{0,\left\lceil\frac{512M_{**}^{3}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}\frac{L_{0}}{\mu}\ln\left(\frac{3(f(x^{0})-f^{*})}{\varepsilon}\right)\right\rceil\right\}\\
&=\max\left\{0,\left\lceil\frac{512M_{**}^{3}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}\frac{L_{0}\widehat{R}^{2}}{\varepsilon}\ln\left(\frac{3(f(x^{0})-f^{*})}{\varepsilon}\right)\right\rceil\right\}
\end{aligned} N = max { 0 , ⌈ ( 1 − α 0 ) 2 ( 1 − α ) 2 512 M ∗∗ 3 μ L 0 ln ( ε 3 ( f ( x 0 ) − f ∗ ) ) ⌉ } = max { 0 , ⌈ ( 1 − α 0 ) 2 ( 1 − α ) 2 512 M ∗∗ 3 ε L 0 R 2 ln ( ε 3 ( f ( x 0 ) − f ∗ ) ) ⌉ }
iterations method will provide f ( x N ) − f ∗ ≤ ε f(x^{N})-f^{*}\le\varepsilon f ( x N ) − f ∗ ≤ ε , where
R ^ 2 = max { 3 R 2 2 , 768 M ∗ 5 R 0 2 ( 1 − α 0 ) 2 ( 1 − α ) 2 } . \widehat{R}^{2}=\max\left\{\frac{3R^{2}}{2},\frac{768M_{*}^{5}R_{0}^{2}}{(1-\alpha_{0})^{2}(1-\alpha)^{2}}\right\}. R 2 = max { 2 3 R 2 , ( 1 − α 0 ) 2 ( 1 − α ) 2 768 M ∗ 5 R 0 2 } .
Following [8 p. 83] , let us introduce a parameterized set of functions Ψ \Psi Ψ , its element defined for c ∈ R c \in\mathbb{R} c ∈ R , κ ∈ R + + \kappa\in\mathbb{R}_{++} κ ∈ R ++ , and u ∈ R n u \in\mathbb{R}^{n} u ∈ R n , as follows
ψ ( x ∣ c , κ , u ) = c + κ 2 ∥ x − u ∥ 2 2 , ∀ x ∈ R n . (17) \psi(x|c,\kappa,u) = c + \frac{\kappa}{2}\lVert x-u\rVert_{2}^{2}, \qquad\forall x \in\mathbb{R}^{n}. \tag*{(17)} ψ ( x ∣ c , κ , u ) = c + 2 κ ∥ x − u ∥ 2 2 , ∀ x ∈ R n . (17)
According to [8 ] , we can mention to the following useful property of the class Ψ \Psi Ψ .
Lemma D.1. Let ψ 1 , ψ 2 ∈ Ψ \psi_{1},\psi_{2} \in\Psi ψ 1 , ψ 2 ∈ Ψ . Then ∀ c 1 , c 2 ∈ R , ∀ η 1 , η 2 , κ 1 , κ 2 ∈ R + + \forall c_{1},c_{2} \in\mathbb{R}, \forall\eta_{1},\eta_{2},\kappa_{1},\kappa_{2} \in\mathbb{R}_{++} ∀ c 1 , c 2 ∈ R , ∀ η 1 , η 2 , κ 1 , κ 2 ∈ R ++ , and ∀ u , v ∈ R n \forall u,v \in\mathbb{R}^{n} ∀ u , v ∈ R n , we have
η 1 ψ 1 ( x ∣ c 1 , κ 1 , u ) + η 2 ψ 2 ( x ∣ c 2 , κ 2 , v ) = ψ 3 ( x ∣ c 3 , κ 3 , w ) , \eta_{1}\psi_{1}(x|c_{1},\kappa_{1},u)+\eta_{2}\psi_{2}(x|c_{2},\kappa_{2},v)=\psi_{3}(x|c_{3},\kappa_{3},w), η 1 ψ 1 ( x ∣ c 1 , κ 1 , u ) + η 2 ψ 2 ( x ∣ c 2 , κ 2 , v ) = ψ 3 ( x ∣ c 3 , κ 3 , w ) , where
c 3 = η 1 c 1 + η 2 c 2 + η 1 η 2 κ 1 κ 2 2 ( η 1 κ 1 + η 2 κ 2 ) ∥ u − v ∥ 2 2 , c_{3}=\eta_{1}c_{1}+\eta_{2}c_{2}+\frac{\eta_{1}\eta_{2}\kappa_{1}\kappa_{2}}{2(\eta_{1}\kappa_{1}+\eta_{2}\kappa_{2})}\lVert u-v\rVert_{2}^{2}, c 3 = η 1 c 1 + η 2 c 2 + 2 ( η 1 κ 1 + η 2 κ 2 ) η 1 η 2 κ 1 κ 2 ∥ u − v ∥ 2 2 , κ 3 = η 1 κ 1 + η 2 κ 2 , w = η 1 κ 1 u + η 2 κ 2 v η 1 κ 1 + η 2 κ 2 . \kappa_{3}=\eta_{1}\kappa_{1}+\eta_{2}\kappa_{2}, \qquad w=\frac{\eta_{1}\kappa_{1}u+\eta_{2}\kappa_{2}v}{\eta_{1}\kappa_{1}+\eta_{2}\kappa_{2}}. κ 3 = η 1 κ 1 + η 2 κ 2 , w = η 1 κ 1 + η 2 κ 2 η 1 κ 1 u + η 2 κ 2 v .
Also from [8 ] we mention the following simple lemma.
Lemma D.2. Let 0 < λ < 1 0<\lambda<1 0 < λ < 1 , A ≥ 0 A\geq0 A ≥ 0 , ψ 0 , ψ ∈ Ψ \psi_{0},\psi\in\Psi ψ 0 , ψ ∈ Ψ , z ∈ R n z\in\mathbb{R}^{n} z ∈ R n such that
f ( z ) ≤ min x ∈ R n ψ ( x ) + A , ψ ( x ) ≤ λ ψ 0 ( x ) + ( 1 − λ ) f ( x ) , ∀ x ∈ R n . f(z)\leq\min_{x\in\mathbb{R}^{n}}\psi(x)+A,\qquad\psi(x)\leq\lambda\psi_{0}(x)+(1-\lambda)f(x),\qquad\forall x\in\mathbb{R}^{n}. f ( z ) ≤ x ∈ R n min ψ ( x ) + A , ψ ( x ) ≤ λ ψ 0 ( x ) + ( 1 − λ ) f ( x ) , ∀ x ∈ R n . Then
f ( z ) − f ∗ ≤ λ ( ψ 0 ( x ∗ ) − f ∗ ) + A . f(z)-f^{*}\leq\lambda\bigl(\psi_{0}(x^{*})-f^{*}\bigr)+A. f ( z ) − f ∗ ≤ λ ( ψ 0 ( x ∗ ) − f ∗ ) + A . Proof.
f ( z ) − f ∗ ≤ min x ∈ R n ψ ( x ) + A − f ∗ ≤ ψ ( x ∗ ) − f ∗ + A ≤ λ ψ 0 ( x ∗ ) + ( 1 − λ ) f ( x ∗ ) − f ∗ + A = λ ( ψ 0 ( x ∗ ) − f ∗ ) + A . \begin{aligned}
f(z)-f^{*}
&\leq\min_{x\in\mathbb{R}^{n}}\psi(x)+A-f^{*}\\
&\leq\psi(x^{*})-f^{*}+A
\leq\lambda\psi_{0}(x^{*})+(1-\lambda)f(x^{*})-f^{*}+A\\
&=\lambda\bigl(\psi_{0}(x^{*})-f^{*}\bigr)+A.
\end{aligned} f ( z ) − f ∗ ≤ x ∈ R n min ψ ( x ) + A − f ∗ ≤ ψ ( x ∗ ) − f ∗ + A ≤ λ ψ 0 ( x ∗ ) + ( 1 − λ ) f ( x ∗ ) − f ∗ + A = λ ( ψ 0 ( x ∗ ) − f ∗ ) + A .
Lemma D.3. Let ∇ ~ f \widetilde{\nabla}f ∇ f satisfies error condition (7) and μ > 0 \mu>0 μ > 0 , then:
( ∀ x , z ∈ R n ) μ 4 ∥ x − z + 2 μ ∇ ~ f ( z ) ∥ 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + μ 2 ∥ x − z ∥ 2 2 + 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 + 2 δ 2 ( 1 − α ) 2 μ , \begin{aligned}
(\forall x,z\in\mathbb{R}^{n})\quad
\frac{\mu}{4}\left\lVert x-z+\frac{2}{\mu}\widetilde{\nabla}f(z)\right\rVert_{2}^{2}
&\leq\langle\nabla f(z),x-z\rangle+\frac{\mu}{2}\lVert x-z\rVert_{2}^{2}\\
&\quad+\frac{1-2\alpha+3\alpha^{2}}{(1-\alpha)^{2}\mu}\lVert\widetilde{\nabla}f(z)\rVert_{2}^{2}
+\frac{2\delta^{2}}{(1-\alpha)^{2}\mu},
\end{aligned} ( ∀ x , z ∈ R n ) 4 μ x − z + μ 2 ∇ f ( z ) 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + 2 μ ∥ x − z ∥ 2 2 + ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ( z ) ∥ 2 2 + ( 1 − α ) 2 μ 2 δ 2 , ( ∀ x , z ∈ R n ) μ 4 ∥ x − z + 2 μ ∇ ~ f ( z ) ∥ 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ + 1 − 2 α − α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
(\forall x,z\in\mathbb{R}^{n})\quad
\frac{\mu}{4}\left\lVert x-z+\frac{2}{\mu}\widetilde{\nabla}f(z)\right\rVert_{2}^{2}
&\geq\langle\nabla f(z),x-z\rangle+\frac{1-2\alpha-\alpha^{2}}{(1-\alpha)^{2}\mu}\lVert\widetilde{\nabla}f(z)\rVert_{2}^{2}\\
&\quad-\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}.
\end{aligned} ( ∀ x , z ∈ R n ) 4 μ x − z + μ 2 ∇ f ( z ) 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ + ( 1 − α ) 2 μ 1 − 2 α − α 2 ∥ ∇ f ( z ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 .
Proof. We will find bounds for each term of sum:
μ 4 ∥ x − z + 2 μ ∇ ~ f ( z ) ∥ 2 2 = μ 4 ∥ x − z ∥ 2 2 + ⟨ ∇ ~ f ( z ) , x − z ⟩ + 1 μ ∥ ∇ ~ f ( z ) ∥ 2 2 \frac{\mu}{4}\left\|x-z+\frac{2}{\mu}\widetilde{\nabla}f(z)\right\|_{2}^{2}
=
\frac{\mu}{4}\|x-z\|_{2}^{2}
+\langle\widetilde{\nabla}f(z),x-z\rangle
+\frac{1}{\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2} 4 μ x − z + μ 2 ∇ f ( z ) 2 2 = 4 μ ∥ x − z ∥ 2 2 + ⟨ ∇ f ( z ) , x − z ⟩ + μ 1 ∥ ∇ f ( z ) ∥ 2 2
Linear form:
⟨ ∇ ~ f ( z ) , x − z ⟩ ≤ Lemma A.1 ⟨ ∇ f ( z ) , x − z ⟩ + 1 μ ∥ ∇ ~ f ( z ) − ∇ f ( z ) ∥ 2 2 + μ 4 ∥ x − z ∥ 2 2 ≤ Lemma A.4 ⟨ ∇ f ( z ) , x − z ⟩ + 1 μ ( α 1 − α ∥ ∇ ~ f ( z ) ∥ 2 + δ 1 − α ) 2 + μ 4 ∥ x − z ∥ 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + 2 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 + 2 δ 2 ( 1 − α ) 2 μ + μ 4 ∥ x − z ∥ 2 2 . \begin{aligned}
\langle\widetilde{\nabla}f(z),x-z\rangle
&\underset{\text{Lemma A.1}}{\leq}
\langle\nabla f(z),x-z\rangle
+\frac{1}{\mu}\|\widetilde{\nabla}f(z)-\nabla f(z)\|_{2}^{2}
+\frac{\mu}{4}\|x-z\|_{2}^{2}\\
&\underset{\text{Lemma A.4}}{\leq}
\langle\nabla f(z),x-z\rangle
+\frac{1}{\mu}\left(\frac{\alpha}{1-\alpha}\|\widetilde{\nabla}f(z)\|_{2}
+\frac{\delta}{1-\alpha}\right)^{2}
+\frac{\mu}{4}\|x-z\|_{2}^{2}\\
&\leq
\langle\nabla f(z),x-z\rangle
+\frac{2\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}
+\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}
+\frac{\mu}{4}\|x-z\|_{2}^{2}.
\end{aligned} ⟨ ∇ f ( z ) , x − z ⟩ Lemma A.1 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + μ 1 ∥ ∇ f ( z ) − ∇ f ( z ) ∥ 2 2 + 4 μ ∥ x − z ∥ 2 2 Lemma A.4 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + μ 1 ( 1 − α α ∥ ∇ f ( z ) ∥ 2 + 1 − α δ ) 2 + 4 μ ∥ x − z ∥ 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + ( 1 − α ) 2 μ 2 α 2 ∥ ∇ f ( z ) ∥ 2 2 + ( 1 − α ) 2 μ 2 δ 2 + 4 μ ∥ x − z ∥ 2 2 .
⟨ ∇ ~ f ( z ) , x − z ⟩ ≥ Lemma A.1 ⟨ ∇ f ( z ) , x − z ⟩ − 1 μ ∥ ∇ ~ f ( z ) − ∇ f ( z ) ∥ 2 2 − μ 4 ∥ x − z ∥ 2 2 ≥ Lemma A.4 ⟨ ∇ f ( z ) , x − z ⟩ − 1 μ ( α 1 − α ∥ ∇ ~ f ( z ) ∥ 2 + δ 1 − α ) 2 − μ 4 ∥ x − z ∥ 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − 2 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ − μ 4 ∥ x − z ∥ 2 2 . \begin{aligned}
\langle\widetilde{\nabla}f(z),x-z\rangle
&\underset{\text{Lemma A.1}}{\geq}
\langle\nabla f(z),x-z\rangle
-\frac{1}{\mu}\|\widetilde{\nabla}f(z)-\nabla f(z)\|_{2}^{2}
-\frac{\mu}{4}\|x-z\|_{2}^{2}\\
&\underset{\text{Lemma A.4}}{\geq}
\langle\nabla f(z),x-z\rangle
-\frac{1}{\mu}\left(\frac{\alpha}{1-\alpha}\|\widetilde{\nabla}f(z)\|_{2}
+\frac{\delta}{1-\alpha}\right)^{2}
-\frac{\mu}{4}\|x-z\|_{2}^{2}\\
&\geq
\langle\nabla f(z),x-z\rangle
-\frac{2\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}
-\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}
-\frac{\mu}{4}\|x-z\|_{2}^{2}.
\end{aligned} ⟨ ∇ f ( z ) , x − z ⟩ Lemma A.1 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − μ 1 ∥ ∇ f ( z ) − ∇ f ( z ) ∥ 2 2 − 4 μ ∥ x − z ∥ 2 2 Lemma A.4 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − μ 1 ( 1 − α α ∥ ∇ f ( z ) ∥ 2 + 1 − α δ ) 2 − 4 μ ∥ x − z ∥ 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − ( 1 − α ) 2 μ 2 α 2 ∥ ∇ f ( z ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 − 4 μ ∥ x − z ∥ 2 2 .
Then:
μ 4 ∥ x − z + 2 μ ∇ ~ f ( z ) ∥ 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + μ 2 ∥ x − z ∥ 2 2 + 2 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 + 2 δ 2 ( 1 − α ) 2 μ + 1 μ ∥ ∇ ~ f ( z ) ∥ 2 2 = ⟨ ∇ f ( z ) , x − z ⟩ + μ 2 ∥ x − z ∥ 2 2 + 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 + 2 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
\frac{\mu}{4}\left\|x-z+\frac{2}{\mu}\widetilde{\nabla}f(z)\right\|_{2}^{2}
&\leq
\langle\nabla f(z),x-z\rangle
+\frac{\mu}{2}\|x-z\|_{2}^{2}\\
&\quad
+\frac{2\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}
+\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}
+\frac{1}{\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}\\
&=
\langle\nabla f(z),x-z\rangle
+\frac{\mu}{2}\|x-z\|_{2}^{2}\\
&\quad
+\frac{1-2\alpha+3\alpha^{2}}{(1-\alpha)^{2}\mu}
\|\widetilde{\nabla}f(z)\|_{2}^{2}
+\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}.
\end{aligned} 4 μ x − z + μ 2 ∇ f ( z ) 2 2 ≤ ⟨ ∇ f ( z ) , x − z ⟩ + 2 μ ∥ x − z ∥ 2 2 + ( 1 − α ) 2 μ 2 α 2 ∥ ∇ f ( z ) ∥ 2 2 + ( 1 − α ) 2 μ 2 δ 2 + μ 1 ∥ ∇ f ( z ) ∥ 2 2 = ⟨ ∇ f ( z ) , x − z ⟩ + 2 μ ∥ x − z ∥ 2 2 + ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ( z ) ∥ 2 2 + ( 1 − α ) 2 μ 2 δ 2 .
μ 4 ∥ x − z + 2 μ ∇ ~ f ( z ) ∥ 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − 2 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ + 1 μ ∥ ∇ ~ f ( z ) ∥ 2 2 = ⟨ ∇ f ( z ) , x − z ⟩ + 1 − 2 α − α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
\frac{\mu}{4}\left\|x-z+\frac{2}{\mu}\widetilde{\nabla}f(z)\right\|_{2}^{2}
\ge\langle\nabla f(z),x-z\rangle
-\frac{2\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}
-\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}
+\frac{1}{\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2} \\
&= \langle\nabla f(z),x-z\rangle
+\frac{1-2\alpha-\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}
-\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}.
\end{aligned} 4 μ x − z + μ 2 ∇ f ( z ) 2 2 ≥ ⟨ ∇ f ( z ) , x − z ⟩ − ( 1 − α ) 2 μ 2 α 2 ∥ ∇ f ( z ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 + μ 1 ∥ ∇ f ( z ) ∥ 2 2 = ⟨ ∇ f ( z ) , x − z ⟩ + ( 1 − α ) 2 μ 1 − 2 α − α 2 ∥ ∇ f ( z ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 .
Now, let us proof the following lemma which provides a lower bound of the function f f f from the set Ψ \Psi Ψ .
Lemma D.4. Let f f f be a μ \mu μ -strongly convex (4) function and ∇ ~ f \widetilde{\nabla}f ∇ f satisfies composite error condition (7). Then for any z ∈ R n z \in\mathbb{R}^{n} z ∈ R n , there is ϕ z ∈ Ψ \phi_z \in\Psi ϕ z ∈ Ψ , such that:
ϕ z ( x ) = c ϕ + κ ϕ 2 ∥ x − u ϕ ∥ 2 2 ≤ f ( x ) , ∀ x ∈ R n . \phi_z(x)=c_\phi+\frac{\kappa_\phi}{2}\|x-u_\phi\|_{2}^{2}\le f(x),\qquad\forall x\in\mathbb{R}^{n}. ϕ z ( x ) = c ϕ + 2 κ ϕ ∥ x − u ϕ ∥ 2 2 ≤ f ( x ) , ∀ x ∈ R n . c ϕ : = f ( z ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( z ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ , c_\phi:=f(z)-\frac{1-2\alpha+3\alpha^{2}}{(1-\alpha)^{2}\mu}\|\widetilde{\nabla}f(z)\|_{2}^{2}-\frac{2\delta^{2}}{(1-\alpha)^{2}\mu}, c ϕ := f ( z ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ( z ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 , κ ϕ : = μ / 2 , \kappa_\phi:=\mu/2, κ ϕ := μ /2 , u ϕ : = z − 2 μ ∇ ~ f ( z ) . u_\phi:=z-\frac{2}{\mu}\widetilde{\nabla}f(z). u ϕ := z − μ 2 ∇ f ( z ) .
Proof. Proof follows directly from Lemma D.3 and strong convexity definition (4).
Lemma D.5. Let α ∈ [ 0 , 1 / 3 ] \alpha\in[0,1/3] α ∈ [ 0 , 1/3 ] , 0 < μ ≤ L 0<\mu\le L 0 < μ ≤ L and denote the following variables:
s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q = ( 1 − α ) 4 ( 1 + α ) 4 μ 32 L . s=1-2\alpha+3\alpha^{2},\qquad m=1-2\alpha-\alpha^{2},\qquad q=\frac{(1-\alpha)^{4}}{(1+\alpha)^{4}}\frac{\mu}{32L}. s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q = ( 1 + α ) 4 ( 1 − α ) 4 32 L μ . ω \omega ω is the largest root of the quadratic equation m ω 2 + ( s − m ) ω − q = 0 m\omega^{2}+(s-m)\omega-q=0 m ω 2 + ( s − m ) ω − q = 0 .
Then:
0 < 1 250 ( μ L ) 1 − 2 γ ∗ ≤ ω ≤ 1 2 ( μ L ) 1 − 2 γ ∗ < 1 , 0<\frac{1}{250}\left(\frac{\mu}{L}\right)^{1-2\gamma^{*}}\le\omega\le\frac{1}{2}\left(\frac{\mu}{L}\right)^{1-2\gamma^{*}}<1, 0 < 250 1 ( L μ ) 1 − 2 γ ∗ ≤ ω ≤ 2 1 ( L μ ) 1 − 2 γ ∗ < 1 , where γ ∗ = min { 1 4 , log μ / L ( 3 α ) } \gamma^{*}=\min\left\{\frac{1}{4},\log_{\mu/L}(3\alpha)\right\} γ ∗ = min { 4 1 , log μ / L ( 3 α ) } (if μ = L \mu=L μ = L or α = 0 \alpha=0 α = 0 , then γ ∗ = 1 4 \gamma^{*}=\frac{1}{4} γ ∗ = 4 1 ).
Proof. We can proof, that 0 < m ≤ 1 0<m\le1 0 < m ≤ 1 :
m = 1 − 2 α − α 2 ≥ α ≤ 1 / 3 1 − 2 3 − 1 9 = 2 9 > 0 , m=1-2\alpha-\alpha^{2}\underset{\alpha\le1/3}{\ge}1-\frac{2}{3}-\frac{1}{9}=\frac{2}{9}>0, m = 1 − 2 α − α 2 α ≤ 1/3 ≥ 1 − 3 2 − 9 1 = 9 2 > 0 ,
m = 1 − 2 α − α 2 ≤ α ≥ 0 1. m=1-2\alpha-\alpha^{2}\underset{\alpha\ge0}{\le}1. m = 1 − 2 α − α 2 α ≥ 0 ≤ 1.
From the definition of γ ∗ \gamma^{*} γ ∗ we can make an estimation α ≤ 1 3 ( μ L ) γ ∗ \alpha\le\frac{1}{3}\left(\frac{\mu}{L}\right)^{\gamma^{*}} α ≤ 3 1 ( L μ ) γ ∗ . We can provide upper bound for linear term coefficient:
s − m = 1 − 2 α + 3 α 2 − 1 + 2 α + α 2 = 4 α 2 ≤ 4 9 ( μ L ) 2 γ ∗ . s-m=1-2\alpha+3\alpha^{2}-1+2\alpha+\alpha^{2}=4\alpha^{2}\le\frac{4}{9}\left(\frac{\mu}{L}\right)^{2\gamma^{*}}. s − m = 1 − 2 α + 3 α 2 − 1 + 2 α + α 2 = 4 α 2 ≤ 9 4 ( L μ ) 2 γ ∗ .
From q q q definition:
1 512 μ L ≤ α ≤ 1 / 3 q = ( 1 − α ) 4 ( 1 + α ) 4 μ 32 L ≤ α ≥ 0 1 32 μ L . \frac{1}{512}\frac{\mu}{L}\underset{\alpha\le1/3}{\le}q=\frac{(1-\alpha)^4}{(1+\alpha)^4}\frac{\mu}{32L}\underset{\alpha\ge0}{\le}\frac{1}{32}\frac{\mu}{L}. 512 1 L μ α ≤ 1/3 ≤ q = ( 1 + α ) 4 ( 1 − α ) 4 32 L μ α ≥ 0 ≤ 32 1 L μ .
Let us prove by contradiction, that ω ≥ 1 250 ( μ L ) 1 − 2 γ ∗ \omega\ge\frac{1}{250}\left(\frac{\mu}{L}\right)^{1-2\gamma^*} ω ≥ 250 1 ( L μ ) 1 − 2 γ ∗ . To that end, we assume ω < 1 250 ( μ L ) 1 − 2 γ ∗ \omega< \frac{1}{250}\left(\frac{\mu}{L}\right)^{1-2\gamma^*} ω < 250 1 ( L μ ) 1 − 2 γ ∗ . Then:
m ω 2 + ( s − m ) ω − q < m 250 2 ( μ L ) 2 ( 1 − 2 γ ∗ ) + s − m 250 ( μ L ) 1 − 2 γ ∗ − q ≤ 1 250 2 ( μ L ) 2 ( 1 − 2 γ ∗ ) + 2 1125 μ L − 1 512 μ L ≤ μ L ( 1 62500 ( μ L ) 1 − 4 γ ∗ + 2 1125 − 1 512 ) ≤ γ ∗ ≤ 1 / 4 − 11473 72000000 μ L < 0. \begin{aligned}
m\omega^2+(s-m)\omega-q<\frac{m}{250^2}\left(\frac{\mu}{L}\right)^{2(1-2\gamma^*)}+\frac{s-m}{250}\left(\frac{\mu}{L}\right)^{1-2\gamma^*}-q \\
&\le\frac{1}{250^2}\left(\frac{\mu}{L}\right)^{2(1-2\gamma^*)}+\frac{2}{1125}\frac{\mu}{L}-\frac{1}{512}\frac{\mu}{L} \\
&\le\frac{\mu}{L}\left(\frac{1}{62500}\left(\frac{\mu}{L}\right)^{1-4\gamma^*}+\frac{2}{1125}-\frac{1}{512}\right)\underset{\gamma^*\le1/4}{\le}-\frac{11473}{72000000}\frac{\mu}{L}<0.
\end{aligned} m ω 2 + ( s − m ) ω − q < 25 0 2 m ( L μ ) 2 ( 1 − 2 γ ∗ ) + 250 s − m ( L μ ) 1 − 2 γ ∗ − q ≤ 25 0 2 1 ( L μ ) 2 ( 1 − 2 γ ∗ ) + 1125 2 L μ − 512 1 L μ ≤ L μ ( 62500 1 ( L μ ) 1 − 4 γ ∗ + 1125 2 − 512 1 ) γ ∗ ≤ 1/4 ≤ − 72000000 11473 L μ < 0.
Thus, we come to a contradiction because ω \omega ω is a root of the equation m ω 2 + ( s − m ) ω − q = 0 m\omega^2+(s-m)\omega-q=0 m ω 2 + ( s − m ) ω − q = 0 .
Let us also prove by contradiction, that ω ≤ 1 2 ( μ L ) 1 − 2 γ ∗ \omega\le\frac{1}{2}\left(\frac{\mu}{L}\right)^{1-2\gamma^*} ω ≤ 2 1 ( L μ ) 1 − 2 γ ∗ . So, we assume ω > 1 2 ( μ L ) 1 − 2 γ ∗ \omega>\frac{1}{2}\left(\frac{\mu}{L}\right)^{1-2\gamma^*} ω > 2 1 ( L μ ) 1 − 2 γ ∗ . Then, there are two cases:
(1) γ ∗ = 1 4 \gamma^*=\frac{1}{4} γ ∗ = 4 1 :
m ω 2 + ( s − m ) ω − q = m ω 2 + 4 α 2 ω − q > 2 36 μ L − 1 32 μ L > 0. m\omega^2+(s-m)\omega-q=m\omega^2+4\alpha^2\omega-q>\frac{2}{36}\frac{\mu}{L}-\frac{1}{32}\frac{\mu}{L}>0. m ω 2 + ( s − m ) ω − q = m ω 2 + 4 α 2 ω − q > 36 2 L μ − 32 1 L μ > 0.
(2) γ ∗ < 1 4 ⟹ α = 1 3 ( μ L ) γ ∗ \gamma^*<\frac{1}{4}\Longrightarrow\alpha=\frac{1}{3}\left(\frac{\mu}{L}\right)^{\gamma^*} γ ∗ < 4 1 ⟹ α = 3 1 ( L μ ) γ ∗ :
m ω 2 + ( s − m ) ω − q > 2 36 ( μ L ) 2 − 4 γ ∗ + 2 9 μ L − 1 32 μ L > 0. m\omega^2+(s-m)\omega-q>\frac{2}{36}\left(\frac{\mu}{L}\right)^{2-4\gamma^*}+\frac{2}{9}\frac{\mu}{L}-\frac{1}{32}\frac{\mu}{L}>0. m ω 2 + ( s − m ) ω − q > 36 2 ( L μ ) 2 − 4 γ ∗ + 9 2 L μ − 32 1 L μ > 0.
In both cases we come to a contradiction, that is ω ≤ 1 2 ( μ L ) 1 − 2 γ ∗ \omega\le\frac{1}{2}\left(\frac{\mu}{L}\right)^{1-2\gamma^*} ω ≤ 2 1 ( L μ ) 1 − 2 γ ∗ .
Lemma D.6. Let f f f be a μ \mu μ -strongly convex (4) and L L L -smooth function, ∇ ~ f \widetilde{\nabla}f ∇ f satisfies composite error condition (7) with α ≤ 1 3 \alpha\le\frac{1}{3} α ≤ 3 1 . Let x , u ∈ R n x,u\in\mathbb{R}^n x , u ∈ R n , A ≥ 0 A\ge0 A ≥ 0 , c ∈ R c\in\mathbb{R} c ∈ R , such that:
ψ ( v ) = c + μ 4 ∥ v − u ∥ 2 2 , f ( x ) ≤ c + A , \psi(v)=c+\frac{\mu}{4}\lVert v-u\rVert_2^2,\qquad f(x)\le c+A, ψ ( v ) = c + 4 μ ∥ v − u ∥ 2 2 , f ( x ) ≤ c + A , h = 1 − α 1 + α 1 4 L , q = ( 1 − α ) 4 ( 1 + α ) 4 μ 32 L , h=\frac{1-\alpha}{1+\alpha}\frac{1}{4L},\qquad q=\frac{(1-\alpha)^4}{(1+\alpha)^4}\frac{\mu}{32L}, h = 1 + α 1 − α 4 L 1 , q = ( 1 + α ) 4 ( 1 − α ) 4 32 L μ , ω – positive root of ω ( 1 − 2 α + 3 α 2 ) − ω ( 1 − ω ) ( 1 − 2 α − α 2 ) = q , \omega\text{ -- positive root of }\omega(1-2\alpha+3\alpha^2)-\omega(1-\omega)(1-2\alpha-\alpha^2)=q, ω – positive root of ω ( 1 − 2 α + 3 α 2 ) − ω ( 1 − ω ) ( 1 − 2 α − α 2 ) = q , y = ω u + x 1 + ω , x ^ = y − h ∇ ~ f ( y ) , y=\frac{\omega u+x}{1+\omega},\qquad\widehat{x}=y-h\widetilde{\nabla}f(y), y = 1 + ω ω u + x , x = y − h ∇ f ( y ) , ψ ^ ( v ) = ( 1 − ω ) ψ ( v ) + ω φ y ( v ) , \widehat{\psi}(v)=(1-\omega)\psi(v)+\omega\varphi_y(v), ψ ( v ) = ( 1 − ω ) ψ ( v ) + ω φ y ( v ) ,
where ϕ y ( v ) \phi_y(v) ϕ y ( v ) – function defined at Lemma D.4, that is:
ϕ y ( v ) = f ( y ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ f ~ ( y ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ + μ 4 ∥ v − y + 2 μ ∇ f ~ ( y ) ∥ 2 2 . \phi_y(v) = f(y) - \frac{1 - 2\alpha+ 3\alpha^2}{(1-\alpha)^2\mu}\lVert\nabla\tilde{f}(y)\rVert_2^2 - \frac{2\delta^2}{(1-\alpha)^2\mu} + \frac{\mu}{4}\left\lVert v-y+\frac{2}{\mu}\nabla\tilde{f}(y)\right\rVert_2^2. ϕ y ( v ) = f ( y ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ~ ( y ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 + 4 μ v − y + μ 2 ∇ f ~ ( y ) 2 2 .
Then:
f ( x ^ ) ≤ min v ∈ R n ψ ^ ( v ) + ( 1 − ω ) A + δ 2 4 ( 1 + α ) 2 L + 4 δ 2 ω ( 1 − α ) 2 μ , f(\hat{x}) \leq\min_{v\in\mathbb{R}^n}\hat{\psi}(v) + (1-\omega)A + \frac{\delta^2}{4(1+\alpha)^2L} + \frac{4\delta^2\omega}{(1-\alpha)^2\mu}, f ( x ^ ) ≤ v ∈ R n min ψ ^ ( v ) + ( 1 − ω ) A + 4 ( 1 + α ) 2 L δ 2 + ( 1 − α ) 2 μ 4 δ 2 ω ,
where:
min v ∈ R n ψ ^ ( v ) = ( 1 − ω ) c + ω ( f ( y ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ f ~ ( y ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ ) + ω ( 1 − ω ) μ 4 ∥ y − u − 2 μ ∇ f ~ ( y ) ∥ 2 2 . \begin{aligned}
\min_{v\in\mathbb{R}^n}\hat{\psi}(v)
={}&(1-\omega)c+\omega\left(f(y)-\frac{1-2\alpha+3\alpha^2}{(1-\alpha)^2\mu}\lVert\nabla\tilde{f}(y)\rVert_2^2-\frac{2\delta^2}{(1-\alpha)^2\mu}\right)\\
&+\frac{\omega(1-\omega)\mu}{4}\left\lVert y-u-\frac{2}{\mu}\nabla\tilde{f}(y)\right\rVert_2^2.
\end{aligned} v ∈ R n min ψ ^ ( v ) = ( 1 − ω ) c + ω ( f ( y ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ~ ( y ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 ) + 4 ω ( 1 − ω ) μ y − u − μ 2 ∇ f ~ ( y ) 2 2 .
Proof. Lemma D.5 guarantees, that 0 < ω < 1 0 < \omega< 1 0 < ω < 1 . Using Lemma D.1:
c ^ = min v ∈ R n ψ ^ ( v ) = ( 1 − ω ) c + ω ( f ( y ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ f ~ ( y ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ ) + ω ( 1 − ω ) μ 4 ∥ y − u − 2 μ ∇ f ~ ( y ) ∥ 2 2 . \begin{aligned}
\hat{c}
={}&\min_{v\in\mathbb{R}^n}\hat{\psi}(v)
=(1-\omega)c+\omega\left(f(y)-\frac{1-2\alpha+3\alpha^2}{(1-\alpha)^2\mu}\lVert\nabla\tilde{f}(y)\rVert_2^2-\frac{2\delta^2}{(1-\alpha)^2\mu}\right)\\
&+\frac{\omega(1-\omega)\mu}{4}\left\lVert y-u-\frac{2}{\mu}\nabla\tilde{f}(y)\right\rVert_2^2.
\end{aligned} c ^ = v ∈ R n min ψ ^ ( v ) = ( 1 − ω ) c + ω ( f ( y ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ~ ( y ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 ) + 4 ω ( 1 − ω ) μ y − u − μ 2 ∇ f ~ ( y ) 2 2 .
From Lemma D.3 we can estimate last term:
ω ( 1 − ω ) μ 4 ∥ y − u − 2 μ ∇ ~ f ( y ) ∥ 2 2 ≥ ω ( 1 − ω ) ⟨ ∇ f ( y ) , u − y ⟩ + ω ( 1 − ω ) 1 − 2 α − α 2 ( 1 − α ) 2 μ ∥ ∇ f ~ ( y ) ∥ 2 2 − ω ( 1 − ω ) 2 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
\frac{\omega(1-\omega)\mu}{4}\left\lVert y-u-\frac{2}{\mu}\tilde{\nabla}f(y)\right\rVert_2^2
\geq{}&\omega(1-\omega)\langle\nabla f(y),u-y\rangle\\
&+\omega(1-\omega)\frac{1-2\alpha-\alpha^2}{(1-\alpha)^2\mu}\lVert\nabla\tilde{f}(y)\rVert_2^2-\omega(1-\omega)\frac{2\delta^2}{(1-\alpha)^2\mu}.
\end{aligned} 4 ω ( 1 − ω ) μ y − u − μ 2 ∇ ~ f ( y ) 2 2 ≥ ω ( 1 − ω ) ⟨ ∇ f ( y ) , u − y ⟩ + ω ( 1 − ω ) ( 1 − α ) 2 μ 1 − 2 α − α 2 ∥ ∇ f ~ ( y ) ∥ 2 2 − ω ( 1 − ω ) ( 1 − α ) 2 μ 2 δ 2 .
Grouping the corresponding terms:
c ^ ≥ ( 1 − ω ) c + ω f ( y ) + ω ( 1 − ω ) ⟨ ∇ f ( y ) , u − y ⟩ − 1 ( 1 − α ) 2 μ ( ω ( 1 − 2 α + 3 α 2 ) − ω ( 1 − ω ) ( 1 − 2 α − α 2 ) ) ∥ ∇ f ~ ( y ) ∥ 2 2 − ω ( 2 − ω ) 2 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
\hat{c}\geq{}&(1-\omega)c+\omega f(y)+\omega(1-\omega)\langle\nabla f(y),u-y\rangle\\
&-\frac{1}{(1-\alpha)^2\mu}\left(\omega(1-2\alpha+3\alpha^2)-\omega(1-\omega)(1-2\alpha-\alpha^2)\right)\lVert\nabla\tilde{f}(y)\rVert_2^2\\
&-\omega(2-\omega)\frac{2\delta^2}{(1-\alpha)^2\mu}.
\end{aligned} c ^ ≥ ( 1 − ω ) c + ω f ( y ) + ω ( 1 − ω ) ⟨ ∇ f ( y ) , u − y ⟩ − ( 1 − α ) 2 μ 1 ( ω ( 1 − 2 α + 3 α 2 ) − ω ( 1 − ω ) ( 1 − 2 α − α 2 ) ) ∥ ∇ f ~ ( y ) ∥ 2 2 − ω ( 2 − ω ) ( 1 − α ) 2 μ 2 δ 2 .
From convexity of function f f f :
( 1 − ω ) c ≥ ( 1 − ω ) ( f ( x ) − A ) ≥ ( 1 − ω ) ( f ( y ) + ⟨ ∇ f ( y ) , x − y ⟩ ) − ( 1 − ω ) A , \begin{aligned}
(1-\omega)c&\geq(1-\omega)(f(x)-A)\\
&\geq(1-\omega)(f(y)+\langle\nabla f(y),x-y\rangle)-(1-\omega)A,
\end{aligned} ( 1 − ω ) c ≥ ( 1 − ω ) ( f ( x ) − A ) ≥ ( 1 − ω ) ( f ( y ) + ⟨ ∇ f ( y ) , x − y ⟩) − ( 1 − ω ) A ,
then, using definition y y y we can eliminate the linear form:
⟨ ∇ f ( y ) , ω ( 1 − ω ) ( u − y ) + ( 1 − ω ) ( x − y ) ⟩ = 0 \langle\nabla f(y),\omega(1-\omega)(u-y)+(1-\omega)(x-y)\rangle=0 ⟨ ∇ f ( y ) , ω ( 1 − ω ) ( u − y ) + ( 1 − ω ) ( x − y )⟩ = 0
and using definition of ω \omega ω we continue c ^ \widehat{c} c estimation:
c ^ ≥ ω ≥ 0 f ( y ) − ( 1 − ω ) A − q ( 1 − α ) 2 μ ∥ ∇ ~ f ( y ) ∥ 2 2 − ω 4 δ 2 ( 1 − α ) 2 μ ≥ f ( y ) − ( 1 − α ) 2 ( 1 + α ) 4 1 32 L ∥ ∇ ~ f ( y ) ∥ 2 2 − ( 1 − ω ) A − ω 4 δ 2 ( 1 − α ) 2 μ . \begin{aligned}
\widehat{c} &\mathrel{\overset{\omega\geq0}{\geq}} f(y)-(1-\omega)A-\frac{q}{(1-\alpha)^2\mu}\lVert\widetilde{\nabla}f(y)\rVert_2^2-\omega\frac{4\delta^2}{(1-\alpha)^2\mu}\\
&\geq f(y)-\frac{(1-\alpha)^2}{(1+\alpha)^4}\frac{1}{32L}\lVert\widetilde{\nabla}f(y)\rVert_2^2-(1-\omega)A-\omega\frac{4\delta^2}{(1-\alpha)^2\mu}.
\end{aligned} c ≥ ω ≥ 0 f ( y ) − ( 1 − ω ) A − ( 1 − α ) 2 μ q ∥ ∇ f ( y ) ∥ 2 2 − ω ( 1 − α ) 2 μ 4 δ 2 ≥ f ( y ) − ( 1 + α ) 4 ( 1 − α ) 2 32 L 1 ∥ ∇ f ( y ) ∥ 2 2 − ( 1 − ω ) A − ω ( 1 − α ) 2 μ 4 δ 2 .
Since x ^ = y − h ∇ ~ f ( y ) \widehat{x}=y-h\widetilde{\nabla}f(y) x = y − h ∇ f ( y ) , where h h h selected consistently with the Lemma A.8 we can apply that Lemma:
f ( x ^ ) ≤ f ( y ) − ( 1 − α ) 2 ( 1 + α ) 4 1 32 L ∥ ∇ ~ f ( y ) ∥ 2 2 + δ 2 4 ( 1 + α ) 2 L . f(\widehat{x})\leq f(y)-\frac{(1-\alpha)^2}{(1+\alpha)^4}\frac{1}{32L}\lVert\widetilde{\nabla}f(y)\rVert_2^2+\frac{\delta^2}{4(1+\alpha)^2L}. f ( x ) ≤ f ( y ) − ( 1 + α ) 4 ( 1 − α ) 2 32 L 1 ∥ ∇ f ( y ) ∥ 2 2 + 4 ( 1 + α ) 2 L δ 2 .
thus:
c ^ ≥ f ( x ^ ) − ( 1 − ω ) A − δ 2 4 ( 1 + α ) 2 L − ω 4 δ 2 ( 1 − α ) 2 μ . \widehat{c}\geq f(\widehat{x})-(1-\omega)A-\frac{\delta^2}{4(1+\alpha)^2L}-\omega\frac{4\delta^2}{(1-\alpha)^2\mu}. c ≥ f ( x ) − ( 1 − ω ) A − 4 ( 1 + α ) 2 L δ 2 − ω ( 1 − α ) 2 μ 4 δ 2 .
Now we can proof convergence of Algorithm 2. We assume that the method accepts L 0 ≥ μ L_0\geq\mu L 0 ≥ μ . Let us denote L ^ k , ω k , c k , A k \widehat{L}_k,\omega_k,c_k,A_k L k , ω k , c k , A k as values selected at step k k k after the completion of the ”while” loop. Let us define, recursively, a pair of sequences { ψ k ( x ) } k ≥ 0 , { λ k } k ≥ 0 \{\psi_k(x)\}_{k\geq0},\{\lambda_k\}_{k\geq0} { ψ k ( x ) } k ≥ 0 , { λ k } k ≥ 0 corresponding to Algorithm 2 as follows:
λ 0 = 1 , c 0 = f ( x 0 ) , λ k + 1 = ( 1 − ω k ) λ k , ∀ k ≥ 0. (18) \lambda_0=1,\quad c_0=f(x^0),\quad\lambda_{k+1}=(1-\omega_k)\lambda_k,\quad\forall k\geq0. \tag*{(18)} λ 0 = 1 , c 0 = f ( x 0 ) , λ k + 1 = ( 1 − ω k ) λ k , ∀ k ≥ 0. (18)
ψ k ( x ∣ c k , μ / 2 , u k ) = c k + μ 4 ∥ x − u k ∥ 2 2 , ∀ k ≥ 0. (19) \psi_k(x\mid c_k,\mu/2,u^k)=c_k+\frac{\mu}{4}\lVert x-u^k\rVert_2^2,\quad\forall k\geq0. \tag*{(19)} ψ k ( x ∣ c k , μ /2 , u k ) = c k + 4 μ ∥ x − u k ∥ 2 2 , ∀ k ≥ 0. (19)
ψ k + 1 ( x ∣ c k + 1 , μ / 2 , u k + 1 ) = ( 1 − ω k ) ψ k ( x ∣ c k , μ / 2 , u k ) + ω k ϕ y k ( x ) , ∀ k ≥ 0 , (20) \psi_{k+1}(x\mid c_{k+1},\mu/2,u^{k+1})=(1-\omega_k)\psi_k(x\mid c_k,\mu/2,u^k)+\omega_k\phi_{y^k}(x),\quad\forall k\geq0, \tag*{(20)} ψ k + 1 ( x ∣ c k + 1 , μ /2 , u k + 1 ) = ( 1 − ω k ) ψ k ( x ∣ c k , μ /2 , u k ) + ω k ϕ y k ( x ) , ∀ k ≥ 0 , (20)
ϕ y k ( x ) = f ( y k ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( y k ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ + μ 4 ∥ x − y k + 2 μ ∇ ~ f ( y k ) ∥ 2 2 , (21) \phi_{y^k}(x)=f(y^k)-\frac{1-2\alpha+3\alpha^2}{(1-\alpha)^2\mu}\lVert\widetilde{\nabla}f(y^k)\rVert_2^2-\frac{2\delta^2}{(1-\alpha)^2\mu}+\frac{\mu}{4}\left\lVert x-y^k+\frac{2}{\mu}\widetilde{\nabla}f(y^k)\right\rVert_2^2, \tag*{(21)} ϕ y k ( x ) = f ( y k ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ( y k ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 + 4 μ x − y k + μ 2 ∇ f ( y k ) 2 2 , (21)
A k + 1 = ( 1 − ω k ) A k + δ 2 4 ( 1 + α ) 2 L ^ k + ω k 4 δ 2 ( 1 − α ) 2 μ , A 0 = 0. (22) A_{k+1}=(1-\omega_k)A_k+\frac{\delta^2}{4(1+\alpha)^2\widehat{L}_k}+\omega_k\frac{4\delta^2}{(1-\alpha)^2\mu},\quad A_0=0. \tag*{(22)} A k + 1 = ( 1 − ω k ) A k + 4 ( 1 + α ) 2 L k δ 2 + ω k ( 1 − α ) 2 μ 4 δ 2 , A 0 = 0. (22)
Lemma D.7. Let functions { ψ k } k \{\psi_k\}_k { ψ k } k defined at (D3) and (D4). Then:
c k + 1 = ( 1 − ω k ) c k + ω k ( f ( y k ) − 1 − 2 α + 3 α 2 ( 1 − α ) 2 μ ∥ ∇ ~ f ( y k ) ∥ 2 2 − 2 δ 2 ( 1 − α ) 2 μ ) + ω k ( 1 − ω k ) μ 4 ∥ y k − u k − 2 μ ∇ ~ f ( y k ) ∥ 2 2 , \begin{aligned}
c_{k+1}
={}&(1-\omega_k)c_k+\omega_k\left(f(y^k)-\frac{1-2\alpha+3\alpha^2}{(1-\alpha)^2\mu}\lVert\widetilde{\nabla}f(y^k)\rVert_2^2-\frac{2\delta^2}{(1-\alpha)^2\mu}\right)\\
&+\frac{\omega_k(1-\omega_k)\mu}{4}\left\lVert y^k-u^k-\frac{2}{\mu}\widetilde{\nabla}f(y^k)\right\rVert_2^2,
\end{aligned} c k + 1 = ( 1 − ω k ) c k + ω k ( f ( y k ) − ( 1 − α ) 2 μ 1 − 2 α + 3 α 2 ∥ ∇ f ( y k ) ∥ 2 2 − ( 1 − α ) 2 μ 2 δ 2 ) + 4 ω k ( 1 − ω k ) μ y k − u k − μ 2 ∇ f ( y k ) 2 2 , u k + 1 = ( 1 − ω k ) u k + ω k y k − 2 ω k μ ∇ ~ f ( y k ) . u^{k+1}=(1-\omega_k)u^k+\omega_k y^k-\frac{2\omega_k}{\mu}\widetilde{\nabla}f(y^k). u k + 1 = ( 1 − ω k ) u k + ω k y k − μ 2 ω k ∇ f ( y k ) .
That is sequence { u k } k \{u^k\}_k { u k } k in the Algorithm 2 corresponds sequence { ψ k } k \{\psi_k\}_k { ψ k } k .
Proof. Since ψ k + 1 ( x ∣ c k + 1 , μ / 2 , u k + 1 ) = ( 1 − ω k ) ψ k ( x ∣ c k , μ / 2 , u k ) + ω k ϕ y k ( x ) \psi_{k+1}(x\mid c_{k+1},\mu/2,u^{k+1})=(1-\omega_k)\psi_k(x\mid c_k,\mu/2,u^k)+\omega_k\phi_{y^k}(x) ψ k + 1 ( x ∣ c k + 1 , μ /2 , u k + 1 ) = ( 1 − ω k ) ψ k ( x ∣ c k , μ /2 , u k ) + ω k ϕ y k ( x ) and ψ k , ϕ y k ∈ Ψ \psi_k,\phi_{y^k}\in\Psi ψ k , ϕ y k ∈ Ψ , we can apply Lemma D.1 and obtained the relations described above.
Lemma D.8. Let f f f be a μ \mu μ -strongly convex (4) and L L L -smooth function, ∇ ~ f \widetilde{\nabla}f ∇ f satisfies composite error condition (7) with α ≤ 1 3 \alpha\le\frac{1}{3} α ≤ 3 1 , then ∀ k ≥ 0 \forall k \ge0 ∀ k ≥ 0 f ( x k ) ≤ c k + A k f(x^k) \le c_k+A_k f ( x k ) ≤ c k + A k for Algorithm 2 with L 0 ≥ μ L_0 \ge\mu L 0 ≥ μ . In this case, the total number of iterations of the inner loop can be estimated as N + J ∗ − 1 N+J_*-1 N + J ∗ − 1 , where:
max 0 ≤ k ≤ N − 1 J k ≤ J ∗ = ⌈ max { 0 , log 2 ( L L 0 ) } ⌉ . \max_{0\le k\le N-1}J_k \le J_*=\left\lceil\max\left\{0,\log_2\left(\frac{L}{L_0}\right)\right\}\right\rceil. 0 ≤ k ≤ N − 1 max J k ≤ J ∗ = ⌈ max { 0 , log 2 ( L 0 L ) } ⌉ . And the total number of inexact gradient ∇ ~ f \widetilde{\nabla}f ∇ f evaluations over N N N iterations of Algorithm 2 is estimated as 2 N + J ∗ − 1 2N+J_*-1 2 N + J ∗ − 1 .
Proof. Condition f ( x k ) ≤ c k + A k f(x^k)\le c_k+A_k f ( x k ) ≤ c k + A k follows from definition of c k , A k c_k,A_k c k , A k and point x k x^k x k obtained after ”while” loop termination. It should be noted that f ( x 0 ) = c 0 + A 0 f(x^0)=c_0+A_0 f ( x 0 ) = c 0 + A 0 , then using induction and Lemma D.6 from f ( x k ) ≤ c k + A k f(x^k)\le c_k+A_k f ( x k ) ≤ c k + A k follows f ( x k + 1 ) ≤ c k + 1 + A k + 1 f(x^{k+1})\le c_{k+1}+A_{k+1} f ( x k + 1 ) ≤ c k + 1 + A k + 1 . By Lemma D.6 the inner loop is guaranteed to terminate, when L ^ k ≥ L \widehat{L}_k\ge L L k ≥ L , thus the total number of inner loop iterations over the entire execution of the algorithm can be estimated as:
J 0 + ∑ k = 0 N − 2 ( J k + 1 − J k + 1 ) = J N − 1 + N − 1 ≤ J ∗ + N − 1 , J_0+\sum_{k=0}^{N-2}(J_{k+1}-J_k+1)=J_{N-1}+N-1\le J_*+N-1, J 0 + k = 0 ∑ N − 2 ( J k + 1 − J k + 1 ) = J N − 1 + N − 1 ≤ J ∗ + N − 1 , and inexact gradient ∇ ~ f \widetilde{\nabla}f ∇ f calls as 2 N + J ∗ − 1 2N+J_*-1 2 N + J ∗ − 1 .
Lemma D.9. Let { λ k } k ≥ 0 \{\lambda_k\}_{k\ge0} { λ k } k ≥ 0 be a sequence defined in (D2) and { ψ k } k ≥ 0 \{\psi_k\}_{k\ge0} { ψ k } k ≥ 0 be the corresponding functions (D3). Then
∀ k ≥ 0 and ∀ x ∈ R n ψ k ( x ) ≤ λ k ψ 0 ( x ) + ( 1 − λ k ) f ( x ) . \forall k\ge0\ \text{and}\ \forall x\in\mathbb{R}^n\quad\psi_k(x)\le\lambda_k\psi_0(x)+(1-\lambda_k)f(x). ∀ k ≥ 0 and ∀ x ∈ R n ψ k ( x ) ≤ λ k ψ 0 ( x ) + ( 1 − λ k ) f ( x ) . Proof. By the principle of induction. For k = 0 k=0 k = 0 , the inequality is obvious. Assume that inequality takes place for k k k . From (D4) and Lemma D.4, we get
ψ k + 1 ( x ) = ( 1 − ω k ) ψ k ( x ) + ω k φ k y ( x ) ≤ ( 1 − ω k ) ( ( 1 − λ k ) f ( x ) + λ k ψ 0 ( x ) ) + ω k f ( x ) = λ k + 1 ψ 0 ( x ) + ( 1 − λ k + 1 ) f ( x ) . \begin{aligned}
\psi_{k+1}(x)&=(1-\omega_k)\psi_k(x)+\omega_k\varphi_k^y(x)\\
&\le(1-\omega_k)((1-\lambda_k)f(x)+\lambda_k\psi_0(x))+\omega_kf(x)\\
&=\lambda_{k+1}\psi_0(x)+(1-\lambda_{k+1})f(x).
\end{aligned} ψ k + 1 ( x ) = ( 1 − ω k ) ψ k ( x ) + ω k φ k y ( x ) ≤ ( 1 − ω k ) (( 1 − λ k ) f ( x ) + λ k ψ 0 ( x )) + ω k f ( x ) = λ k + 1 ψ 0 ( x ) + ( 1 − λ k + 1 ) f ( x ) .
Proof of the Theorem 3.1. From Lemma D.8 we obtain:
f ( x N ) ≤ c N + A N = min x ∈ R n ψ N ( x ) + A N . f(x^N)\le c_N+A_N=\min_{x\in\mathbb{R}^n}\psi_N(x)+A_N. f ( x N ) ≤ c N + A N = x ∈ R n min ψ N ( x ) + A N .
Applying Lemma D.9 and then Lemma D.2:
f ( x N ) − f ∗ ≤ λ N ( ψ 0 ( x ∗ ) − f ∗ ) + A N = ( D 3 ) λ N ( f ( x 0 ) − f ∗ + μ 4 ∥ x 0 − x ∗ ∥ 2 2 ) + A N . f(x^N)-f^*\le\lambda_N(\psi_0(x^*)-f^*)+A_N\overset{\mathrm{(D3)}}{=}\lambda_N\left(f(x^0)-f^*+\frac{\mu}{4}\lVert x^0-x^*\rVert_2^2\right)+A_N. f ( x N ) − f ∗ ≤ λ N ( ψ 0 ( x ∗ ) − f ∗ ) + A N = ( D3 ) λ N ( f ( x 0 ) − f ∗ + 4 μ ∥ x 0 − x ∗ ∥ 2 2 ) + A N .
From definition of { λ k } k \{\lambda_k\}_k { λ k } k (D2) we obtain λ N = ∏ k = 0 N − 1 ( 1 − ω k ) \lambda_N=\prod_{k=0}^{N-1}(1-\omega_k) λ N = ∏ k = 0 N − 1 ( 1 − ω k ) . Let us denote γ k ∗ = min { 1 4 , log μ L ^ k ( 3 α ) } \gamma_k^*=\min\left\{\frac{1}{4},\log\frac{\mu}{\widehat{L}_k}(3\alpha)\right\} γ k ∗ = min { 4 1 , log L k μ ( 3 α ) } (if μ = L ^ k \mu=\widehat{L}_k μ = L k or α = 0 \alpha=0 α = 0 , then γ k ∗ = 1 4 \gamma_k^*=\frac{1}{4} γ k ∗ = 4 1 ), then using Lemma D.5 – 1 250 ( μ L k ) 1 − 2 γ k ∗ ≤ ω k \frac{1}{250}\left(\frac{\mu}{L_k}\right)^{1-2\gamma_k^*} \le\omega_k 250 1 ( L k μ ) 1 − 2 γ k ∗ ≤ ω k . Since L ^ k ≤ L ∗ \widehat{L}_k \le L_* L k ≤ L ∗ , then γ ∗ ≤ γ k ∗ \gamma^* \le\gamma_k^* γ ∗ ≤ γ k ∗ , that is 1 250 ( μ L ∗ ) 1 − 2 γ ∗ ≤ ω k \frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*} \le\omega_k 250 1 ( L ∗ μ ) 1 − 2 γ ∗ ≤ ω k . Then
λ N ≤ ( 1 − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ ) N ≤ exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) . \lambda_N \le\left(1-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}\right)^N \le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right). λ N ≤ ( 1 − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ ) N ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) .
Let us denote:
b k = δ 2 4 ( 1 + α ) 2 L ^ k + ω k 4 δ 2 ( 1 − α ) 2 μ . b_k=\frac{\delta^2}{4(1+\alpha)^2\widehat{L}_k}+\omega_k\frac{4\delta^2}{(1-\alpha)^2\mu}. b k = 4 ( 1 + α ) 2 L k δ 2 + ω k ( 1 − α ) 2 μ 4 δ 2 .
then A N A_N A N can be expressed as (using its definition D6).
A N = ∑ k = 0 N − 1 b k ∏ j = k + 1 N − 1 ( 1 − ω j ) . A_N=\sum_{k=0}^{N-1}b_k\prod_{j=k+1}^{N-1}(1-\omega_j). A N = k = 0 ∑ N − 1 b k j = k + 1 ∏ N − 1 ( 1 − ω j ) .
Since ω k \omega_k ω k is the root of the quadratic equation m ω k 2 + ( s − m ) ω k − q k = 0 m\omega_k^2+(s-m)\omega_k-q_k=0 m ω k 2 + ( s − m ) ω k − q k = 0 , where:
s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q k = ( 1 − α ) 4 ( 1 + α ) 4 μ 32 L ^ k . s=1-2\alpha+3\alpha^2,\qquad m=1-2\alpha-\alpha^2,\qquad q_k=\frac{(1-\alpha)^4}{(1+\alpha)^4}\frac{\mu}{32\widehat{L}_k}. s = 1 − 2 α + 3 α 2 , m = 1 − 2 α − α 2 , q k = ( 1 + α ) 4 ( 1 − α ) 4 32 L k μ .
From proof of the Lemma D.5 it follows, that m > 0 m>0 m > 0 and ω k < 1 \omega_k<1 ω k < 1 . Then q k = s ω k + m ω k ( ω k − 1 ) ≤ s ω k q_k=s\omega_k+m\omega_k(\omega_k-1)\le s\omega_k q k = s ω k + m ω k ( ω k − 1 ) ≤ s ω k . Thus:
b k = δ 2 4 ( 1 + α ) 2 L ^ k + ω k 4 δ 2 ( 1 − α ) 2 μ = 8 ( 1 + α ) 2 δ 2 q k ( 1 − α ) 4 μ + ω k 4 δ 2 ( 1 − α ) 2 μ ≤ q k ≤ s ω k ( 8 ( 1 + α ) 2 s ( 1 − α ) 4 + 4 ( 1 − α ) 2 ) ω k δ 2 μ = ( 8 ( 1 + α ) 2 ( 1 − 2 α + 3 α 2 ) ( 1 − α ) 4 + 4 ( 1 − α ) 2 ) ω k δ 2 μ = ( 8 ( 1 + α ) 2 ( 1 − α ) 2 ( 1 + 2 α 2 ( 1 − α ) 2 ) + 4 ( 1 − α ) 2 ) ω k δ 2 μ ≤ α ≤ 1 / 3 ( 8 ⋅ 4 ( 1 + 1 2 ) + 9 ) ω k δ 2 μ = 57 ω k δ 2 μ . \begin{aligned}
b_k
&=\frac{\delta^2}{4(1+\alpha)^2\widehat{L}_k}+\omega_k\frac{4\delta^2}{(1-\alpha)^2\mu}\\
&=\frac{8(1+\alpha)^2\delta^2q_k}{(1-\alpha)^4\mu}+\omega_k\frac{4\delta^2}{(1-\alpha)^2\mu}\\
&\underset{q_k\le s\omega_k}{\le}\left(\frac{8(1+\alpha)^2s}{(1-\alpha)^4}+\frac{4}{(1-\alpha)^2}\right)\omega_k\frac{\delta^2}{\mu}\\
&=\left(\frac{8(1+\alpha)^2(1-2\alpha+3\alpha^2)}{(1-\alpha)^4}+\frac{4}{(1-\alpha)^2}\right)\omega_k\frac{\delta^2}{\mu}\\
&=\left(\frac{8(1+\alpha)^2}{(1-\alpha)^2}\left(1+\frac{2\alpha^2}{(1-\alpha)^2}\right)+\frac{4}{(1-\alpha)^2}\right)\omega_k\frac{\delta^2}{\mu}\\
&\underset{\alpha\le1/3}{\le}\left(8\cdot4\left(1+\frac{1}{2}\right)+9\right)\omega_k\frac{\delta^2}{\mu}=57\omega_k\frac{\delta^2}{\mu}.
\end{aligned} b k = 4 ( 1 + α ) 2 L k δ 2 + ω k ( 1 − α ) 2 μ 4 δ 2 = ( 1 − α ) 4 μ 8 ( 1 + α ) 2 δ 2 q k + ω k ( 1 − α ) 2 μ 4 δ 2 q k ≤ s ω k ≤ ( ( 1 − α ) 4 8 ( 1 + α ) 2 s + ( 1 − α ) 2 4 ) ω k μ δ 2 = ( ( 1 − α ) 4 8 ( 1 + α ) 2 ( 1 − 2 α + 3 α 2 ) + ( 1 − α ) 2 4 ) ω k μ δ 2 = ( ( 1 − α ) 2 8 ( 1 + α ) 2 ( 1 + ( 1 − α ) 2 2 α 2 ) + ( 1 − α ) 2 4 ) ω k μ δ 2 α ≤ 1/3 ≤ ( 8 ⋅ 4 ( 1 + 2 1 ) + 9 ) ω k μ δ 2 = 57 ω k μ δ 2 .
Hence:
A N ≤ 57 δ 2 μ ∑ k = 0 N − 1 ω k ∏ j = k + 1 N − 1 ( 1 − ω j ) = 57 δ 2 μ ( 1 − ∏ k = 0 N − 1 ( 1 − ω k ) ) = 57 ( 1 − λ N ) δ 2 μ ≤ 57 δ 2 μ . \begin{aligned}
A_N\le57\frac{\delta^2}{\mu}\sum_{k=0}^{N-1}\omega_k\prod_{j=k+1}^{N-1}(1-\omega_j)=57\frac{\delta^2}{\mu}\left(1-\prod_{k=0}^{N-1}(1-\omega_k)\right) \\
&=57(1-\lambda_N)\frac{\delta^2}{\mu}\le57\frac{\delta^2}{\mu}.
\end{aligned} A N ≤ 57 μ δ 2 k = 0 ∑ N − 1 ω k j = k + 1 ∏ N − 1 ( 1 − ω j ) = 57 μ δ 2 ( 1 − k = 0 ∏ N − 1 ( 1 − ω k ) ) = 57 ( 1 − λ N ) μ δ 2 ≤ 57 μ δ 2 .
Combining inequalities above one can obtain convergence:
f ( x N ) − f ∗ ≤ exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 57 δ 2 μ . f(x^N)-f^*\le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right)\left(f(x^0)-f^*+\frac{\mu}{4}R^2\right)+57\frac{\delta^2}{\mu}. f ( x N ) − f ∗ ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 57 μ δ 2 .
□ \square □
Proof of the Theorem 3.2. Since L 0 = L L_0 = L L 0 = L , then ∀ k ≥ 0 \forall k \ge0 ∀ k ≥ 0 , L ^ k = L ∗ = L 0 = L \widehat{L}_k = L_* = L_0 = L L k = L ∗ = L 0 = L (see Theorem 3.1 ) and we can apply previous Theorem.
Proof of the Theorem 3.3. Similar to the proof of Theorem 2.4 , let us consider f μ = f ( x ) + μ 2 ∥ x − x 0 ∥ 2 2 f_\mu= f(x) + \frac{\mu}{2}\lVert x - x^0\rVert_2^2 f μ = f ( x ) + 2 μ ∥ x − x 0 ∥ 2 2 . It us known, that f μ f_\mu f μ is μ \mu μ strongly convex (4) and L + μ L + \mu L + μ smooth (3) . Corresponding gradient estimation ∇ ~ f μ = ∇ ~ f + μ ( x − x 0 ) \widetilde{\nabla}f_\mu= \widetilde{\nabla}f + \mu(x - x^0) ∇ f μ = ∇ f + μ ( x − x 0 ) satisfies composite error condition with relative error parameter α \alpha α and absolute error α μ R \alpha\mu R α μ R (by Lemma B.3). Using Theorem 3.1 convergence for f μ f_\mu f μ one can obtain:
f μ ( x N ∣ x 0 ) − f μ ∗ ≤ exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f μ ( x 0 ∣ x 0 ) − f μ ∗ + μ 4 R 2 ) + 57 δ 2 μ . f_\mu(x^N\mid x^0)-f_\mu^* \le\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right)\left(f_\mu(x^0\mid x^0)-f_\mu^*+\frac{\mu}{4}R^2\right)+57\frac{\delta^2}{\mu}. f μ ( x N ∣ x 0 ) − f μ ∗ ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f μ ( x 0 ∣ x 0 ) − f μ ∗ + 4 μ R 2 ) + 57 μ δ 2 .
where:
L ∗ = max 0 ≤ k ≤ N − 1 L ^ k ≤ max { L 0 , 2 ( L + μ ) } , L_*=\max_{0\le k\le N-1}\widehat{L}_k\le\max\{L_0,2(L+\mu)\}, L ∗ = 0 ≤ k ≤ N − 1 max L k ≤ max { L 0 , 2 ( L + μ )} ,
γ ∗ = min { 1 4 , log μ L ∗ ( 3 α ) } , if L ∗ = μ or α = 0 , then γ ∗ = 1 4 . \gamma^*=\min\left\{\frac{1}{4},\log_{\frac{\mu}{L_*}}(3\alpha)\right\},\quad\text{if }L_*=\mu\text{ or }\alpha=0,\text{ then }\gamma^*=\frac{1}{4}. γ ∗ = min { 4 1 , log L ∗ μ ( 3 α ) } , if L ∗ = μ or α = 0 , then γ ∗ = 4 1 .
J ∗ = ⌈ max { 0 , log 2 ( L + μ L 0 ) } ⌉ . J_*=\left\lceil\max\left\{0,\log_2\left(\frac{L+\mu}{L_0}\right)\right\}\right\rceil. J ∗ = ⌈ max { 0 , log 2 ( L 0 L + μ ) } ⌉ .
Then (since f μ ∗ = f ( x μ ∗ ) + μ 2 ∥ x μ ∗ − x 0 ∥ 2 2 ≥ f ∗ f_\mu^*=f(x_\mu^*)+\frac{\mu}{2}\lVert x_\mu^*-x^0\rVert_2^2\ge f^* f μ ∗ = f ( x μ ∗ ) + 2 μ ∥ x μ ∗ − x 0 ∥ 2 2 ≥ f ∗ ):
f ( x N ) − f ∗ ≤ Lemma B.2 f μ ( x N ∣ x 0 ) − f μ ∗ + μ 2 R 2 f(x^N)-f^* \underset{\text{Lemma B.2}}{\le} f_\mu(x^N\mid x^0)-f_\mu^*+\frac{\mu}{2}R^2 f ( x N ) − f ∗ Lemma B.2 ≤ f μ ( x N ∣ x 0 ) − f μ ∗ + 2 μ R 2
≤ Lemma B.1 exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 57 α μ R 2 + μ 2 R 2 \underset{\text{Lemma B.1}}{\le}\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right)\left(f(x^0)-f^*+\frac{\mu}{4}R^2\right)+57\alpha\mu R^2+\frac{\mu}{2}R^2 Lemma B.1 ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 57 α μ R 2 + 2 μ R 2
≤ α ≤ 1 / 3 exp ( − 1 250 ( μ L ∗ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + μ 4 R 2 ) + 39 μ R 2 2 . \underset{\alpha\le1/3}{\le}\exp\left(-\frac{1}{250}\left(\frac{\mu}{L_*}\right)^{1-2\gamma^*}N\right)\left(f(x^0)-f^*+\frac{\mu}{4}R^2\right)+\frac{39\mu R^2}{2}. α ≤ 1/3 ≤ exp ( − 250 1 ( L ∗ μ ) 1 − 2 γ ∗ N ) ( f ( x 0 ) − f ∗ + 4 μ R 2 ) + 2 39 μ R 2 .
Thus, to solve problem f ( x N ) − f ∗ ≤ ε f(x^N)-f^*\le\varepsilon f ( x N ) − f ∗ ≤ ε , where 0 < ε ≤ f ( x 0 ) − f ∗ 0<\varepsilon\le f(x^0)-f^* 0 < ε ≤ f ( x 0 ) − f ∗ one can choose (with L 0 ≥ μ L_0\ge\mu L 0 ≥ μ ):
μ = ε 39 R 2 ⟹ γ ∗ = min { 1 4 , log ε 39 L ∗ R 2 ( 3 α ) } , if α = 0 , then γ ∗ = 1 4 . \mu=\frac{\varepsilon}{39R^2}\Longrightarrow\gamma^*=\min\left\{\frac{1}{4},\log_{\frac{\varepsilon}{39L_*R^2}}(3\alpha)\right\},\quad\text{if }\alpha=0,\text{ then }\gamma^*=\frac{1}{4}. μ = 39 R 2 ε ⟹ γ ∗ = min { 4 1 , log 39 L ∗ R 2 ε ( 3 α ) } , if α = 0 , then γ ∗ = 4 1 .
then after (since μ 4 R 2 ≤ ε 156 \frac{\mu}{4}R^2\le\frac{\varepsilon}{156} 4 μ R 2 ≤ 156 ε ):
N = max { 0 , ⌈ 250 ( L ∗ μ ) 1 − 2 γ ∗ ln ( 157 ( f ( x 0 ) − f ∗ ) 78 ε ) ⌉ } = max { 0 , ⌈ 250 ( 39 L ∗ R 2 ε ) 1 − 2 γ ∗ ln ( 157 ( f ( x 0 ) − f ∗ ) 78 ε ) ⌉ } . \begin{aligned}
N=\max\left\{0,\left\lceil250\left(\frac{L_*}{\mu}\right)^{1-2\gamma^*}\ln\left(\frac{157(f(x^0)-f^*)}{78\varepsilon}\right)\right\rceil\right\} \\
&=\max\left\{0,\left\lceil250\left(\frac{39L_*R^2}{\varepsilon}\right)^{1-2\gamma^*}\ln\left(\frac{157(f(x^0)-f^*)}{78\varepsilon}\right)\right\rceil\right\}.
\end{aligned} N = max { 0 , ⌈ 250 ( μ L ∗ ) 1 − 2 γ ∗ ln ( 78 ε 157 ( f ( x 0 ) − f ∗ ) ) ⌉ } = max { 0 , ⌈ 250 ( ε 39 L ∗ R 2 ) 1 − 2 γ ∗ ln ( 78 ε 157 ( f ( x 0 ) − f ∗ ) ) ⌉ } .
iterations method will provide f ( x N ) − f ∗ ≤ ε f(x^{N}) - f^{*} \le\varepsilon f ( x N ) − f ∗ ≤ ε .