11institutetext: A. Vasin 22institutetext: Moscow Institute of Physics and
Technology, Russia
A. Gasnikov 33institutetext: Moscow Institute of Physics and Technology,
Russia
Institute for Information Transmission Problems RAS, Russia
Weierstrass Institute for Applied Analysis and Stochastics, Germany
V. Spokoiny 44institutetext: Weierstrass Institute for Applied Analysis and
Stochastics, Germany
Institute for Information Transmission Problems RAS, Russia

# Stopping rules for accelerated gradient methods with additive noise in
gradient††thanks: The research of A. Gasnikov was supported by the Ministry of
Science and Higher Education of the Russian Federation (Goszadaniye)
075-00337-20-03, project no. 0714-2020-0005. The work of A. Vasin was
supported by Andrei M. Raigorodskii Scholarship in Optimization.

Vasin Artem  Alexander Gasnikov  Vladimir Spokoiny

(Received: date / Accepted: date)

###### Abstract

In this article, we investigate  an accelerated first-order method, namely,
the method of similar triangles, which is optimal in the class of convex
(strongly convex) problems with a Lipschitz gradient. The paper considers a
model of additive noise in a gradient and a Euclidean prox-structure for not
necessarily bounded sets. Convergence estimates are obtained in the case of
strong convexity and its absence, and a stopping criterion is proposed for not
strongly convex problems.

##  1 Introduction

We consider $L$-smooth ($\mu$-strongly) convex optimization problem ($\mu\geq
0$):

$\min_{x\in Q}f(x).$

This means that $Q$ is convex set, and for all $x,y\in Q$:

$f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|_{2}^{2}\leq f(y),$
$\|\nabla f(y)-\nabla f(x)\|_{2}\leq L\|y-x\|_{2}.$

In the analysis of the rates of convergence of different first-order methods
these relations are typically rewrite as follows devolder2013exactness ;
bubeck2014convex ; ben-tal2015lectures ; gasnikov2016efficient ; beck2017first
; gasnikov2017modern ; nesterov2018lectures ; lan2020first ;
tyurin2020adaptive ; dvurechensky2020numerical ; stonyakin2020adaptive ;
dvurechensky2021first ; daspremont021acceleration

$\displaystyle f(x)+\langle\nabla
f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|_{2}^{2}\leq f(y)$ $\displaystyle\hskip
85.35826pt\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|y-x\|_{2}^{2}.$
(1)

Note, that the last relation is a consequence of the previous ones and in
general is not equivalent to them taylor2017smooth ; gasnikov2017modern .

In many applications, especially for gradient-free methods (when estimating
the gradient by finite differences conn2009introduction ;
risteski2016algorithms ; berahas2019theoretical ) optimization problems in
infinite dimensional spaces (such examples arise when solving inverse problems
kabanikhin2011inverse ; gasnikov2017convex ) instead of an access to $\nabla
f(x)$ we have an access to its inexact approximation $\tilde{\nabla}f(x)$.

The two most popular conception of inexactness of gradient in practice are
polyak1987introduction : for all $x\in Q$

$\|\tilde{\nabla}f(x)-\nabla f(x)\|_{2}\leq\delta,$ (2)
$\|\tilde{\nabla}f(x)-\nabla f(x)\|_{2}\leq\alpha\|\nabla
f(x)\|_{2},\quad\alpha\in[0,1).$ (3)

For the first conception (2) several results about the accumulation of error
can be found in polyak1987introduction ; d2008smooth ; cohen2018acceleration ;
ajalloeian2020analysis , but all these results are still far from to be
optimistic in general. The reason was described in poljak1981iterative . We
can explain this reason by very simple example:

$\min_{x\in\mathbb{R}^{n}}f(x):=\frac{1}{2}\sum_{i=1}^{n}\lambda_{i}\cdot(x^{i})^{2},$
(4)

where $0\geq\mu=\lambda_{1}\leq\lambda_{2}\leq...\leq\lambda_{n}=L$, $L\geq
2\mu$. The solution of this problem is $x_{*}=0$. Assume that inexactness
takes place only in the first component. That is instead of $\partial
f(x)/\partial x^{1}=\mu x^{1}$ we have an access to
$\tilde{\partial}f(x)/\partial x^{1}=\mu x^{1}-\delta$. For simple gradient
dynamic

$x_{k}=x_{k-1}-\frac{1}{L}\tilde{\nabla}f(x_{k-1}),$

we can conclude that for all $k\in\mathbb{N}$

$x_{k}^{1}\geq\frac{\delta}{L}\frac{1-(1-\mu/L)^{k}}{1-(1-\mu/L)}\geq\frac{\delta}{8\mu}.$
(5)

Hence***This bound corresponds to the worst-case philosophy concerning the
choice of considered example for considered class of methods
nemirovsky1983problem ; nesterov2018lectures ; bubeck2014convex ;
gasnikov2017modern . We expect more interesting results here by considering
average-case complexity scieur2020universal ; pedregosa2020average  (spectrum
$\\{\lambda_{i}\\}$ average).

$f(x_{k})-f(x_{*})\geq\frac{\delta^{2}}{2\mu}.$

So we have a problem with (5), since $\mu$ can be to small
($\mu\lesssim\varepsilon$ – degenerate regime, where $\varepsilon$ – desired
accuracy in function value) in denominator of the RHS. We may expect even more
serious troubles for accelerated gradient methods, since they are more
sensitive to the level of noise devolder2014first ; gasnikov2017modern . The
solution of this problem is well known (see, for example, poljak1981iterative
; polyak1987introduction ; nemirovski1986regularizing ): to propose a stopping
rule for the considered algorithm or to use regularization
$\mu\sim\varepsilon$ gasnikov2017modern . Roughly speaking, for non
accelerated algorithms in poljak1981iterative ; polyak1987introduction  it was
proved that if $\delta\sim\varepsilon^{2}$, then it’s possible to reach
$\varepsilon$-accuracy in function value (with almost the same number of
iterations as for no noise case $\delta=0$) by applying computationally
convenient stopping rule.

In this paper we show that it’s sufficient to have $\delta\sim\varepsilon$
both for primal-dual non accelerated and accelerated gradient type methods
nesterov2018lectures ; gasnikov2017modern . Primal-duality of methods is used
to build computationally convenient stopping rule in degenerate regime. We
emphasize, that the results $\delta\sim\varepsilon$ has a simple explanation
(see section 2) and one might think that it is well known. But to the best of
our knowledge the best results for accelerated methods require
$\delta\sim\varepsilon^{3/2}$. So we consider our observation (that
$\delta\sim\varepsilon$) to be an important part of this paper, although it
has rather simple explanation.

The situation with the second criteria (3) is significantly better. For non
accelerated algorithms inexactness in this case lead only to the deceleration
of convergence $\sim(1-\alpha)^{-1}$-times polyak1987introduction . This
result holds true with the relaxed strong convexity assumption
gasnikov2017modern  (Polyak–Lojasiewicz condition). For accelerated case to
the best of our knowledge this is an open problem to estimate accumulation of
an error gasnikov2017modern .

In this paper we show that if $\alpha\lesssim\left(\frac{\mu}{L}\right)^{3/4}$
in $\mu$-strongly convex case and (on $k$-th iteration)
$\alpha_{k}\lesssim\left(\frac{1}{k}\right)^{3/2}$ in degenerate regime we do
not have any deceleration. Numerical experiments demonstrate that in general
for $\alpha$ larger than mentioned above thresholds the convergence may slow
down a lot up to divergence for considered accelerated method.

Note, that close results (with the requirement
$\alpha\lesssim\left(\frac{\mu}{L}\right)^{5/4}$) in the case
$\mu\gg\varepsilon$ were recently obtained by using another techniques in
Stochastic Optimization with decision dependent distribution
drusvyatskiy2020stochastic  and Policy Evaluation in Reinforcement Learning
via reduction to stochastic Variational Inequality with Markovian noise
kotsalis2020simple . In kotsalis2020simple ; drusvyatskiy2020stochastic  it
was assumed that

$\|\tilde{\nabla}f(x)-\nabla f(x)\|_{2}\leq
B\|x-x_{*}\|_{2},\quad\alpha\in[0,1).$ (6)

Since $x_{*}$ is a solution, from Fermat’s principle $\nabla f(x_{*})=0$.
Therefore,

$\|\nabla f(x)\|_{2}=\|\nabla f(x)-\nabla f(x_{*})\|_{2}\leq
L\|x-x_{*}\|_{2}.$

So if (3) holds true then 6 also holds true with $B=\alpha L$.

##  2 Ideas behind the results

Important results in gradient error accumulation for first-order methods were
developed in the cycle of works of O. Devolder, F. Glineur and Yu. Nesterov
2011–2014 devolder2011stochastic ; devolder2014first ; devolder2013first ;
devolder2013exactness . In these works authors were motivated by (1). The idea
is to “relax” (1), assuming inexactness in gradient. So they introduce inexact
gradient $\tilde{\nabla}f(x)$, satisfying for all $x,y\in Q$

$\displaystyle
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|_{2}^{2}-\delta\leq
f(y)$ $\displaystyle\hskip 85.35826pt\leq
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{L}{2}\|y-x\|_{2}^{2}+\delta.$
(7)

Such a definition allows to develop precise theory for error accumulation for
first-order methods.

Namely, it was proved that for non-accelerated gradient methods

$f(x_{k})-f(x_{*})=O\left(\min\left\\{\frac{LR^{2}}{k}+\delta,LR^{2}\exp\left(-\frac{\mu}{L}k\right)+\delta\right\\}\right),$
(8)

and for accelerated ones devolder2014first ; dvinskikh2020accelerated

$f(x_{k})-f(x_{*})=O\left(\min\left\\{\frac{LR^{2}}{k^{2}}+k\delta,LR^{2}\exp\left(-\sqrt{\frac{\mu}{L}}\frac{k}{2}\right)+\sqrt{\frac{L}{\mu}}\delta\right\\}\right),$
(9)

where $R=\|x_{start}-x_{*}\|_{2}$ – the distance between starting point and
the solution $x_{*}$. If $x_{*}$ is not unique we take such $x_{*}$ that is
the closest to $x_{start}$. Both of these bounds are unimprovable
devolder2014first ; devolder2013first . See also devolder2013exactness ;
dvurechensky2016stochastic ; kamzolov2020universal  for “indermediate”
situations between accelerated and non-accelerated methods.

Following to devolder2013first  we may reduce conception (2) to (2) by putting

$\delta=\delta_{\eqref{inexact_model_1}}=\frac{\delta_{\eqref{inexact}}^{2}}{2L}+\frac{\delta_{\eqref{inexact}}^{2}}{\mu}\simeq\frac{\delta_{\eqref{inexact}}^{2}}{\mu}$
(10)

and changing 2-times constant $\mu,L$. The key observations here are

$\langle\tilde{\nabla}f(x)-\nabla
f(x),y-x\rangle\leq\frac{1}{2L}\|\tilde{\nabla}f(x)-\nabla
f(x)\|_{2}^{2}+\frac{L}{2}\|y-x\|_{2}^{2},$ $\langle\tilde{\nabla}f(x)-\nabla
f(x),y-x\rangle\geq\frac{1}{\mu}\|\tilde{\nabla}f(x)-\nabla
f(x)\|_{2}^{2}-\frac{\mu}{4}\|y-x\|_{2}^{2}.$

So, when $\mu>0$ for non-accelerated methods this result is almost the same as
we’ve obtained by considering example (4). To reach
$f(x_{k})-f(x_{*})=\varepsilon$ when†††If $\mu\lesssim\varepsilon$, we can
regularize the problem and guarantee the required condition gasnikov2017modern
. Another advantage of strong convexity is possibility to use the norm of
inexact gradient for the stopping criteria gasnikov2017modern , like in
poljak1981iterative . But regularization requires some prior knowledge about
the size of the solution gasnikov2017modern . Since we typically don not have
such information the procedure becomes more difficult via applying the
restarts gasnikov2016efficient ; gasnikov2017modern . $\mu\gtrsim\varepsilon$
we should put $\delta_{\eqref{inexact}}\sim\varepsilon$ that is good and
rather expected. Unfortunately, for accelerated methods from this approach we
will have $\delta_{\eqref{inexact}}\sim\varepsilon^{3/2}$. That is far from
what we’ve declared in section 1. To improve this it’s worth to propose more
detailed conception rather then (2).

In the following works devolder2014first ; dvinskikh2019decentralized ;
dvinskikh2020accelerated ; stonyakin2020inexact ; stonyakin2020adaptive  the
conception (2) was further developed

$\displaystyle
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|_{2}^{2}-\delta_{1}\|y-x\|_{2}\leq
f(y)$ $\displaystyle\hskip 85.35826pt\leq
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{L}{2}\|y-x\|_{2}^{2}+\delta_{2}.$
(11)

In this case (8) and (9) take a form for non-accelerated gradient methods

