---
abstract: 'We study the iteration complexity of stochastic gradient descent (SGD) for minimizing the gradient norm of smooth, possibly nonconvex functions. We provide several results, implying that the classical $\mathcal{O}(\epsilon^{-4})$ upper bound (for making the average gradient norm less than $\epsilon$) cannot be improved upon, unless a combination of additional assumptions is made. Notably, this holds even if we limit ourselves to convex quadratic functions. We also show that for nonconvex functions, the feasibility of minimizing gradients with SGD is surprisingly sensitive to the choice of optimality criteria.'
author:
- |
    Yoel Drori\
    Google Research
- |
    Ohad Shamir\
    Weizmann Institute of Science\
    and Google Research
bibliography:
- 'bib.bib'
title: |
    The Complexity of Finding Stationary Points\
    with Stochastic Gradient Descent
---

Introduction
============

Stochastic gradient descent (SGD) is today one of the main workhorses for solving large-scale supervised learning and optimization problems. Much of its popularity is due to its extreme simplicity: Given a function $f$ and an initialization point ${\mathbf{x}}$, we perform iterations of the form ${\mathbf{x}}_{t+1}={\mathbf{x}}_t-\eta_t {\mathbf{g}}_t$, where $\eta_t>0$ is a step size parameter and ${\mathbf{g}}_t$ is a stochastic vector which satisfies ${\mathbb{E}}[{\mathbf{g}}_t|{\mathbf{x}}_t]=\nabla f({\mathbf{x}}_t)$. For example, in the context of machine learning, $f({\mathbf{x}})$ might be the expected loss of some predictor parameterized by ${\mathbf{x}}$ (over some underlying data distribution) and ${\mathbf{g}}_t$ is the gradient of the loss w.r.t. a single data sample. For convex problems, the convergence rate of SGD to a global minimum of $f$ has been very well studied (for example, [@kushner2003stochastic; @nemirovski2009robust; @moulines2011non; @bertsekas2011incremental; @rakhlin2012making; @bottou2018optimization]). However, for nonconvex problems, convergence to a global minimum cannot in general be guaranteed. A reasonable substitute is to study the convergence to local minima, or at the very least, to stationary points. This can also be quantified as an optimization problem, where the goal is not to minimize $f({\mathbf{x}})$ over ${\mathbf{x}}$, but rather ${\|\nabla f({\mathbf{x}})\|}$. This question of finding stationary points has gained more attention in recent years, with the rise of deep learning and other large-scale nonconvex optimization methods.

Compared to optimizing function values, the convergence of SGD in terms of minimizing the gradient norm is relatively less well-understood. A folklore result (see e.g., [@ghadimi2013stochastic], which we repeat in [Appendix \[sec:upperbounds\]]{} for completeness, as well as [@allen2018make]) states that for smooth (Lipschitz gradient) functions, ${\mathcal{O}}(\epsilon^{-4})$ iterations are sufficient to make the average expected gradient ${\mathbb{E}}[\frac{1}{T}\sum_{t=1}^{T}{\|\nabla f({\mathbf{x}}_t)\|}]$ (or minimal gradient ${\mathbb{E}}[\min_t {\|\nabla f({\mathbf{x}}_t)\|}]$) less than $\epsilon$, and it was widely conjectured that this is the best complexity achievable with SGD. However, this bound was recently improved in Fang et al. [@fang2019sharp], which showed a complexity bound of ${\mathcal{O}}(\epsilon^{-3.5})$ for SGD, under the following additional assumptions/algorithmic modifications:

1.  **(Complex) aggregation.** Rather than considering the average or minimal gradient norm of the iterates, the algorithm considers the norm of a certain adaptive average of a suffix of the iterates (those which do not deviate too much from the final iterate).

2.  \[as:hessian\] **Lipschitz Hessian.** The function is twice differentiable, with a Lipschitz Hessian as well as a Lipschitz gradient.

3.  \[as:noise\] **“Dispersive” noise.** The stochastic noise satisfies a “dispersive” property, which intuitively implies that it is well-spread (it is satisfied, for example, for Gaussian or uniform noise in some ball).

4.  \[as:dimension\] **Bounded dimension.** The dimension is bounded, in the sense that there is an explicit logarithmic dependence on it in the iteration complexity bound (in contrast, the folklore ${\mathcal{O}}(\epsilon^{-4})$ result is dimension-free).

In fact, the result of Fang et al. is even stronger, as it shows convergence to a *second-order* stationary point (where the Hessian is nearly positive definite), but this will not be our focus here. Moreover, it is known that some dimension dependence is difficult to avoid when considering second-order stationary points (see [@simchowitz2017gap]).

In this paper, we study the performance limits of SGD for minimizing gradients, through several variants of lower bounds under different assumptions. In particular, we wish to understand which of the assumptions/modifications above are necessary to break the $\epsilon^{-4}$ barrier. Our main take-home message is that most of these indeed appear to be needed in order to attain an iteration complexity better than ${\mathcal{O}}(\epsilon^{-4})$, in some cases even if we limit ourselves just to convex quadratic functions. In a bit more detail:

-   If we drop assumption \[as:dimension\] (bounded dimension), and consider the norm of the gradient at the output of some fixed, deterministic aggregation scheme (as opposed to returning, for example, an iterate with a minimal gradient norm), then perhaps surprisingly, we show that it is impossible to provide *any* finite complexity bound. This holds under mild algorithmic conditions, which extend far beyond SGD. This implies that for dimension-free bounds, we must either consider rather complicated aggregation schemes, apply randomization, or use optimality criteria which do not depend on a single point (e.g., consider the average gradient $\frac{1}{T}\sum_{t=1}^{T}{\|\nabla f({\mathbf{x}}_t)\|}$ or $\min_t {\|\nabla f(x_t)\|}$, as is often done in the literature). This result is formalized as [Thm. \[thm:infdim\]]{} in [Subsection \[subsec:fixedpoint\]]{}.

-   Without assumptions \[as:hessian\] (Lipschitz Hessian) and \[as:noise\] (dispersive noise), then even with rather arbitrary aggregation schemes, the iteration complexity of SGD is $\Omega(\epsilon^{-4})$. This result is formalized as [Thm. \[thm:aggregation\_step\]]{} in [Subsection \[subsec:sgdlowbound\]]{}.

-   Without aggregation and without assumption \[as:noise\] (dispersive noise), the iteration complexity of SGD required to satisfy ${\mathbb{E}}[\min_t {\|\nabla f({\mathbf{x}}_t)\|}]\leq \epsilon$ is $\Omega(\epsilon^{-3})$. This result is formalized as [Thm. \[thm:nonconvex\]]{} in [Subsection \[subsec:sgdlowbound\]]{}.

-   Without aggregation, the iteration complexity of SGD with “reasonable” step sizes to attain ${\mathbb{E}}[\min_t {\|\nabla f({\mathbf{x}}_t)\|}]\leq \epsilon$ is $\Omega(\epsilon^{-4})$, even for quadratic *convex* functions in moderate dimension and Gaussian noise (namely, all other assumptions are satisfied as well as convexity). This result is formalized as [Thm. \[thm:sgdlow\]]{} in Section \[sec:convex\].

It is important to note that the SGD algorithm, which is the main focus of this paper, is not necessarily an optimal algorithm (in terms of iteration complexity) for minimizing gradient norms in our stochastic optimization setting. For example, for convex problems, it is known that it is possible to achieve an iteration complexity of $\tilde{O}(\epsilon^{-2})$, strictly smaller than our $\Omega(\epsilon^{-4})$ lower bound (see [@foster2019complexity], and for a related result in the deterministic setting see [@nesterov2012make]). However, these algorithms are more complicated and less natural than plain SGD. Our results indicate that this algorithmic complexity might be a necessary price to pay in order to achieve optimal iteration complexity in some cases.

Setting and Notation {#sec:setting}
====================

We let bold-face letters denote vectors, use ${\mathbf{e}}_i$ to denote the canonical unit vector, and use $[T]$ as shorthand for $\{1,2,\ldots,T\}$.

We assume throughout that the objective $f$ maps ${\mathbb{R}}^d$ to ${\mathbb{R}}$, and either has an $L$-Lipschitz gradient for some fixed parameter $L>0$ or a $\rho$-Lipschitz Hessian for some $\rho>0$.

We consider algorithms which use a standard stochastic first-order oracle ([@Book:NemirovskyYudin; @agarwal2009information]) in order to minimize some optimality criteria: This oracle, given a point ${\mathbf{x}}_t$, returns $\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t$, where ${\boldsymbol{\xi}}_t$ is a random variable satisfying $${\mathbb{E}}[{\boldsymbol{\xi}}_t|{\mathbf{x}}_t]=0~~~\text{and}~~~{\mathbb{E}}[{\|{\boldsymbol{\xi}}_t\|}^2|{\mathbf{x}}_t]\leq \sigma^2$$ almost surely for some fixed $\sigma^2$. In this paper, we focus on optimality criteria involving minimizing gradient norms, using the Stochastic Gradient Descent (SGD) algorithm. This algorithm, given a budget of $T$ iterations and an initialization point ${\mathbf{x}}_1$, produces $T$ stochastic iterates ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_T$ according to $$\label{eq:sgd}
 {\mathbf{x}}_{t+1}~=~{\mathbf{x}}_t-\eta_t \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t)~,$$ where $\eta_t$ is a fixed step size parameter. In some cases, we will also allow the algorithm to perform an additional aggregation step, generating a point ${{\mathbf{x}_{\mathrm{out}}}}$ which is some function of ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_T$ (for example, the average $\frac{1}{T}\sum_{t=1}^{T}{\mathbf{x}}_t$). Additionally, in some of our results, we will allow the step size to be adaptive, and depend on the previous iterates (under appropriate assumptions), in which case we will use the notation $$\label{eq:adaptive_sgd}
 {\mathbf{x}}_{t+1} ={\mathbf{x}}_t - \eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t} \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t).$$

Regarding the initial conditions, we make the standard assumption[^1] that ${\mathbf{x}}_1$ has bounded suboptimality, i.e., $$f({\mathbf{x}}_1)-f({\mathbf{x}}_*)\leq \Delta$$ for some fixed $\Delta > 0$, where in the convex case, we assume ${\mathbf{x}}_*$ is some point ${\mathbf{x}}_* \in \arg\min_{{\mathbf{x}}}f({\mathbf{x}})$, and in the non-convex case, we assume ${\mathbf{x}}_*$ is a stationary point with $f({\mathbf{x}}_*) \leq f({\mathbf{x}}_t)$ for all $t\in [T]$. We note that some analyses (see for example [@allen2018make; @foster2019complexity]) replace the assumption $f({\mathbf{x}}_1)-f({\mathbf{x}}_*)\leq \Delta$ with the assumption ${\|{\mathbf{x}}_1-{\mathbf{x}}_*\|}\leq R$, but we do not consider this variant in this paper (in fact, some of our constructions rely on the fact that even if $f({\mathbf{x}}_1)-f({\mathbf{x}}_*)$ is small, ${\|{\mathbf{x}}_1-{\mathbf{x}}_*\|}$ might be very large). It should also be pointed out that in the non-convex setting, ${\mathbf{x}}_*$ might not be uniquely defined or even belong to a single connected set, which makes ${\|{\mathbf{x}}_1-{\mathbf{x}}_*\|}$ somewhat ambiguous.