$\displaystyle f(x_{k})-f(x_{*})$
$\displaystyle=O\left(\min\left\\{\frac{LR^{2}}{k}+\tilde{R}\delta_{1}+\delta_{2},LR^{2}\exp\left(-\frac{\mu}{L}k\right)+\tilde{R}\delta_{1}+\delta_{2}\right\\}\right),$
(12)

and for accelerated ones devolder2014first ; dvinskikh2020accelerated

$\displaystyle f(x_{k})-f(x_{*})$
$\displaystyle=O\left(\min\left\\{\frac{LR^{2}}{k^{2}}+\tilde{R}\delta_{1}+k\delta_{2},LR^{2}\exp\left(-\sqrt{\frac{\mu}{L}}\frac{k}{2}\right)+\tilde{R}\delta_{1}+\sqrt{\frac{L}{\mu}}\delta_{2}\right\\}\right),$
(13)

where $\tilde{R}$ is the maximal distance between generated points and the
solution.

Thus from (2), (2) we may conclude that if $\tilde{R}$ is bounded,‡‡‡In many
situations this is true. For example, when $Q$ is bounded, when
$\mu\gg\varepsilon$. then by choosing

$\delta_{1}=\delta_{\eqref{inexact}},\delta_{2}=\frac{\delta_{\eqref{inexact}}^{2}}{2L},$

we will have the desired result: it is possible to reach
$f(x_{k})-f(x_{*})=\varepsilon$ with
$\delta_{\eqref{inexact}}\sim\varepsilon$.

But in general situation there is a problem in the assumption “if $\tilde{R}$
is bounded”. As we may see from example (4) in general degenerate regime only
such bound

$\tilde{R}\simeq R+\frac{\delta_{\eqref{inexact}}}{\mu}\gtrsim
R+\frac{\delta_{\eqref{inexact}}}{\varepsilon}$

takes place gasnikov2017modern . This dependence spoils the result. The growth
of $\tilde{R}$ we observe in different experiments. In the paper below we
investigate this problem. In particular, we propose an alternative approach to
regularization§§§By using regularization we can guarantee $\mu\sim\varepsilon$
and therefore with $\delta_{\eqref{inexact}}\sim\varepsilon$ we have the
desired $\tilde{R}\simeq R$. that is based on “early stopping”¶¶¶This
terminology is popular also in Machine Learning community, where “early
stopping” is used also as alternative to regularization to prevent overfitting
goodfellow2016deep . of considered iterative procedure by developing proper
stopping rule.

Now we explain how to reduce relative inexactness (3) to (2) and to apply (9)
when $\mu\gg\varepsilon$. Since $f(x)$ has Lipschitz gradient from (3), (2) we
may derive that after $k$ iterations (where $k$ is greater than $\sqrt{L/\mu}$
on a logarithmic factor $\log\left(LR^{2}/\varepsilon\right)$, where
$\varepsilon$ – accuracy in function value)

$\displaystyle
f(x_{k})-f(x_{*})\stackrel{{\scriptstyle\eqref{convergenceA},\eqref{deltamu}}}{{\simeq}}\frac{\varepsilon}{2}+\sqrt{\frac{L}{\mu}}\frac{\delta_{\eqref{inexact}}^{2}}{\mu}\simeq\sqrt{\frac{L}{\mu}}\frac{\delta_{\eqref{inexact}}^{2}}{\mu}$
$\displaystyle\stackrel{{\scriptstyle\eqref{relative_inexact},\eqref{inexact_model_1}}}{{\simeq}}\sqrt{\frac{L}{\mu}}\frac{\alpha^{2}\max_{t=1,...,k}\|\nabla
f(x_{t})\|_{2}^{2}}{\mu}\leq\sqrt{\frac{L}{\mu}}\frac{2L\alpha^{2}\max_{t=1,...,k}(f(x_{k})-f(x_{*}))}{\mu}$
$\displaystyle\lesssim\sqrt{\frac{L}{\mu}}\frac{4L\alpha^{2}\left(f(x_{0})-f(x_{*})\right)}{\mu}.$
(14)

To guarantee that (restart condition)

$f(x_{k})-f(x_{*})\leq\frac{1}{2}\left(f(x_{0})-f(x_{*})\right)$

we should have $\alpha\lesssim\left(\frac{\mu}{L}\right)^{5/4}$. Then we
restart the method. After $\log\left(\Delta f/\varepsilon\right)$ restarts we
can guarantee the desired $\varepsilon$-accuracy in function value. In
degenerate case the calculations are more tricky, but the idea remains the
same with the replacing $\sqrt{L/\mu}$ to $k$ (see (9)) that lead to
$\alpha_{k}\lesssim\left(\frac{1}{k}\right)^{5/2}$. More accurate analysis in
the subsequent part of the paper allows to improve these bounds:

$\alpha\lesssim\left(\frac{\mu}{L}\right)^{3/4}$,
$\alpha_{k}\lesssim\left(\frac{1}{k}\right)^{3/2}$.

Below we’ll concentrate only on accelerated method and choose the method with
one projection (Similar Triangles Method (STM)), see gasnikov2018universal ;
cohen2018acceleration ; gorbunov2019optimal ; stonyakin2020inexact ;
dvurechensky2021first  and reference there in. We decided to choose this
method because: 1) it’s primal-dual gasnikov2018universal ; 2) has a nice
theory of how to bound $\tilde{R}$ in no noise regime gasnikov2018universal ;
nesterov2018lectures  ($\tilde{R}\leq R$) and noise one gorbunov2019optimal ;
3) and has previously been intensively investigated, see dvurechensky2021first
and references there in.

##  3 Some motivation for inexact gradients

In this section we describe only two directions where inexact gradient play an
important role. We emphasise that although the results below are not new, the
way they are presented is of some value in our opinion and can be useful for
specialist in these directions.

###  3.1 Gradient-free methods

In this section we consider convex optimization problem:

$\min_{x\in Q\subseteq\mathbb{R}^{n}}f(x).$

In some applications we do not have an access to gradient $\nabla f(x)$ of
target function, but can calculate the value of∥∥∥Note, that the approach
describe above required that function values should be available not only in
$Q$, but also in some (depends on approach we used) vicinity of $Q$. This
problem can be solved in a two different ways. The first one is “margins
inward approach” beznosikov2020gradient . The second one is “continuation” $f$
to $\mathbb{R}^{n}$ with preserving of convexity and Lipschitz continuity
risteski2016algorithms :
$f_{new}(x):=f\left(\text{proj}_{Q}(x)\right)+\alpha\min_{y\in Q}\|x-y\|_{2}$.
$f(x)$ with accuracy $\delta_{f}$ conn2009introduction :

$|\tilde{f}(x)-f(x)|\leq\delta_{f}.$

In this case there exist different conceptions for full gradient estimation
(see berahas2019theoretical  and references there in). For example (below we
assuming that $f$ has $L_{p}$-Lipschitz $p$-order derivatives in 2-norm),

  * •

($p$-order finite-differences)

$\tilde{\nabla}_{i}f(x)=\frac{\tilde{f}(x+he_{i})-\tilde{f}(x-he_{i})}{2h}\text{
for }p=2,$

where $e_{i}$ is $i$-th ort. Here we have

$\delta=\sqrt{n}O\left(L_{p}h^{p}+\frac{\delta_{f}}{h}\right)$

in the conception (2), see berahas2019theoretical . Optimal choice of $h$
guarantees $\delta\sim\sqrt{n}\delta_{f}^{\frac{p}{p+1}}$. From section 1 we
know that it is possible to solve the problem with accuracy (in function
value) $\varepsilon\sim\delta$. Hence,

$\delta_{f}\sim\left(\frac{\varepsilon}{\sqrt{n}}\right)^{\frac{p+1}{p}}.$

Unfortunately, such simple idea does not give tight lower bound in the class
of algorithm that has sample complexity $\text{Poly}(n,\frac{1}{\varepsilon})$
risteski2016algorithms  (obtained for $p=0$, that is only Lipschitz-continuity
of $f$ required):

$\delta_{f}\sim\max\left\\{\frac{\varepsilon^{2}}{\sqrt{n}},\frac{\varepsilon}{n}\right\\}.$
(15)

Note, that instead of finite-difference approximation approach in some
applications we can use kernel approach polyak1990optimal ; bach16highly-
smooth . The interest to this alternative has grown last time
akhavan2020exploiting ; novitskii2021improved .

  * •

(Gaussian Smoothed Gradients)

$\tilde{\nabla}f(x)=\frac{1}{h}\mathbb{E}{\tilde{f}(x+he)e},$

where $e\in N(0,I_{n})$ is standard normal random vector. Here we have

$\delta=O\left(n^{p/2}L_{p}h^{p}+\frac{\sqrt{n}\delta_{f}}{h}\right)$

in the conception (2), see nesterov2017random ; berahas2019theoretical .
Optimal choice of $h$ guarantees
$\delta\sim\left(n\delta_{f}\right)^{\frac{p}{p+1}}$. Hence,

$\delta_{f}\sim\frac{\varepsilon^{\frac{p+1}{p}}}{n}.$

That is also does not match the lower bound. Moreover, here (and in the
approach below) we have additional difficulty: how to estimate $\tilde{f}(x)$.
We can do it only roughly, for example, by using Monte Carlo approach
berahas2019theoretical . This is a payment for the better quality of
approximation!

  * •

(Sphere Smoothed Gradients)

$\tilde{\nabla}f(x)=\frac{n}{h}\mathbb{E}{\tilde{f}(x+he)e},$

where $e$ is random vector with uniform distribution in a unit sphere (with
center at $0$) in $\mathbb{R}^{n}$. Here we have

$\delta=O\left(L_{p}h^{p}+\frac{n\delta_{f}}{h}\right)$

in the conception (2), see berahas2019theoretical . Optimal choice of $h$
guarantees $\delta\sim\left(n\delta_{f}\right)^{\frac{p}{p+1}}$. Hence,

$\delta_{f}\sim\frac{\varepsilon^{\frac{p+1}{p}}}{n}.$

That is also does not match the lower bound. One can consider that the last
two approach are almost the same, but below we describe more accurate result
concerning Sphere smoothing. We do not know how to obtain such a result for
Gaussian smoothing. The results is as follows devolder2014first ;
risteski2016algorithms : For Sphere smoothed gradient in conception (2) we
have

$\delta\simeq 2L_{0}h+\frac{\sqrt{n}\delta_{f}\tilde{R}}{h},$ (16)

where $L_{0}$ is Lipschitz constant of $f$ and
$L=\min\left\\{L_{1},\frac{7L_{0}^{2}}{h}\right\\}$ in (2), when $p=1$ and
$L=\frac{7L_{0}^{2}}{h}$, when $p=0$. The bound (16) is more accurate than the
previous ones, since it corresponds to the first part of the lower bound (15).
Indeed, by choosing properly $h$ in (16) we obtain $\varepsilon\sim\delta\sim
n^{1/4}\delta_{f}^{1/2}$. Hence,

$\delta_{f}\sim\frac{\varepsilon^{2}}{\sqrt{n}}.$

The rest part ($\delta_{f}\sim\frac{\varepsilon}{n}$) of lower bound (15) is
also tight, see belloni2015escaping .

The last calculations (see (16)) additionally confirm that the conception of
inexactness and algorithms we use and develop in section 2 are also tight
(optimal) enough. Otherwise, it’d be hardly possible to reach lower bound by
using gradient-free methods reduction to gradient ones and proposed analysis
of an error accumulation for gradient-type methods.

###  3.2 Inverse problems

Another rather big direction of research where gradients are typically
available only approximately is optimization in a Hilbert spaces
vasilyev2002optimization . Such optimization problems arise, in particular, in
inverse problems theory kabanikhin2011inverse .

We start with the reminder of how to calculate a derivative in general Hilbert
space. Let

$J(q):=J(q,u(q)),$

where $u(q)$ is determine as unique solution of

$G(q,u)=0.$

Assume that $G_{q}(q,u)$ is invertible, then

$G_{q}(q,u)+G_{u}(q,u)\nabla u(q)=0,$

hence

$\nabla u(q)=-\left[G_{u}(q,u)\right]^{-1}G_{q}(q,u).$

Therefore

$\nabla J(q):=J_{q}(q,u)+J_{u}(q,u)\nabla
u(q)=J_{q}(q,u)-J_{u}(q,u)\left[G_{u}(q,u)\right]^{-1}G_{q}(q,u).$

The same result could be obtained by considering Lagrange functional

$L(q,u;\psi)=J(q,u(q))+\langle\psi,G(q,u)\rangle$

with

$L_{u}(q,u;\psi)=0,G_{q}(q,u)=0$

and

$\nabla J(q)=L_{q}(q,u;\psi).$

Indeed, by simple calculations we can relate these two approaches, where

$\psi(q,u)=-\left[G_{u}(q,u)^{T}\right]^{-1}J_{u}(q,u)^{T}.$

Now we demonstrate this technique on inverse problem for elliptic initial-
boundary value problem.

Let $u$ be the solution of the following problem (P)

$u_{xx}+u_{yy}=0,\quad x,y\in\left({0,1}\right),$
$u\left({1,y}\right)=q\left(y\right),\quad y\in\left({0,1}\right),$
$u_{x}\left({0,y}\right)=0,\quad y\in\left({0,1}\right),$
$u\left({x,0}\right)=u\left({x,1}\right)=0,\quad x\in\left({0,1}\right).$

The first two relations

$-u_{xx}-u_{yy}=0,\quad x,y\in\left({0,1}\right),$
$q\left(y\right)-u\left({1,y}\right)=0,\quad y\in\left({0,1}\right),$

we denote as $G(q,u)=\bar{G}\cdot(q,u)=0$ and the last two ones as $u\in Q$.

Assume that we want to estimate $q(y)\in L_{2}(0,1)$ by observing
$b(y)=u(0,y)\in L_{2}(0,1)$, where $u(x,y)\in
L_{2}\left((0,1)\times(0,1)\right)$ is the (unique) solution of (P)
kabanikhin2011inverse . This is an inverse problem. We can reduce this problem
to optimization one kabanikhin2011inverse :

$\min_{q}\mathfrak{J}(q):=\min_{u:\text{ }\bar{G}\cdot(q,u)=0,u\in
Q}J(q,u):=J(u)=\int_{0}^{1}|u(0,y)-b(y)|^{2}dy.$ (17)

We can solve (17) numerically. This problem is convex quadratic optimization
problem. We can directly apply Lagrange multipliers principle to (17), see
vasilyev2002optimization :

$L\left(q,u;\psi:=\left(\psi(x,y),\lambda(y)\right)\right)=J(u)+\langle\psi,\bar{G}\cdot(q,u)\rangle=\int_{0}^{1}|u(0,y)-b(y)|^{2}dy-\\\
\int_{0}^{1}\int_{0}^{1}\left(u_{xx}+u_{yy}\right)\psi(x,y)dxdy+\int_{0}^{1}\left(q(y)-u(1,y)\right)\lambda(y)dy.$

To obtain conjugate problem for $\psi$ we should vary $L\left(q,u;\psi\right)$
on $\delta u$ satisfying $u\in Q$:

$\delta_{u}L\left(q,u;\psi\right)=2\int_{0}^{1}\left(u(0,y)-b(y)\right)\delta
u(0,y)dy-\\\ \int_{0}^{1}\int_{0}^{1}\left(\delta u_{xx}+\delta
u_{yy}\right)\psi(x,y)dxdy-\int_{0}^{1}\delta u(1,y)\lambda(y)dy,$ (18)

where

$\delta u_{x}\left({0,y}\right)=0,\quad y\in\left({0,1}\right),$ $\delta
u\left({x,0}\right)=\delta u\left({x,1}\right)=0,\quad
x\in\left({0,1}\right).$

Using integration by part, from (18) we can derive

$\delta_{u}L\left(q,u;\psi\right)=\int_{0}^{1}\left(2\left(u(0,y)-b(y)\right)-\psi_{x}(0,y)\right)\delta
u(0,y)dy-\\\ \int_{0}^{1}\psi(1,y)\delta
u_{x}(1,y)dy-\int_{0}^{1}\psi(x,1)\delta
u_{y}(x,1)dx+\int_{0}^{1}\psi(x,0)\delta u_{y}(x,0)dy+\\\
\int_{0}^{1}\int_{0}^{1}\left(\psi_{xx}+\psi_{yy}\right)\delta
u(x,y)dxdy+\int_{0}^{1}\left(\psi_{x}(1,y)-\lambda(y)\right)\delta u(1,y)dy.$

Consider corresponding conjugate problem (D)

$\psi_{xx}+\psi_{yy}=0,\quad x,y\in\left({0,1}\right),$
$\psi_{x}\left({0,y}\right)=2\left(u(0,y)-b(y)\right),\quad
y\in\left({0,1}\right),$ $\psi\left({1,y}\right)=0,\quad
y\in\left({0,1}\right),$
$\psi\left({x,0}\right)=\psi\left({x,1}\right)=0,\quad x\in\left({0,1}\right)$

and additional relation between Lagrange multipliers

$\lambda(y)=\psi_{x}(1,y),\quad y\in\left({0,1}\right).$ (19)

These relations appears since $\delta_{u}L\left(q,u;\psi\right)=0$ and $\delta
u(0,y),\delta u_{x}(1,y),\delta u(1,y)\in L_{2}(0,1)$; $\delta
u_{y}(x,1),\delta u_{y}(x,0)\in L_{2}(0,1)$; $\delta u(x,y)\in
L_{2}\left((0,1)\times(0,1)\right)$ are arbitrary.

Since rockafellar1970convex

$\mathfrak{J}(q)=\min_{u:(q,u)\in(P)}J(u)=\min_{u:\text{
}\bar{G}\cdot(q,u)=0,u\in Q}J(u)=\min_{u\in Q}\max_{\psi\in(D)}L(q,u;\psi),$

from the Demyanov–Danskin’s formula rockafellar1970convex ******The same
result in more simple situation (without additional constraint $u\in Q$) we
consider at the beginning of this section. We don’t apply Demyanov–Danskin’s
formula and use inverse function theorem.

$\nabla\mathfrak{J}(q)=\nabla_{q}\min_{u\in
Q}\max_{\psi\in(D)}L(q,u;\psi)=L_{q}(q,u(q);\psi(q)),$

where $u(q)$ is the solution of (P) and $\psi(q)$ is the solution of (D) where

$\psi_{x}\left({0,y}\right)=2\left(u(0,y)-b(y)\right),\quad
y\in\left({0,1}\right)$

and $u(0,y)$ depends on $q(y)$ via (P) and, at the same time, the pair
$\left(u(q),\psi(q)\right)$ is the solution of

$\min_{u\in Q}\max_{\psi\in(D)}L(q,u;\psi)$

saddle-point problem. Since $\delta_{\psi}L(q,u;\psi)=0$ entails
$\bar{G}\cdot(q,u)=0$ that is form (P) if we add $u\in Q$ and
$\delta_{u}L_{(}q,u;\psi)=0$, when $u\in Q$ entails (D) as we’ve shown above.

Note also that

$L_{q}(q,u(q);\psi(q))(y)=\lambda(y),\quad y\in\left({0,1}\right).$

Hence, due to (19)

$\nabla\mathfrak{J}(q)(y)=\psi_{x}(1,y),\quad y\in\left({0,1}\right)$

So we reduce $\nabla\mathfrak{J}(q)(y)$ calculation to the solution of two
correct initial-boundary value problem for elliptic equation in a square (P)
and (D) kabanikhin2011inverse .

This result can be also interpreted in a little bit different manner. We
introduce a linear operator

$A:\quad q(y):=u(1,y)\mapsto u(0,y).$

Here $u(x,y)$ is the solution of problem (P). It was shown in
kabanikhin2011inverse  that

$A:L_{2}(0,1)\rightarrow L_{2}(0,1).$

Conjugate operator is kabanikhin2011inverse

$A^{\ast}:\quad p(y):=\psi_{x}(0,y)\mapsto\psi_{x}(1,y),\qquad
A^{\ast}:L_{2}(0,1)\rightarrow L_{2}(0,1).$

Here $\psi(x,y)$ is the solution of conjugate problem (D). So, by considering

$\mathfrak{J}(q)(y)=\|Aq-b\|_{2}^{2},$

we can write

$\nabla\mathfrak{J}(q)(y)=A^{\ast}\left(2\left(Aq-b\right)\right),$

that completely corresponds to the same scheme as described above:

1. Based on $q(y)$ we solve (P) and obtain $u(0,y)=Aq(y)$ and define $p(y)=2\left(u(0,y)-b(y)\right)$.

2. Based on $p(y)$ we solve (D) and calculate $\nabla\mathfrak{J}(q)(y)=A^{\ast}p(y)=\psi_{x}(1,y)$.

So inexactness in gradient $\nabla\mathfrak{J}(q)$ arises since we can solve
(P) and (D) only numerically.

The described above technique can be applied to many different inverse
problems kabanikhin2011inverse  and optimal control problems
vasilyev2002optimization . Note that for optimal control problems in practice
another strategy widely used. Namely, instead of approximate calculation of
gradient, optimization problem replaced by approximate one (for example, by
using finite-differences schemes). For this reduced (finite-dimensional)
problem the gradient is typically available precisely
evtushenko2013optimization . Moreover, in evtushenko2013optimization  the
described above Lagrangian approach is based to explain the core of automatic
differentiation where the function calculation tree represented as system of
explicitly solvable interlocking equations.

##  4 Basic assumptions and problem description

We consider convex optimization problem on a convex (not necessarily bounded)
set $Q\subseteq\mathbb{R}^{n}$:

$\min\limits_{x\in Q}f(x).$

Assume that

$\|\tilde{\nabla}f(x)-\nabla{f(x)}\|_{2}\leqslant\delta,$ (20)

where $\tilde{\nabla}f(x)$ oracle gradient value. We consider two cases: $Q$
is a compact set and $Q$ is unbounded, for example $\mathbb{R}^{n}$. We define
the constant:

$R=\|x_{start}-x^{*}\|_{2}$

to be the distance between the solution $x^{*}$ and starting point
$x_{start}$, if $x^{*}$ is not unique we take such $x^{*}$ that is the closest
to $x_{start}$. We assume that function $f$ has Lipschitz gradient with
constant $L_{f}$:

$\forall x,y\in Q,\;\|\nabla f(x)-\nabla f(y)\|_{2}\leqslant
L_{f}\|x-y\|_{2}.$ (21)

This implies inequality:

$\forall x,y\in Q,\;f(y)\leqslant f(x)+\langle\nabla
f(x),y-x\rangle+\frac{L_{f}}{2}\|x-y\|_{2}^{2}.$ (22)

We will use following lemma:

######  Lemma 1 (Fenchel inequality)

Let $\;(\mathcal{E},\langle\cdot,\cdot\rangle)$ – euclidean space, then
$\forall\lambda\in\mathbb{R}_{+},\forall u,v\in\mathcal{E}$ the inequality
holds:

$\langle
u,v\rangle\leqslant\frac{1}{2\lambda}\|u\|^{2}_{\mathcal{E}}+\frac{\lambda}{2}\|v\|^{2}_{\mathcal{E}}.$

From previous assumptions we can get upper bound with inexact oracle.

###### Claim

$\forall x,y\in Q,$ the following estimate holds:

$f(y)\leqslant
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{L}{2}\|x-y\|_{2}^{2}+\delta_{2},$

where $L=2L_{f},\delta_{2}=\frac{\delta^{2}}{2L_{f}}$.

###### Proof

The proof follows from

$f(y)\leqslant f(x)+\langle\nabla
f(x),y-x\rangle+\frac{L_{f}}{2}\|x-y\|_{2}^{2}\leqslant\\\ \leqslant
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{1}{2L_{f}}\|\nabla
f(x)-\tilde{\nabla}f(x)\|_{2}^{2}+\frac{L_{f}}{2}\|x-y\|_{2}^{2}+\frac{L_{f}}{2}\|x-y\|_{2}^{2}\leqslant\\\
\leqslant
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{L}{2}\|x-y\|_{2}^{2}+\delta_{2}.$

We also assume strong convexity of $f$ with parameter $\mu$, however $\mu$ may
equal zero – this corresponds to the ordinary convexity, supposed initially.
Further we will use only a consequence of this:

$f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}\leqslant
f(y).$ (23)

We obtain similar to claim 4 two lower bounds with inexact oracle.

###### Claim

$\forall x,y\in Q$, the following estimate holds:

$f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}-\delta_{1}\|x-y\|_{2}\leqslant
f(y),$

where $\delta_{1}=\delta$.

###### Proof

Using Cauchy inequality and (23) we obtain:

$f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}-\delta_{1}\|x-y\|_{2}\leqslant
f(x)+\\\
+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}-\|\tilde{\nabla}f(x)-\nabla
f(x)\|_{2}\|x-y\|_{2}\leqslant\\\ \leqslant
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}-\\\
-\langle\tilde{\nabla}f(x)-\nabla f(x),y-x\rangle=f(x)+\langle\nabla
f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}\leqslant f(y)\Rightarrow\\\
f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{2}\|x-y\|_{2}^{2}-\delta_{1}\|x-y\|_{2}\leqslant
f(y).$

###### Claim

$\forall x,y\in Q$, if in (23) $\mu\not=0$, the following estimate holds,

$f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{4}\|y-x\|_{2}^{2}-\delta_{3}\leqslant
f(y),$

where $\delta_{3}=\frac{\delta^{2}}{\mu}$.

###### Proof

Trivial calculations bring

$f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{4}\|x-y\|_{2}^{2}-\delta_{3}=f(x)+\langle\nabla
f(x),y-x\rangle+\\\ +\langle\tilde{\nabla}f(x)-\nabla
f(x),y-x\rangle+\frac{\mu}{4}\|x-y\|_{2}^{2}-\delta_{3}.$