Lower bounds in the non-convex case {#sec:nonconvex}
===================================

In this section, we present several lower bounds relating to first-order methods in the non-convex stochastic setting. We start by considering a wide range of first-order methods, showing that if we consider any point which is a *fixed* function of the iterates, then *no* meaningful, dimension-free worst-case bound can be attained on its expected gradient norm. We conclude that it is necessary for any useful optimality criterion to relate to more than one iterate in some way, as is indeed the case with the standard optimality criteria, which considers the average expected norm of the gradients ($\frac{1}{T} \sum_t {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|$) or the minimal expected norm of the gradients ($\min_t {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|$).

We then turn our focus to the SGD method under the standard set of assumptions (see [Sec. \[sec:setting\]]{}), and show that it requires $\Omega(\epsilon^{-4})$ iterations (or $\Omega(\epsilon^{-3})$ with Lipschitz Hessians) to attain a value of $\epsilon$ for any of the standard optimality criteria mentioned above.

Impossibility of minimizing the gradient at any fixed point {#subsec:fixedpoint}
-----------------------------------------------------------

In this subsection, we show that in the nonconvex setting, perhaps surprisingly, *no* meaningful iteration complexity bound can be provided on ${\|\nabla f({{\mathbf{x}_{\mathrm{out}}}})\|}$, where ${{\mathbf{x}_{\mathrm{out}}}}$ is the point returned by any fixed, deterministic aggregation scheme which depends continuously on the iterates and stochastic gradients (for example, some fixed weighted combination of the iterates).

To state the result, recall that SGD can be phrased in an oracle-based setting, where we model an optimization algorithm as interacting with a stochastic first-order oracle: Given an initial point ${\mathbf{x}}_1$, at every iteration $t=2,\ldots,T$, the algorithm chooses a point ${\mathbf{x}}_t$, and the oracle returns a stochastic gradient estimate ${\mathbf{g}}_t:=\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t$, where ${\mathbb{E}}[{\boldsymbol{\xi}}_t|{\mathbf{x}}_t]=0$ and ${\mathbb{E}}[{\|{\boldsymbol{\xi}}_t\|}^2|{\mathbf{x}}_t]\leq \sigma^2$ for some known $\sigma^2$. The algorithm then uses ${\mathbf{g}}_t$ (as well as ${\mathbf{g}}_1,\ldots,{\mathbf{g}}_{t-1}$ and ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_{t}$) to select a new point ${\mathbf{x}}_{t+1}$. After $T$ iterations, the algorithm returns a final point ${{\mathbf{x}_{\mathrm{out}}}}$, which depends on ${\mathbf{g}}_1,\ldots,{\mathbf{g}}_T$ and ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_T$.

\[thm:infdim\] Consider any deterministic algorithm as above, which satisfies the following:

-   There exists a finite $C_{T}$ (dependent only on $T$) such that for any initialization ${\mathbf{x}}_1$ and any $t\in [T]$, if ${\mathbf{g}}_1=\ldots={\mathbf{g}}_{t}=\mathbf{0}$, then ${\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_1\|}\leq C_{T}$. Moreover, if this holds for $t=T$, then ${\|{{\mathbf{x}_{\mathrm{out}}}}-{\mathbf{x}}_1\|}\leq C_T$.

-   For any $t\in [T]$, ${\mathbf{x}}_{t+1}$ is a fixed continuous function of ${\mathbf{x}}_1,{\mathbf{g}}_1,\ldots,{\mathbf{x}}_t,{\mathbf{g}}_t$, and ${{\mathbf{x}_{\mathrm{out}}}}$ is a fixed continuous function of ${\mathbf{x}}_1,{\mathbf{g}}_1,\ldots,{\mathbf{x}}_T,{\mathbf{g}}_T$.

Then for any $\delta\in (0,1)$, and any choice of random variables ${\boldsymbol{\xi}}_t$ satisfying the assumptions above, there exists a dimension $d$, a twice-differentiable function $f:{\mathbb{R}}^d\mapsto{\mathbb{R}}$ with $2$-Lipschitz gradients and $4$-Lipschitz Hessians, and an initialization point ${\mathbf{x}}_1$ satisfying $f({\mathbf{x}}_1)-\inf_{\mathbf{x}}f({\mathbf{x}})\leq 1$, such that with probability at least $1-\delta$, $${\|\nabla f({{\mathbf{x}_{\mathrm{out}}}})\|}\geq \frac{1}{2}$$ Moreover, if there is no stochastic noise (${\boldsymbol{\xi}}_t\equiv 0$), then the result holds for $d=1$.

Intuitively, the first condition in the theorem requires that the algorithm does not “move” too much from the initialization point ${\mathbf{x}}_1$, if all stochastic gradients are zero (this is trivially satisfied for SGD, and any other reasonable algorithm we are aware of). The second condition requires the iterates produced by the algorithm to depend continuously on the previous iterates and stochastic gradients (again, this is satisfied by SGD).

The theorem suggests that to get non-trivial results, we must either use a dimension-dependent analysis, use a non-continuous/adaptive/randomized scheme to compute ${{\mathbf{x}_{\mathrm{out}}}}$, or measure the performance of the generated sequence using an optimality criterion that does not depend on a fixed point (e.g., the average gradient $\frac{1}{T}\sum_{t=1}^{T}{\|\nabla f({\mathbf{x}}_t)\|}$ or $\min_{t}{\|\nabla f({\mathbf{x}}_t)\|}$). We note that the positive result of [@fang2019sharp] assumes both finite dimension, and computes ${{\mathbf{x}_{\mathrm{out}}}}$ according to an adaptive non-continuous decision rule (involving branching depending on how far the iterates have moved), hence there is no contradiction to the alluded theorem.

We will first prove the result in the case where there is no noise, i.e. ${\mathbf{g}}_t=\nabla f({\mathbf{x}}_t)$ deterministically, in which case ${\mathbf{x}}_2,\ldots,{\mathbf{x}}_{T}$ and ${{\mathbf{x}_{\mathrm{out}}}}$ are deterministic functions of ${\mathbf{x}}_1$. To that end, let $d=1$ and let $f(x)=s(x)$, where $s$ is the sigmoid-like function $$s(x)~=~\begin{cases}
    -\frac{1}{2} & x\leq -1\\
    \frac{2}{3}(x+1)^3  -\frac{1}{2}& x\in [-1,-\frac{1}{2}] \\
    -\frac{2}{3}x^3+x& x\in [-\frac{1}{2},\frac{1}{2}] \\
    \frac{2}{3}(x-1)^3+\frac{1}{2}& x\in [\frac{1}{2},1] \\
    \frac{1}{2} & x\geq 1\end{cases}$$ This function smoothly and monotonically interpolates between $-1/2$ at $x=-1$ at $1/2$ at $x=1$. It can be easily verified to have $2$-Lipschitz gradients and $4$-Lipschitz Hessians, and for any $x$, satisfies $f(x)-\inf_{x}f(x) \leq 1$.

Let us consider the iterates generated by the algorithm, $x_1,\dots,x_T$ and ${{x_{\mathrm{out}}}}$, as we make $x_1\rightarrow\infty$. Our function is such that $\nabla f(x)=0$ for all $x\geq 1$, so at every iteration, the algorithm gets $g_t=0$ as long as $x_t \geq 1$. Moreover, by the assumptions, as long as the gradients are zero, $|x_t-x_1|$ is bounded. As a result, by induction and our assumption that $|{{x_{\mathrm{out}}}}-x_1|$ is bounded, we get that ${{x_{\mathrm{out}}}}\rightarrow\infty$. A similar argument shows that when $x_1\rightarrow -\infty$, we also have ${{x_{\mathrm{out}}}}\rightarrow -\infty$.

Next, we argue that ${{x_{\mathrm{out}}}}$ is a continuous function of $x_1$. Indeed, $x_2$ is a continuous function of $x_1$, since it is a continuous function of $g_1=\nabla f(x_1)$ by assumption, and $\nabla f(x_1)$ is Lipschitz (hence continuous) in $x_1$, and compositions of continuous functions is continuous. By induction, a similar arguments holds for $x_t$ for any $t$, and hence also to ${{x_{\mathrm{out}}}}$.

Overall, we showed that ${{x_{\mathrm{out}}}}$ is a continuous function of $x_1$, that ${{x_{\mathrm{out}}}}\rightarrow\infty$ when $x_1\rightarrow\infty$, and that ${{x_{\mathrm{out}}}}\rightarrow-\infty$ when $x_1\rightarrow-\infty$. Therefore, by the mean value theorem, there exists some $x_1$ for which ${{x_{\mathrm{out}}}}$ is precisely zero, in which case $|f'({{x_{\mathrm{out}}}})|=|f'(0)|=|s'(0)|=1$, satisfying the Theorem statement.

It remains to prove the theorem in the noisy case, where ${\boldsymbol{\xi}}_i$ are non-zero random variables. In that case, instead of choosing $f(x)=s(x)$, we let $f({\mathbf{x}})=s(\langle {\mathbf{x}}, {\mathbf{e}}_r \rangle)$, where the coordinate $r$ is defined as $$r:=\arg\min_{j\in [d]} \max_{t\in [T]}{\mathbb{E}}[\langle{\boldsymbol{\xi}}_t, {\mathbf{e}}_j\rangle^2].$$ Since we assume $\max_t {\mathbb{E}}[{\|{\boldsymbol{\xi}}_t\|}^2]=\max_t \sum_{j=1}^{d}{\mathbb{E}}[\langle{\boldsymbol{\xi}}_{t}, {\mathbf{e}}_j\rangle^2]$ is bounded by $\sigma^2$ independently of $d$, it follows that the variance of ${\boldsymbol{\xi}}_1,\ldots,{\boldsymbol{\xi}}_t$ along coordinate $r$ goes to zero as $d\rightarrow \infty$. Therefore, by making $d$ large enough and using Chebyshev’s inequality, we can ensure that $\max_t |\langle {\boldsymbol{\xi}}_{t},{\mathbf{e}}_j\rangle|$ is arbitrarily small with arbitrarily high probability. Since the gradients of $f$ are Lipschitz, and we assume each ${\mathbf{x}}_{t+1}$ is a continuous function of the noisy gradients ${\mathbf{g}}_1,{\mathbf{g}}_2,\ldots,{\mathbf{g}}_t$, it follows that the trajectory of ${\mathbf{x}}_1,{\mathbf{x}}_2,\ldots,{\mathbf{x}}_{T}$ and ${{\mathbf{x}_{\mathrm{out}}}}$ on the $j$-th coordinate can be made arbitrarily close to the noiseless case analyzed earlier (where ${\boldsymbol{\xi}}_t\equiv \mathbf{0}$), with arbitrarily high probability. In particular, we can find an initialization point ${\mathbf{x}}_1$ such that the $j$-th coordinate of ${{\mathbf{x}_{\mathrm{out}}}}$ is arbitrarily close to $0$, hence the gradient is arbitrarily close to $1$ (and in particular, larger than $1/2$).

The theorem considers deterministic algorithms for simplicity, but the same proof idea holds for larger families of randomized algorithms, where the randomness is used “obliviously”. For example, consider the popular technique of adding random perturbations to the iterates: If the perturbations have a fixed distribution with finite variance, then we can always embed our construction in a high enough dimension, so that the effective variance of the perturbations is arbitrarily small, and we are back to the deterministic setting.

Lower bounds on SGD {#subsec:sgdlowbound}
-------------------

In this subsection, we focus on the analysis of SGD in the nonconvex setting. We present two main results: A lower bound on the performance of SGD with an aggregation step for objectives with $L$-Lipschitz gradient, followed by a lower bound in the case where the objective has $\rho$-Lipschitz Hessian that applies to “plain” SGD methods that do not perform an aggregation step. In both cases, the step sizes chosen by the method are allowed to be adaptive, in the sense that they are allowed to depend on past iterates and gradients. This dependence is *not* allowed to be completely general, but rather we assume that the dependence on the past iterates and gradients is done through a function of their norm and the dot-products between them (in the Lipschitz Hessian case, we also allow the step size to depend on the Hessians). Note, that all commonly used adaptive schemes (including Adagrad [@duchi2011adaptive], normalized gradient [@nesterov1984minimization; @kiwiel2001convergence], among others) follow this type of adaptive scheme.

We start the analysis with a technical lemma.

\[L:detbound\] Let $f:{\mathbb{R}}^d \mapsto {\mathbb{R}}$ be a function with $L$-Lipschitz gradient, and assume that the vectors ${\mathbf{y}}_1,\dots,{\mathbf{y}}_m, {\mathbf{z}}_1,\dots,{\mathbf{z}}_n, {\boldsymbol{\gamma}}\in {\mathbb{R}}^d$ ($n,m\in\mathbb{N}$) are such that

1.  \[itm:grad\_eq\] $\nabla f({\mathbf{y}}_1) = \dots = \nabla f({\mathbf{y}}_m)= \nabla f({\mathbf{z}}_1) = \dots = \nabla f({\mathbf{z}}_n) = {\boldsymbol{\gamma}}$,

2.  \[itm:constant\_vals\] $f({\mathbf{y}}_1)=\dots=f({\mathbf{y}}_m)$, and

3.  \[itm:constant\_prod\] $\langle {\boldsymbol{\gamma}}, {\mathbf{y}}_1\rangle = \dots = \langle {\boldsymbol{\gamma}}, {\mathbf{y}}_m\rangle$.

Then there exists a function $\hat f$ with $L$-Lipschitz gradient that has the same first-order information as $f$ at $\{{\mathbf{z}}_i\}_{i\in [n]}$, i.e., for all $i\in [n]$ $$\begin{aligned}
    & \hat f({\mathbf{z}}_{i}) = f({\mathbf{z}}_{i}), \\
    & \nabla \hat f({\mathbf{z}}_i) = \nabla f({\mathbf{z}}_i) = {\boldsymbol{\gamma}},\end{aligned}$$ and in addition, for all $j\in [m]$ $$\begin{aligned}
    & \hat f({\mathbf{y}}_j) \geq \min_{k\in [n]} f({\mathbf{z}}_k) - \frac{1}{L} \|{\boldsymbol{\gamma}}\|^2, \\
    & \nabla \hat f({\mathbf{y}}_j) = \nabla f({\mathbf{y}}_j) = {\boldsymbol{\gamma}}.\end{aligned}$$

We postpone the proof of this lemma to the appendix and turn to present the first main result of this subsection.

\[thm:aggregation\_step\] Consider a first-order method that given a function $f:{\mathbb{R}}^d\rightarrow{\mathbb{R}}$ and an initial point ${\mathbf{x}}_1\in {\mathbb{R}}^d$ generates a sequence of points $\{{\mathbf{x}}_i\}$ satisfying $$\begin{aligned}
     & {\mathbf{x}}_{t+1} = {\mathbf{x}}_t + \eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t} \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t), \quad t\in [T-1],\end{aligned}$$ where ${\boldsymbol{\xi}}_i$ are some random noise vectors, and returns a point ${{\mathbf{x}_{\mathrm{out}}}}\in {\mathbb{R}}^d$ as a non-negative linear combination of the iterates: $${{\mathbf{x}_{\mathrm{out}}}}= \sum_{t=1}^T \zeta^{(t)}_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_T} {\mathbf{x}}_t.$$ We further assume that the step sizes $\eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t}$ and aggregation coefficients $\zeta^{(t)}_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_T}$ are deterministic functions of the norms and inner products between the vectors ${\mathbf{x}}_1,\dots,{\mathbf{x}}_t, \nabla f({\mathbf{x}}_1)+{\boldsymbol{\xi}}_1,\dots, \nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t$. Then for any $L,\Delta, \sigma\in {\mathbb{R}}_{++}$ and $T\in\mathbb{N}$ there exists a function $f:{\mathbb{R}}^{T}\mapsto {\mathbb{R}}$ with $L$-Lipschitz gradient, a point ${\mathbf{x}}_1\in {\mathbb{R}}^T$ and independent random variables ${\boldsymbol{\xi}}_t$ with ${\mathbb{E}}[{\boldsymbol{\xi}}_t]=0$ and ${\mathbb{E}}[\|{\boldsymbol{\xi}}_t\|^2]=\sigma^2$ such that $\forall t\in[T]$ $$\begin{aligned}
        & f({\mathbf{x}}_1) - f({\mathbf{x}}_t) \overset{\text{a.s.}}{\leq} \Delta, \\
        & \nabla f({\mathbf{x}}_t) \overset{\text{a.s.}}{=} {\boldsymbol{\gamma}},
    \end{aligned}$$ and in addition, $$\begin{aligned}
        & f({\mathbf{x}}_1) - f({{\mathbf{x}_{\mathrm{out}}}}) \overset{\text{a.s.}}{\leq} \Delta + \frac{\sigma}{2L} \sqrt{\frac{L \Delta}{T-1} }, \\
        & \nabla f({{\mathbf{x}_{\mathrm{out}}}}) \overset{\text{a.s.}}{=} {\boldsymbol{\gamma}}.
    \end{aligned}$$ where ${\boldsymbol{\gamma}}\in {\mathbb{R}}^T$ is a vector such that $$\|{\boldsymbol{\gamma}}\|^2 = \frac{\sigma}{2} \sqrt{\frac{L \Delta}{T-1} }.$$

We start by assuming that the algorithm performs gradient steps with fixed step size $\eta_t$ and aggregation coefficients $\zeta_i$, i.e., the algorithm is defined by the rule $$\begin{aligned}
    & {\mathbf{x}}_{t+1} = {\mathbf{x}}_t - \eta_t (\nabla f({\mathbf{x}}_t) + {\boldsymbol{\xi}}_t), \quad t\in[T-1],  \\
    & {{\mathbf{x}_{\mathrm{out}}}}= \sum_{t=1}^T \zeta_i {\mathbf{x}}_i.\end{aligned}$$ Under this assumption, the proof proceeds by

defining an adversarial objective and noise distribution,

showing that the iterates of SGD on that example posses the claimed properties, then

using [Lemma \[L:detbound\]]{}, modifying the objective at ${{\mathbf{x}_{\mathrm{out}}}}$ so that the claimed bounds at ${{\mathbf{x}_{\mathrm{out}}}}$ are attained while keeping the behavior of the function at the previous iterates unaffected.

We start by defining an adversarial example, choosing the noise vectors $\{{\boldsymbol{\xi}}_t\}$ to be independent random variables distributed such that $$\label{def:nonconvex_xi}
    P({\boldsymbol{\xi}}_t=\pm \sigma {\mathbf{e}}_{t+1}) = \frac{1}{2}, \quad t\in [T-1],$$ where ${\mathbf{e}}_i$ stands for the canonical unit vector, and defining the objective $f:=f_{\{\eta_t\},\{\zeta_t\}}:{\mathbb{R}}^{T} \mapsto {\mathbb{R}}$ by $$\label{def:nonconvex_f}
    f_{\{\eta_t\},\{\zeta_t\}}({\mathbf{x}}) := G \cdot \langle {\mathbf{x}}, {\mathbf{e}}_1\rangle + \sum_{t=1}^{T-1} h_t (\langle {\mathbf{x}}, {\mathbf{e}}_{t+1}\rangle),$$ where $G \geq 0$ is such that $$G^2 = \frac{\sigma}{2} \sqrt{\frac{L \Delta}{T-1} },$$ and the functions $h_t$ are defined as follows: First denote by $h^{(1,L)}_{b,-}(x)$ and $h^{(1,L)}_{b,+}(x)$ the functions (see [Fig. \[fig:sfunc\]]{}) $$\begin{aligned}
& h^{(1,L)}_{b,+}(x) := \begin{cases}
    \frac{L}{2} x^2 &   |x| \leq b/4,\\
    \frac{L}{16} b^2  - \frac{L}{2} (|x|-b/2)^2 & b/4 < |x| < b/2, \\
    \frac{L}{16} b^2 & |x|\geq b/2,
\end{cases}\end{aligned}$$ $$\begin{aligned}
& h^{(1,L)}_{b,-}(x) := \begin{cases}
    0               &  |x| \leq b/2,\\
    \frac{L}{2} (|x|-b/2)^2 &  b/2 \leq |x| \leq 3b/4,\\
    \frac{L}{16} b^2  - \frac{L}{2} (|x-b/2|-b/2)^2 & 3b/4 < |x| < b, \\
    \frac{L}{16} b^2 & |x|\geq b,
\end{cases}\end{aligned}$$ then at iterates $t$ where the aggregation coefficient $|\zeta_{t+1}| \leq \frac{1}{2}$, take $h_t$ to be $h_t=h^{(1,L)}_{|\eta_t| \sigma,-}(x)$, and otherwise take $h_t=h^{(1,L)}_{|\eta_t| \sigma,+}$. Note that for all $t\in[T-1]$, $$\begin{aligned}
    & h_t(0)=0, \\
    & h_t(x)=h_t(-x), \quad \forall x\in {\mathbb{R}}, \\
    & h_t'(0)=h_t'(\eta_t \sigma)=h_t'(-\eta_t \sigma)=h_t'(\zeta_{t+1} \eta_t \sigma)=h_t'(-\zeta_{t+1} \eta_t \sigma)=0,\end{aligned}$$ and that $h_t$ has $L$-Lipschitz gradient. From the definition of $f$ we conclude that (being a separable sum of functions with $L$-Lipschitz gradient) $f$ also shares the $L$-Lipschitz gradient of the functions $h_t$.

![$h^{(1,1)}_{1,-}$ and $h^{(1,1)}_{1,+}$.[]{data-label="fig:sfunc"}](sfig1.eps){width="0.6\linewidth"}