Using lemma 1 we obtain:

$f(x)+\langle\tilde{\nabla}f(x),y-x\rangle+\frac{\mu}{4}\|x-y\|_{2}^{2}-\delta_{3}\leqslant
f(x)+\\\ +\langle\nabla
f(x),y-x\rangle+\frac{\delta^{2}}{\mu}+\frac{\mu}{4}\|x-y\|_{2}^{2}+\frac{\mu}{4}\|y-x\|_{2}^{2}-\delta_{3}=\\\
=f(x)+\langle\nabla f(x),y-x\rangle+\frac{\mu}{2}\|y-x\|_{2}^{2}\leqslant
f(y).$

The last two inequalities give different results in convergence under certain
conditions. We will study two models based on statements 4, 4 and we will
denote them by the index $\boldsymbol{\tau}$, that is denote:

$\begin{gathered}\mu_{1}=\mu,\\\ \mu_{2}=\frac{\mu}{2}.\end{gathered}$ (24)

Further in the text, we will use statements 4 and 4 in the notation
corresponding to $\eqref{eq2.5}$.

##  5 Similar Triangles Method and its properties

In this section we describe an accelerated method we choose to investigate
gradient-error accumulation.

Algorithm 1 $STM(L,\mu,\tau,x_{start})$, $Q\subseteq\mathbb{R}^{n}$

Input: Starting point $x_{start}$, number of steps $N$

Set $\tilde{x}_{0}=x_{start}$,

Set $A_{0}=\frac{1}{L}$,

Set $\alpha_{0}=\frac{1}{L}$,

$\psi_{0}(x)=\frac{1}{2}\|x-\tilde{x}_{0}\|_{2}^{2}+\alpha_{0}\left(f(\tilde{x}_{0})+\langle\tilde{\nabla}f(\tilde{x}_{0}),x-\tilde{x}_{0}\rangle+\frac{\mu}{2}\|x-\tilde{x}_{0}\|_{2}^{2}\right)$,

Set $z_{0}=\mathop{\arg\\!\min}_{y\in Q}{\psi_{0}(y)}$,

Set $x_{0}=z_{0}$.

for $k=1\dots N$ do

$\alpha_{k}=\frac{1+\mu_{\tau}A_{k-1}}{2L}+\sqrt{\frac{1+\mu_{\tau}A_{k-1}}{4L^{2}}+\frac{A_{k-1}}{1+\mu_{\tau}A_{k-1}}},$

$A_{k}=A_{k-1}+\alpha_{k},$

$\tilde{x}_{k}=\frac{A_{k-1}x_{k-1}+\alpha_{k}z_{k-1}}{A_{k}},$

$\psi_{k}(x)=\psi_{k-1}(x)+\alpha_{k}\left((f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),x-\tilde{x}_{k}\rangle+\frac{\mu}{2}\|x-\tilde{x}_{k}\|_{2}^{2}\right),$

$z_{k}=\mathop{\arg\\!\min}_{y\in Q}\psi_{k}(y),$

$x_{k}=\frac{A_{k-1}x_{k-1}+\alpha_{k}z_{k}}{A_{k}}.$

end for

Output: $x_{N}$.

Figure 1 describes the position of the vertices. On the sides, not their
lengths are marked, but the relationships in the corresponding sides in the
similarity of triangles. In the case $Q=\mathbb{R}^{n}$, we can simplify the
step of the algorithm by replacing it with:

$z_{k}=z_{k-1}-\frac{\alpha_{k}}{1+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}A_{k}}\mu_{\tau}}\left(\tilde{\nabla}f(\tilde{x}_{k}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+}\mu_{\tau}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\left(z_{k-1}-\tilde{x}_{k}\right)}\right).$

We define constant:

$\tilde{R}=\max\limits_{0\leqslant k\leqslant
N}\\{\|z_{k}-x^{*}\|_{2},\|x_{k}-x^{*}\|_{2},\|\tilde{x}_{k}-x^{*}\|_{2}\\}.$

We will also write down several identities that we will need in the proofs

$\begin{gathered}A_{k}(x_{k}-\tilde{x}_{k})=\alpha_{k}(z_{k}-\tilde{x}_{k})+A_{k-1}(x_{k-1}-\tilde{z}_{k}),\\\
\frac{1+\mu_{\tau}A_{k-1}}{2}\|z_{k}-z_{k-1}\|_{2}^{2}=\frac{L}{2}\|x_{k}-\tilde{x}_{k}\|_{2}^{2},\\\
A_{k-1}\|\tilde{x}_{k}-x_{k-1}\|_{2}=\alpha_{k}\|\tilde{x}_{k}-z_{k-1}\|_{2}.\end{gathered}$
(25)

Some of the identities can be obtained from geometric considerations, for
example, from a figure, others by direct substitution into the definitions of
the sequences $x_{k},\tilde{x}_{k},z_{k}$. Also very important are the
estimates for the sequence $A_{k}$.

Figure 1: Geometry of Similar Triangles method gasnikov2018universal

###### Claim

If $\mu\not=0$ and $\forall k\in\mathbb{N}$ the following inequality holds:

$A_{k}\geqslant A_{k-1}\lambda_{\mu_{\tau},L},$

where

$\theta_{\mu_{\tau},L}=\frac{\mu_{\tau}}{L},\;\lambda_{\mu_{\tau},L}=\left(1+\frac{1}{2}\theta_{\mu_{\tau},L}+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu_{\tau},L}}\right).$

###### Proof

Using the definition of the sequences $A_{k}$ and solving the quadratic
equation, we obtain:

$A_{k}(1+\mu_{\tau}A_{k-1})=L\alpha_{k}^{2}=L(A_{k}-A_{k-1})^{2}=LA_{k}^{2}-2LA_{k}A_{k-1}+LA_{k-1}\Leftrightarrow\\\
\Leftrightarrow
A_{k}^{2}-A_{k}\left(1+A_{k-1}\left(2+\theta_{\mu_{\tau},L}\right)\right)+A_{k-1}^{2}=0,\mathcal{D}=\left(1+2A_{k-1}+\theta_{\mu_{\tau},L}\right)^{2}-4A_{k}^{2}\\\
A_{k,apex}=\frac{1}{2}+\left(1+\frac{1}{2}\theta_{\mu_{\tau},L}\right)A_{k}\Rightarrow
A_{k}=\frac{1}{2}\left(\left(1+\left(2+\theta_{\mu_{\tau},L}\right)\right)A_{k-1}+\sqrt{\mathcal{D}}\right)\\\
\sqrt{\mathcal{D}}=\sqrt{1+\left(2\theta_{\mu_{\tau},L}+4\right)A_{k-1}+\left(\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu,L}\right)A_{k-1}^{2}}\geqslant
A_{k-1}\sqrt{\theta_{\mu,L}^{2}+4\theta_{\mu,L}}\Rightarrow\\\ \Rightarrow
A_{k}\geqslant\frac{1}{2}\left(2+\theta_{\mu_{\tau},L}+\sqrt{\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu_{\tau},L}}\right)A_{k-1}=\\\
=\left(1+\frac{1}{2}\theta_{\mu_{\tau},L}+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu_{\tau},L}}\right)A_{k-1}\Rightarrow\\\
\Rightarrow
A_{k}\geqslant\frac{1}{L}\lambda_{\mu_{\tau},L}^{k},\;\lambda_{\mu_{\tau},L}=\left(1+\frac{1}{2}\theta_{\mu_{\tau},L}+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu_{\tau},L}}\right).$

###### Corollary 1

$\begin{gathered}\lambda_{\mu_{\tau},L}>\left(1+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}}\right)^{2}=\left(1+\sqrt{\theta_{\mu_{\tau},L}}+\frac{1}{4}\theta_{\mu_{\tau},L}\right),\\\
\left(1+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}}\right)^{2}>e^{\frac{1}{2}\theta_{\mu_{\tau},L}}.\end{gathered}$

###### Claim

If $\mu\not=0$ $\forall k\in\mathbb{N}$ the following inequality holds:

$\frac{\displaystyle\sum_{j=0}^{k}A_{j}}{A_{k}}\leqslant
1+\sqrt{\frac{L}{\mu_{\tau}}}.$

$\lambda_{\mu_{\tau},L}=\left(1+\frac{1}{2}\theta_{\mu_{\tau},L}+\frac{1}{2}\sqrt{\theta_{\mu_{\tau},L}^{2}+4\theta_{\mu_{\tau},L}}\right),\theta_{\mu_{\tau},L}=\frac{\mu_{\tau}}{L}.$

###### Proof

Using previous claim we can reduce this amount exponentially.

$\frac{\displaystyle\sum_{j=0}^{k}A_{j}}{A_{k}}\leqslant\displaystyle\sum_{j=0}^{k}\lambda_{\mu_{\tau},L}^{-j}=\frac{\lambda_{\mu_{\tau},L}^{k+1}-1}{\lambda_{\mu_{\tau},L}^{k+1}-\lambda_{\mu_{\tau},L}^{k}}\leqslant\frac{\lambda_{\mu_{\tau},L}}{\lambda_{\mu_{\tau},L}-1}\leqslant
1+\sqrt{\frac{L}{\mu_{\tau}}}.$

###### Claim

If $\mu=0$ then:

$A_{k}\geqslant\frac{(k+1)^{2}}{4L}.$

###### Proof

If $\mu=0$ then $A_{k}=L\alpha_{k}^{2}$ and solving quadratic equation we get:

$\alpha_{k}=\frac{1+\sqrt{1+4L^{2}\alpha_{k-1}^{2}}}{2L}.$

Then by induction it is easy to get that:

$\alpha_{k}\geqslant\frac{k+1}{2L}\Rightarrow
A_{k}=La_{k}^{2}\geqslant\frac{(k+1)^{2}}{2L}.$

###### Claim

If $\mu=0$ we have:

$\frac{\displaystyle\sum_{j=0}^{k}A_{j}}{A_{k}}\leqslant k.$

###### Proof

The proof follows from the simple calculations:

$\frac{\displaystyle\sum_{j=0}^{k}A_{j}}{A_{k}}\leqslant\frac{\displaystyle\sum_{j=0}^{k}a_{j}^{2}}{a_{k}^{2}}\leqslant\frac{k\alpha_{k-1}^{2}}{\alpha_{k}^{2}}=\frac{k\alpha_{k-1}^{2}}{(\frac{1}{2L}+\sqrt{\frac{1}{4L^{2}}+\alpha_{k-1}^{2}})^{2}}\leqslant
k.$

###### Lemma 2

$\forall k\geqslant 1$ the following inequality holds:

$\psi_{k}(z_{k})\geqslant\psi_{k-1}(z_{k-1})+\frac{1+\mu_{\tau}A_{k-1}}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+\\\
+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}\right).$

###### Proof

From the definition of the $\psi_{k-1}$ function, it has a minimum at the
point $z_{k-1}$, then:

$\langle\nabla\psi_{k-1}(z_{k-1}),z_{k}-z_{k-1}\rangle\geqslant
0,\;\nabla\psi_{k-1}(z_{k-1})=\left(z_{k-1}-\tilde{x}_{0}\right)+\\\
+\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(\tilde{\nabla}f\left(\tilde{x}_{j}\right)+\mu_{\tau}\left(z_{k-1}-\tilde{x}_{j}\right)\right)\Rightarrow\\\
\Rightarrow\psi_{k}(z_{k})=\psi_{k-1}(z_{k})+\alpha_{k}\left(f\left(\tilde{x}_{k}\right)+\langle\tilde{\nabla}f\left(\tilde{x}_{k}\right),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}\right)=\\\
=\frac{1}{2}\|z_{k}-\tilde{x}_{0}\|_{2}^{2}+\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(f\left(\tilde{x}_{j}\right)+\langle\tilde{\nabla}f\left(\tilde{x}_{j}\right),z_{k}-\tilde{x}_{j}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{j}\|_{2}^{2}\right)+\\\
+\alpha_{k}\left(f\left(\tilde{x}_{k}\right)+\langle\tilde{\nabla}f\left(\tilde{x}_{k}\right),z_{k}-\tilde{x}_{k}\rangle\right)+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}.$

From $\eqref{useful_def}$ and the above we obtain:

$\psi_{k}(z_{k})\geqslant\frac{1}{2}\|z_{k-1}-\tilde{x}_{0}\|^{2}_{2}+\langle
z_{k-1}-\tilde{x}_{0},z_{k}-z_{k-1}\rangle+\frac{1}{2}\|z_{k-1}-z_{k}\|_{2}^{2}+\\\
+\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(f(\tilde{x}_{j})+\langle\tilde{\nabla}f(\tilde{x}_{j}),z_{k}-\tilde{x}_{j}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{j}\|_{2}^{2}\right)+\\\
+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|^{2}_{2}\right)=\\\
=\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(\langle\tilde{\nabla}f(\tilde{x}_{j})+\mu_{\tau}(z_{k-1}-\tilde{x}_{j}),z_{k-1}-z_{k}\rangle\right)+\\\
+\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(f(\tilde{x}_{j})+\langle\tilde{\nabla}f(\tilde{x}_{j}),z_{k}-\tilde{x}_{j}\rangle+\frac{\mu}{2}\|z_{k}-\tilde{x}_{j}\|_{2}^{2}\right)+\\\
+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}\right)+\frac{1}{2}\|z_{k-1}-\tilde{x}_{0}\|^{2}_{2}+\frac{1}{2}\|z_{k-1}-z_{k}\|_{2}^{2}.$