We now turn to analyze the dynamics of SGD when applied on the function $f$ defined above. Given the objective $f$ and the staring point ${\mathbf{x}}_1=0$, the algorithm at the first iteration sets $${\mathbf{x}}_2 = {\mathbf{x}}_1 - \eta_1 (\nabla f({\mathbf{x}}_1)+ {\boldsymbol{\xi}}_1) = (-\eta_1 G, \pm \eta_1 \sigma, 0, \dots, 0)^\top,$$ hence, from the properties of $h_1$, we get $$\begin{aligned}
    & f({\mathbf{x}}_2) = - G^2 \eta_1 + h_1(\pm \eta_1 \sigma) + \sum_{t=2}^{T-1} h_t(0) = - G^2 \eta_1 + h_1(\eta_t \sigma), \\
        & \nabla f({\mathbf{x}}_2) = G {\mathbf{e}}_1 + h_1'(\pm \eta_1 \sigma){\mathbf{e}}_2 + \sum_{t=2}^{T-1} h_t'(0) {\mathbf{e}}_{t+1} = G {\mathbf{e}}_1.\end{aligned}$$ Similarly, at the $t$-th iteration, $t\in [T-1]$, the algorithm sets $$\label{eq:x_t_value}
    {\mathbf{x}}_{t+1} = {\mathbf{x}}_t - \eta_t (\nabla f({\mathbf{x}}_t)+ {\boldsymbol{\xi}}_t) ) = (-\sum_{k=1}^t \eta_k G, \pm \eta_1 \sigma, \dots, \pm \eta_t \sigma, 0, \dots, 0)^\top,$$ which leads to $$\begin{aligned}
    & f({\mathbf{x}}_t) = - G^2 \sum_{k=1}^{t-1} \eta_k + \sum_{k=1}^{t-1} h_k(\eta_k \sigma), \\
    & \nabla f({\mathbf{x}}_t) = G {\mathbf{e}}_1. \label{eq:nabla_F_x_t}\end{aligned}$$ At the aggregation step, the algorithm sets $$\label{eq:x_out}
    {{\mathbf{x}_{\mathrm{out}}}}= \sum_{t=1}^T \zeta_t {\mathbf{x}}_t = (-\sum_{t=1}^T \zeta_t \sum_{k=1}^{t-1} \eta_k G, \pm \zeta_2 \eta_1 \sigma, \dots, \pm \zeta_T \eta_{T-1} \sigma)^\top,$$ then by the properties of $h_t$, we get $$\begin{aligned}
    & f({{\mathbf{x}_{\mathrm{out}}}}) = - G^2 \sum_{t=1}^T \zeta_t \sum_{k=1}^{t-1} \eta_k + \sum_{k=1}^{t-1} h_k(\zeta_{k+1} \eta_k \sigma), \label{eq:F_xout} \\
    & \nabla f({{\mathbf{x}_{\mathrm{out}}}}) = G {\mathbf{e}}_1, \label{eq:nabla_F_xout}\end{aligned}$$ where the first equality follows since $h_t$ is even, and second equality follows from $h_t'(\pm \zeta_{t+1} \eta_t \sigma)=0$. We get $$\begin{aligned}
  f({\mathbf{x}}_1) - f({\mathbf{x}}_t)  & = 0 + G^2 \sum_{k=1}^{t-1} \eta_k - \sum_{k=1}^{t-1} h_k(\eta_k \sigma) = \sum_{k=1}^{t-1} \left(G^2 \eta_k - h_k(\eta_k \sigma)\right),\end{aligned}$$ and therefore $$\begin{aligned}
    f({\mathbf{x}}_1) - f({\mathbf{x}}_t)
    & = \sum_{k=1}^{t-1} \left(G^2 \eta_k - h_k(\eta_k \sigma)\right) \\
    & = \sum_{k=1}^{t-1} \left(\frac{\sigma}{2} \sqrt{\frac{L \Delta}{T - 1} } \eta_k - \frac{L}{16} \eta_k^2 \sigma^2\right) \\
    & = \sum_{k=1}^{t-1} \left(\sqrt{\frac{\Delta}{T-1} } \left(\frac{1}{2} \eta_k \sigma \sqrt{L}\right) - \frac{1}{4} \left(\frac{1}{2}\eta_k \sigma \sqrt{L}\right)^2 \right) \\
    & \leq (t-1) \frac{\Delta}{T-1} \leq \Delta,\end{aligned}$$ where the one before last inequality follows since $a x - \frac{1}{4} x^2 \leq a^2$ for all $x\in {\mathbb{R}}$.

To complete our treatment of the fixed-step case, we turn to show that it is possible to modify the value of $f$ at ${{\mathbf{x}_{\mathrm{out}}}}$ without affecting the first-order information at the previous iterates and such that the claimed bound on $f({{\mathbf{x}_{\mathrm{out}}}})$ is satisfied. For this purpose, we continue to show that [Lemma \[L:detbound\]]{} can be applied when taking for ${\mathbf{y}}_1,\dots,{\mathbf{y}}_m$ all the possible values for ${{\mathbf{x}_{\mathrm{out}}}}$ , and for ${\mathbf{z}}_1,\dots,{\mathbf{z}}_n$ all possible values the random variables $\{{\mathbf{x}}_t\}_{t\in [T]}$ can attain .

Indeed, in view of  and , the first condition of [Lemma \[L:detbound\]]{} holds with ${\boldsymbol{\gamma}}= G {\mathbf{e}}_1$. Furthermore, the second requirement follows from , and the third requirement follows since $$\langle \nabla f({{\mathbf{x}_{\mathrm{out}}}}), {{\mathbf{x}_{\mathrm{out}}}}\rangle = -\sum_{t=1}^T \zeta_t \sum_{k=1}^{t-1} \eta_k G^2$$ does not depend on the sign of the noise vectors ${\boldsymbol{\xi}}_t$. As all the requirements of [Lemma \[L:detbound\]]{} hold, we conclude that there exists a function $\hat f$ that shares the the first-order information of $f$ at the iterates, and satisfies the claimed properties $$\begin{aligned}
    & \hat f({{\mathbf{x}_{\mathrm{out}}}}) \overset{\text{a.s.}}{\geq} \min_k f({\mathbf{x}}_k) - \frac{G^2}{L}, \\
    & \nabla \hat f({{x_{\mathrm{out}}}}) \overset{\text{a.s.}}{=} G {\mathbf{e}}_1.\end{aligned}$$ As SGD does not have access the objective beyond the first-order information at the iterates, we conclude that the algorithm proceeds on $\hat f$ in exactly the same dynamics as it does on $f$, maintaining all bounds derived above.

We turn to the general, adaptive step-size case: $$\begin{aligned}
    & {\mathbf{x}}_{t+1} = {\mathbf{x}}_t + \eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t} \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t), \quad t\in [T-1], \\
    & {{\mathbf{x}_{\mathrm{out}}}}= \sum_{t=1}^T \zeta^{(t)}_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_T} {\mathbf{x}}_i.\end{aligned}$$ Here, our goal is to show that constants $\eta_t$ and $\zeta_t$ can be chosen in such a way that the method, when applied on $f_{\{\eta_t\},\{\zeta_t\}}$ constructed above, chooses step sizes and aggregation coefficients that are almost surely equal to the selected constants, i.e, $$\eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t} \overset{\text{a.s.}}{=} \eta_t, \quad \zeta^{(t)}_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_T} \overset{\text{a.s.}}{=} \zeta_t,$$ and thus the proof for the fixed-step case can proceed without change.

We use the following procedure to select $\eta_t$ and $\zeta_t$. We start by executing the first step of the algorithm on the initial point ${\mathbf{x}}_1=0$ and $f$, where the constants $\{\eta_t\}$ and $\{\zeta_t\}$ are set to arbitrarily values. Note that

the first-order information of $f$ at ${\mathbf{x}}_1$ is independent of the choice for $\eta_t, \zeta_t$, and

the norm of the noise vector ${\boldsymbol{\xi}}_1$ and its inner product with ${\mathbf{x}}_1$ and $\nabla f({\mathbf{x}}_1)$ are independent of the specific direction chosen for the noise; therefore, by the assumption on the step size $\eta_{{\mathbf{x}}_1}$, it is independent of the specific value for ${\boldsymbol{\xi}}_1$, i.e., it is almost surely a constant.

We denote this constant by $\eta_1$.

We continue by executing the second step of the algorithm on $f$, using the value of $\eta_1$ chosen above while keeping the constants $\eta_2,\dots,\eta_{T-1}$, $\{\zeta_t\}_{t\in[T]}$ set to arbitrary values. As in the first iteration,

the first-order information of $f$ at ${\mathbf{x}}_2$ is independent of the specific choice for $\eta_2,\dots,\eta_{T-1}$, $\{\zeta_t\}_{t\in[T]}$ and

the norm of the noise vector ${\boldsymbol{\xi}}_2$ and its inner product with ${\mathbf{x}}_1, {\mathbf{x}}_2$, $\nabla f({\mathbf{x}}_1), \nabla f({\mathbf{x}}_2)$ and ${\boldsymbol{\xi}}_1$ are independent of the specific direction chosen for the noise; therefore by the assumption on $\eta_{{\mathbf{x}}_1,{\mathbf{x}}_2}$ it is almost surely a constant.

As before, we denote the step size performed by the algorithm $\eta_2$.

Continuing in this fashion, we obtain a set of constants $\eta_1,\dots,\eta_{T-1}$ with the property that when applying the method on $f=f_{\{\eta_t\},\{\zeta_t\}}$, then for any choice of aggregation coefficients $\{\zeta_t\}$ the step-sizes chosen by the method are almost surely equal to $\{\eta_t\}$. Finally, executing the aggregation step, by the assumption on the aggregation function, the coefficients are almost surely constants, which we denote by $\zeta_1,\dots,\zeta_{T}$. To conclude, we have found a function $f=f_{\{\eta_t\},\{\zeta_t\}}$ such that the step sizes performed by the method on $f$ are almost surely $\eta_1,\dots,\eta_{T-1}$ and the aggregation coefficients chosen by the method are almost surely $\zeta_1,\dots,\zeta_{T}$, hence the proof can continue as in the fixed-step case.

The example provided by [Thm. \[thm:aggregation\_step\]]{} comes with a guarantee that the gradient of the objective at all iterates is almost surely a constant; as a result, the theorem is applicable for forming lower bounds for all first-order optimality criteria used in the literature, including the best expected gradient norm $\min_t {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|$, average expected gradient norm $\frac{1}{T} \sum_t {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|$, and expected norm of the average gradient ${\mathbb{E}}\|\frac{1}{T} \sum_t \nabla f({\mathbf{x}}_t)\|$, both when taking the actual gradient and when taking the noisy version of the gradient.

Note that although the theorem does not directly consider randomized sampling schemes for computing ${{\mathbf{x}_{\mathrm{out}}}}$, the performance of any scheme that samples ${{\mathbf{x}_{\mathrm{out}}}}$ out of $\{{\mathbf{x}}_1,\dots,{\mathbf{x}}_T\}$ is bounded from below by the optimality criterion $\min_{t}{\|\nabla f({\mathbf{x}}_t)\|}$, making the guarantees by the theorem applicable.

The example provided by the theorem comes with a guarantee that $f({\mathbf{x}}_1) - f({\mathbf{x}}_t)\leq \Delta$ holds almost surely for any $t$: This is a strictly weaker assumption on ${\mathbf{x}}_1$ than used in the standard bounds in this setting, which require $f({\mathbf{x}}_1) - f({\mathbf{x}}_*)\leq \Delta$ with ${\mathbf{x}}_*$ being a stationary point with $f({\mathbf{x}}_*)\leq {\mathbb{E}}f({\mathbf{x}}_T)$. Note that although the specific function used in the proof of the theorem does not have any stationary points, the construction can be adjusted at areas that are far enough from the points queried by the method such that a stationary point (see e.g., [Lemma \[L:detbound\]]{}).

Setting $$\Delta \leftarrow \Delta - \frac{ \sigma \sqrt{\Delta  L (T-1)+\sigma ^2/16}-\sigma^2/4}{2L(T-1)}$$ in [Thm. \[thm:aggregation\_step\]]{}, we get (after some basic algebra) that $\forall t\in \{1,\dots, T,\mathrm{out}\}$ $$\begin{aligned}
    & f({\mathbf{x}}_1) - f({\mathbf{x}}_t) \overset{\text{a.s.}}{\leq} \Delta, \\
    & \| \nabla f({\mathbf{x}}_t) \|^2 \overset{\text{a.s.}}{\geq} \frac{ \sigma \sqrt{\Delta  L (T - 1)+\sigma ^2/16}-\sigma^2/4}{2(T - 1)} \geq \frac{\sigma}{2} \sqrt{\frac{L \Delta}{T - 1} } - \frac{\sigma^2}{8(T - 1)},\end{aligned}$$ establishing that SGD with an additional aggregation step require $\Omega(\epsilon^{-4})$ iterations to reach a value smaller than $\epsilon$ for all standard optimality criteria.

\[rem:tight\_bounds\] Consider the upper bound by Ghadimi and Lan (see [Thm. \[T:upper\_noncovex\]]{} in the appendix) and set the step size by $$\label{eq:optimal_step}
    \eta_t \equiv \eta:=\sqrt{\frac{2\Delta}{(T-1)L \sigma^2}},$$ where $\Delta$ is an upper bound on $f({\mathbf{x}}_1)-f({\mathbf{x}}_*)$. We obtain $$\begin{aligned}
    \min_{t \in [T]} \|\nabla f({\mathbf{x}}_t)\|^2 
    \leq \frac{2\Delta + L (T-1) \eta^2 \sigma^2}{(T-1) \eta (2-L \eta)}
    \underset{T\gg 1}{\approx}
    \frac{2\Delta + L (T-1) \eta^2 \sigma^2}{2 (T-1) \eta}
    = \sqrt{2}\sigma \sqrt{\frac{L \Delta}{T-1}},\end{aligned}$$ which establishes on one hand, that the lower bound obtained in [Thm. \[thm:aggregation\_step\]]{} on the iterates ${\mathbf{x}}_t$ is tight up to the constant factor $2\sqrt{2}$, and on the other hand, establishes that the constant step-size scheme  is optimal up to the same constant.

The second main result of this subsection gives a lower bound on the performance of “plain” SGD methods (i.e., methods that do not perform an aggregation step) acting on objectives with Lipchitz Hessians.

\[thm:nonconvex\] Consider a method that given a function $f:{\mathbb{R}}^d\rightarrow{\mathbb{R}}$ and an initial point ${\mathbf{x}}_1\in {\mathbb{R}}^d$ generates a sequence of points $\{{\mathbf{x}}_t\}$ satisfying $${\mathbf{x}}_{t+1} = {\mathbf{x}}_t + \eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t} \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t),$$ where ${\boldsymbol{\xi}}_t$ are some random noise vectors. We further assume that the step sizes $\eta_{{\mathbf{x}}_1,\dots,{\mathbf{x}}_t}$ are deterministic functions of the norms and inner products between ${\mathbf{x}}_1,\dots,{\mathbf{x}}_t, \nabla f({\mathbf{x}}_1)+{\boldsymbol{\xi}}_1,\dots, \nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t$ and may also depend on the exact second-order information $\nabla^2 f({\mathbf{x}}_1),\dots, \nabla^2 f({\mathbf{x}}_t)$. Then for any $\rho,\Delta,\sigma \in {\mathbb{R}}_{++}$ and $T\in\mathbb{N}$ there exists a function $f:{\mathbb{R}}^{T}\mapsto {\mathbb{R}}$ with $\rho$-Lipschitz Hessian, ${\mathbf{x}}_1\in {\mathbb{R}}^T$, and independent random variables ${\boldsymbol{\xi}}_t$ with ${\mathbb{E}}[{\boldsymbol{\xi}}_t]=0$ and ${\mathbb{E}}[\|{\boldsymbol{\xi}}_t\|^2]=\sigma^2$ such that $\forall t\in[T]$ $$\begin{aligned}
        & f({\mathbf{x}}_1) - f({\mathbf{x}}_t) \overset{\text{a.s.}}{\leq} \Delta, \\
        & \|\nabla f({\mathbf{x}}_t)\|^2 \overset{\text{a.s.}}{=} {\boldsymbol{\gamma}},
    \end{aligned}$$ where ${\boldsymbol{\gamma}}\in {\mathbb{R}}^T$ is a vector that satisfies $$\|{\boldsymbol{\gamma}}\|^2 = \frac{\sigma}{2}\left(\frac{\rho \Delta ^2}{ (T-1)^2}\right)^{1/3}.$$