Using the linearity of the dot product, we split the sum by two and apply to:

$\mu_{\tau}\langle z_{k-1}-\tilde{x}_{j},z_{k-1}-z_{k}\rangle.$

Equality from $\eqref{useful_def}$, and finally get:

$\psi_{k}(z_{k})\geqslant\frac{1}{2}\|z_{k-1}-\tilde{x}_{0}\|^{2}_{2}+\frac{1+\mu_{\tau}A_{k-1}}{2}\|z_{k-1}-z_{k}\|_{2}^{2}+\\\
+\displaystyle\sum_{j=0}^{k-1}\alpha_{j}\left(f(\tilde{x}_{j})+\langle\tilde{\nabla}f(\tilde{x}_{j}),z_{k-1}-\tilde{x}_{j}\rangle+\frac{\mu_{\tau}}{2}\|z_{k-1}-\tilde{x}_{j}\|_{2}^{2}\right)+\\\
+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}\right)=\\\
=\psi_{k-1}(z_{k-1})+\frac{1+\mu_{\tau}A_{k-1}}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+\\\
+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\frac{\mu_{\tau}}{2}\|z_{k}-\tilde{x}_{k}\|_{2}^{2}\right).$

###### Remark 1

In the case $\mu=0$, we obtain a corollary from the strongly convexity of
functions $\psi_{k}$ and their definition, that is:

$\begin{gathered}\psi_{k}(z_{k})=\psi_{k-1}(z_{k})+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}{f}(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle\right)\Rightarrow\\\
\psi_{k}(z_{k})\geqslant\psi_{k-1}(z_{k-1})+\frac{1}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}{f}(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle\right).\end{gathered}$

##  6 Main results

Here we will describe some results based on the previously presented lemmas
and statements.

###  6.1 Additive noise and main theorems.

###### Theorem 6.1

$\forall k\in\mathbb{N}$ the following inequality holds:

$A_{k}f(x_{k})\leqslant\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k}.$

###### Proof

Base, $k$ = 0:

$f(x_{0})\leqslant
f(\tilde{x}_{0})+\langle\tilde{\nabla}f(\tilde{x}_{0}),x_{0}-\tilde{x}_{0}\rangle+\frac{L}{2}\|x_{0}-\tilde{x}_{0}\|_{2}^{2}+\delta_{2}\leqslant\\\
\leqslant
L\psi_{0}(z_{0})-\frac{L\mu}{2}\|z_{0}-\tilde{x}_{0}\|_{2}^{2}+\delta_{2}\leqslant
L\psi_{0}(z_{0})+\delta_{2}.$

Induction step:

$A_{k}f(x_{k})-A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}\leqslant\\\
\leqslant
A_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),x_{k}-\tilde{x}_{k}\rangle+\frac{L}{2}\|x_{k}-\tilde{x}_{k}\|_{2}^{2}+\delta_{2}\right)-A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}.$

Using equations $\eqref{useful_def}$ we obtain:

$A_{k}f(x_{k})-A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}\leqslant\\\
\leqslant
A_{k-1}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),x_{k-1}-\tilde{x}_{k}\rangle\right)+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle\right)+\\\
+\frac{(1+\mu_{1}A_{k-1})}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+A_{k}\delta_{2}-A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}\leqslant\\\
\leqslant
A_{k-1}f(x_{k-1})+\alpha_{k}(f(\tilde{x}_{k})\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle+\\\
+\frac{1+\mu_{1}A_{k-1}}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+A_{k}\delta_{2}.$

Using the induction hypothesis, we obtain:

$A_{k}f(x_{k})-A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}\leqslant\psi_{k-1}(z_{k-1})+\delta_{2}\displaystyle\sum_{j=0}^{k-1}A_{j}+2\tilde{R}\delta_{1}A_{k-1}+\\\
+\frac{1+\mu_{1}A_{k-1}}{2}\|z_{k}-z_{k-1}\|_{2}^{2}+\alpha_{k}\left(f(\tilde{x}_{k})+\langle\tilde{\nabla}f(\tilde{x}_{k}),z_{k}-\tilde{x}_{k}\rangle\right)+A_{k}\delta_{2}.$

Using lemma 2 we can get:

$A_{k}f(x_{k})\leqslant
A_{k-1}\delta_{1}\|x_{k-1}-\tilde{x}_{k}\|_{2}+\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k-1}=\\\
=\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k-1}+\alpha_{k}\|\tilde{x}_{k}-z_{k-1}\|_{2}\leqslant\\\
\leqslant\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k-1}+\alpha_{k}\left(\|z_{k-1}-x^{*}\|_{2}+\|\tilde{x}_{k}-x^{*}\|_{2}\right)\delta_{1}\leqslant\\\
\leqslant\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k-1}+2\alpha_{k}\tilde{R}\Rightarrow\\\
\Rightarrow
A_{k}f(x_{k})\leqslant\psi(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+2\tilde{R}\delta_{1}A_{k}.$

###### Remark 2

We should note that this inequality is true both in the case of $\mu\not=0$
and in the case of $\mu=0$.

###### Theorem 6.2

If $\mu\not=0$ $\forall k\in\mathbb{N}$ the following inequality holds:

$A_{k}f(x_{k})\leqslant\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+\delta_{3}\displaystyle\sum_{j=0}^{k-1}A_{j}$

The proof repeats verbatim theorem 6.1, except for claim 4, replaced by claim
4.

###### Theorem 6.3

If $\;\;\delta_{1}=\delta_{2}=\delta_{3}=0$ then $\tilde{R}=R$.

###### Proof

Using theorem 6.1 we get $\;A_{k}f(x_{k})\leqslant\psi_{k}(z_{k})$ then:

$\frac{1}{2}\|z_{k}-x^{*}\|_{2}^{2}=\frac{1}{2}\|z_{k}-x^{*}\|_{2}^{2}+A_{k}f(x_{k})-A_{k}f(x_{k})\leqslant\\\
\leqslant\psi_{k}(z_{k})+\frac{1}{2}\|z_{k}-x^{*}\|_{2}^{2}-A_{k}f(x_{k})\leqslant\displaystyle\sum_{j=0}^{k}\alpha_{j}(f(\tilde{x}_{j})+\langle\nabla
f(\tilde{x}_{k}),x^{*}-\tilde{x}_{k}\rangle+\\\
+\frac{\mu}{2}\|x^{*}-x_{k}\|_{2}^{2})+\frac{1}{2}\|x^{*}-\tilde{x}_{0}\|_{2}^{2}\leqslant
A_{k}f(x_{k})-A_{k}f(x_{k})+\frac{1}{2}\|x_{0}-x^{*}\|_{2}^{2}=\frac{1}{2}R^{2}.$

We now prove bound for the sequence $x_{k}$, similarly for $\tilde{x}_{k}$. We
prove by induction, so assume fairness for $k-1$, base is obvious.

$\|x_{k}-x^{*}\|_{2}^{2}=\|\frac{A_{k-1}}{A_{k}}(x_{k-1}-x^{*})+\frac{\alpha_{k}}{A_{k}}(z_{k}-x^{*})\|_{2}^{2}\leqslant\\\
\leqslant\frac{A_{k-1}}{A_{k}}\|x_{k-1}-x^{*}\|_{2}^{2}+\frac{\alpha_{k}}{A_{k}}\|z_{k}-x^{*}\|_{2}^{2}=R^{2}.$

######  Theorem 6.4 (convergence in function)

Both inequalities take place with $\mu\not=0$

$\begin{gathered}f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp\left({{-\frac{1}{2}\sqrt{\frac{\mu}{L}}N}}\right)+\left(1+\sqrt{{\frac{L}{\mu_{1}}}}\right)\delta_{2}+3\tilde{R}\delta_{1},\\\
f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp{\left(-\frac{1}{2}\sqrt{\frac{\mu}{2L}}N\right)}+\left(1+\sqrt{{\frac{L}{\mu_{2}}}}\right)\delta_{2}+\left(1+\sqrt{\frac{L}{\mu_{2}}}\right)\delta_{3}.\\\
\end{gathered}$

###### Proof

Using, all of the above is easy to show what is required, the proof of both
convergence is the same with the replacement of theorem 6.1 by theorem 6.2 and
replacement claim 4 by claim 4, therefore, we present only the proof of the
first inequality.

$A_{N}f(x_{N})\leqslant\psi_{N}(z_{N})+\delta_{2}\displaystyle\sum_{j=0}^{N}A_{j}+2\tilde{R}\delta_{1}A_{N}\leqslant\frac{1}{2}\|x^{*}-\tilde{x}_{0}\|_{2}^{2}+\\\
+\delta_{2}\displaystyle\sum_{j=0}^{N}A_{j}+2\tilde{R}\delta_{1}A_{N}+\displaystyle\sum_{j=0}^{N}\alpha_{k}(f(\tilde{x}_{j})+\langle\tilde{\nabla}f(\tilde{x}_{j}),x^{*}-\tilde{x}_{j}\rangle+\frac{\mu_{1}}{2}\|x^{*}-x_{i}\|_{2}^{2})\leqslant\\\
\leqslant\delta_{2}\displaystyle\sum_{j=0}^{N}A_{j}+2\tilde{R}\delta_{1}A_{N}+\displaystyle\sum_{j=0}^{N}\alpha_{k}(\tilde{R}\delta_{1}+f(x^{*}))+\frac{1}{2}R^{2}=\\\
=\delta_{2}\displaystyle\sum_{j=0}^{N}A_{j}+3\tilde{R}\delta_{1}A_{N}+A_{N}f(x^{*})+\frac{1}{2}R^{2}\Longleftrightarrow\\\
\Longleftrightarrow f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp{\left(-\frac{1}{2}\sqrt{\frac{\mu}{L}}N\right)}+\left(1+\sqrt{{\frac{L}{\mu_{1}}}}\right)\delta_{2}+3\tilde{R}\delta_{1}.$

###### Remark 3

If $\mu=0$ we can get analogue of the first convergence, repeating the proof
using claims 5, 5.

$f(x_{N})-f(x^{*})\leqslant\frac{4LR^{2}}{N^{2}}+3\tilde{R}\delta_{1}+N\delta_{2}.$

###### Remark 4

Suppose $\mu=0$, then consider the auxiliary problem:

$\begin{gathered}f^{\mu}(x)=f(x)+\frac{\mu}{2}\|x-\tilde{x}_{0}\|_{2}^{2}\to\min\limits_{x\in
Q},\\\ \nabla f^{\mu}(x)=\nabla f(x)+\mu(x-\tilde{x}_{0}),\\\
\tilde{\nabla}f^{\mu}(x)=\tilde{\nabla}f(x)+\mu(x-\tilde{x}_{0}),\\\
\|\tilde{\nabla}f^{\mu}(x)-\nabla f^{\mu}(x)\|_{2}=\|\tilde{\nabla}f(x)-\nabla
f(x)\|_{2}\leqslant\delta.\end{gathered}$

The resulting function will satisfy the condition that the gradient is
Lipschitz, that is $\forall x,y\in Q$:

$\|\nabla f^{\mu}(x)-\nabla f^{\mu}(y)\|_{2}^{2}=\|(\nabla f(x)-\nabla
f(y))+\mu(x-y)\|_{2}\leqslant\\\ \leqslant\|(\nabla f(x)-\nabla
f(y)\|_{2}+\mu\|x-y\|_{2}\leqslant\\\ \leqslant
L_{f}\|x-y\|_{2}+\mu\|x-y\|_{2}\leqslant(L_{f}+\mu)\|x-y\|_{2}.$

We will assume, that $\mu<1$. That is, we can let
$L^{\mu}=2(L_{f}+1)=L+2\geqslant L_{f^{\mu}}$. The resulting function will
already be strongly convex, which means that the second model is applicable to
it $\tau=2$. Using theorem 6.4 we can get the following inequality:

$\begin{gathered}x_{\mu}^{*}=\mathop{\arg\\!\min}_{x\in Q}f^{\mu}(x),\\\
R_{\mu}=\|x_{\mu}^{*}-\tilde{x}_{0}\|_{2},\\\
f^{\mu}(x_{k})-f^{\mu}(x_{\mu}^{*})\leqslant\frac{L^{\mu}R_{\mu}^{2}}{2\lambda_{\frac{\mu}{2},2L^{\mu}}^{k}}+\left(1+\sqrt{\frac{2L+4}{\mu}}\right)(\delta_{2}+\delta_{3})\Rightarrow\\\
f^{\mu}(x_{k})-f^{\mu}(x_{\mu}^{*})\leqslant
LR_{\mu}^{2}\exp\left({-\frac{1}{2}\sqrt{\frac{\mu}{2(L+2)}}k}\right)+\left(1+\sqrt{\frac{2L+4}{\mu}}\right)\left(\frac{1}{L}+\frac{1}{\mu}\right)\delta^{2},\\\
f^{\mu}(x_{\mu}^{*})\leqslant f(x^{*})+\frac{\mu}{2}R^{2}.\end{gathered}$

Then we can get convergence rate for not regularized function:

$f(x_{k})-f(x^{*})\leqslant f^{\mu}(x_{k})-f(x^{*})\leqslant
f^{\mu}(x_{k})-f(x_{\mu}^{*})+\frac{\mu}{2}R^{2}\leqslant\\\ \leqslant
LR_{\mu}^{2}\exp\left({-\frac{1}{2}\sqrt{\frac{\mu}{2(L+2)}}k}\right)+\\\
+\left(1+\sqrt{\frac{2L+4}{\mu}}\right)\left(\frac{1}{L}+\frac{1}{\mu}\right)\delta^{2}+\frac{\mu}{2}R^{2}.$

Using strong convexity of the function $f^{\mu}$ we get:

$\begin{gathered}f(x^{*})+\frac{\mu}{2}R_{\mu}^{2}\leqslant
f(x_{\mu}^{*})+\frac{\mu}{2}R_{\mu}^{2}=f^{\mu}(x_{\mu}^{*})\leqslant
f^{\mu}(x^{*})=f(x^{*})+\frac{\mu}{2}R^{2}\Rightarrow\\\ R_{\mu}\leqslant
R.\end{gathered}$

Finally we get convergence:

$f(x_{k})-f(x^{*})\leqslant
LR^{2}\exp\left({-\frac{1}{2}\sqrt{\frac{\mu}{2(L+2)}}k}\right)+\\\
+\left(1+\sqrt{\frac{2L+4}{\mu}}\right)\left(\frac{1}{L}+\frac{1}{\mu}\right)\delta^{2}+\frac{\mu}{2}R^{2}.$

We choose value for parameter $\mu$ in the remark 9.

###### Remark 5

If we consider the problem in the first model $\tau=1$, the case $\mu=0$ and
assume that $\|x^{*}\|_{2}\leqslant R_{*}$. Then we choose a starting point
for the $STM$ algorithm in a ball of radius $R_{*}$, specifically put
$x_{start}=0$.

$R=\|x^{*}-\tilde{x}_{0}\|_{2}\leqslant R_{*}$

Let us formulate a stopping rule for the this model $(\forall\zeta>0)$.

$f(x_{k})-f(x^{*})\leqslant
k\delta_{2}+R_{*}\delta_{1}+\delta_{1}\displaystyle\sum_{j=1}^{k}\frac{\alpha_{j}}{A_{k}}\|\tilde{x}_{j}-z_{j-1}\|_{2}+\zeta.\\\
$

######  Lemma 3 (Bound for $\tilde{R}$)

Before the stopping criterion is satisfied, the following inequality holds:

$\tilde{R}\leqslant R.$

###### Proof

Note, that from $\|z_{k}-x^{*}\|_{2}\leqslant R$ we get
$\|x_{k}-x^{*}\|_{2}\leqslant R,\|\tilde{x}_{k}-x^{*}\|_{2}\leqslant R$
similarly to theorem 6.3. But it’s worth noting that to estimate
$\|\tilde{x}_{k}-x^{*}\|_{2}$, only inequalities are required for all
$j\leqslant k-1$.

$\|\tilde{x}_{k}-x^{*}\|_{2}=\|\frac{A_{k-1}}{A_{k}}(x_{k-1}-x^{*})+\frac{\alpha_{k}}{A_{k}}(z_{k-1}-x^{*})\|_{2}\leqslant\\\
\leqslant\frac{A_{k-1}}{A_{k}}\|x_{k-1}-x^{*}\|_{2}+\frac{\alpha_{k}}{A_{k}}\|z_{k-1}-x^{*}\|_{2}\leqslant
R$

An analysis of the proof of theorem 6.2 gives a stronger convergence:

$A_{k}f(x_{k})\leqslant\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+\delta_{1}\displaystyle\sum_{j=1}^{k}\alpha_{j}\|\tilde{x}_{j}-z_{j-1}\|_{2}^{2}$

Then, using the convexity of the function $\psi_{k}$ we get:

$A_{k}f(x_{k})+\frac{1}{2}\|z_{k}-x^{*}\|_{2}^{2}\leqslant\frac{1}{2}\|z_{k}-x^{*}\|_{2}+\psi_{k}(z_{k})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+\\\
+\delta_{1}\displaystyle\sum_{j=1}^{k}\alpha_{j}\|\tilde{x}_{j}-z_{j-1}\|_{2}\leqslant\psi_{k}(x^{*})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+\\\
+\delta_{1}\displaystyle\sum_{j=1}^{k}\alpha_{j}\|\tilde{x}_{j}-z_{j-1}\|_{2}\leqslant\frac{1}{2}R^{2}+A_{k}f(x^{*})+\delta_{2}\displaystyle\sum_{j=0}^{k}A_{j}+\\\
+\delta_{1}\displaystyle\sum_{j=1}^{k}\alpha_{j}\|\tilde{x}_{j}-z_{j-1}\|_{2}+\delta_{1}\displaystyle\sum_{j=0}^{k}\alpha_{j}\|z_{k}-x^{*}\|_{2}\Rightarrow\frac{1}{2}(R^{2}-\|z_{k}-x^{*}\|_{2})\geqslant\\\
\geqslant
A_{k}\left(\left(f(x_{k})-f(x^{*})\right)-\left(k\delta_{2}+\delta_{1}\displaystyle\sum_{j=1}^{k}\frac{\alpha_{j}}{A_{k}}\|\tilde{x}_{j}-z_{j-1}\|_{2}+R_{*}\delta_{1}+\zeta\right)\right)\geqslant
0.$

Therefore, when the stopping criterion is met, we will receive the estimate:

$f(x_{k})-f(x^{*})\leqslant
k\delta_{2}+\delta_{1}R_{*}+\delta_{1}\displaystyle\sum_{j=0}^{k}\alpha_{j}\|\tilde{x}_{j}-z_{j-1}\|_{2}+\zeta.$

From remark 3 we get an estimate of the number of iterations:

$N_{stop}\geqslant 2\sqrt{\frac{LR^{2}}{\zeta}}.$
$f(x_{N})-f(x^{*})\leqslant\frac{4LR^{2}}{N^{2}}+N\delta_{2}+R_{*}\delta_{1}+\delta_{1}\displaystyle\sum_{j=1}^{N}\frac{\alpha_{j}}{A_{N}}\|\tilde{x}_{j}-z_{j-1}\|_{2}\leqslant\\\
\leqslant
N\delta_{2}+R_{*}\delta_{1}+\delta_{1}\displaystyle\sum_{j=1}^{N}\|\tilde{x}_{j}-z_{j-1}\|_{2}+\zeta\Rightarrow\frac{4LR^{2}}{N^{2}}\leqslant\zeta\Leftrightarrow
N^{2}\geqslant\frac{4LR^{2}}{\zeta}.$

Summing up, we obtain the following theorem:

###### Theorem 6.5

For model $\tau=1$ with $\mu=0$, using stopping rule:

$f(x_{N})-f(x^{*})\leqslant
N\delta_{2}+R_{*}\delta_{1}+\delta_{1}\displaystyle\sum_{j=1}^{N}\frac{\alpha_{j}}{A_{N}}\|\tilde{x}_{j}-z_{j-1}\|_{2}+\zeta.$

We can guarantee, that:

$\tilde{R}\leqslant R.$

And the criterion is reached after:

$N_{stop}=\left[2\sqrt{\frac{LR^{2}}{\zeta}}\right]+1.$

###  6.2 Relative noise.

Recall that we denote:

$L=2L_{f}.$

Where $L_{f}$ – Lipschitz constant of $\nabla{f}$. From theorem 6.2 and
similar to theorem 6.4 reasoning we get:

$\begin{gathered}f(x_{k})-f(x^{*})\leqslant\frac{R^{2}}{A_{k}}+\frac{3}{2}\displaystyle\sum_{j=0}^{k-1}\frac{A_{j}\alpha^{2}\|\nabla{f}(x_{k})\|_{2}^{2}}{A_{k}\mu}+\frac{3\alpha^{2}\|\nabla{f}(x_{k})\|_{2}^{2}}{2\mu},\\\
\Delta_{k}=f(x_{k})-f(x^{*}),\\\
\Delta_{k}\leqslant\frac{R^{2}}{A_{k}}+\frac{3}{2}\displaystyle\sum_{j=0}^{k-1}\frac{A_{j}\alpha^{2}\|\nabla{f}(x_{j})\|_{2}^{2}}{A_{k}\mu}+\frac{3\alpha^{2}}{2\mu}\|\nabla{f}(x_{k})\|_{2}^{2}.\\\
\end{gathered}$

We define:

$\begin{gathered}\theta=\frac{3L\alpha^{2}}{2\mu(1-\frac{3L\alpha^{2}}{2\mu})},\\\
\lambda=\frac{R^{2}}{1-\frac{3L\alpha^{2}}{2\mu}}.\end{gathered}$

From inequality:

$\|\nabla{f}(x_{k})\|_{2}^{2}\leqslant L\left(f(x_{k})-f(x^{*})\right).$

We obtain:

$\Delta_{k}\leqslant\frac{\lambda}{A_{k}}+\theta\displaystyle\sum_{j=0}^{k-1}\frac{A_{j}}{A_{k}}\Delta_{j}.$

In these designations by induction we can obtain:

###### Claim

$\Delta_{k}\leqslant\frac{\left(1+\theta\right)^{k-1}}{A_{k}}\lambda+\theta\frac{A_{0}\left(1+\theta\right)^{k-1}}{A_{k}}\Delta_{0}.$

###### Proof

Base, $k=1$ is obvious. Induction step:

$\Delta_{k}\leqslant\frac{\lambda}{A_{k}}+\theta\displaystyle\sum_{j=0}^{k-1}\frac{A_{j}}{A_{k}}\Delta_{j}\leqslant\\\
\leqslant\frac{\lambda}{A_{k}}+\displaystyle\sum_{j=0}^{k-1}\left(\frac{A_{j}}{A_{k}}\frac{(1+\theta)^{j-1}}{A_{k}}\lambda+\theta\frac{A_{0}(1+\theta)^{j-1}}{A_{k}}\Delta_{0}\right)+\frac{A_{0}}{A_{k}}\Delta_{0}\leqslant\\\
\leqslant\frac{\lambda}{A_{k}}+\displaystyle\sum_{j=0}^{k-2}\left(\frac{\lambda(1+\theta)^{j}}{A_{k}}+\theta\frac{A_{0}(1+\theta)^{j}}{A_{k}}\Delta_{0}\right)+\frac{A_{0}}{A_{k}}\Delta_{0}=\\\
=\frac{\left(1+\theta\right)^{k-1}}{A_{k}}\lambda+\theta\frac{A_{0}\left(1+\theta\right)^{k-1}}{A_{k}}\Delta_{0}.$

That is we can formulate the following inequality:

$f(x_{k})-f(x^{*})\leqslant\frac{\lambda(1+\theta)^{k}}{A_{k}}+\theta\frac{A_{0}(1+\theta)^{k}}{A_{k}}\left(f(x_{0})-f(x^{*})\right).$

Using corollary 1 we can estimate:

$A_{k}\geqslant\left(1+\sqrt{\frac{\mu}{2L}}\right)^{k}A_{0}.$ (26)

We will choose an alpha such that:

$\frac{1+\theta}{A_{k}}\leqslant\frac{1}{1+\frac{1}{3\sqrt{2}}\sqrt{\frac{\mu}{L}}}.$

Using (26) and definition of $\theta$ we obtain, that we should choose
$\alpha$ from:

$\begin{gathered}\alpha\leqslant\sqrt{\frac{1}{\frac{1}{2\sqrt{2}}\left(\frac{L}{\mu}\right)^{\frac{3}{2}}+\frac{2L}{\mu}}}\\\
\alpha=O\left(\left(\frac{\mu}{L}\right)^{\frac{3}{4}}\right)\end{gathered}$
(27)

From simple inequality:

$1+\frac{1}{3\sqrt{2}}\sqrt{\frac{\mu}{L}}>\exp{\left({\displaystyle\frac{1}{6\sqrt{2}}\sqrt{\frac{\mu}{L}}}\right)}.$

We get the following theorem:

###### Theorem 6.6

If in the model described in (3) in the strongly convex case we can chose
$\alpha$ according to (27) we obtain:

$f(x_{k})-f(x^{*})\leqslant\left(\frac{LR^{2}}{1-\alpha^{2}}+\frac{3L\alpha^{2}}{2\mu(1-\alpha^{2})}\left(f(x_{0})-f(x^{*})\right)\right)\exp{\left({\displaystyle-\frac{1}{6\sqrt{2}}\sqrt{\frac{\mu}{L}}}\right)}.$

###### Corollary 2

Under the conditions of the theorem, we obtain convergence in the argument:

$\|x_{k}-x^{*}\|_{2}^{2}\leqslant
R^{2}\left(\frac{2L}{\mu(1-\alpha^{2})}+\frac{3L^{2}\alpha^{2}}{4\mu^{2}(1-\alpha^{2})}\right)\exp{\left({\displaystyle-\frac{1}{6\sqrt{2}}\sqrt{\frac{\mu}{L}}}\right)}.$

###### Proof

This is a direct consequence of the inequalities:

$\begin{gathered}f(x_{k})-f(x^{*})\leqslant\frac{L}{4}\|x_{k}-x^{*}\|_{2}^{2}\\\
f(x_{k})-f(x^{*})\geqslant\frac{\mu}{2}\|x_{k}-x^{*}\|_{2}^{2}\end{gathered}$

##  7 Conclusions and observations

###### Remark 6

Using Theorem 6.3 and assume, that $Q$ – compact set we can we can denote $R$
as $\;\mathrm{diam}(Q)$ instead of $\;\|x_{0}-x^{*}\|_{2}$, then we can also
bound $\tilde{R}\leqslant R$ and this will simplify bounds in theorem 6.4.

###### Remark 7

With the same assumption $\mu\not=0$ we obtain a comparison of the two
convergences in the Theorem 6.4. Recall that:

$\begin{gathered}\delta_{1}=\delta,\quad\delta_{2}=\frac{\delta^{2}}{L},\quad\delta_{3}=\frac{\delta^{2}}{\mu}.\end{gathered}$

So if

$\delta<\frac{3\tilde{R}}{\frac{1+\sqrt{\frac{L}{\mu}}}{\mu}+\frac{\sqrt{\frac{L}{\mu}}(\sqrt{2}-1)}{L}}.$

Then the accumulation of noise in the model corresponding to $\tau=2$, that
described in (4) is less than in model $\tau=1$, described in (4).

###### Remark 8

If we use model $\tau=2$, described in theorem 6.4 one can set the desired
accuracy of the solution.

$f(x_{N})-f(x^{*})\leqslant\varepsilon.$

Then we get from theorem 6.4 that:

$\begin{gathered}f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp{\left(-\frac{1}{2}\sqrt{\frac{\mu}{2L}}N\right)}+\left(1+\sqrt{{\frac{L}{\mu_{2}}}}\right)\delta_{2}+\left(1+\sqrt{\frac{L}{\mu_{2}}}\right)\delta_{3},\\\
f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp{\left(-\frac{1}{2}\sqrt{\frac{\mu}{2L}}N\right)}+\left(\frac{L+\mu}{\sqrt{\mu^{3}L}}(\sqrt{2}+1)\right)\delta^{2}.\end{gathered}$

That is we can get estimates for $\delta$ value and number of steps $N$:

$\begin{gathered}\left(\frac{L+\mu}{\sqrt{\mu^{3}L}}(\sqrt{2}+1)\right)\delta^{2}\leqslant\frac{\varepsilon}{2},\\\
\delta\leqslant\sqrt{\varepsilon}\sqrt{\frac{\sqrt{2}+1}{2}}\sqrt{\frac{L+\mu}{\sqrt{\mu^{3}L}}},\\\
\delta=O\left(\sqrt{\varepsilon}\frac{(L+\mu)^{\frac{1}{2}}}{(\mu^{3}L)^{\frac{1}{4}}}\right){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0};}\\\
LR^{2}\exp{\left(-\frac{1}{2}\sqrt{\frac{\mu}{2L}}N\right)}\leqslant\frac{\varepsilon}{2},\\\
N\geqslant
2\sqrt{\frac{2L}{\mu}}\left(\ln{2LR^{2}}+\ln{\varepsilon^{-1}}\right),\\\
N=O\left(\sqrt{\frac{L}{\mu}}\ln{\frac{LR^{2}}{\varepsilon}}\right).\end{gathered}$

###### Remark 9

Using remark 4 and previous remark 8, we can found similar bounds. Remind
that:

$f(x_{N})-f(x^{*})\leqslant
LR^{2}\exp\left({-\frac{1}{2}\sqrt{\frac{\mu}{2(L+2)}}N}\right)+\\\
+\left(1+\sqrt{\frac{2L+4}{\mu}}\right)\left(\frac{1}{L}+\frac{1}{\mu}\right)\delta^{2}+\frac{\mu}{2}R^{2}.$

However we should value of the parameter $\mu$. We will let:

$\mu=\frac{2}{3}\frac{\varepsilon}{R^{2}}.$

Using inequality:

$\delta^{2}\left(1+\sqrt{\frac{2L+4}{\mu}}\right)\left(\frac{\mu+L}{\mu
L}\right)\leqslant\frac{\varepsilon}{3}.$

And the selected value of the parameter mu we get required value of error
$\delta$:

$\begin{gathered}\delta\leqslant\left(\frac{2}{243}\right)^{\frac{1}{4}}\frac{1}{\sqrt{1+\sqrt{2L+4}}}R^{-\frac{3}{2}}\varepsilon^{\frac{5}{4}},\\\
\delta=O\left(L^{-\frac{1}{4}}R^{-\frac{3}{2}}\varepsilon^{\frac{5}{4}}\right).\end{gathered}$

Similarly, get an estimate of the number of steps:

$\begin{gathered}LR^{2}\exp\left({-\frac{1}{2}\sqrt{\frac{\mu}{2(L+2)}}N}\right)\leqslant\frac{\varepsilon}{3},\\\
N\geqslant\sqrt{12L+24}R\ln{2LR^{2}}+2\sqrt{2L+4}\frac{1}{\sqrt{\varepsilon}}\ln{\frac{1}{\varepsilon}},\\\
N=O\left(\sqrt{\frac{L}{\varepsilon}}\ln{\frac{LR^{2}}{\varepsilon}}\right).\end{gathered}$

###### Remark 10

Using remark 5 and theorem 6.5 we can apply it to problem:

$\begin{gathered}Ax=b,\\\
A\in\mathrm{GL}_{n}{\left(\mathbb{R}\right)}.\end{gathered}$

Solving such a problem is equivalent to solving the convex optimization
problem:

$\begin{gathered}f(x)=\frac{1}{2}\|Ax-b\|_{2}^{2}\to\min,\\\ \nabla
f(x)=A^{T}\left(Ax-b\right).\end{gathered}$

We will assume similarly the estimate of the norm $x^{*}$:

$\|x^{*}\|_{2}\leqslant R_{*}.$

Let the original problem be solved with an $\varepsilon_{1}$ accuracy in the
sense:

$\begin{gathered}\|Ax-b\|_{2}\leqslant\varepsilon_{1},\\\
f(x)-f(x^{*})=\frac{1}{2}\|Ax-b\|_{2}^{2}\leqslant\varepsilon,\\\
\varepsilon=\frac{1}{2}\varepsilon_{1}^{2}.\end{gathered}$

When the algorithm stops, we get the convergence:

$\begin{gathered}f(x_{N_{stop}})-f(x^{*})\leqslant
N\delta_{2}+3\delta_{1}R_{*},\\\
N_{stop}=\left[2\sqrt{\frac{LR^{2}}{\zeta}}\right]+1.\\\ \end{gathered}$

Then we choose $\delta,\zeta$ from the following conditions:

$\begin{cases}\zeta\leqslant\frac{\varepsilon}{3},\\\
\delta\leqslant\left(\frac{L^{\frac{1}{4}}}{6\sqrt{3R}}\right)\varepsilon^{\frac{3}{4}},\\\
\delta\leqslant\varepsilon\frac{1}{9R_{*}}.\end{cases}$

For example, we can let:

$\begin{gathered}\delta=\mathrm{C}_{R,R_{*},L}\varepsilon,\\\
\mathrm{C}_{R,R_{*},L}=\min\left\\{\frac{L^{\frac{1}{4}}}{6\sqrt{3R}},\frac{1}{9R_{*}}\right\\}.\end{gathered}$

Then the number of steps required is expressed as:

$\begin{gathered}N_{\varepsilon}=\left[2\sqrt{\frac{3LR^{2}}{\varepsilon}}\right]+1.\end{gathered}$

Accordingly, the estimate required for solving the problem of linear
equations:

$N_{\varepsilon_{1}}=\left[2\frac{\sqrt{3LR^{2}}}{\varepsilon_{1}}\right]+1.$

###### Remark 11

The work considered a model of additive noise in equation (20), similar to
poljak1981iterative , that is we can consider that:

$\begin{gathered}\tilde{\nabla}f(x)=\nabla f(x)+r_{x},\\\
\|r_{x}\|_{2}\leqslant\delta.\end{gathered}$

Similarly to this work, a stopping criterion was proposed for the $STM$
algorithm, as was proposed for gradient descent.

$x_{k+1}=x_{k}-\frac{1}{L}\nabla{f}(x_{k}).$

Note that in the same noise model, the convergence estimate in both considered
cases will be:

$\begin{gathered}j_{N}=\mathop{\arg\\!\min}_{1\leqslant k\leqslant
N}f\left(x_{k}\right),\\\ y_{N}=x_{j_{N}},\\\
f(y_{N})-f(x^{*})=O\left(\frac{LR^{2}}{N}+\frac{\delta^{2}}{L}+\tilde{R}\delta\right),\\\
f(y_{N})-f(x^{*})=O\left(LR^{2}\exp{\left(-\frac{\mu}{L}N\right)}+\frac{\delta^{2}}{L}+\tilde{R}\delta\right).\\\
f(y_{N})-f(x^{*})=O\left(LR^{2}\exp{\left(-\frac{\mu}{2L}\right)}+\frac{\delta^{2}}{L}+\frac{\delta^{2}}{\mu}\right),\\\
\tilde{R}=\max_{k\leqslant N}\|x_{k}-x^{*}\|_{2}.\end{gathered}$

Despite the fact that in the work devolder2013first , a slightly different
model was considered, namely $(\delta,L)$ and $(\delta,L,\mu)$ oracle
(equation 3.1 Definition 1 in devolder2013first ) similar orders of
convergence were obtained, that is theorem 6.4 and relevant remark 3. Namely,
function satisfies the $(\delta,L,\mu)$ model at point $x\in Q$ means, that
exists functions $f_{\delta}(x)$ and $\psi_{\delta}(x,y)$, such that:

$\begin{gathered}\forall y\in Q\\\ \frac{\mu}{2}\|x-y\|_{2}^{2}\leqslant
f(x)-f_{\delta}(y)-\psi_{\delta}(x,y)\leqslant\frac{L}{2}\|x-y\|_{2}^{2}+\delta.\end{gathered}$

Similarly to papers stonyakin2020inexact , devolder2013first , the results
also hold in the case of an unbounded set $Q$(result in stonyakin2020inexact
is on the page 26, obtained for fast adaptive gradient method page 13).
Stopping criteria are also formulated, which give an estimate on $\tilde{R}$
for a non-compact $Q$, remind that:

$\tilde{R}=\max_{0\leqslant k\leqslant
N}\\{\|x_{k}-x^{*}\|_{2},\|\tilde{x}_{k}-x^{*}\|_{2},\|z_{k}-x^{*}\|_{2}\\}.$

We also note that a similar models of $(\delta,\Delta,L)$ and
$(\delta,\Delta,L,\mu)$ oracle was considered in the work
stonyakin2020adaptive . Moreover, the function satisfies
$(\delta,\Delta,L,\mu)$–model

$\begin{gathered}f(y)\leqslant
f_{\delta}+\psi(y,x)+\Delta\|x-y\|+\delta+LV(y,x),\\\
f_{\delta}+\psi(x^{*},x)+\mu V(y,x)\leqslant f(x^{*}),\\\ f(x)-\delta\leqslant
f_{\delta}(x)\leqslant f(x),\\\ \psi(x,x)=0.\\\ \end{gathered}$

Here $V(x,y)$ – Bregman divergence. At the same time, an adaptive analogue of
STM was considered. As well as similar estimations for a $\delta$ and number
of steps $N$, following devolder2013first  (page 24, remarks 11 – 14 ), namely
there are remarks 8, 9, 10. Also considered an example of using regularization
to obtain convergence in the model $\tau=1$, for the case $\mu=0$.

##  8 Numerical experiments

For testing $STM$ for degenerate problems, the function described in
nesterov2018lectures  on page 69, that is:

$\begin{gathered}f(x)=\frac{L}{8}\left(x_{1}^{2}+\displaystyle\sum_{j=0}^{k-1}\left(x_{j}-x_{j+1}\right)^{2}+x_{k}^{2}\right)-\frac{L}{4}x_{1}\\\
x^{*}=\left(1-\frac{1}{k+1},\>\dots\>,1-\frac{k}{k+1},\>0,\>\dots\>,0\right)^{T}\\\
1\leqslant k\leqslant\dim{x}\end{gathered}$

These two plots reflect the convergence of the method at the first 50 000 and
10 000 iterations, respectively, at different $\delta$.

Figure 2: First test – first 50 000 steps. Figure 3: First test – first 10 000
steps.

Let’s also consider a drawing with two types of noise.

Figure 4: Second test – relative and additive types of noises comparison.

To compare the convergence of a degenerate problem with different $\alpha$
parameters in the case of relative noise, consider the following graph.

Figure 5: Third test – relative noise with different values of $\alpha$ for
$\mu=0$.

The last figure shows that for $\alpha\leqslant 0.71$ the convergence of the
method does not deteriorate, but we can assume the existence of such a
threshold value $\alpha^{*}\approx 0.71$, that at large of $\alpha$ values the
method diverges.

Also for testing on strongly convex functions, an analogue of the finite-
dimensional Nesterov function was used from nesterov2018lectures  on page 78,
that is:

$\begin{gathered}f(x)=\frac{\mu\left(\chi-1\right)}{8}\left(x_{1}^{2}+\displaystyle\sum_{j=1}^{n-1}{\left(x_{j}-x_{j+1}\right)^{2}}-2x_{1}\right)+\frac{\mu}{2}\|x\|_{2}^{2}\\\
\chi=\frac{L}{\mu}\\\ \nabla{f}(x)=\left(\frac{\mu\left(\chi-1\right)}{4}A+\mu
E\right)x-\frac{\mu\left(\chi-1\right)}{4}e_{1}\\\
e_{1}=\left(1,\>0,\>\dots\>,0\>\right)^{T}\end{gathered}$

Where $E$ – identity operator, A is the matrix defined as:

${2}$${-1}$${0}$${\dots}$${\dots}$${0}$${-1}$${2}$${-1}$${0}$${\dots}$${0}$${\vdots}$${\vdots}$${\vdots}$${\ddots}$${\ddots}$${\vdots}$${0}$${\dots}$${0}$${-1}$${2}$${-1}$${0}$${\dots}$${\dots}$${0}$${-1}$${2}$$\left(\vbox{\hrule
height=42.89804pt,depth=42.89804pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=42.89804pt,depth=42.89804pt,width=0.0pt}\right)$

Then minimum $f$, $x^{*}$, can be found from systems of linear equations.

Let us consider the graphs of the residuals for different parameters of the
delta additive noise.

Figure 6: Fourth test – $\delta\in\\{0.5,0.6,0.7,0.8,0.9,1.0\\}.$ Figure 7:
Fifth test – mean of 30 tests, level of approximation and required number of
steps.

The last plot confirms theorem 6.4 and remark 8. Similarly to the degenerate
case, consider the behavior of the method for different parameters $\alpha$.

Figure 8: Sixth test – relative noise with different values of $\alpha$ for
$\mu>0$.

Note that in the strongly convex case, we obtain a property similar to the
degenerate case: for $\alpha$ values less than a certain threshold value
$\alpha^{*}$, from the figure we can assume a value of 0.71, the convergence
of the method does not deteriorate, and for large $\alpha$ values, the method
diverges.

Figure 9: Seventh test – relative noise with different values of $\alpha$ for
other $L$ and $\mu$.

Figure 9 shows, that The figure shows that changing the parameters $L$ and
$\mu$, the value of the assumed threshold $\alpha^{*}$ does not change much.
We also note that such threshold values turned out to be approximately equal
for the degenerate and strongly convex problem.

##  9 Acknowledgment

The authors are grateful to Eduard Gorbunov for useful discussions.

## References

  * (1) Ajalloeian, A., Stich, S.U.: Analysis of sgd with biased gradient estimators.  arXiv preprint arXiv:2008.00051 (2020)
  * (2) Akhavan, A., Pontil, M., Tsybakov, A.B.: Exploiting higher order smoothness in derivative-free optimization and continuous bandits.  arXiv preprint arXiv:2006.07862 (2020)
  * (3) Bach, F., Perchet, V.: Highly-smooth zero-th order online optimization.  In: V. Feldman, A. Rakhlin, O. Shamir (eds.) 29th Annual Conference on Learning Theory, _Proceedings of Machine Learning Research_ , vol. 49, pp. 257–283. PMLR, Columbia University, New York, New York, USA (2016).  URL http://proceedings.mlr.press/v49/bach16.html
  * (4) Beck, A.: First-order methods in optimization.  SIAM (2017)
  * (5) Belloni, A., Liang, T., Narayanan, H., Rakhlin, A.: Escaping the local minima via simulated annealing: Optimization of approximately convex functions.  In: P. Grünwald, E. Hazan, S. Kale (eds.) Proceedings of The 28th Conference on Learning Theory, _Proceedings of Machine Learning Research_ , vol. 40, pp. 240–265. PMLR, Paris, France (2015).  URL http://proceedings.mlr.press/v40/Belloni15.html
  * (6) Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization (Lecture Notes).  Personal web-page of A. Nemirovski (2015)
  * (7) Berahas, A.S., Cao, L., Choromanski, K., Scheinberg, K.: A theoretical and empirical comparison of gradient approximations in derivative-free optimization.  arXiv preprint arXiv:1905.01332 (2019)
  * (8) Beznosikov, A., Sadiev, A., Gasnikov, A.: Gradient-free methods with inexact oracle for convex-concave stochastic saddle-point problem.  In: International Conference on Mathematical Optimization Theory and Operations Research, pp. 105–119. Springer (2020)
  * (9) Bubeck, S.: Convex optimization: Algorithms and complexity.  arXiv preprint arXiv:1405.4980 (2014)
  * (10) Cohen, M.B., Diakonikolas, J., Orecchia, L.: On acceleration with noise-corrupted gradients.  arXiv preprint arXiv:1805.12591 (2018)
  * (11) Conn, A., Scheinberg, K., Vicente, L.: Introduction to Derivative-Free Optimization.  Society for Industrial and Applied Mathematics (2009).  DOI 10.1137/1.9780898718768.  URL http://epubs.siam.org/doi/abs/10.1137/1.9780898718768
  * (12) d’Aspremont, A.: Smooth optimization with approximate gradient.  SIAM Journal on Optimization 19(3), 1171–1183 (2008)
  * (13) d’Aspremont, A., Scieur, D., Taylor, A.: Acceleration methods.  arXiv preprint arXiv:2001.09545 (2021)
  * (14) Devolder, O.: Stochastic first order methods in smooth convex optimization.  CORE Discussion Paper 2011/70 (2011)
  * (15) Devolder, O.: Exactness, inexactness and stochasticity in first-order methods for large-scale convex optimization.  Ph.D. thesis, ICTEAM and CORE, Université Catholique de Louvain (2013)
  * (16) Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle.  Mathematical Programming 146(1), 37–75 (2014).  DOI 10.1007/s10107-013-0677-5.  URL http://dx.doi.org/10.1007/s10107-013-0677-5
  * (17) Devolder, O., Glineur, F., Nesterov, Y., et al.: First-order methods with inexact oracle: the strongly convex case.  CORE Discussion Papers 2013016, 47 (2013)
  * (18) Drusvyatskiy, D., Xiao, L.: Stochastic optimization with decision-dependent distributions.  arXiv preprint arXiv:2011.11173 (2020)
  * (19) Dvinskikh, D., Gasnikov, A.: Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems.  Journal of Inverse and Ill-posed Problems (2021)
  * (20) Dvinskikh, D.M., Turin, A.I., Gasnikov, A.V., Omelchenko, S.S.: Accelerated and non accelerated stochastic gradient descent in model generality.  Matematicheskie Zametki 108(4), 515–528 (2020)
  * (21) Dvurechensky, P.: Numerical methods in large-scale optimization: inexact oracle and primal-dual analysis.  HSE. Habilitation (2020)
  * (22) Dvurechensky, P., Gasnikov, A.: Stochastic intermediate gradient method for convex problems with stochastic inexact oracle.  Journal of Optimization Theory and Applications 171(1), 121–145 (2016).  DOI 10.1007/s10957-016-0999-6.  URL http://dx.doi.org/10.1007/s10957-016-0999-6
  * (23) Dvurechensky, P., Staudigl, M., Shtern, S.: First-order methods for convex optimization.  arXiv preprint arXiv:2101.00935 (2021)
  * (24) Evtushenko, Y.G.: Optimization and fast automatic differentiation.  Computing Center of RAS, Moscow (2013)
  * (25) Gasnikov, A.: Universal gradient descent.  arXiv preprint arXiv:1711.00394 (2017)
  * (26) Gasnikov, A., Kabanikhin, S., Mohammed, A., Shishlenin, M.: Convex optimization in hilbert space with applications to inverse problems.  arXiv preprint arXiv:1703.00267 (2017)
  * (27) Gasnikov, A.V., Gasnikova, E.V., Nesterov, Y.E., Chernov, A.V.: Efficient numerical methods for entropy-linear programming problems.  Computational Mathematics and Mathematical Physics 56(4), 514–524 (2016).  DOI 10.1134/S0965542516040084.  URL http://dx.doi.org/10.1134/S0965542516040084
  * (28) Gasnikov, A.V., Nesterov, Y.E.: Universal method for stochastic composite optimization problems.  Computational Mathematics and Mathematical Physics 58(1), 48–64 (2018)
  * (29) Goodfellow, I., Bengio, Y., Courville, A., Bengio, Y.: Deep learning, vol. 1.  MIT press Cambridge (2016)
  * (30) Gorbunov, E., Dvinskikh, D., Gasnikov, A.: Optimal decentralized distributed algorithms for stochastic convex optimization.  arXiv preprint arXiv:1911.07363 (2019)
  * (31) Kabanikhin, S.I.: Inverse and ill-posed problems: theory and applications, vol. 55.  Walter De Gruyter (2011)
  * (32) Kamzolov, D., Dvurechensky, P., Gasnikov, A.V.: Universal intermediate gradient method for convex problems with inexact oracle.  Optimization Methods and Software pp. 1–28 (2020)
  * (33) Kotsalis, G., Lan, G., Li, T.: Simple and optimal methods for stochastic variational inequalities, ii: Markovian noise and policy evaluation in reinforcement learning.  arXiv preprint arXiv:2011.08434 (2020)
  * (34) Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning.  Springer (2020)
  * (35) Nemirovski, A.S.: Regularizing properties of the conjugate gradient method for ill-posed problems.  Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki 26(3), 332–347 (1986)
  * (36) Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization.  J. Wiley & Sons, New York (1983)
  * (37) Nesterov, Y.: Lectures on convex optimization, vol. 137.  Springer (2018)
  * (38) Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions.  Found. Comput. Math. 17(2), 527–566 (2017).  DOI 10.1007/s10208-015-9296-2.  URL https://doi.org/10.1007/s10208-015-9296-2.  First appeared in 2011 as CORE discussion paper 2011/16
  * (39) Novitskii, V., Gasnikov, A.: Improved exploiting higher order smoothness in derivative-free optimization and continuous bandit.  arXiv preprint arXiv:2101.03821 (2021)
  * (40) Pedregosa, F., Scieur, D.: Average-case acceleration through spectral density estimation.  arXiv preprint arXiv:2002.04756 (2020)
  * (41) Poljak, B.: Iterative algorithms for singular minimization problems.  In: Nonlinear Programming 4, pp. 147–166. Elsevier (1981)
  * (42) Polyak, B.: Introduction to Optimization.  New York, Optimization Software (1987)
  * (43) Polyak, B.T., Tsybakov, A.B.: Optimal order of accuracy of search algorithms in stochastic optimization.  Problemy Peredachi Informatsii 26(2), 45–53 (1990)
  * (44) Risteski, A., Li, Y.: Algorithms and matching lower bounds for approximately-convex optimization.  Advances in Neural Information Processing Systems 29, 4745–4753 (2016)
  * (45) Rockafellar, R.T.: Convex analysis, vol. 36.  Princeton university press (1970)
  * (46) Scieur, D., Pedregosa, F.: Universal asymptotic optimality of polyak momentum.  In: International Conference on Machine Learning, pp. 8565–8572. PMLR (2020)
  * (47) Stonyakin, F.: Adaptive methods for variational inequalities, minimization problems and functional with generalized growth condition.  MIPT. Habilitation (2020)
  * (48) Stonyakin, F., Tyurin, A., Gasnikov, A., Dvurechensky, P., Agafonov, A., Dvinskikh, D., Pasechnyuk, D., Artamonov, S., Piskunova, V.: Inexact relative smoothness and strong convexity for optimization and variational inequalities by inexact model.  arXiv preprint arXiv:2001.09013 (2020)
  * (49) Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods.  Mathematical Programming 161(1-2), 307–345 (2017)
  * (50) Tyurin, A.: Development of a method for solving structural optimization problems.  HSE. PhD Thesis (2020)
  * (51) Vasilyev, F.: Optimization Methods.  Moscow, Russia: FP (2002)