We proceed as in the proof of [Thm. \[thm:aggregation\_step\]]{}, taking for $G$ the positive value that satisfies $$G^2 
        = \frac{3 \sigma}{32} \left(\frac{16^2 \rho \Delta ^2}{ (T-1)^2}\right)^{1/3}
    \geq \frac{\sigma}{2}\left(\frac{\rho \Delta ^2}{ (T-1)^2}\right)^{1/3}, \\$$ and set $h_t:=h^{(2,\rho)}_{|\eta_t| \sigma}$, with $h^{(2,\rho)}_{b}$ defined by (see [Fig. \[fig:sfunc2\]]{}) $$\begin{aligned}
    & h^{(2,\rho)}_{b}(x) := \begin{cases}
        \frac{\rho}{6} |x|^3 &   |x| \leq b/4,\\
        \frac{\rho}{192} \left(b^3-12 b^2 |x|+48 b x^2-32 |x|^3\right) &   b/4 \leq |x| < 3b/4,\\
        \frac{\rho}{32} b^3 - \frac{\rho}{6} \left(b - |x| \right)^3 & 3b/4 \leq |x| < b, \\
        \frac{\rho}{32} b^3 & |x|\geq b.
    \end{cases}\end{aligned}$$ It is straightforward to verify that $h_t$ has $\rho$-Lipschitz Hessian, and as in the Lipschitz gradient case, we have $$\begin{aligned}
    & h_t(0)=0, \\
    & h_t(x)=h_t(-x), \quad \forall x\in {\mathbb{R}}, \\
    \text{and}\quad & h_t'(0)=h_t'(\eta_t \sigma)=h_t'(-\eta_t \sigma)=0.\end{aligned}$$

Proceeding with new values, we reach $$\begin{aligned}
    & f({\mathbf{x}}_1) - f({\mathbf{x}}_t) \\
    & = \sum_{k=1}^{t-1} \left(G^2 \eta_k - h^{(2)}_{|\eta_k| \sigma}(|\eta_k| \sigma)\right) \\
    & = \sum_{k=1}^{t-1} \left( \frac{3 \sigma}{32}\left(\frac{16^2 \rho \Delta ^2}{ (T-1)^2}\right)^{1/3} \eta_k - \frac{\rho}{32} |\eta_k|^3 \sigma^3\right) \\
        & = \frac{1}{32} \sum_{k=1}^{t-1} \left(3 \left(\frac{16^2 \Delta ^2} {(T-1)^2}\right)^{1/3} (\rho^{1/3} \sigma \eta_k) - |\rho^{1/3} \eta_k \sigma|^3\right) \\
    & \leq (t-1) \frac{\Delta}{T-1} \leq \Delta,\end{aligned}$$ where the one before last inequality follows from the inequality $3 a x - |x|^3 \leq 2 a^{\frac{3}{2}}$.

Finally, note that $h''_t (\eta_t \sigma) = h''_t (-\eta_t \sigma) = 0$, and as a result, the second-order information of $f$ at all iterates is identically zero, thus the proof in the adaptive step-size case can proceed without change.

![$h^{(2,1)}_{1}$.[]{data-label="fig:sfunc2"}](sfig2.eps){width="0.6\linewidth"}

Note that the main missing component needed for establishing a result on SGD with aggregation steps in the Lipschitz-Hessian case is a set of necessary and sufficient interpolation conditions for Lipschitz-Hessian functions (as in the case of Lipschitz-gradient, [Thm. \[T:nonconvex\_interpolation\]]{}). The existence of such conditions remains an open question.

Lower bounds in the convex quadratic case {#sec:convex}
=========================================

In this section, we continue our analysis of the SGD method, showing that even for convex, quadratic functions in moderate dimensions, and a standard Gaussian noise, SGD cannot achieve an iteration complexity better than ${\mathcal{O}}(\epsilon^{-4})$ in order for any of its iterates to have gradient norm less than $\epsilon$. Note that for quadratic functions, the Hessian is constant, so the result still holds under additional Lipschitz assumptions on the Hessian and higher-order derivatives. We emphasize that the lower bounds only hold for the iterates themselves, without any aggregation step. Formally, we have the following:

\[thm:sgdlow\] Consider the SGD method defined by $${\mathbf{x}}_{t+1} = {\mathbf{x}}_t + \eta_t \cdot (\nabla f({\mathbf{x}}_t)+{\boldsymbol{\xi}}_t),  \quad t\in [T-1],$$ for some $T>1$ and suppose that the step sizes $\eta_1,\ldots,\eta_{T-1}$ are non-negative and satisfy at least one of the following conditions:

1.  *(Small step sizes)* $\max_{t\in [T-1]} \eta_t\leq 1/L$, and $\sum_{t=1}^{T-1}\eta_t \leq c\sqrt{T}/L$ for some constant $c$ (independent of the problem parameters).

2.  *(Fixed step sizes)* $\eta_t$ is the same for all $t$.

3.  *(Polynomial decay schedule)* $\eta_t = \frac{a}{b+t^{\theta}}$ for some non-negative constants $a,b,\theta$ (independent of the problem parameters).

Then for any $\delta\in (0,1)$, there exists a *quadratic* function $f$ on ${\mathbb{R}}^d$ (for any $d\geq d_0$ with $d_0={\mathcal{O}}(\log(T/\delta)\sigma^2T/(L^2\Delta))$ with $L$-Lipschitz gradients, and ${\mathbf{x}}_1$ for which $f({\mathbf{x}}_1)-\inf_{{\mathbf{x}}}f({\mathbf{x}})\leq \Delta$, such that if ${\boldsymbol{\xi}}_t$ has a Gaussian distribution ${\mathcal{N}}(\mathbf{0},\frac{\sigma^2}{d}I_d)$, with probability at least $1-\delta$, $$\min_{t\in [T-1]}{\|\nabla f({\mathbf{x}}_t)\|}^2 \geq c_0 \frac{\min\{L \Delta, \sigma^2\}}{\sqrt{T}},$$ where $c_0$ is a positive constant depending only on the constants in the conditions stated above.

We note that all standard analyses for (non-adaptive) SGD methods rely on one of these step size strategies. Moreover, the proof technique can plausibly be extended to other step sizes. Thus, the theorem provides a strong indication that SGD (without an aggregation step) cannot achieve a better iteration complexity, at least when the optimality criterion is $\min_t{\|\nabla f({\mathbf{x}}_t)\|}$, even for convex quadratic functions.

The proof is based on the following two more technical propositions, which provide lower bounds depending on the step sizes and the problem parameters:

\[prop:distance\] For any $L>0,\Delta>0,T>1$ and $\delta\in (0,1)$, there exists a convex quadratic function $f$ on ${\mathbb{R}}^d$ (for any $d\geq d_0$ where $d_0={\mathcal{O}}(\log(T/\delta)\sigma^2T/(L^2\Delta))$) with $L$-Lipschitz gradient, and an ${\mathbf{x}}_1$ such that $f({\mathbf{x}}_1)-\inf_{{\mathbf{x}}}f({\mathbf{x}})\leq \Delta$, such that if we initialize SGD at ${\mathbf{x}}_1$ with Gaussian noise ${\mathcal{N}}(\mathbf{0},\frac{\sigma^2}{d}I_d)$and use step sizes $\eta_1,\ldots,\eta_{T-1}$ in $[0,1/L]$, then with probability at least $1-\delta$, $$\min_{t\in [T]}{\|\nabla 
    f({\mathbf{x}}_t)\|}^2 \geq \frac{\Delta}{25 \max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}.$$

\[prop:noise\] For any $L>0,\Delta>0,T>1$ and $\delta\in (0,1)$, there exists a convex quadratic function $f$ on ${\mathbb{R}}^d$ (for any $d\geq d_0$ where $d_0={\mathcal{O}}(\log(T/\delta))$) with $L$-Lipschitz gradient, and a vector ${\mathbf{x}}_1$ such that $f({\mathbf{x}}_1)-\inf_{{\mathbf{x}}}f({\mathbf{x}})\leq \Delta$, such that if we initialize SGD at ${\mathbf{x}}_1$ with Gaussian noise ${\mathcal{N}}(\mathbf{0},\frac{\sigma^2}{d}I_d)$, then the following holds with probability at least $1-\delta$:

-   If for all $t$, $\eta_t=\eta$ with $\eta\in [0,1/L)$, then $
            \min_{t\in [T]}{\|\nabla f({\mathbf{x}}_t)\|}^2 \geq \frac{L}{2} \min\{\Delta,\frac{\eta \sigma^2}{2-L\eta}\}.
            $

-   If for all $t$, $\eta_t \geq c/L$ for some constant $c>0$ then $\min_{t\in [T]}{\|\nabla f({\mathbf{x}}_t)\|}^2 \geq \frac{\sigma^2 c^2}{2}$.

-   If $\eta_t = \frac{a}{L(b+t^\theta)}$ for some positive constants $a>0,b\geq 0$ and $\theta\in (0,1)$, then $$\min_{t\in [T]}{\|\nabla f({\mathbf{x}}_t)\|}^2 \geq c_{a,b,\theta} \sigma^2 \min\{1, L \eta_T\},$$ where $c_{a,b,\theta}$ is a constant dependant only on $a,b,\theta$.

The proofs of these propositions appear in [Appendix \[sec:proofs\]]{}. Together, Propositions \[prop:distance\] and \[prop:noise\] imply the theorem:

The theorem, under the first condition, is an immediate corollary of [Proposition \[prop:distance\]]{}. Indeed, $$\begin{aligned}
    \min_{t\in [T]}{\|\nabla 
    f({\mathbf{x}}_t)\|}^2 
    & \geq \frac{\Delta}{25\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}} \geq \frac{L \Delta}{25\max\left\{1,c \sqrt{T}\right\}} \\
    & \geq 
    \frac{L \Delta}{25\max\{1, c\} \sqrt{T}} \geq 
    \frac{\min\{L \Delta, \sigma^2\}}{25\max\{1, c\} \sqrt{T}}.\end{aligned}$$

As to the second condition, let us consider three cases. First, if $\eta_t=\eta$ is at most $T^{-1/2}/L$, then $\sum_{t=1}^{T-1}\eta_t< \sqrt{T}/L$ and the result again follows from [Proposition \[prop:distance\]]{} as in the previous case. Next, suppose $T^{-1/2}/L \leq \eta < 1/L$, then the result follows from [Proposition \[prop:noise\]]{}: $$\min_{t\in [T]} {\|\nabla f({\mathbf{x}}_t)\|}^2 \geq \frac{L}{2} \min\{\Delta, \frac{ \eta \sigma^2}{2-L\eta}\}
    \geq \frac{1}{2} \min\{L \Delta, \frac{\sigma^2 T^{-1/2}}{2-T^{-1/2}}\}
    \geq \frac{1}{2} \frac{\min\{L \Delta,\sigma^2\}}{2\sqrt{T}-1}.$$ The last case for this condition is $1/L \leq \eta$, which does not converge due to the second case in [Proposition \[prop:noise\]]{}.

As to the third condition (namely $\eta_t = \frac{a}{b+t^{\theta}}$), we can assume without loss of generality that $a>0$ (otherwise we are back to the first condition in the theorem, and nothing is left to prove), and that $\theta \in (0,1)$ (since if $\theta=0$, we are back to the second condition in the theorem, and if $\theta \geq 1$, we are back to the first condition in the theorem). The result then follows from third case of Proposition \[prop:noise\].

Additional Proofs {#sec:proofs}
=================

Proof of [Lemma \[L:detbound\]]{} {#S:lemma_proof}
---------------------------------

We start by recalling a recent and fundamental theorem by Taylor, Hendrickx and Glineur. This theorem can be viewed as providing necessary and sufficient conditions under which a set $\{{\mathbf{x}}_i, {\mathbf{g}}_i, f_i\}_{i\in I}$ can be *interpolated* (or *extended* using the terminology from the classical text [@whitney1934analytic]) to a function $f$ with $L$-Lipschitz gradient such that $f({\mathbf{x}}_i) =f_i$ and $\nabla f({\mathbf{x}}_i) = {\mathbf{g}}_i$ for all $i\in I$.

\[T:nonconvex\_interpolation\] Let $L>0$, $d\in \mathbb{N}$ and suppose $\{({\mathbf{x}}_i, {\mathbf{g}}_i, f_i)\}_{i\in I}$ is some finite subset of ${\mathbb{R}}^d\times{\mathbb{R}}^d\times {\mathbb{R}}$, where $I$ is a finite set of indices. Then there exists a function $f$ with $L$-Lipschitz gradient that satisfies $f({\mathbf{x}}_i) = f_i$ and $\nabla f({\mathbf{x}}_i) = {\mathbf{g}}_i$ if and only if $$\label{E:nonconvex_interpolation_conditions}
        \frac{1}{2L} \|{\mathbf{g}}_i - {\mathbf{g}}_j\|^2 - \frac{L}{4} \|{\mathbf{x}}_i - {\mathbf{x}}_j - \frac{1}{L}({\mathbf{g}}_i - {\mathbf{g}}_j)\|^2 \leq f_i - f_j - \langle {\mathbf{g}}_j, {\mathbf{x}}_i - {\mathbf{x}}_j\rangle, \quad \forall i,j \in I.$$

Theorem \[T:nonconvex\_interpolation\] will be the main tool used in the proof of [Lemma \[L:detbound\]]{} below.

By Theorem \[T:nonconvex\_interpolation\], it is sufficient to show that there is a choice $\beta$ for the value of $\hat f({\mathbf{y}}_1),\dots,\hat f({\mathbf{y}}_m)$ with $\beta \geq \min_{i \in [n]} f({\mathbf{z}}_{i}) - \frac{1}{L} \|{\boldsymbol{\gamma}}\|^2$ such that the set $$\{({\mathbf{y}}_j, {\boldsymbol{\gamma}}, \beta)\}_{j\in [m]} \cup \{({\mathbf{z}}_{i}, {\boldsymbol{\gamma}}, f({\mathbf{z}}_i) \}_{i\in [n]},$$ satisfies the interpolation conditions . Noting that all the interpolation conditions involving two points from $\{{\mathbf{z}}_i\}$ are naturally satisfied by the assumption that there exists some function with $L$-Lipschitz gradient (namely $f$) that interpolates $\{({\mathbf{z}}_i, \nabla f({\mathbf{z}}_i), f({\mathbf{z}}_i) \} = \{({\mathbf{z}}_i, {\boldsymbol{\gamma}}, f({\mathbf{z}}_i) \}$, and further note that by the assumptions, $\langle {\boldsymbol{\gamma}}, {\mathbf{y}}_i - {\mathbf{y}}_j\rangle=0$, hence the interpolation conditions involving both point in ${\mathbf{y}}_i$ are also trivially satisfied. We conclude that we only need to consider  for cases where one of the points is ${\mathbf{z}}_i$ and the other is ${\mathbf{y}}_j$, i.e., we are left the following set of inequalities: $$\begin{aligned}
    & - \frac{L}{4} \|{\mathbf{z}}_{i} - {\mathbf{y}}_j \|^2 \leq f({\mathbf{z}}_i) - \beta - \langle {\boldsymbol{\gamma}}, {\mathbf{z}}_i - {\mathbf{y}}_j \rangle, \quad i\in [n],\ j\in [m], \\
    & - \frac{L}{4} \|{\mathbf{y}}_j - {\mathbf{z}}_{i} \|^2 \leq \beta - f({\mathbf{z}}_{i}) - \langle {\boldsymbol{\gamma}}, {\mathbf{y}}_j - {\mathbf{z}}_{i}\rangle, \quad i\in [n],\ j\in [m].\end{aligned}$$ Clearly, these inequalities hold if and only if $$\begin{aligned}
    & \beta \in [\max_{i,j} \left( f({\mathbf{z}}_{i}) + \langle {\boldsymbol{\gamma}}, {\mathbf{y}}_j - {\mathbf{z}}_{i}\rangle - \frac{L}{4} \|{\mathbf{y}}_j - {\mathbf{z}}_{i} \|^2\right), \min_{i,j} \left( f({\mathbf{z}}_{i}) + \langle {\boldsymbol{\gamma}}, {\mathbf{y}}_j - {\mathbf{z}}_{i}\rangle + \frac{L}{4} \|{\mathbf{z}}_{i} - {\mathbf{y}}_j \|^2 \right) ].\end{aligned}$$ Now, this range is non-empty since it contains $f({\mathbf{y}}_1)$ (recall that $f({\mathbf{y}}_1)=\dots=f({\mathbf{y}}_m)$, $\nabla f({\mathbf{y}}_1)=\dots=\nabla f({\mathbf{y}}_m) = {\boldsymbol{\gamma}}$, and that the interpolation conditions for the set $\{({\mathbf{y}}_j, \nabla f({\mathbf{y}}_j), f({\mathbf{y}}_j)\} \cup \{({\mathbf{z}}_i, \nabla f({\mathbf{z}}_i), f({\mathbf{z}}_i) \}$ naturally hold), hence there exits some $i,j$ such that the choice $$\hat \beta := f({\mathbf{z}}_{i}) + \langle {\boldsymbol{\gamma}}, {\mathbf{y}}_j - {\mathbf{z}}_{i}\rangle + \frac{L}{4} \|{\mathbf{z}}_{i} - {\mathbf{y}}_j \|^2$$ is a feasible choice for $\beta$. We get $$\begin{aligned}
    \hat \beta 
        & = f({\mathbf{z}}_{i}) + \frac{L}{4} \| {\mathbf{z}}_{i} - {\mathbf{y}}_j - \frac{2}{L} {\boldsymbol{\gamma}}\|^2 - \frac{1}{L} \|{\boldsymbol{\gamma}}\|^2 \\
    & \geq \min_{k} f({\mathbf{z}}_{k}) - \frac{1}{L} \|{\boldsymbol{\gamma}}\|^2.\end{aligned}$$ which concludes the proof, as all interpolation conditions are satisfied, hence a function with the claimed properties exists.

Proof of Proposition \[prop:distance\]
--------------------------------------

We will utilize the following function: $$f({\mathbf{x}}) = \frac{1}{4\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\cdot \langle {\mathbf{x}}, {\mathbf{e}}_1\rangle^2$$ and assume that the initialization ${\mathbf{x}}_1$ is $${\mathbf{x}}_1 := 
\left(\sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}~,~0,0,\ldots,0\right)~.$$ It is easily verified that $f$ has $L$-Lipschitz gradient, and that $f({\mathbf{x}}_1)-\inf_{{\mathbf{x}}} f({\mathbf{x}})<\Delta$. Moreover, $$\label{eq:norm_f_distance}
    {\|\nabla 
    f({\mathbf{x}})\|}=\frac{|\langle {\mathbf{x}}, {\mathbf{e}}_1\rangle|}{2\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}.$$

Hereafter, for the sake of simplicity we drop the subscript indicating the coordinate number, and let $x_t$ denote the first coordinate of iterate $t$, and $\xi_t$ the first coordinate of the noise at iteration $t$.

We now turn to show that when $d$ is large enough $$\label{eq:toshoww}
\min_{t\in [T]}|x_t|\geq 
\frac{2}{5}\sqrt{\Delta\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}$$ holds with arbitrarily high probability, which together with  implies the desired result.

The dynamics of SGD on the first coordinate is as follows: we initially have $$x_1 = \sqrt{\Delta\cdot\max\{1/L,\sum_{t=1}^{T-1}\eta_t\}},$$ and $$x_{t+1} = 
\left(1-\frac{\eta_t}{2\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right)x_t
-\eta_t
\xi_{t}.$$ Unrolling this recurrence, we have for any $t$ $$\label{eq:xtexpression}
\begin{aligned}
    x_t  & = \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}} \cdot \prod_{j=1}^{t-1}\left(1-\frac{\eta_j}{2\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right) \\
    &\qquad - \sum_{j=1}^{t-1}\eta_j \xi_j  \prod_{i=j+1}^{t-1}\left(1-\frac{\eta_j}{2\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right),
\end{aligned}$$ where we use the convention that $\prod_{i=a}^{b}c_i$ is always $1$ if $b<a$. Since each $\xi_j$ is a zero-mean independent Gaussian, $x_t$ is also Gaussian with $$\begin{aligned}
{\mathbb{E}}[ x_t ] &= \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}} \cdot \prod_{j=1}^{t-1}\left(1-\frac{\eta_j}{2\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right) \\
& \geq \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\cdot 
\exp\left(\ln \frac{1}{2}\cdot \sum_{j=1}^{t-1}\frac{ \eta_j}{\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right) \\
&\geq
\frac{1}{2} \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}},\end{aligned}$$ here we used the assumption $\eta_t \geq 0$ and the fact that $1-z/2\geq \exp(\ln \frac{1}{2} \cdot z)$ for all $z\in [0,1]$. In addition, $$\begin{aligned}
    {\mathbb{V}}[x_t] 
    & = \sum_{j=1}^{t-1}\eta_j^2 {\mathbb{V}}[\xi_j] \prod_{i=j+1}^{t-1}\left(1-\frac{\eta_j}{2\max\left\{1/L, \sum_{t=1}^{T-1}\eta_t\right\}}\right)^2 \\
    & \leq \sum_{j=1}^{t-1}\eta_j^2 {\mathbb{V}}[\xi_j]  \leq \frac{\sigma^2 (T-1)}{L^2d},\end{aligned}$$ which follows since each $\xi_j$ is independent and with variance at most $\sigma^2/d$, and $0\leq \eta_j \leq 1/L$. Choosing $$d \geq d_0 := \frac{ \Phi^{-1}(1-\delta/T)^2 \sigma^2 (T-1)}{\left(\frac{1}{2} - \frac{2}{5} \right)^2 L^2 \Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}} = {\mathcal{O}}(\log(T/\delta)\sigma^2T/(L^2\Delta)),$$ where $\Phi^{-1}$ is the inverse CDF of the normal distribution, we get that for all $t$ with ${\mathbb{V}}[x_t]>0$ $$\begin{aligned}
    & \Pr \left(x_t \geq \frac{2}{5} \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}\right) \\
    & = \Pr \left(\frac{x_t - {\mathbb{E}}x_t}{\sqrt{{\mathbb{V}}[x_t]}} \geq -\frac{\left( \frac{1}{2} - \frac{2}{5} \right) \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}}{ \sqrt{\sigma^2(T-1) / (L^2 d)}}\right) \\
    & \geq \Pr \left(\frac{x_t - {\mathbb{E}}x_t}{\sqrt{{\mathbb{V}}[x_t]}} \geq -\frac{\left( \frac{1}{2} - \frac{2}{5} \right) \sqrt{\Delta\cdot\max\left\{1/L,\sum_{t=1}^{T-1}\eta_t\right\}}}{ \sqrt{\sigma^2(T-1) / (L^2 d_0)}}\right) = 1- \delta/T,\end{aligned}$$ and furthermore, the same bound holds almost surely for all $t$ with ${\mathbb{V}}[x_t]=0$. Finally, taking a union bound over $t$, we conclude that this lower bound holds for all $x_t$ with probability $1-\delta$, which implies as required.

Proof of Proposition \[prop:noise\]
-----------------------------------

To prove the proposition, we will need the following Lemma, which formalizes the fact that the norm of high-dimensional Gaussian random variables tend to be concentrated around a fixed value:

\[lem:gausscon\] Let $M,\gamma>0$ be fixed. For any $d$, let ${\mathbf{x}}_d$ be a random variable normally distributed with ${\mathbf{x}}_d \sim {\mathcal{N}}({\mathbf{u}}, \frac{\gamma}{d}I_d)$, where ${\mathbf{u}}$ is some vector in ${\mathbb{R}}^d$ with $\|{\mathbf{u}}\|^2=M$. Then for any $\epsilon\in (0,1)$, $$\Pr\left(\left|\frac{{\|{\mathbf{x}}_d\|}^2}{M+\gamma}-1\right|\leq
    \epsilon\right)~\geq~1-4\exp\left(-\frac{d\epsilon^2}{24}\right).$$

Consider ${\mathbf{x}}_d$ for some fixed $d$. We can decompose it as ${\mathbf{u}}+\sqrt{\frac{\gamma}{d}}{\mathbf{n}}$, where ${\mathbf{n}}$ has a standard Gaussian distribution in ${\mathbb{R}}^d$ (zero mean and covariance matrix being the identity). Thus, $$\begin{aligned}
    \frac{{\|{\mathbf{x}}_d\|}^2}{M+\gamma}-1 ~&=~ 
    \frac{{\|{\mathbf{u}}\|}^2+2\sqrt{\frac{\gamma}{d}}{\mathbf{u}}^\top{\mathbf{n}}+\frac{\gamma}{d}{\|{\mathbf{n}}\|}^2}
    {M+\gamma}-1~=~
    \frac{2\sqrt{\frac{\gamma}{d}}{\mathbf{u}}^\top{\mathbf{n}}+\gamma\left(\frac{1}{d}{\|{\mathbf{n}}\|}^2-1\right)}
    {M+\gamma}\notag\\
    &=~\frac{2\sqrt{\gamma/d}}{M+\gamma}{\mathbf{u}}^\top{\mathbf{n}}+\frac{\gamma}{M+\gamma}\left(\frac{1}{d}{\|{\mathbf{n}}\|}^2-1\right). \label{eq:twoterms}
    \end{aligned}$$ The first term in the sum above is distributed as a Gaussian in ${\mathbb{R}}$ with zero mean and variance $\frac{4\gamma}{d(M+\gamma)^2}{\|{\mathbf{u}}\|}^2=\frac{4\gamma M}{d(M+\gamma)^2}\leq \frac{4\gamma M}{d\cdot 2\gamma M}=\frac{2}{d}$. By a standard Gaussian tail bound, it follows that the probability that it exceeds $\epsilon/2$ in absolute value is at most $2\exp(-d\epsilon^2/16)$. Similarly, for the second term, we have by a standard tail bound for Chi-squared random variables (see for example [@shalev2014understanding Lemma B.12]) that $$\Pr\left(\frac{\gamma}{M+\gamma}\left|\frac{1}{d}{\|{\mathbf{n}}\|}^2-1\right|\geq \frac{\epsilon}{2}\right)
    ~\leq~
    \Pr\left(\left|\frac{1}{d}{\|{\mathbf{n}}\|}^2-1\right|\geq \frac{\epsilon}{2}\right)
    ~\leq~ 2\exp(-d\epsilon^2/24)~.$$ Combining the above with a union bound, it follows that has absolute value more than $\epsilon$ with probability at most $$2\exp(-d\epsilon^2/16)+2\exp(-d\epsilon^2/24)
    ~\leq~ 4\exp(-d\epsilon^2/24)~.$$

We will utilize the function $$f({\mathbf{x}}) = \frac{L}{2}{\|{\mathbf{x}}\|}^2,$$ where ${\mathbf{x}}_1$ is some vector such that ${\|{\mathbf{x}}_1\|}=\sqrt{\Delta/L}$. Using a derivation similar to the one used in , we have $${\mathbf{x}}_{t+1}= {\mathbf{x}}_t-\eta_t \cdot (L {\mathbf{x}}_t + {\boldsymbol{\xi}}_t) = (1-L\eta_t) {\mathbf{x}}_t - \eta_t {\boldsymbol{\xi}}_t,$$ hence $$\label{eq:xtexpression2}
    {\mathbf{x}}_t = \prod_{j=1}^{t-1}\left(1-L\eta_j\right){\mathbf{x}}_1-
    \sum_{j=1}^{t-1}\eta_j 
    \prod_{i=j+1}^{t-1}\left(1-L\eta_i\right){\boldsymbol{\xi}}_j.$$ Since each ${\boldsymbol{\xi}}_j$ is an independent zero-mean Gaussian with covariance matrix $\frac{\sigma^2}{d}I_d$, we get that ${\mathbf{x}}_t$ has a Gaussian distribution with mean $\prod_{j=1}^{t-1}\left(1-L\eta_j\right){\mathbf{x}}_1$ and covariance matrix $\frac{\gamma_t}{d}I_d$, where $$\gamma_t = \sigma^2 \sum_{j=1}^{t-1}\eta_j^2
    \prod_{i=j+1}^{t-1}\left(1-L\eta_i\right)^2.$$ By [Lemma \[lem:gausscon\]]{}, taking $\epsilon=1/2$ and $d\geq d_0$ with $$d_0 := 96 \log \frac{4T}{\delta} = {\mathcal{O}}(\log(T/\delta)),$$ it follows that ${\|\nabla f({\mathbf{x}}_t)\|}^2={\|L {\mathbf{x}}_t\|}^2$ is at least $$\label{eq:lowboundthis}
    \frac{L}{2}\cdot\left( \Delta\prod_{j=1}^{t-1}\left(1 - L\eta_j\right)^2
    + L \sigma^2 \sum_{j=1}^{t-1}\eta_j^2
    \prod_{i=j+1}^{t-1}\left(1-L\eta_i\right)^2\right)$$ with probability at least $1-\delta/T$. Our goal now will be to lower bound  under the conditions in the proposition. Plugging this lower bound and applying a union bound over all $t\in [T]$ will result in our proposition.

-   If $\eta_t=\eta$ and $\eta\in [0,1/L)$, we can lower bound by $$\begin{aligned}
            & \frac{L}{2} \left( \Delta(1-L\eta)^{2(t-1)} + L \sigma^2 \sum_{j=1}^{t-1} \eta^2 (1-L\eta)^{2(t-1-j)}
            \right) \\
            & = \frac{L}{2} \left(\Delta(1 - L\eta)^{2(t-1)} + L \sigma^2 \eta^2\cdot \frac{1-(1-L\eta)^{2(t-1)}}{1-(1-L\eta)^2} \right) \\
            &= \frac{L}{2} \left( \Delta(1 - L\eta)^{2(t-1)} + \frac{\eta \sigma^2}{2-L\eta}\left(1-(1-L\eta)^{2(t-1)}\right)\right).
            \end{aligned}$$ For any $t$, this is a convex combination of $\frac{L}{2} \Delta$ and $\frac{L}{2} \frac{\eta \sigma^2}{2-L\eta}$, hence is at least the minimum between them.

-   If there exists some constant $c\geq 0$ such that $\eta_t \geq c/L$ for all $t$, we can lower bound by $\frac{L^2}{2} \sigma^2 \eta_{t-1}^2\geq \frac{\sigma^2 c^2}{2}$ (i.e., accounting for the noise at the last iterate).

-   If $\eta_t=\frac{a}{L(b+t^\theta)}$ (where $a>0, b\geq 0,\theta\in (0,1/2)$), then it is easily verified that for a certain constant $\tau_{a,b,\theta}$ depending only on $a,b,\theta$, $$1\leq\frac{1}{L\eta_t}\leq \frac{t}{2}~~\text{for all}~~t\geq \tau_{a,b,\theta}.$$ In that case, we can lower bound by $$\begin{aligned}
                & \frac{L^2 \sigma^2}{2} \sum_{j=t-\lfloor 1/(L\eta_t)\rfloor}^{t-1}\eta_j^2\prod_{i=j+1}^{t-1}(1-L\eta_i)^{2} \\
                & \geq \frac{L^2 \sigma^2 \eta_t^2}{2}\cdot \left\lfloor\frac{1}{L\eta_t}\right\rfloor\left(1-L\eta_{\lfloor t/2\rfloor}\right)^{2\lfloor 1/(L\eta_t) \rfloor} 
                \geq \frac{\sigma^2 L \eta_t}{4}\left(1-\frac{a}{b+\lfloor 
                t/2\rfloor^{\theta}}\right)^{2\left\lfloor \frac{b+t^\theta}{a}\right\rfloor},
            \end{aligned}$$ which is at least $c_{a,b,\theta} \sigma^2 L \eta_t\geq c_{a,b,\theta} \sigma^2 L \eta_T$ if $t\geq \tau'_{a,b,\theta}$ (for some parameters $c_{a,b,\theta},\tau'_{a,b,\theta}$ depending on $a,b,\theta$). Moreover, if $t<\tau'_{a,b,\theta}$, then is at least $$\frac{L^2 \sigma^2}{2} \eta_{t-1}^2 \geq \frac{L^2 \sigma^2}{2} \eta_{\tau'_{a,b,\theta}}^2 = \frac{\sigma^2}{2} \cdot \left( \frac{a}{b+(\tau'_{a,b,\theta})^\theta}\right)^2.$$ Combining both cases, we get that is at least $c'_{a,b,\theta} \sigma^2 \cdot\min\{1,L \eta_T\}$, where $c'_{a,b,\theta}$ is again some constant dependant on $a,b,\theta$, implying the stated result.

Upper Bounds for SGD {#sec:upperbounds}
====================

In order to place our lower bounds in perspective, we state and prove a rather standard ${\mathcal{O}}(\epsilon^{-4})$ complexity bound for SGD, which unlike the result discussed in the introduction, does not assume anything special about the Hessians or the noise, and is completely independent of the dimension.

We start the analysis with a technical lemma that we will use to derive bounds both in the stochastic and deterministic settings.

\[L:nonconvex\_upper\] Consider the Stochastic Gradient Descent $${\mathbf{x}}_{t+1} = {\mathbf{x}}_t - \eta_{t} \left(\nabla f({\mathbf{x}}_t) + {\boldsymbol{\xi}}_t\right), \quad t\in [T-1],$$ where $0 < \eta_t < 1/L$, $f$ is a non-convex function with $L$-Lipschitz gradient, and ${\boldsymbol{\xi}}_t$ is a random noise with ${\mathbb{E}}({\boldsymbol{\xi}}_t)=0$, $V({\boldsymbol{\xi}}_t)=\sigma^2$. Then for any choice of $\kappa_t$, $t\in [T-1]$ such that $1-L\eta_t\leq \kappa_t \leq (1-L\eta_t)^{-1}$ we have $$\min_{t \in [T]} {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|^2 \leq \frac{4L(f({\mathbf{x}}_1)-f({\mathbf{x}}_*)) + \sum_{t=1}^{T-1} \frac{L^2 \eta_{t}^2(1-L \eta_{t}+\kappa_{t})}{1 - L\eta_{t}} \sigma^2}{3 (T-1) - \sum_{t=1}^{T-1} (1 - L \eta_t) (1 - L \eta_t + \kappa_t + \frac{1}{\kappa_{t}})},$$ where $x_*$ is a stationary point with $f({\mathbf{x}}_*) \leq f({\mathbf{x}}_T)$.

By [Thm. \[T:nonconvex\_interpolation\]]{} we have $$\begin{aligned}
    & \frac{1}{2L} \|\nabla f({\mathbf{x}}_{t})-\nabla f({\mathbf{x}}_{t+1})\|^2 - \frac{L}{4} \|{\mathbf{x}}_{t} - {\mathbf{x}}_{t+1} - \frac{1}{L}(\nabla f({\mathbf{x}}_{t})-\nabla f({\mathbf{x}}_{t+1}))\|^2 \\&\quad\overset{\text{a.s.}}{\leq} f({\mathbf{x}}_{t}) - f({\mathbf{x}}_{t+1}) - \langle \nabla f({\mathbf{x}}_{t+1}), {\mathbf{x}}_{t}-{\mathbf{x}}_{t+1}\rangle, \quad t\in [T-1],\end{aligned}$$ which by the definition of ${\mathbf{x}}_{t+1}$ becomes $$\begin{aligned}
    & \frac{1}{2L} \|\nabla f({\mathbf{x}}_{t})-\nabla f({\mathbf{x}}_{t+1})\|^2 - \frac{1}{4L} \|L \eta_{t} {\boldsymbol{\xi}}_t - (1-L \eta_{t})\nabla f({\mathbf{x}}_{t}) + \nabla f({\mathbf{x}}_{t+1})\|^2 \\&\quad \overset{\text{a.s.}}{\leq} f({\mathbf{x}}_{t}) - f({\mathbf{x}}_{t+1}) - \langle \nabla f({\mathbf{x}}_{t+1}), \eta_{t} \left(\nabla f({\mathbf{x}}_t) + {\boldsymbol{\xi}}_t\right)\rangle, \quad t\in [T-1],\end{aligned}$$ Adding up the inequality above for all $t\in [T-1]$ brings us to $$\begin{aligned}
    & \frac{1}{2L} \sum_{t=1}^{T-1} \|\nabla f({\mathbf{x}}_{t})-\nabla f({\mathbf{x}}_{t+1})\|^2 - \frac{1}{4L} \sum_{t=1}^{T-1} \|L \eta_{t} {\boldsymbol{\xi}}_t - (1-L \eta_{t})\nabla f({\mathbf{x}}_{t}) + \nabla f({\mathbf{x}}_{t+1})\|^2 \\&\quad+ \sum_{t=1}^{T-1} \eta_{t} \langle \nabla f({\mathbf{x}}_{t+1}), \nabla f({\mathbf{x}}_t) + {\boldsymbol{\xi}}_t \rangle \overset{\text{a.s.}}{\leq} f({\mathbf{x}}_1) - f({\mathbf{x}}_{T}),\end{aligned}$$ which, after adding $$\frac{1}{4} \sum_{t=1}^{T-1} \eta_{t} (1-L \eta_{t}+\kappa_{t}) \left(\frac{L \eta_{t}}{1-L \eta_{t}} \|{\boldsymbol{\xi}}_t\|^2 + 2 \langle \nabla f({\mathbf{x}}_t), {\boldsymbol{\xi}}_t\rangle \right)$$ to both sides and rearranging the terms, brings us to $$\begin{aligned}
    & \frac{1}{4L} \sum_{t=1}^{T-1} \left( 2 - (1-L \eta_t) (1 - L \eta_t + \kappa_t) \right) \|\nabla f({\mathbf{x}}_t)\|^2 + \frac{1}{4L} \sum_{t=1}^{T-1} \left(1 - \frac{1-L \eta_{t}}{\kappa_{t}}\right) \|\nabla f({\mathbf{x}}_{t+1})\|^2 \\&\quad + \frac{1}{4L} \sum_{t=0}^{T-1}(1 - L \eta_t)\kappa_t \left\| \nabla f({\mathbf{x}}_t) - \frac{1}{\kappa_t} \nabla f({\mathbf{x}}_{t+1}) -  \frac{L \eta_t}{1-L \eta_t}{\boldsymbol{\xi}}_t \right\|^2 \\&\quad \overset{\text{a.s.}}{\leq} f({\mathbf{x}}_1) - f({\mathbf{x}}_{T}) + \frac{1}{4} \sum_{t=0}^{T-1} \eta_{t} (1-L \eta_{t}+\kappa_{t}) \left(\frac{L \eta_{t}}{1-L \eta_{t}} \|{\boldsymbol{\xi}}_t\|^2 + 2 \langle \nabla f({\mathbf{x}}_t), {\boldsymbol{\xi}}_t\rangle \right)\end{aligned}$$ Finally, taking the expected value of both side, and noting that ${\mathbb{E}}\|{\boldsymbol{\xi}}_t\|=\sigma$, ${\mathbb{E}}\langle \nabla f({\mathbf{x}}_t), {\boldsymbol{\xi}}_t\rangle=0$, and ${\mathbb{E}}f({\mathbf{x}}_T)\geq f({\mathbf{x}}_*)$, we reach $$\begin{aligned}
    & \frac{1}{4L} \left(3 (T-1) - \sum_{t=1}^{T-1}  (1-L \eta_t) (1 - L \eta_t + \kappa_t) - \sum_{t=1}^{T-1} \frac{1-L \eta_t}{\kappa_t} \right)\min_{t\in [T]} {\mathbb{E}}\|\nabla f({\mathbf{x}}_t)\|^2 \\&\quad \leq f({\mathbf{x}}_1) - f({\mathbf{x}}_*) + \frac{1}{4} \sum_{t=1}^{T-1} \eta_{t} (1-L \eta_{t}+\kappa_{t}) \frac{L \eta_{t}}{1-L \eta_{t}} \sigma^2,\end{aligned}$$ concluding the proof.

An explicit optimal expression for $\kappa_i$ appear to be complex in the general case, however, for two important cases a good approximation can be obtained. First, when $\sigma$ is large, the term in the nominator dominates the expression, thus the optimal value for $\kappa_t$ approaches $1-L \eta_t$ as $\sigma\rightarrow\infty$, recovering the following result by Ghadimi and Lan:

\[T:upper\_noncovex\] Consider the fixed-step Stochastic Gradient Descent $${\mathbf{x}}_{t+1} = {\mathbf{x}}_t - \eta_t \left(\nabla f({\mathbf{x}}_t) + {\boldsymbol{\xi}}_t\right), \quad t \in [T-1],$$ where $f$ is a nonconvex function with $L$-Lipschitz gradient, ${\boldsymbol{\xi}}_t$ is a random noise with ${\mathbb{E}}({\boldsymbol{\xi}}_t)=0$, $V({\boldsymbol{\xi}}_t)=\sigma^2$ and $0 < L \eta_t < 1$. Then $$\label{eq:sgp_upper_bound}
    \min_{t \in [T]} \|\nabla f({\mathbf{x}}_t)\|^2 \leq \frac{2(f({\mathbf{x}}_1)-f({\mathbf{x}}_*)) + L \sum_{t=1}^{T-1} \eta_t^2 \sigma^2}{\sum_{t=1}^{T-1} \eta_t (2 - L \eta_t)}.$$ where $x_*$ is a stationary point with $f({\mathbf{x}}_*) \leq f({\mathbf{x}}_T)$.

The result follows directly from [Lemma \[L:nonconvex\_upper\]]{}, taking $\kappa_t = 1-L \eta_t$.

A second case where a simple expression for $\kappa_t$ can be easily attained is when $\sigma=0$, i.e., in the deterministic case. Here an optimal choice for $\kappa$ is $\kappa_i=1$, giving the following result which appears to be a new and slightly improved version of the classical result by Nesterov [@Book:Nesterov (1.2.15)]:

\[C:gd\_upper\_bound\] Consider the fixed-step Gradient Descent $${\mathbf{x}}_{t+1} = {\mathbf{x}}_t - \eta_t \nabla f({\mathbf{x}}_t), \quad t \in [T-1],$$ where $f$ is a nonconvex function with $L$-Lipschitz gradient and $0 < \eta_t < 1/L$. Then $$\min_{t \in [T]} \|\nabla f({\mathbf{x}}_t)\|^2 \leq \frac{4 (f({\mathbf{x}}_1)-f({\mathbf{x}}_*))}{\sum_{t=1}^{T-1} \eta_t(4-L \eta_t)},$$ where $x_*$ is a stationary point with $f({\mathbf{x}}_*) \leq f({\mathbf{x}}_T)$.

The discovery of the proof of [Lemma \[L:nonconvex\_upper\]]{} was guided by numerically solving an optimization problem called the Performance Estimation Problem, whose solution captures the worst-case performance of the SGD method. This technique was first introduced in [@Article:Drori] and was later shown in [@taylor2015smooth] to achieve tight bounds for a wide range of methods in the deterministic case. This, in conjunction with the nearly matching lower bound established in [Thm. \[thm:aggregation\_step\]]{}, motivates us to raise the conjecture that [Lemma \[L:nonconvex\_upper\]]{} gives a tight bound (including the constant) in the stochastic case.

[^1]: See e.g. [@Book:Nesterov] and references mentioned earlier.
