
\section{Convergence of ASGD}
\label{sec:acceleration}
For analyzing the convergence of ASGD, we will assume that the stochastic gradients satisfy a growth condition similar to~\citet{bottou2018optimization, li2020second, khaled2020better} -- there exists a $(\rho, \sigma)$ with $\rho \geq 1$ and $\sigma \geq 0$, such that for all $w$,
\begin{align}
\mathbb{E}_{i} \normsq{\nabla f_{i}(w)} & \leq \rho \normsq{\grad{w}} + \sigma^2. 
\label{eq:growth-condition}
\end{align}
Note that in the deterministic setting (when using the full-gradient in~\cref{eq:sgd-update}), $\rho = 1$ and $\sigma = 0$. Similarly, $\sigma = 0$ when the stochastic gradients satisfy the \emph{strong-growth condition} when using over-parameterized models~\citep{schmidt2013fast,ma2018power, vaswani2019fast}. Under the above growth condition, we prove the following theorem in~\cref{app:acceleration-proof}.  

\begin{thmbox}
\begin{restatable}{theorem}{restatescacc}
Assuming (i) convexity and $L_i$-smoothness of each $f_i$, (ii) $\mu$ strong-convexity of $f$ and (iii) the growth condition in~\cref{eq:growth-condition}, ASGD (\cref{eq:extrapolation,eq:sgd-update}) with $w_0 = y_0$, $\gamma_{k} = \frac{1}{\rho L}$, $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$, $\alpha_{k} = \alpha^{k}$, $r_{k} = \sqrt{\frac{\mu}{\rho L}} \left(\frac{\beta}{T} \right)^{k/2T}$ and $b_{k}$ computed as:
\begin{align}
b_{k} &= \frac{(1 - r_{k-1}) \, r_{k-1} \, \alpha}{r_{k} + r_{k-1}^2 \, \alpha}, \label{eq:b-a-main}    
\end{align}
has the following convergence rate:
\begin{align*}
\mathbb{E} [f(w_T) - f^*] & \leq 2c_3  \exp\left( - \frac{T}{\sqrt{\kappa \rho}} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) [f(w_0) - f^*] \\ & + \frac{8 \sigma^2 c_4 \kappa }{ \rho L e^2} \frac{(\ln(\nicefrac{T}{\beta}))^2}{\alpha^2 T} 
\end{align*}
where $\kappa = \frac{L}{\mu}$, $c_3 = \exp\left( \frac{1}{ \sqrt{\rho \kappa}}\frac{2 \beta}{ \ln(\nicefrac{T}{\beta})}\right)$ and $c_4 = \exp\left( \frac{1}{\alpha \sqrt{\rho \kappa}} \, \frac{2 \beta}{ \ln(\nicefrac{T}{\beta})}\right)$.
\label{thm:sc-accelerated}
\end{restatable}
\end{thmbox}
The above theorem implies that ASGD achieves an $\tilde{O} \left(\exp \left(\frac{-T}{\sqrt{\kappa \rho}} \right) + \frac{\sigma^2}{T} \right)$ convergence rate. This improves over the non-accelerated $\tilde{O} \left(\exp \left(\frac{-T}{\kappa} \right) + \frac{\sigma^2}{T} \right)$ noise-adaptive rate obtained in~\citet{stich2019unified, khaled2020better, li2020second}. Under the strong-growth condition (when $\sigma = 0$), ASGD improves (by a $\sqrt{\rho}$ factor) over the rate in~\citet{vaswani2019fast} and matches (upto log factors) the rate in~\citet{mishkin2020interpolation}. In the general stochastic case, when $\sigma \neq 0$,~\citet{cohen2018acceleration, vaswani2019fast} prove convergence to a neighbourhood of the solution, while we sshow convergence to the minimizer at a rate governed by the $O(\sigma^2/T)$ term. In the fully-deterministic setting ($\rho = 1$ and $\sigma = 0$),~\cref{thm:sc-accelerated} implies an $\tilde{O}(\exp(-T/\sqrt{\kappa}))$ convergence to the minimizer, matching the optimal rate in the deterministic setting~\citep{nesterov2013introductory}. We note that ASGD does not require knowledge of $\sigma^2$ and is thus completely noise-adaptive. To smoothly interpolate between the stochastic (mini-batch size $1$) and fully deterministic (mini-batch size $n$) setting, we generalize the growth condition (and the above result) to show an explicit dependence on the mini-batch size in~\cref{sec:additional-theory}. 

Finally, we note that ASGD requires the knowledge of both $\mu$ and $L$ and is thus not problem-adaptive. In the next section, we consider strategies towards achieving problem-adaptivity. 

\section{Acknowledgements}
\label{sec:ack}
We would like to thank Si Yi Meng for helpful feedback on the paper. 
\section{Towards noise and problem adaptivity}
\label{sec:adaptivity}
In this section, we consider approaches for achieving both noise and  problem adaptivity when minimizing smooth, strongly-convex functions. In order to make progress towards this objective, we will only consider SGD and aim to obtain the non-accelerated noise-adaptive rate matching~\citet{stich2019unified,li2020second, khaled2020better}, but do so without knowing problem-dependent constants. 

For this section, we will consider a different weaker notion of noise in the stochastic gradients. Instead of using the growth condition in~\cref{eq:growth-condition} or the more typical assumption of finite gradient noise $z^2 := \mathbb{E}_i [\norm{\nabla f_i(w^{*})}^2] < \infty$, we assume a finite optimal objective difference. Specifically, we redefine the noise as $\sigma^2 := \mathbb{E}_i [f_{i}(w^{*}) - f_{i}^*] \geq 0$. This notion of noise has been used to study the convergence of constant step-size SGD in the \emph{interpolation} setting for over-parameterized models~\citep{zhang2019stochastic,loizou2021stochastic, vaswani2020adaptive}. Note that when interpolation is exactly satisfied, $\sigma = z = 0$. In general, if each function $f_i$ is $\mu$-strongly convex and $L$-smooth, then $\frac{1}{2L}z^2\leq \sigma^2 \leq\frac{1}{2\mu}z^2$. 

We will continue to use exponentially decreasing step-sizes. As a warm-up towards problem-adaptivity, we first assume knowledge of the smoothness constant in~\cref{sec:sc-known} and analyze the resulting SGD algorithm. In~\cref{sec:sc-unknown-correlated}, we consider using a stochastic line-search~\citep{vaswani2019painless,vaswani2020adaptive} in order to estimate the smoothness constant and set the step-size on the fly. Finally, in~\cref{sec:sc-unknown-decorrelated}, we analyze the convergence of SGD when using an offline estimate of the smoothness. 

\subsection{Known smoothness}
\label{sec:sc-known}
We use the knowledge of smoothness to set the problem-dependent part of the step-size for SGD, specifically, $\gamma_{k} = \nicefrac{1}{L}$. With an exponentially decreasing $\alpha_{k}$-sequence, we prove the following theorem in~\cref{app:sc-known-proof}. 
\begin{thmbox}
\begin{restatable}{theorem}{restatesck}
Assuming (i) convexity and $L_i$-smoothness of each $f_i$, (ii) $\mu$ strong-convexity of $f$, SGD (\cref{eq:sgd}) with $\gamma_{k} = \frac{1}{L}$, $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$, $\alpha_{k} = \alpha^k$, has the following convergence rate,
\begin{align*}
\mathbb{E} \normsq{w_{T+1} - w^{*}} & \leq \normsq{w_{1} - w^{*}} c_2 \, \exp\left( - \frac{T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) \\ & + \frac{8 \sigma^2 c_2 \kappa^2}{L e^2} \frac{(\ln(\nicefrac{T}{\beta}))^2}{\alpha^2 T}
\end{align*}
where $\kappa = \frac{L}{\mu}$ and $c_2 = \exp\left( \frac{1}{\kappa} \cdot \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$.
\label{thm:sc-known}
\end{restatable}
\end{thmbox}
Compared to~\citet{moulines2011non} that use a polynomially decreasing step-sizes, the proposed step-size results in a better trade-off between the bias (initial distance to the minimizer) and variance (noise) terms. We use exponentially decreasing step-sizes rather than the step-size schemes used in~\citet{stich2019unified, khaled2020better} because both of these also require the knowledge of the strong-convexity parameter which is considerably more difficult to estimate. 

Since strongly-convex functions also satisfy the PL condition~\citep{karimi2016linear}, the above result can be deduced from~\citep{li2020second}. However, unlike~\citep{li2020second}, our result does not require the growth condition and uses a weaker notion of noise. Moreover, we use a different proof technique, specifically,~\citet{li2020second} use the smoothness inequality in the first step and obtain the rate in terms of the function suboptimality, $\mathbb{E}[f(w_T) - f^*]$. In contrast, our proof uses an expansion of the iterates to obtain the rate in terms of the distance to the minimizer, $\mathbb{E} \normsq{w_{T+1} - w^{*}}$. This change allows us to handle the case when the smoothness constant is unknown and needs to be estimated.

Next, we use stochastic line-search techniques to estimate the unknown smoothness constant and set the step-size on the fly.

\subsection{Online estimation of unknown smoothness}
\label{sec:sc-unknown-correlated}
In this section, we assume that the smoothness constant is unknown, aim to estimate it and set the step-size in an \emph{online} fashion. By online estimation, we mean that in iteration $k$ of SGD, we use knowledge of the sampled function $i_k$ to set the step-size, i.e. setting $\gamma_{k}$ depends on $i_k$. We only consider methods that use the knowledge of $i_k$ in iteration $k$ and are not allowed to access the other functions in $f$ (for example, to compute the full-batch gradient at $w_{k}$). Recent methods based on a stochastic line-search~\citep{vaswani2019painless, vaswani2020adaptive}, stochastic Polyak step-size~\citep{loizou2021stochastic, berrada2020training} or stochastic Barzilai-Borwein-like step-size~\citep{malitsky2019adaptive} are techniques that can set the step-size by only using the current sampled function.     

We use stochastic line-search (SLS) to estimate the local Lipschitz constant and set $\gamma_{k}$, the problem-dependent part of the step-size. SLS is the stochastic analog of the traditional Armijo line-search~\citep{armijo1966minimization} used for deterministic gradient descent~\citep{nocedal2006numerical}. In each iteration $k$ of SGD, SLS estimates the smoothness constant $L_{ik}$ of the sampled function using $f_{ik}$ and $\nabla f_{ik}$. In particular, starting from a guess ($\gamma_{\max}$) of the step-size, SLS uses a backtracking procedure and returns the largest step-size $\gamma_{k}$ that satisfies the following conditions: $\gamma_{k} \leq \gamma_{\max}$ and 
\begin{align}
f_{ik}(w_{k} - \gamma_{k} \gradk{w_{k}}) & \leq f_{ik}(w_{k}) - c \gamma_{k} \normsq{\gradk{w_{k}}}.
\label{eq:armijo-ls}    
\end{align}
Here, $c \in (0,1)$ is a hyper-parameter to be set according to the theory. SLS guarantees that resulting the step-size $\gamma_{k}$ lies in the $\left[ \min \left\{ \frac{2 (1 - c)}{L_{ik}}, \gamma_{\max} \right\}, \gamma_{\max} \right]$ range (see~\cref{lem:sls-bounds} for the proof). If the initial guess is large enough i.e. $\gamma_{\max} > 1/L_{ik}$, then the resulting step-size $\gamma_{k} \geq \frac{2 (1 -c)}{L_{ik}}$. Thus, with $c = \nicefrac{1}{2}$, SLS can be used to obtain an upper-bound on $\nicefrac{1}{L_{ik}}$. 

In the interpolation ($\sigma = 0$) setting, a constant step-size suffices ($\alpha_{k} = 1$ for all $k$), and SGD obtains a linear rate of convergence (for $c \geq \nicefrac{1}{2}$) when minimizing smooth, strongly-convex functions~\citep{vaswani2019painless}. 
In general, for a non-zero $\sigma$, using SGD with SLS and no step-size decay ($\alpha_{k} = 1$) results in $O\left(\exp(-T/\kappa) + \gamma_{\max} \sigma^2 \right)$ rate~\citep{vaswani2020adaptive}, implying convergence to a neighbourhood determined by the $\gamma_{\max} \sigma^2$ term.   

In order to obtain a similar rate as~\cref{thm:sc-known} but without the knowledge of $L$, we set $\gamma_{k}$ with SLS and use the same exponentially decreasing $\alpha_{k}$-sequence. We prove the following theorem in~\cref{app:sc-unknown-correlated-proof}. 
\begin{thmbox}
\begin{restatable}{theorem}{restatescukc}
Assuming (i) convexity and $L_i$-smoothness of each $f_i$, (ii) $\mu$ strong-convexity of $f$, SGD (\cref{eq:sgd}) with $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$, $\alpha_{k} = \alpha^k$ and $\gamma_{k}$ as the largest step-size that satisfies $\gamma_{k} \leq \gamma_{\max}$ and~\cref{eq:armijo-ls} with $c = \nicefrac{1}{2}$, has the following convergence rate,
\begin{align*}
\mathbb{E} \normsq{w_{T+1} - w^{*}} & \leq \normsq{w_1 - w^{*}} c_1 \, \exp\left( - \frac{T}{\kappa'} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) \\ & + \frac{8 \sigma^2 c_1 (\kappa')^2 \gamma_{\max}}{e^2} \frac{(\ln(\nicefrac{T}{\beta}))^2}{\alpha^2 T} \\ & + \frac{2 \sigma^2 c_1 \kappa' \ln (T / \beta)}{e \alpha} \, \left(\gamma_{\max} - \frac{1}{L}\right)
\end{align*}
with $\kappa' = \max\left\{\frac{L}{\mu}, \frac{1}{\mu \gamma_{\max}}\right\}$, $c_1 = \exp\left( \frac{1}{\kappa'} \cdot \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$.
\label{thm:sc-unknown-correlated}
\end{restatable}
\end{thmbox}
We observe that the first two terms are similar to those in~\cref{thm:sc-known}. For $\gamma_{\max} \geq \frac{1}{L}$, $\kappa' = \kappa$ and the above theorem implies the same $\tilde{O}\left(\exp(-T/\kappa) + \frac{\sigma^2}{T}\right)$ rate of convergence. However, as $T \rightarrow \infty$, $w_{T+1}$ does not converge to $w^{*}$, but rather to a neighbourhood determined by the last term $\frac{2 \, \sigma^2 \kappa' c_1 \ln(T/\beta)}{e \alpha} \, \left(\gamma_{\max} - \frac{1}{L}\right)$. The neighbourhood thus depends on the noise $\sigma^2$ and $\left(\gamma_{\max} - \frac{1}{L}\right)$, the estimation error (in the smoothness) of the initial guess.  

When $\sigma^2 = 0$, this neighbourhood term disappears, and SGD converges to the minimizer despite the estimation error. This matches the result for SLS in the interpolation setting~\citep{vaswani2019painless}. Conversely, when the smoothness is known and $\gamma_{\max}$ can be set equal to $\frac{1}{L}$, we also obtain convergence to the minimizer and recover the result of~\cref{thm:sc-known}. In fact, if we can ``guess'' a value of $\gamma_{\max} \leq \frac{1}{L}$, it would result in the neighbourhood term becoming negative, thus ensuring convergence to the minimizer. In this case, the stochastic line-search does not decrease the step-size in any iteration, and the algorithm becomes the same as using a constant step-size equal to $\gamma_{\max}$. Finally, we contrast our result for SGD with SLS and $\alpha_{k} = 1$~\citep{vaswani2020adaptive} and observe that instead of the dependence on $\gamma_{\max}$, our neighbourhood term depends on the estimation error in the smoothness. 

In the next section, we prove a lower-bound that shows the necessity of such a neighbourhood term.   
\subsubsection{Lower bound on quadratics}
\label{sec:lb-correlated}
In order to prove a lower-bound, we consider a pair of $1$-dimensional quadratics $f_i(w) = \nicefrac{1}{2} \, (x_i w - y_i)^2$ for $i = 1, 2$. Here, $w$, $x_i$, $y_i$ are all scalars. The overall function to be minimized is $f(w) = (1/2) \cdot [f_1(w) + f_2(w)]$. We assume that $\norm{x_1} \neq \norm{x_2}$, and since $L_i = \normsq{x_i}$, this assumption implies different smoothness constants for the two functions. For a sufficiently large value of $\gamma_{\max}$ i.e.  $\left(\gamma_{\max} \geq \frac{1}{\min_{i \in [2]} L_i} \right)$, using SLS with $c \geq 1/2$ (required for convergence) results in $\gamma_{k} \leq \nicefrac{1}{L_{ik}}$\footnote{For $1$-dimensional quadratics, $\gamma_{k} = \nicefrac{1}{L_{ik}}$ for $c = \nicefrac{1}{2}$.} (see~\cref{lem:sls-bounds}). With these choices, we prove the following lower-bound in~\cref{app:lb-correlated-proof}.
\begin{thmbox}
\begin{restatable}{theorem}{restatescukclb}
When using $T$ iterations of SGD to minimize the sum $f(w) = \frac{f_1(w) + f_2(w)}{2}$ of two one-dimensional quadratics, $ f_1(w) = \frac{1}{2}(w - 1)^2$ and $f_2(w) = \frac{1}{2}\left(2w + \nicefrac{1}{2} \right)^2$, setting the step-size using SLS with $\gamma_{\max} \geq 1$ and $c \geq \nicefrac{1}{2}$, any convergent sequence of $\alpha_{k}$ results in convergence to a neighbourhood of the solution. Specifically, if $w^{*}$ is the minimizer of $f$ and $w_1 > 0$, then,
\begin{align*}
    \mathbb{E} (w_T - w^*) \geq \min\left( w_1, \frac{3}{8}\right). 
\end{align*}
\label{thm:lb-correlated}
\end{restatable}
\end{thmbox}

The above result shows that using SGD with SLS to set $\gamma_{k}$ and \emph{any convergent sequence of $\alpha_{k}$} (including the exponentially-decreasing sequence in~\cref{thm:sc-unknown-correlated}) will necessarily result in convergence to a neighbourhood. 

The neighbourhood term can thus be viewed as the \emph{price of misestimation} of the unknown smoothness constant. This result is in contrast to the conventional thinking that choosing an $\alpha_{k}$ sequence such that $\lim_{k \rightarrow \infty} \alpha_{k} = 0$ will always ensure convergence to the minimizer. This result is not specific to SLS and would hold for other methods~\citep{loizou2021stochastic,berrada2020training,malitsky2019adaptive} that set $\gamma_{k}$ in an online fashion. Since the lower-bound holds for any convergent $\alpha_{k}$ sequence, a possible reason for  convergence to the neighbourhood is the correlation between $i_k$ (the sampled function) and the computation of $\gamma_{k}$. We verify this hypothesis in the next section. 

\subsection{Offline estimation of unknown smoothness}
\label{sec:sc-unknown-decorrelated}
In this section, we consider an offline estimation of the smoothness constant. By offline, we mean that in iteration $k$ of SGD, $\gamma_{k}$ is set \emph{before} sampling $i_k$ and cannot use any information about it. This ensures that $\gamma_{k}$ is decorrelated with the sampled function $i_k$. The entire sequence of $\gamma_{k}$ can even be chosen before running SGD. 

For simplicity of calculations, we consider a fixed $\gamma_{k} = \gamma$ for all iterations. Here $\gamma$ is an offline estimate of $\frac{1}{L}$, and can be obtained by any method. Without loss of generality, we assume that this offline estimate is off by a multiplicative factor $\nu$ that is $\gamma = \frac{\nu}{L}$ for some $\nu > 0$. Here $\nu$ quantifies the estimation error in $\gamma$ with $\nu = 1$ corresponding to an exact estimation of $L$. In practice, it is typical to be able to obtain lower-bounds on the smoothness constant. Hence, the $\nu > 1$ regime is of practical interest.

For SGD with $\gamma_{k} = \gamma = \frac{\nu}{L}$ and an exponentially decreasing $\alpha_{k}$-sequence, we prove the following theorem in~\cref{app:sc-unknown-decorrelated-proof}. 
\begin{thmbox}
\begin{restatable}{theorem}{restatescukdc}
Assuming (i) convexity and $L_i$-smoothness of each $f_i$, (ii) $\mu$ strong-convexity of $f$, SGD (\cref{eq:sgd}) with $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$, $\alpha_{k} = \alpha^k$ and $\gamma_{k} = \frac{\nu}{L}$ for $\nu > 0$ has the following convergence rate,
\begin{align*}
& \normsq{w_{T+1} - w^{*}} \leq \normsq{w_{1} - w^{*}} \, c_2  \exp\left( - \frac{\nu \, T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) \\ & + \frac{8  \sigma^2}{L \, T}\exp\left(\frac{\nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \frac{4 \kappa^2 \ln(T/\beta)^2}{e^2\alpha^2} \\
& + \left[\max_{j \in \left[T \, \frac{[\ln(\nu)]_{+}}{\ln(\nicefrac{T}{\beta})}\right]} \{ f(w_j) - f^* \}  \frac{(\nu - 1)}{L}\right]  \\ & \times \exp \left( \frac{\nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \, \frac{8 \kappa^2}{\nu e^2\alpha^2 } \frac{[\ln(\nu)]_{+} \, \ln(T/\beta)}{T },
\end{align*}
where $\kappa = \frac{L}{\mu}$, $c_2 = \exp\left( \frac{1}{\kappa} \, \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$ and $[x]_{+} = \max\{x, 0\}$.
\label{thm:sc-unknown-decorrelated}
\end{restatable}
\end{thmbox}
Observe that as $T \rightarrow \infty$, SGD converges to the minimizer $w^{*}$. The first two terms are similar to that in~\cref{thm:sc-known} and imply an $O \left( \exp(-T) + \frac{\sigma^2}{T} \right)$ convergence to the minimizer. The third term can be viewed as the \emph{price of misestimation} of the unknown smoothness constant. Unlike in~\cref{thm:sc-unknown-correlated} where this price was convergence to a neighbourhood, here, the price of misestimation is slower convergence to the minimizer. 

Analyzing the third term, we observe that when $\nu \leq 1$, the third term is zero (since $[\ln(\nu)]_{+} = 0$), and the rate matches that of~\cref{thm:sc-known} up to constants that depend on $\nu$. For $\nu > 1$, the convergence rate slows down by a factor that depends on $\nu$. The third term depends on $\left[\max_{j \in [T \, \nicefrac{[\ln(\nu)]_{+}}{\ln(T/\beta)}]} \{ f(w_j) - f^* \} \right]$ because if $\nu > 1$, SGD can diverge and move away from the solution for the initial $T \, \frac{[\ln(\nu)]_{+}}{\ln(T/\beta)}$ iterations. This can be explained as follows: for $\nu > 1$, the step-size $\gamma_{k} = \frac{\nu}{L} \, \alpha_{k} \geq \frac{1}{L}$ initially, and SGD diverges in this regime. However, since $\alpha_{k}$ is an exponentially decreasing sequence, after $k_0 := T \frac{\ln(\nu)}{\ln(T/\beta)}$ iterations, $\frac{\nu}{L} \, \alpha_{k} \leq \frac{1}{L}$, and the distance to the minimizer decreases after iteration $k_0$, eventually resulting in convergence to the solution. 

Finally, observe that the third term depends on $O \left( \exp(\nu) [\ln(v)]_{+} \right)$ meaning that if we misestimate the smoothness constant by a multiplicative factor of $\nu$, it can slow down the convergence rate by a factor exponential in $\nu$. In the next section, we justify this dependence by proving a corresponding lower-bound.
\subsubsection{Lower bound on quadratics}
\label{sec:lb-decorrelated}
In this section, we consider gradient descent on a one-dimensional quadratic and study the effect of misestimating the smoothness constant by a factor of $\nu > 1$. For simplicity, we consider minimizing a single quadratic, thus ensuring $\sigma^2 = 0$. We prove the following lower-bound in~\cref{app:lb-decorrelated-proof}. \begin{thmbox}     
\begin{restatable}{theorem}{restatescukdclb}
When using gradient descent to minimize a one-dimensional quadratic function $f(w) = \frac{1}{2}(xw - y)^2$, with $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$, $\alpha_{k} = \alpha^k$ and $\gamma_{k} = \frac{\nu}{L}$ for $\nu > 3$ we have
\begin{align*}
    w_{k+1} - w^* = (w_1 - w^*) \prod_{i=1}^k ( 1- \nu \alpha_i).
\end{align*}
After $k' := \frac{T}{\ln (T / \beta)} \ln\left(\frac{\nu}{3}\right)$ iterations, we have that
\begin{align*}
    \abs{w_{k'+1} - w^*} \geq 2^{k'} \abs{w_1 - w^*}.
\end{align*}
\label{thm:lb-decorrelated}
\end{restatable}
\end{thmbox}     
Instantiating this lower-bound, suppose the estimate of $L$ is off by a factor of $\nu = 10$, then $\ln\left(\frac{\nu}{3}\right) \geq 1$, which implies that $k' \geq \floor{\frac{T}{\ln(\nicefrac{T}{\beta})}}$. In other words, we do not make any progress in the first $\frac{T}{\ln(\nicefrac{T}{\beta})}$ iterations, and at this point the optimality gap has been multiplied by a factor of $2^{T/\ln(\nicefrac{T}{\beta})}$ compared to the starting optimality gap. This simple example thus shows the (potentially exponential) slowdown in the rate of convergence by misestimating the smoothness.


In the next section, we design a variant of SLS that ensures convergence to the minimizer while obtaining good empirical control over the misestimation. 




 
  












\section{Additional theoretical results}
\label{sec:additional-theory}
In this section, we relax the strong-convexity assumption to handle broader function classes in~\cref{app:relax} and prove results that help provide an explicit dependence on the mini-batch size (\cref{app:minibatch}) and in~\cref{app:polynomial} show that polynomially decreasing step-sizes cannot obtain the desired noise-adaptive rate. 

\subsection{Relaxing the assumptions}
\label{app:relax}
In this section, we extend our theoretical results to a richer class of functions - strongly quasar-convex functions~\citep{hinder2020near} in~\cref{sec:qsc-ub}, and (non-strongly) convex functions in~\cref{sec:convex-ub}. 

\subsubsection{Extension to strongly star-convex functions}
\label{sec:qsc-ub}
We consider the class of smooth, non-convex, but strongly star-convex functions~\citep{hinder2020near,gower2021sgd}, a subset of strongly quasar-convex functions. Quasar-convex functions are unimodal along lines that pass
through a global minimizer i.e. the function monotonically decreases along the line to the minimizer, and monotonically increases thereafter. In addition to this, strongly quasar-convex functions also have curvature near the global minimizer. Importantly, this property is satisfied for neural networks for common architectures and learning problems~\citep{lucas2021analyzing,kleinberg2018alternative}. 

Formally, a function is $(\zeta,\mu)$ strongly quasar-convex if it satisfies the following for all $w$ and minimizers $w^{*}$,
\begin{align}
f(w^{*}) & \geq f(w) + \frac{1}{\zeta} \langle \grad{w},w^{*} - w \rangle + \frac{\mu}{2} \normsq{w - w^{*}}.
\label{eq:qsc-def}    
\end{align}
Strongly star-convex functions are a subset of this class of functions with $\zeta = 1$. If $L$ is known, it is straightforward to show that the results of~\cref{thm:sc-known} carry over to the strongly star-convex functions and we obtain the similar $O\left(\exp(-T/\kappa) + \frac{\sigma^2}{T} \right)$ rate. In the case when $L$ is not known, it was recently shown that SGD with a stochastic Polyak step-size~\citep{gower2021sgd} results in linear convergence to the minimizer on strongly star-convex functions under interpolation and achieves an $O \left(\exp(-T) + \gamma_{\max} \sigma^2 \right)$ convergence rate in general. The proposed stochastic Polyak step-size (SPS) does not require knowledge of $L$, and matches the rate achieved for strongly-convex functions~\citep{loizou2021stochastic}. However, SPS requires knowledge of $f_{i}^*$, which is usually zero for machine learning models under interpolation but difficult to get a handle on in the general case.

Consequently, we continue to use SLS to estimate the smoothness constant. Our proofs only use strong-convexity between $w$ and a minimizer $w^{*}$, and hence we can extend all our results from strongly-convex functions, to structured non-convex functions satisfying the strongly star-convexity property, matching the rates in~\cref{thm:sc-unknown-correlated} and~\cref{thm:sc-unknown-decorrelated}. Finally, we note that given knowledge of $\zeta$, there is no fundamental limitation in extending all our results to strongly quasar-convex functions. In the next section, we relax the strong-convexity assumption in a different way - by considering convex functions without curvature. 

\subsubsection{Handling (non-strongly)-convex functions}
\label{sec:convex-ub}
In this section, we analyze the behaviour of exponentially decreasing step-sizes on convex functions (without strong-convexity). As a starting point, we assume that $L$ is known, and the algorithm is only required to adapt to the noise $\sigma^2$. In the following theorem (proved in~\cref{app:c-known-proof}), we show that SGD with an exponentially decreasing step-size is not guaranteed to converge to the minimizer, but to a neighbourhood of the solution.   
\begin{restatable}{theorem}{restateck}
Assuming (i) convexity and (ii) $L_i$-smoothness of each $f_i$, SGD with step-size $\eta_{k} = \frac{1}{2 L} \, \alpha_{k}$ has the following convergence rate,
\begin{align}
\mathbb{E} [f(\bar{w}_{T+1}) - f(w^{*})] &\leq \frac{2 L \, \normsq{w_1 - w^{*}}}{\sum_{k = 1}^{T} \alpha_{k}} + \sigma^2 \frac{\sum_{k = 1}^{T} \alpha_{k}^2}{\sum_{k = 1}^{T} \alpha_{k}} 
\label{eq:c-known-general}
\end{align}
where $\bar{w}_{T+1} = \frac{\sum_{k = 1}^{T} \alpha_{k} w_k}{\sum_{k= 1}^{T} \alpha_{k}}$. 
For $\alpha_{k} = \left[\frac{\beta}{T}\right]^{k/T}$, the convergence rate is given by, 
\begin{align*}
\mathbb{E} [f(\bar{w}_{T+1}) - f(w^{*})] &\leq \frac{2 L \, \ln(T/\beta) \, \normsq{w_1 - w^{*}}}{\alpha T - 2 \beta} + \sigma^2 \frac{T}{T - \beta}
\end{align*}
\label{thm:c-known}
\end{restatable}
We thus see that even with the knowledge of $L$, SGD converges to a neighbourhood of the solution at an $O(1/T)$ rate. We contrast our result to AdaGrad~\citep{duchi2011adaptive, levy2018online} that adapts the step-sizes as the algorithm progresses (as opposed to using a predetermined sequence of step-sizes like in our case), is able to adapt to the noise, and achieves an $O\left(\frac{1}{T} + \frac{\sigma^2}{\sqrt{T}}\right)$ rate. 

In order to be noise-adaptive and match the AdaGrad rate, we can use~\cref{eq:c-known-general} to infer that a sufficient condition is for the $\alpha_{k}$-sequence to satisfy the following inequalities, (i) $\alpha_{k} \geq C_1 \, T$ and (ii) $\alpha_{k}^2 \leq C_2 \sqrt{T}$ where $C_1, C_2$ are constants. Unfortunately, in~\cref{lemma:polynomial-convex-bad,lemma:exponential-convex-bad}, we prove that it is not possible for \emph{any} polynomially or exponentially-decreasing sequence to satisfy these sufficient conditions. While we do not have a formal lower-bound in the convex case, it seems unlikely that these $\alpha_{k}$-sequences can result in the desired rate, and we conjecture a possible lower-bound. Finally, we note that to the best of our knowledge, the only predetermined (non-adaptive) step-size that achieves the AdaGrad rate is $\min \left\{\frac{1}{2 L}, \frac{1}{\sigma \sqrt{T}} \right\}$~\citep{ghadimi2012optimal}. We also conjecture a lower-bound that shows that there is no predetermined sequence of step-sizes (that does not use knowledge of $\sigma^2$) that is noise-adaptive and can achieve the $O\left(\frac{1}{T} + \frac{\sigma^2}{\sqrt{T}}\right)$ rate. 

\subsection{Dependence on the mini-batch size}
\label{app:minibatch}
In this section, we prove two results in order to explicitly model the dependence on the mini-batch size. We denote a mini-batch as ${\mathcal{B}}$, its size as $B \in [1, n]$ and the corresponding mini-batch gradient as $\gradb{w}= \frac{1}{B} \sum_{f_{i} \in {\mathcal{B}}}  \nabla f_{i}(w)$. The mini-batch gradient is also unbiased i.e. $\mathbb{E}_{\mathcal{B}}[\gradb{w}] = \grad{w}$, implying that all the proofs remain unchanged, but we need to use a different growth condition for the ASGD proofs in~\cref{sec:acceleration} and a different definition of $\sigma$ for the SGD proofs in~\cref{sec:adaptivity}. We refine these quantities here, and show the explicit dependence on the mini-batch size. 
\begin{thmbox}
\begin{lemmanew}
If 
$$
\mathbb{E}_{i} \normsq{\nabla f_{i}(w)} \leq \rho \normsq{\grad{w}} + \sigma^2,
$$
then, 
$$
\mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w)}} \leq \left( (\rho - 1) \frac{n - B}{n B} + 1 \right) \normsq{\grad{w}} + \frac{n - B}{n B} \sigma^2. 
$$
\label{lemma:mb-growth}
\end{lemmanew}
\end{thmbox}
\begin{proof}
\begin{align*}
\mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w)}} &= \mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w} - \grad{w} + \grad{w}} = \mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w} - \grad{w}} + \normsq{\grad{w}} & \tag{Since $\mathbb{E}_{\mathcal{B}}[\gradb{w}] = \grad{w}$} \\
\intertext{Since we are sampling the batch with replacement, using~\citep{lohr2019sampling},}
& \leq \frac{n - B}{n B} \left(E_i \normsq{\nabla f_{i}(w)} - \normsq{\grad{w}} \right) + \normsq{\grad{w}} \\
& \leq \frac{n - B}{n B} \left((\rho - 1) \normsq{\grad{w}} + \sigma^2 \right) + \normsq{\grad{w}} & \tag{Using the growth condition} \\
\implies \mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w)}} & \leq \left( (\rho - 1) \frac{n - B}{n B} + 1 \right) \normsq{\grad{w}} + \frac{n - B}{n B} \sigma^2. 
\end{align*}
\end{proof}

\begin{thmbox}
\begin{lemmanew}
If $$\sigma^2 := \mathbb{E}[f_{i}(w^{*}) - f_{i}^*],$$ and each function $f_i$ is $\mu$ strongly-convex and $L$-smooth, then 
$$\sigma_B^2 := \mathbb{E}_{{\mathcal{B}}}[f_{{\mathcal{B}}}(w^{*}) - f_{{\mathcal{B}}}^*] \leq \frac{L}{\mu} \, \frac{n - B}{n B} \sigma^2.$$
\label{lemma:mb-sigma}
\end{lemmanew}
\end{thmbox}
\begin{proof}
\begin{align*}
\intertext{By strong-convexity of $f_i$,}
\mathbb{E}_{{\mathcal{B}}}[f_{{\mathcal{B}}}(w^{*}) - f_{{\mathcal{B}}}^*] & \leq \frac{1}{2 \mu} \mathbb{E}_{{\mathcal{B}}} \normsq{\gradb{w^{*})}}  \\
\intertext{Since we are sampling the batch with replacement, using~\citep{lohr2019sampling},}
& \leq \frac{1}{2 \mu} \frac{n - B}{n B} \mathbb{E}_i \normsq{\nabla f_{i}(w^{*})} \\
& \leq \frac{L}{\mu} \frac{n - B}{n B} \mathbb{E}[f_{i}(w^{*}) - f_{i}^*] & \tag{By smoothness of $f_i$} \\
\implies \sigma_B^2 & \leq \frac{L}{\mu} \frac{n - B}{n B} \sigma^2.
\end{align*}
\end{proof}

 \subsection{Polynomially decaying stepsizes}
 \label{app:polynomial}
 In this section, we analyze polynomially decreasing step-sizes, namely when $\eta_k = \frac{\eta}{(k+1)^{\delta}}$ for some constants $\eta > 0$ and $0 \leq \delta \leq 1$. We argue that even with knowledge of the smoothness constant, these step-sizes fail to converge at the desired noise-adaptive rate even on simple quadratics. In particular, the next lemma shows that gradient descent (GD) applied to a strongly-convex quadratic with a polynomially decreasing step-size fails to obtain the usual linear rate of the form $O(\rho^{-T})$ for some $\rho < 1$.

 \begin{thmbox}
 \begin{lemmanew}
 When using $T$ iterations of GD to minimize a one-dimensional quadratic $f(w) = \frac{1}{2}(xw - y)^2$, setting $\eta_k = \frac{1}{L} \frac{1}{(k+1)^\delta}$ for some $0 < \delta \leq 1$ results in the following lower bounds.\\
 If $\delta = 1$,
 \begin{align*}
     w_{T+1} - w^* = \left( w_1 - w^*\right) \frac{1}{T+1}
 \end{align*}
 If $0 < \delta < 1$,  $w_1 - w^* > 0$ and $T$ is large enough,
 \begin{align*}
     w_{T+1} - w^* \geq (w_1 - w^*) \left(1 -  \frac{1}{2^\delta}\right)^{\floor{2^{1/\delta}} - 1} 4^{\frac{2\delta - 1}{1 - \delta}}4 ^{- \frac{(T+1)^{1- \delta}}{1- \delta}}
 \end{align*}
 \label{lemma:polynomial-lb-1}
 \end{lemmanew}
 \end{thmbox}
\begin{proof}
Observe that $w^* = \nicefrac{y}{x}$ and $L = x^2$. The GD iteration with $\eta_k = \frac{1}{L} \frac{1}{(k+1)^\delta}$ reads
\begin{align*}
    w_{k+1} = w_k - \frac{1}{L} \frac{1}{(k+1)^\delta} \left( x^2 w_k - xy\right) = w_k\left( 1 - \frac{1}{(k+1)^\delta}\right) + \frac{y}{x} \frac{1}{(k+1)^\delta} = w_k\left( 1 - \frac{1}{(k+1)^\delta}\right) + w^* \frac{1}{(k+1)^\delta}
\end{align*}
and thus
\begin{align*}
    w_{k+1} - w^* = \left( w_k - w^* \right) \left( 1-  \frac{1}{(k+1)^\delta}\right) \Rightarrow w_{T+1} - w^* = (w_1 - w^*) \prod_{k=1}^T \left( 1 - \frac{1}{(k+1)^\delta}\right)
\end{align*}
If $\delta = 1$,
\begin{align*}
    w_{T+1} - w^* = (w_1 - w^*) \prod_{k=1}^T \frac{k}{k+1} = (w_1 - w^*) \frac{1}{T+1}
\end{align*}
If $0 < \delta < 1$ and $w_1 - w^* > 0$,
\begin{align*}
    w_{T+1} - w^* = (w_1 - w^*) \prod_{k=1}^T \left( 1 - \frac{1}{(k+1)^\delta}\right) = (w_1 - w^*) \prod_{k=1}^T \left( 1 - \frac{2}{2(k+1)^\delta}\right)
\end{align*}
We wish to use the inequality $1 - \frac{2x}{2} \geq 2^{-2x}$ which is true for all $x \in [0, 1/2]$. In our case it holds for
\begin{align*}
    \frac{1}{(k+1)^\delta} \leq \frac{1}{2} \Rightarrow k \geq 2^{1/\delta} - 1
\end{align*}
Let $k_0 = \floor{2^{1/\delta}}$. Then for $ T \geq k_0$, 
\begin{align*}
    w_{T+1} - w^* = (w_1 - w^*) \prod_{k=1}^{k_0 - 1} \left( 1- \frac{1}{(k+1)^{\delta}}\right) \prod_{k=k_0}^{T} \left( 1- \frac{2}{2(k+1)^{\delta}}\right)
\end{align*}
Now, for $k \leq k_0 - 1$, we have that $\frac{1}{(k+1)^{\delta}} \leq \frac{1}{2^\delta}$ and thus
\begin{align*}
    \prod_{k=1}^{k_0 - 1} \left( 1- \frac{1}{(k+1)^{\delta}}\right) \geq \left( 1 - \frac{1}{2^\delta} \right)^{k_0 - 1} = \left(1 -  \frac{1}{2^\delta}\right)^{\floor{2^{1/\delta}} - 1}
\end{align*}
For $k \geq k_0$, we have $1 - \frac{2}{2(k+1)^\delta} \geq 2^{-2 \frac{1}{(k+1)^\delta}}$ and thus
\begin{align*}
    \prod_{k=k_0}^T \left( 1- \frac{2}{2(k+1)^\delta}\right) \geq 2^{-2 \sum_{k=k_0}^T \frac{1}{(k+1)^{\delta}}} = 2^{-2 \left(\sum_{k=1}^{T+1} \frac{1}{k^\delta} - \sum_{k=1}^{k_0} \frac{1}{k^\delta}\right)} \geq 2^{-2 \sum_{k=1}^{T+1} \frac{1}{k^\delta}}
\end{align*}
Using the bound in the proof of~\cref{lemma:polynomial-convex-bad}, we have
\begin{align*}
    \sum_{k=1}^{T+1} \frac{1}{k^\delta} &\leq 1 + \frac{1}{1- \delta} \left( (T+1)^{1 - \delta} - 1\right)
\end{align*}
Putting this together we have that
\begin{align*}
    2^{-2 \sum_{k=1}^{T+1} \frac{1}{k^\delta} } \geq 2^{-2 \left(1 + \frac{1}{1- \delta} \left( (T+1)^{1 - \delta} - 1\right)\right) } = \frac{4^{1/(1-\delta)}}{4}4^{- \frac{(T+1)^{1- \delta}}{1- \delta}} = 4^{\frac{2\delta - 1}{1 - \delta}}4 ^{- \frac{(T+1)^{1- \delta}}{1- \delta}}
\end{align*}
Putting everything together we get that
\begin{align*}
    w_{T+1 } - w^* \geq (w_1 - w^*) \left(1 -  \frac{1}{2^\delta}\right)^{\floor{2^{1/\delta}} - 1} 4^{\frac{2\delta - 1}{1 - \delta}}4 ^{- \frac{(T+1)^{1- \delta}}{1- \delta}}
\end{align*}
\end{proof}

 The next lemma shows that when $\delta = 0$, namely when the step-size is constant, SGD applied to the sum of two quadratics fails to converge to the minimizer.

 \begin{thmbox}
 \begin{lemmanew}
 When using SGD to minimize the sum $f(w) = \frac{f_1(w) + f_2(w)}{2}$ of two one-dimensional quadratics: $f_1(w) = \frac{1}{2}(w - 1)^2$ and $f_2(w) = \frac{1}{2}(2w + \nicefrac{1}{2})^2$ with a constant step-size $\eta = \frac{1}{L}$, the following holds: whenever $\abs{w_{k} - w^*}  < \nicefrac{1}{8}$, the next iterate satisfies $\abs{w_{k+1} - w^*} > \nicefrac{1}{8}$.
 \label{lemma:polynomial-lb-2}
 \end{lemmanew}
 \end{thmbox}
 \begin{proof}
 First observe that $w^* = 0$ and that $L = 4$. The updates then read
 \begin{align*}
     &\text{If } i_k = 1: \quad w_{k+1} = w_k - \eta (w_k - 1) = w_k(1 - \frac{1}{4}) + \frac{1}{4} = \frac{3}{4}w_k + \frac{1}{4}\\
     &\text{If } i_k = 2: \quad w_{k+1} = w_k - \eta 2(2w_k + \frac{1}{2}) = w_k(1 - \frac{4}{4}) - \frac{1}{4} =  - \frac{1}{4}
 \end{align*}
 Suppose that $\abs{w_k - w^*} = \abs{w_k} < \nicefrac{1}{8}$. We want to show that $\abs{w_{k+1}} > \nicefrac{1}{8}$. We can separate the analyses in three cases.\\
 If $w_k \in (-\nicefrac{1}{8}, 0)$ and $i_k = 1$ then
\begin{align*}
     w_{k+1} = \frac{3}{4} w_k + \frac{1}{4} > -\frac{3}{4}\times \frac{1}{8} + \frac{1}{4} = \frac{5}{32} > \frac{1}{8} 
 \end{align*}
 If $w_k \in (0, \nicefrac{1}{8})$ and $i_k = 1$ then
 \begin{align*}
     w_{k+1} = \frac{3}{4} w_k + \frac{1}{4} > \frac{1}{8} 
 \end{align*}
 If $i_k = 2$ then
 \begin{align*}
     w_{k+1} = -\frac{1}{4}  < - \frac{1}{8} 
 \end{align*}
 implying that in each case, $\abs{w_{k+1}} > \nicefrac{1}{8}$.
 \end{proof}

\section{Proof for ASGD}
\label{app:acceleration-proof}

\subsection{Reformulation}
\label{app:reformulation}
Let us consider a general ASGD update whose parameters satisfy the following conditions. 
\begin{align}
r_{k}^2 &= (1 - r_{k}) r_{k-1}^2 \frac{\eta_{k}}{\eta_{k-1}} + r_{k} \mu \eta_{k}. \label{eq:a-def} \\
b_{k} &= \frac{(1 - r_{k-1}) r_{k-1} \frac{\eta_{k}}{\eta_{k-1}}}{r_{k} + r_{k-1}^2 \frac{\eta_{k}}{\eta_{k-1}}}, \label{eq:b-a} 
\end{align}
It can be verified that setting $\eta_{k} = \gamma_{k} \alpha_{k} = \frac{1}{\rho L} \left(\frac{\beta}{T} \right)^{k/T}$, $r_{k} = \sqrt{\frac{\mu}{\rho L}} \left(\frac{\beta}{T} \right)^{k/2T}$ satisfies~\cref{eq:a-def}.


We first show that the update in~\cref{eq:extrapolation}-\cref{eq:sgd-update} satisfying the conditions in~\cref{eq:b-a} and ~\cref{eq:a-def} can be written in an equivalent form more amenable to the analysis. 
\begin{lemmanew}
The following update:
\begin{align}
y_{k} & = w_{k} - \frac{r_{k} q_{k}}{q_{k} + r_{k} \mu} (w_{k} - z_{k}) \label{eq:y-update} \\
w_{k+1} &= y_{k} - \eta_{k} \gradk{y_{k}} & \label{eq:x-update} \\
z_{k+1} &= w_{k} + \frac{1}{r_{k}} [w_{k+1} - w_{k}] & \label{eq:z-update} 
\end{align}
where,
\begin{align}
q_{k+1} &= (1 - r_{k}) q_{k} + r_{k} \mu & \label{eq:q-update} \\
r_{k}^2 & = q_{k+1} \eta_{k} \label{eq:a-q} \\ 
z_{k+1} &= \frac{1}{q_{k+1}} \left[ (1 - r_{k}) q_{k} z_{k} + r_{k} \mu y_{k} - r_{k} \gradk{y_{k}} \right] & \label{eq:z-def} 
\end{align}
is equivalent to the update in~\cref{eq:extrapolation}-\cref{eq:sgd-update}.
\label{lemma:reformulation}
\end{lemmanew}
\begin{proof}
\begin{align*}
\intertext{First we check the consistency of the update (\cref{eq:z-update}) and definition (\cref{eq:z-def}) of $z_{k}$. Using~\cref{eq:z-def},}
z_{k+1} &= \frac{1}{q_{k+1}} \left[ (1 - r_{k}) q_{k} z_{k} + r_{k} \mu y_{k} - r_{k} \gradk{y_{k}} \right] \\
& = -\frac{(1 - r_{k})}{r_{k}} w_{k} - \frac{r_{k}}{q_{k+1}} \gradk{y_{k}} + y_{k} \left[\frac{(1 - r_{k}) (q_{k} + r_{k} \mu)}{q_{k+1} r_{k}} + \frac{r_{k} \mu}{q_{k+1}} \right] \\
& = -\frac{(1 - r_{k})}{r_{k}} w_{k} - \frac{r_{k}}{q_{k+1}} \gradk{y_{k}} + y_{k} \left[\frac{q_{k} (1 - r_{k}) +  (r_{k} \mu - r_{k}^2 \mu)}{q_{k+1} r_{k}} + \frac{r_{k}^2 \mu}{q_{k+1} r_{k}} \right] \\
& = -\frac{(1 - r_{k})}{r_{k}} w_{k} - \frac{r_{k}}{q_{k+1}} \gradk{y_{k}} + y_{k} \left[\frac{(q_{k+1} - r_{k} \mu) +  (r_{k} \mu - r_{k}^2 \mu) + r_{k}^2 \mu}{q_{k+1} r_{k}} \right] & \tag{From~\cref{eq:q-update}} \\
& = w_{k} - \frac{w_{k}}{r_{k}} + \frac{1}{r_{k}} \left[y_{k} - \eta_{k} \gradk{y_{k}} \right] & \tag{From~\cref{eq:a-q}} \\
z_{k+1} & = w_{k} + \frac{1}{r_{k}} \left[w_{k+1} - w_{k} \right] & \tag{From~\cref{eq:x-update}} 
\intertext{which recovers~\cref{eq:z-update} showing that the definition of $z_{k}$ and its update is consistent.} 
\intertext{Now we check the equivalence of~\cref{eq:a-def} and ~\cref{eq:q-update}-\cref{eq:a-q}. Eliminating $q_{k}$ using~\cref{eq:q-update}-\cref{eq:a-q},}
\frac{r_{k}^2}{\eta_{k}} &= (1 - r_{k}) \frac{r_{k-1}^2}{\eta_{k-1}} + r_{k} \mu 
\intertext{Multiplying by $\eta_{k}$ recovers~\cref{eq:a-def}.}
\end{align*}
\begin{align*}
\intertext{Since~\cref{eq:sgd-update} and~\cref{eq:x-update} are equivalent, we need to establish the equivalence of~\cref{eq:extrapolation} and the updates in~\cref{eq:y-update}-\cref{eq:z-update}. From~\cref{eq:z-update}}
z_{k} & = w_{k-1} + \frac{1}{r_{k-1}} \left[w_{k} - w_{k-1} \right] \implies z_{k} - w_{k}  = \frac{1 - r_{k-1}}{r_{k-1}} (w_{k} - w_{k-1})
\intertext{Starting from~\cref{eq:y-update} and using the above relation to eliminate $z_{k}$,}
y_{k}& = w_{k} + \frac{r_{k} q_{k}}{q_{k} + r_{k} \mu} \frac{1 - r_{k-1}}{r_{k-1}} \left[w_{k} - w_{k-1} \right] 
\intertext{which is in the same form as~\cref{eq:extrapolation}. We now eliminate $q_{k}$ from $\frac{r_{k} q_{k}}{q_{k} + r_{k} \mu} \frac{1 - r_{k-1}}{r_{k-1}}$. From~\cref{eq:q-update} and~\cref{eq:a-q},}
\frac{r_{k}^2}{\eta_{k}} &= (1 - r_{k}) q_{k} + r_{k} \mu \implies q_{k} + r_{k} \mu = \frac{r_{k}^2}{\eta_{k}} + r_{k} q_{k} 
\intertext{Using this relation,}
\frac{r_{k} q_{k}}{q_{k} + r_{k} \mu} \frac{1 - r_{k-1}}{r_{k-1}} &= \frac{q_{k} \eta_{k}}{r_{k} + q_{k} \eta_{k}} \frac{1 - r_{k-1}}{r_{k-1}} \\
\intertext{Using~\cref{eq:a-q}, observe that $\eta_{k} q_{k} = \frac{\eta_{k}}{\eta_{k-1}} \eta_{k-1} q_{k} = \frac{\eta_{k}}{\eta_{k-1}} r_{k-1}^2$. Using this relation, }
\frac{r_{k} q_{k}}{q_{k} + r_{k} \mu} \frac{1 - r_{k-1}}{r_{k-1}} & = \frac{\frac{\eta_{k}}{\eta_{k-1}} r_{k-1}^2}{r_{k} + \frac{\eta_{k}}{\eta_{k-1}} r_{k-1}^2} \frac{1 - r_{k-1}}{r_{k-1}} = \frac{(1 - r_{k-1}) r_{k-1}}{r_{k} \frac{\eta_{k-1}}{\eta_{k}} + r_{k-1}^2} = b_{k} 
\intertext{which establishes the equivalence to~\cref{eq:extrapolation} and completes the proof.}
\end{align*}
\end{proof}

\subsection{Estimating sequences}
\label{app:estimating-sequences}
Similar to~\citep{nesterov2013introductory, mishkin2020interpolation}, we will use the estimating sequence $\{\phi_{k}$, $\lambda_{k} \}_{k = 1}^{\infty}$ such that $\lambda_{k} \in (0,1)$ and 
\begin{align}
\lambda_0 & = 1 \quad \text{;} \quad \lambda_{k+1} = (1 - r_{k}) \lambda_{k},  \label{eq:lambda-def}  \\    
\phi_{k}(w) &= [\inf_{w} \phi_{k}(w)] + \frac{q_{k}}{2} \normsq{w - z_{k}},  \label{eq:phi-def} 
\end{align}
and satisfies the following update condition 
\begin{align}
\phi_{k}(w) & \leq (1 - \lambda_{k}) f(w) + \lambda_{k} \phi_0(w)
\label{eq:phi-relation} 
\end{align}
The above definitions impose the following update for $\phi_{k}^* := [\inf_{w} \phi_{k}(w)]$, 
\begin{align}
\phi_{k+1}^* & = (1 - r_{k}) \phi_{k}^* + r_{k} \left[f(y_{k}) - \frac{r_{k}}{2 q_{k+1}} \normsq{\grad{y_{k}}} + \frac{(1 - r_{k}) \, q_{k}}{q_{k+1}} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right)\right] \label{eq:phistar-update}
\end{align}
Finally note that the definition of $\phi_{k}$ can be used to rewrite~\cref{eq:y-update} as 
\begin{align}
y_{k} & = w_{k} - \frac{r_{k}}{q_{k} + r_{k} \mu} \nabla \phi_{k}(w_{k}).  \label{eq:y-update-2}    
\end{align}

\subsection{Proof of~\cref{thm:sc-accelerated}}
\label{app:acceleration-thm-proof}
Given the definitions in~\cref{app:estimating-sequences}, we first prove the descent lemma for $\eta_{k} = \frac{1}{\rho L} \alpha_{k}$, where $\alpha_{k} \leq 1$ is the exponentially decreasing step-size. 
\begin{lemmanew}
Using the update in~\cref{eq:x-update} with $\eta_{k} = \frac{1}{\rho L} \alpha_{k}$, we obtain the following descent condition. 
\begin{align*}
\mathbb{E}[f(w_{k+1})] & \leq \mathbb{E}[f(y_{k})] - \frac{\eta_{k}}{2} \normsq{\grad{y_{k}}} + \frac{1}{2 \rho^2 L} \alpha_{k}^2 \sigma^2    
\end{align*}
\label{lemma:descent-lemma}
\end{lemmanew}
\begin{proof}
By smoothness, and the update in~\cref{eq:x-update},
\begin{align*}
f(w_{k+1}) & \leq f(y_{k}) - \eta_{k} \inner{\grad{y_{k}}}{\gradk{y_{k}}} + \frac{L}{2} \eta_{k}^2 \normsq{\gradk{y_{k}}} \\
\intertext{Taking expectation w.r.t. $i_k$,}
\mathbb{E}[f(w_{k+1})] & \leq \mathbb{E}[f(y_{k})] - \eta_{k} \normsq{\grad{y_{k}}} + \frac{L}{2} \eta_{k}^2 \mathbb{E}[\normsq{\gradk{y_{k}}}] & \tag{$\eta_{k}$ is independent of the randomness in $i_k$.} \\
& \leq \mathbb{E}[f(y_{k})] - \eta_{k} \normsq{\grad{y_{k}}} + \frac{\rho L}{2} \eta_{k}^2 \mathbb{E}[\normsq{\grad{y_{k}}}] + \frac{L}{2} \eta_{k}^2 \sigma^2 & \tag{By the growth condition in~\cref{eq:growth-condition}} \\
& = \mathbb{E}[f(y_{k})] - \eta_{k} \normsq{\grad{y_{k}}} + \frac{\eta_{k} \alpha_{k}}{2} \mathbb{E}[\normsq{\grad{y_{k}}}] + \frac{1}{2 \rho^2 L} \sigma^2 \\
& \leq \mathbb{E}[f(y_{k})] - \frac{\eta_{k}}{2} \normsq{\grad{y_{k}}} + \frac{1}{2 \rho^2 L} \sigma^2 \\
\end{align*}
\end{proof}

The main part of the proof is to show that $\phi_{k}^*$ is an upper-bound on $f(w_{k})$ (upto a factor governed by the noise term ${\mathcal{N}_k}$ depending on $\sigma^2$) for all $k$ and is proved in the following lemma. 
\begin{lemmanew}
For the estimating sequences defined in~\cref{app:estimating-sequences} and the updates in~\cref{eq:y-update}-\cref{eq:z-def}, for all $k$, 
\begin{align*}
\mathbb{E}[\phi_{k}^*] :=  \mathbb{E}[ \inf_{w} \phi_{k}(w)] & \geq \mathbb{E}[f(w_{k})] - {\mathcal{N}_k}
\end{align*}
where ${\mathcal{N}_k} := \frac{2 \sigma^2}{\rho^2 L} \sum_{j = 0}^{k-1} \alpha_j^2 \, \prod_{i = j+1}^{k-1} (1 - r_i)$. 
\label{lemma:acceleration-induction}
\end{lemmanew}
\begin{proof}
We will prove the lemma by induction. For $k = 0$, we define $\phi^* _0 = f(w_0)$, and since ${\mathcal{N}_k} \geq 0$ for all $k$, $\mathbb{E}[\phi^*] \geq f(w_0) - {\mathcal{N}}_0$, thus satisfying the base-case for the induction. For the induction, we will use the fact that ${\mathcal{N}_{k+1}} = (1 - r_{k}) {\mathcal{N}_k} + \frac{2 \sigma^2}{\rho^2 L} \alpha_{k}^2$.

Assuming the induction hypothesis, $\mathbb{E}[\phi_{k}^*] \geq \mathbb{E}[f(w_{k})] - {\mathcal{N}_k}$, we use~\cref{eq:phistar-update} to prove the statement for $k+1$ as follows. Taking expectations w.r.t to the randomness in $j = 1$ to $k$,
\begin{align*}
\mathbb{E}[\phi_{k+1}^*] & = (1 - r_{k}) \mathbb{E}[\phi_{k}^*] + r_{k} \mathbb{E}\left[f(y_{k}) - \frac{r_{k}}{2 q_{k+1}} \normsq{\grad{y_{k}}} +  \frac{(1 - r_{k}) \, q_{k}}{q_{k+1}} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right)\right] \\
& \geq (1 - r_{k}) \mathbb{E}[f(w_{k}) - {\mathcal{N}_k}] + r_{k} \mathbb{E}\left[f(y_{k}) - \frac{r_{k}}{2 q_{k+1}} \normsq{\grad{y_{k}}} +  \frac{(1 - r_{k}) \, q_{k}}{q_{k+1}} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right)\right] & \tag{by the induction hypothesis} \\
& = (1 - r_{k}) \mathbb{E}[f(w_{k})] + r_{k} \mathbb{E}[f(y_{k})] - \frac{r_{k}^2}{2 q_{k+1}} \mathbb{E}\normsq{\grad{y_{k}}} +  \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E}\left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) \\ & - (1 - r_{k}) {\mathcal{N}_k} \\
& = (1 - r_{k}) \mathbb{E}[f(w_{k})] + r_{k} \mathbb{E}[f(y_{k})] - \frac{\eta_{k}}{2} \mathbb{E}\normsq{\grad{y_{k}}}\\
& +  \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E}\left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) - (1 - r_{k}) {\mathcal{N}_k} & \tag{Using~\cref{eq:a-q}} \\
\intertext{By convexity, $f(w_{k}) \geq f(y_{k}) + \inner{\grad{y_{k}}}{w_{k} - y_{k}}$,}
& \geq (1 - r_{k}) \mathbb{E}[f(y_{k}) + \inner{\grad{y_{k}}}{w_{k} - y_{k}}] + r_{k} \mathbb{E}[f(y_{k})] - \frac{\eta_{k}}{2} \mathbb{E}\normsq{\grad{y_{k}}} \\ & + \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}}  \mathbb{E} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right)  - (1 - r_{k}) {\mathcal{N}_k} \\
& = \mathbb{E} \left[f(y_{k}) - \frac{\eta_{k}}{2} \normsq{\grad{y_{k}}} \right] +  \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) \\ & +  (1 - r_{k}) \mathbb{E}[\inner{\grad{y_{k}}}{w_{k} - y_{k}}] - (1 - r_{k}) {\mathcal{N}_k} \\
\intertext{By~\cref{lemma:descent-lemma},}
& \geq \mathbb{E} \left[f(w_{k+1}) - \frac{1}{2 \rho^2 L} \alpha_{k}^2 \sigma^2 \right] +  \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) \\ & + (1 - r_{k}) \mathbb{E}[\inner{\grad{y_{k}}}{w_{k} - y_{k}}] - (1 - r_{k}) {\mathcal{N}_k} \\
& = \mathbb{E} \left[f(w_{k+1}) \right] +  \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) +  (1 - r_{k}) \mathbb{E}[\inner{\grad{y_{k}}}{w_{k} - y_{k}}] \\ & - \left[(1 - r_{k}) {\mathcal{N}_k} +  \frac{1}{2 \rho^2 L} \alpha_{k}^2 \sigma^2 \right]\\
\intertext{Since ${\mathcal{N}_{k+1}} = \left[(1 - r_{k}) {\mathcal{N}_k} + \frac{1}{2 \rho^2 L} \alpha_{k}^2 \sigma^2 \right]$,}
\mathbb{E}[\phi_{k+1}^*] & \geq \mathbb{E} \left[f(w_{k+1}) \right] - {\mathcal{N}_{k+1}} + (1 - r_{k}) \mathbb{E}[\inner{\grad{y_{k}}}{w_{k} - y_{k}}] + \frac{r_{k} (1 - r_{k}) \, q_{k}}{q_{k+1}} \mathbb{E} \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right)  \\
\end{align*}
Now we show that the remaining terms $(1 - r_{k}) \mathbb{E}\left[ \inner{\grad{y_{k}}}{w_{k} - y_{k}} + \frac{r_{k} \, q_{k}}{q_{k+1}}  \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) \right] \geq 0$. For this, we use~\cref{eq:y-update}
\begin{align*}
y_{k} & = w_{k} - \frac{q_{k} r_{k}}{q_{k} + r_{k} \mu} (w_{k} - z_{k}) \\
\implies z_{k} - y_{k} &= z_{k} - w_{k} + \frac{q_{k} r_{k}}{q_{k} + r_{k} \mu} (w_{k} - z_{k}) = \left(1 - \frac{q_{k} r_{k}}{q_{k} + r_{k} \mu} \right) (z_{k} - w_{k}) \\
& = \left( \frac{q_{k} (1 - r_{k}) + r_{k} \mu}{q_{k} + r_{k} \mu} \right) (z_{k} - w_{k}) = \left( \frac{q_{k+1}}{q_{k} + r_{k} \mu} \right) (z_{k} - w_{k}) & \tag{By~\cref{eq:q-update}} \\
\implies \frac{r_{k} q_{k}}{q_{k+1}} \inner{\grad{y_{k}}}{z_{k} - y_{k}} &= \left \langle \grad{y_{k}} , \left( - \frac{r_{k} \, q_{k}}{q_{k} + r_{k} \mu} \right) (w_{k} - z_{k}) \right \rangle = \left \langle \grad{y_{k}} , y_{k}- w_{k} \right \rangle
\end{align*}
Using this relation to simplify, 
\begin{align*}
& (1 - r_{k})\mathbb{E} \left[ \inner{\grad{y_{k}}}{w_{k} - y_{k}} + \frac{r_{k} \, q_{k}}{q_{k+1}}  \left( \frac{\mu}{2} \normsq{y_{k} - z_{k}} + \inner{\grad{y_{k}}}{z_{k} - y_{k}} \right) \right] \\ 
&= (1 - r_{k}) \mathbb{E} \left[\frac{r_{k} \, q_{k}}{q_{k+1}} \frac{\mu}{2} \normsq{y_{k} - z_{k}} + (1 - r_{k}) \left[\inner{\grad{y_{k}}}{w_{k} - y_{k}} + \left \langle \grad{y_{k}} , y_{k}- w_{k} \right \rangle \right] \right]\\
& = (1 - r_{k}) \mathbb{E} \left[\frac{r_{k} \, q_{k}}{q_{k+1}} \frac{\mu}{2} \normsq{y_{k} - z_{k}} \right]\geq 0 & \tag{Since $r_{k} \leq 1$.}
\end{align*}
Putting everything together, 
\begin{align*}
\mathbb{E}[\phi_{k+1}^*] & \geq \mathbb{E} \left[f(w_{k+1}) \right] - {\mathcal{N}_{k+1}}    
\end{align*}
and we conclude that $\mathbb{E}[\phi_{k}^*] \geq \mathbb{E} \left[f(w_{k}) \right] - {\mathcal{N}_k}$ for all $k$ by induction.  
\end{proof}
We now use the above lemma to prove the rate for strongly-convex functions. 

\myquote{\begin{thmbox}
\restatescacc*
\end{thmbox}
}
\begin{proof}
Using the reformulation in~\cref{lemma:reformulation} gives us $q_{k} = \mu$ for all $k$ and $z_0 = w_0$. For the estimating sequences defined in~\cref{app:estimating-sequences}, using~\cref{lemma:acceleration-induction}, we know that the (reformulated) updates satisfy the following relation, \begin{align*}
\mathbb{E}[f(w_{T})] & \leq \mathbb{E}[\phi^*_{T}] + {\mathcal{N}}_{T}  \leq  \mathbb{E}[\phi_{T}(w^{*})] + {\mathcal{N}}_{T}
\end{align*}
From~\cref{eq:phi-relation}, we know that for all $w$ and $k$, 
\begin{align*}
\phi_{k}(w) &\leq (1 - \lambda_{k}) f(w) + \lambda_{k} \phi_0(w)    
\end{align*}
Using these relations, 
\begin{align*}
\mathbb{E}[f(w_{T})] & \leq (1 - \lambda_{T}) f^* + \lambda_{T} \phi_0(w^{*}) + {\mathcal{N}}_{T} \\
\implies \mathbb{E}[f(w_{T}) - f^*] & \leq \lambda_{T} \left[\phi_0(w^{*}) - f^* \right] + {\mathcal{N}}_{T} \\
\intertext{By~\cref{eq:phi-def},}
& \leq \lambda_{T} \left[\phi^*_0 + \frac{q_0}{2} \normsq{w^{*}- z_0} - f^* \right] + {\mathcal{N}}_{T} \\
\intertext{Choosing $\phi^*_0 = f(w_0)$,}
& \leq \lambda_{T} \left[f(w_0) - f^* + \frac{q_0}{2} \normsq{w^{*}- z_0} \right] + {\mathcal{N}}_{T} \\
\intertext{Since $z_0 = w_0$, $q_0 = \mu$,}
\implies \mathbb{E}[f(w_{T}) - f^*] & \leq \lambda_{T} \left[f(w_0) - f^* + \frac{\mu}{2} \normsq{w^{*}- w_0} \right] + \frac{2 \sigma^2}{\rho^2 L} \sum_{j = 0}^{T-1} \alpha_j^2 \, \prod_{i = j+1}^{T-1} (1 - r_i) 
\end{align*}
Using the fact that $\lambda_0 = 1$ and $\lambda_{k+1} = (1 - r_{k}) \lambda_{k}$, we know that that $\lambda_{T} = \prod_{k = 1}^{T} (1 - r_{k})$, and 
\begin{align*}
\mathbb{E}[f(w_{T}) - f^*] & \leq \left[\prod_{k = 1}^{T} (1 - r_{k}) \right] \, \left[f(w_0) - f^* + \frac{\mu}{2} \normsq{w^{*}- w_0} \right] + \frac{2 \sigma^2}{\rho^2 L} \sum_{j = 0}^{T-1} \alpha_j^2 \, \prod_{i = j+1}^{T-1} (1 - r_i).
\end{align*}
Now our task is to upper-bound bound the $1 - r_{k}$ terms. From~\cref{eq:a-q}, we know that 
\begin{align*}
r_{k} & =  \sqrt{q_{k+1} \eta_{k}} = \sqrt{\frac{q_{k+1}}{\rho L}} \sqrt{\alpha_{k}} \geq \sqrt{\frac{q_{k+1}}{\rho L}} \alpha_{k}  & \tag{Since $\alpha_{k} \leq 1$ for all $k$}  \\
\implies (1 - r_{k}) & \leq \left( 1 - \sqrt{\frac{q_{k+1}}{\rho L}} \alpha_{k} \right)
\end{align*}
Since $q_{k} = \mu$ for all $k$, putting everything together, 
\begin{align*}
\mathbb{E}[f(w_{T}) - f^*] & \leq \left[\prod_{k = 1}^{T} \left( 1 - \sqrt{\frac{1}{\rho \kappa}} \alpha_{k} \right) \right] \, \left[f(w_0) - f^* + \frac{\mu}{2} \normsq{w^{*}- w_0} \right] + \frac{2 \sigma^2}{\rho^2 L} \sum_{j = 0}^{T-1} \alpha_j^2 \, \prod_{i = j+1}^{T-1} \left( 1 - \sqrt{\frac{1}{\rho \kappa}} \alpha_i \right) 
\intertext{Denoting $\Delta_k = \mathbb{E}[f(w_k) - f^*]$, and using the exponential step-size $\alpha_{k} = \alpha^{\nicefrac{k}{T}} = \left(\frac{1}{T}\right)^{\nicefrac{k}{T}}$,}
\Delta_T & \leq 2 \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \sum_{k = 1}^{T}  \alpha^{k} \right) \Delta_0 + \frac{2 \sigma^2}{\rho^2 L} \sum_{k = 0}^{T-1} \alpha^{2k} \, \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \sum_{i = k+1}^{T-1}  \alpha^i \right)
\end{align*}
Using~\cref{lemma:A-bound}, we can bound the first term as
\begin{align*}
    2 \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \sum_{k = 1}^{T}  \alpha^{k} \right) \Delta_0 &\leq 2 \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \left( \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right) \right) \Delta_0\\
    &= 2c_3 \exp\left( - \frac{T}{\sqrt{\kappa \rho}} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) [f(w_0) - f^*]
\end{align*}
where $c_3 = \exp \left( \frac{2 \beta}{\sqrt{\rho \kappa} \ln (\nicefrac{T}{\beta})}\right)$. We can now bound the second term by a proof similar to~\cref{lemma:B-bound}. Indeed we have
\begin{align*}
     \sum_{k = 0}^{T-1} \alpha^{2k} \, \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \sum_{i = k+1}^{T-1}  \alpha^i \right) &=  \sum_{k = 0}^{T-1} \alpha^{2k} \, \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \frac{\alpha^{k+1} - \alpha^T}{1 - \alpha} \right)\\
     &= \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right)\sum_{k = 0}^{T-1} \alpha^{2k} \, \exp \left( -\sqrt{\frac{1}{\rho \kappa}} \frac{\alpha^{k+1}}{1 - \alpha} \right)\\
     &\leq \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right)\sum_{k = 0}^{T-1} \alpha^{2k} \left( \frac{2 (1- \alpha) \sqrt{\rho \kappa}}{e\alpha^{k+1}}\right)^2 &\tag{\cref{lem:ineq2}}\\
     &= \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right) \frac{4 \rho \kappa}{e^2 \alpha^2} T(1 - \alpha)^2 \\
     &\leq \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right) \frac{4 \rho \kappa}{e^2 \alpha^2} T \ln( \nicefrac{1}{\alpha})^2\\
     &= \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right) \frac{4 \rho \kappa \ln(\nicefrac{T}{\beta})^2}{e^2 \alpha^2 T}
\end{align*}
Finally, 
\begin{align*}
    \exp\left( \frac{1}{\sqrt{\rho \kappa}}\frac{\alpha^{T}}{1 - \alpha}\right) &= \exp\left( \frac{1}{\alpha \sqrt{\rho \kappa}}\frac{\alpha^{T+1}}{1 - \alpha}\right)\\
    &\leq \exp\left( \frac{2 \beta}{\alpha\sqrt{\rho \kappa} \ln(\nicefrac{T}{\beta})}\right)
\end{align*}
where the inequality comes from the bound in~\cref{ineq:lemma-A-bound} in the proof of~\cref{lemma:A-bound}.
Putting everything together we obtain
\begin{align*}
    \mathbb{E} [f(w_T) - f^*] & \leq 2c_3  \exp\left( - \frac{T}{\sqrt{\kappa \rho}} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) [f(w_0) - f^*]  + \frac{8\sigma^2 c_4 \kappa \ln(\nicefrac{T}{\beta})^2}{\rho L e^2 \alpha^2 T}
\end{align*}
where $c_4 = \exp\left( \frac{2 \beta}{\alpha\sqrt{\rho \kappa} \ln(\nicefrac{T}{\beta})}\right)$.
\end{proof}

\subsection{Lemmas for acceleration proofs}
\label{app:acceleration-lemmas}
\begin{thmbox}
\begin{lemmanew}
\label{lemma:A-bound}
\begin{align*}
A := \sum_{t=1}^T \alpha^t & \geq \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}     
\end{align*}
\end{lemmanew}
\end{thmbox}
\begin{proof}
\begin{align*}
    \sum_{t=1}^T \alpha^t = \frac{\alpha - \alpha^{T+1}}{ 1- \alpha} = \frac{\alpha}{1 - \alpha} - \frac{\alpha^{T+1}}{1 - \alpha}
\end{align*}
We have
\begin{align}
    \label{ineq:lemma-A-bound}
    \frac{\alpha^{T+1}}{1 - \alpha} &= \frac{\alpha \beta}{T(1 - \alpha)} = \frac{\beta}{T} \cdot \frac{1}{\nicefrac{1}{\alpha} - 1} \leq \frac{\beta}{T} \cdot \frac{2}{\ln(\nicefrac{1}{\alpha})} = \frac{\beta}{T} \cdot \frac{2}{\frac{1}{T}\ln(\nicefrac{T}{\beta})} = \frac{2\beta}{\ln(\nicefrac{T}{\beta})}
    \end{align}
where in the inequality we used Lemma \ref{lem:ineq1} and the fact that $\nicefrac{1}{\alpha} > 1$. Plugging back into $A$ we get, 
\begin{align*}
    A &\geq \frac{\alpha}{1- \alpha} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\\
    &\geq \frac{\alpha }{\ln(\nicefrac{1}{\alpha})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \tag{$1-x \leq \ln(\frac{1}{x})$}\\
    &= \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}
\end{align*}
\end{proof}

\begin{thmbox}
\begin{lemmanew}
For $\alpha = \left( \frac{\beta}{T}\right)^{1/T}$ and any $\kappa > 0$,
\begin{align*}
 \sum_{k=1}^T \alpha^{2k} \exp \left(-\frac{1}{\kappa} \sum_{i=k+1}^T \alpha^i \right) & \leq \frac{4 \kappa^2 c_2 (\ln(\nicefrac{T}{\beta}))^2}{e^2 \alpha^2 T} 
\end{align*}
where $c_2= \exp\left( \frac{1}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta}}\right)$
\label{lemma:B-bound}
\end{lemmanew}
\end{thmbox}
\begin{proof}
First observe that, 
\begin{align*}
\sum_{i=t+1}^T \alpha^i = \frac{\alpha^{t+1} - \alpha^{T+1}}{1 - \alpha} 
\end{align*}
We have
\begin{align*}
    \frac{\alpha^{T+1}}{1 - \alpha} &= \frac{\alpha \beta}{T(1 - \alpha)} = \frac{\beta}{T} \cdot \frac{1}{\nicefrac{1}{\alpha} - 1} \leq \frac{\beta}{T} \cdot \frac{2}{\ln(\nicefrac{1}{\alpha})} = \frac{\beta}{T} \cdot \frac{2}{\frac{1}{T}\ln(\nicefrac{T}{\beta})} = \frac{2\beta}{\ln(\nicefrac{T}{\beta})}
    \end{align*}
where in the inequality we used~\ref{lem:ineq1} and the fact that $\nicefrac{1}{\alpha} > 1$. These relations imply that, 
\begin{align*}
\sum_{i=t+1}^T \alpha^i \geq \frac{\alpha^{t+1}}{1 - \alpha} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \\
\implies 
\exp\left( - \frac{1}{\kappa} \sum_{i=t+1}^T \alpha^i \right) \leq \exp\left( -\frac{1}{\kappa} \frac{\alpha^{k+1}}{1- \alpha} + \frac{1}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right) = c_2 \exp\left(-\frac{1}{\kappa} \frac{\alpha^{k+1}}{1- \alpha} \right) 
\end{align*}
We then have
\begin{align*}
\sum_{k=1}^T \alpha^{2k} \exp\left( - \frac{1}{\kappa} \sum_{i=t+1}^T \alpha^i \right) & \leq c_2 \sum_{k=1}^T \alpha^{2k} \exp\left(-\frac{1}{\kappa} \frac{\alpha^{k+1}}{1- \alpha} \right) \\
& \leq c_2 \sum_{k=1}^T \alpha^{2k} \left( \frac{2 (1-\alpha) \kappa}{e \alpha^{k+1}} \right)^2 & \tag{Lemma \ref{lem:ineq2}} \\
& = \frac{4 \kappa^2 c_2}{e^2 \alpha^2} \, T (1 - \alpha)^2 \\
& \leq \frac{4 \kappa^2 c_2}{e^2 \alpha^2} \, T (\ln(1/\alpha))^2 \\
& = \frac{4 \kappa^2 c_2 (\ln(\nicefrac{T}{\beta}))^2}{e^2 \alpha^2 T}
\end{align*}
\end{proof}


\section{Lower-bound proofs for~\cref{sec:adaptivity}}
\label{app:lb-proofs}

\subsection{Proof of~\cref{thm:lb-correlated}}
\label{app:lb-correlated-proof}
\myquote{\begin{thmbox}
\restatescukclb*
\end{thmbox} 
}
\begin{proof}
For SLS with a general $c \geq \nicefrac{1}{2}$ on quadratics, we know that $\gamma_{k} = \frac{2(1 - c)}{L_{i_k}}$ (see~\cref{lem:sls-bounds} for a formal proof). Recall that we consider two one-dimensional quadratics $f_i(w) = \frac{1}{2} (w x_i - y_i)^2$ for $i \in \{1,2\}$ such that $x_1 = 1$, $y_1 = 1$, $x_2 = 2$, $y_2 = -\frac{1}{2}$. Specifically, 
\begin{align*}
    f_1(w) &= \frac{1}{2}(w - 1)^2 \Rightarrow L_1 = 1\\
    f_2(w) &= \frac{1}{2}(2w + \frac{1}{2})^2  \Rightarrow L_2 = 4\\
    f(w) &= \frac{1}{4}(w - 1)^2 + \frac{1}{4}(2w + \frac{1}{2})^2 = \frac{5}{4} w^2  + \frac{1}{4} + \frac{1}{16} \Rightarrow w^* = 0
\end{align*}
If $i_k = 1$,
\begin{align*}
    w_{k+1} = w_k - \alpha_k2(1 - c)(w_k - 1) = 2(1 - c)\alpha_k + (1-2( 1- c)\alpha_k)w_k
\end{align*}
If $i_k = 2$,
\begin{align*}
    w_{k+1} = w_k - 2(1 - c)\alpha_k \frac{2}{4}(2w_k + \frac{1}{2}) = (1 - 2(1 - c)\alpha_k)w_k - \frac{1}{4} 2(1-c)\alpha_k
\end{align*}
Then
\begin{align*}
    \mathbb{E} w_{k+1} = (1- 2(1 - c)\alpha_k) w_k + \frac{1}{2} 2(1-c)\alpha_k - \frac{1}{8} 2(1- c)\alpha_k = (1- 2(1-c)\alpha_k) w_k + \frac{3}{8}2(1-c) \alpha_k
\end{align*}
and
\begin{align*}
    \mathbb{E} w_T = \mathbb{E} (w_T - w^*) = (w_1 - w^*) \prod_{k=1}^T (1 - 2(1-c)\alpha_k) + \frac{3}{8} \sum_{k=1}^T 2(1-c)\alpha_k \prod_{i=k+1}^T (1 - 2(1-c)\alpha_i)
\end{align*}
Using~\cref{lem:sum-prod-eq} and the fact that $2(1-c)\alpha_k \leq 1$ for all $k$, we have that if $w_1 - w^* = w_1 > 0$,
\begin{align*}
    \mathbb{E} (w_T - w^*) \geq \min\left( w_1, \frac{3}{8}\right) 
\end{align*}
\end{proof}

\clearpage
\subsection{Proof of~\cref{thm:lb-decorrelated}}
\label{app:lb-decorrelated-proof}
\myquote{\begin{thmbox}
\restatescukdclb*
\end{thmbox} 
}
\begin{proof}
One has $w^* = \frac{y}{x}$ and $L = x^2$. Therefore
\begin{align*}
    w_{k+1} - w^* &= w_k - w^* - \alpha_k \eta_k x \left( xw_k -y  \right)\\
    &= w_k - w^* - \alpha_k \frac{\nu}{L} L w_k + \alpha_k \frac{\nu}{L} xy\\
    &= w_k - w^* - \alpha_k \nu w_k + \alpha_k \rho w^* = (1 - \nu \alpha_k) (w_k - w^*)
\end{align*}
Iterating gives the first part of the result. Now, for $k \leq k'$, we have
\begin{align*}
    1 - \nu \alpha^k &\leq 1 - \nu \alpha^{k'} \leq 1 - \nu \alpha^{\frac{T}{\ln (T/\beta)} (\ln \nu - \ln 3)} = 1 - \nu \left(\frac{\beta}{T}\right)^{\frac{1}{\ln (T/\beta)} (\ln \nu - \ln 3)} = 1 - \nu \left( \frac{3}{\nu}\right) = -2
\end{align*}
and thus
\begin{align*}
    \abs{w_{k' + 1} - w^*} = \abs{w_1 - w^*} \prod_{i=1}^{k'} \abs{ 1- \nu \alpha_k} \geq \abs{w_1 - w^*} 2^{k'}
\end{align*}
\end{proof}

\subsection{Lemmas for convex setting}
\label{app:lemmas-convex}

\begin{thmbox}
\begin{lemmanew}
The polynomial stepsize defined as $\alpha_k = (\nicefrac{1}{k})^{\delta}$ for some $0 \leq \delta \leq 1$ cannot satisfy $\sum_{k=1}^T \alpha_k \geq C_1 T$ and $\sum_{k=1}^T \alpha_k^2 \leq C_2 \sqrt{T}$ for positive constants $C_1 $ and $C_2$.
\label{lemma:polynomial-convex-bad}
\end{lemmanew}
\end{thmbox}
\begin{proof}
If $\delta = 0$, $\alpha_k = 1$ for all $k$, and then $\sum_{k=1}^T \alpha_k^2 = T$. If $\delta = 1$, then $\sum_{k=1}^T \alpha_k = \Theta(\ln T)$.\\
If $0 < \delta < 1$, basic calculus shows that
\begin{align*}
    \int_{1}^{T+1} \frac{1}{x^\delta} \leq \sum_{k=1}^T \frac{1}{k^\delta} \leq 1 + \int_{1}^T \frac{1}{x^\delta}
\end{align*}
and thus
\begin{align*}
    \frac{1}{1 - \delta} \left( (T+1)^{1 - \delta} - 1\right) \leq \sum_{k=1}^T \frac{1}{k^\delta} \leq 1 + \frac{1}{1 - \delta} \left( T^{1 - \delta} - 1 \right)
\end{align*}
which shows that $\sum_{k=1}^T \alpha_k = \Theta( T^{1- \delta})$, and thus we cannot have $\sum_{k=1}^T \alpha_k \geq C_1 T$ for all $T$.
\end{proof}

\begin{thmbox}
\begin{lemmanew}
The exponential stepsize defined as $\alpha_k = \alpha^k$ for some $\alpha < 1$ cannot satisfy $\sum_{k=1}^T \alpha_k \geq C_1 T$ and $\sum_{k=1}^T \alpha_k^2 \leq C_2 \sqrt{T}$ for positive constants $C_1 $ and $C_2$.
\label{lemma:exponential-convex-bad}
\end{lemmanew}
\end{thmbox}
\begin{proof}
Suppose by contradiction that the exponential stepsize satisfies the two conditions. Then
\begin{align*}
    C_2 \sqrt{T} \geq \sum_{k=1}^T \alpha_k^2 &= \sum_{k=1}^T \alpha^{2k} = \sum_{k=1}^{2T} \alpha^k - \sum_{k=1}^T \alpha^{2k - 1} = \sum_{k=1}^{2T} \alpha^k - \frac{1}{\alpha} \sum_{k=1}^T \alpha^{2k}
\end{align*}
By assumption, $\sum_{k=1}^{2T} \alpha^k \geq C_1 2T$ and $\sum_{k=1}^T \alpha^{2k} \leq C_2 \sqrt{T}$. Therefore 
\begin{align*}
    \sum_{k=1}^{2T} \alpha^k - \frac{1}{\alpha} \sum_{k=1}^T \alpha^{2k} \geq 2C_1 T - \frac{1}{\alpha} C_2 \sqrt{T}
\end{align*}
But then we obtain
\begin{align*}
    C_2 \sqrt{T} \geq 2C_1 T - \frac{1}{\alpha}C_2 \sqrt{T}
\end{align*}
which is a contradiction by taking $T$ to infinity.
\end{proof}




\section{Helper Lemmas}
\label{app:helper-lemmas}

\begin{thmbox}
\begin{lemmanew}
\label{lem:ineq1}
For all $x>1$,
\begin{align*}
    \frac{1}{x - 1} \leq \frac{2}{\ln(x)}
\end{align*}
\end{lemmanew}
\end{thmbox}
\begin{proof}
For $x > 1$, we have
\begin{align*}
    \frac{1}{x - 1} \leq \frac{2}{\ln(x)} &\iff \ln(x) < 2x - 2
\end{align*}
Define $f(x) = 2x - 2 - \ln(x)$. We have $f'(x) = 2 - \frac{1}{x}$. Thus for $x \geq 1$, we have $f'(x) > 0$ so $f$ is increasing on $[1, \infty)$. Moreover we have $f(1) = 2 - 2 - \ln(1) = 0$ which shows that $f(x) \geq 0$ for all $x > 1$ and ends the proof.
\end{proof}

\begin{thmbox}
\begin{lemmanew}
\label{lem:ineq2}
For all $x, \gamma >0$,
\begin{align*}
    \exp(-x) \leq \left( \frac{\gamma}{ex }\right)^\gamma
\end{align*}
\end{lemmanew}
\end{thmbox}
\begin{proof}
Let $x > 0$. Define $f(\gamma) = \left( \frac{\gamma}{ex }\right)^\gamma - \exp(-x)$. We have
\begin{align*}
    f(\gamma) = \exp\left( \gamma\ln(\gamma) - \gamma\ln(ex)\right) - \exp(-x)
\end{align*}
and
\begin{align*}
    f'(\gamma) = \left( \gamma \cdot \frac{1}{\gamma} + \ln(\gamma) - \ln(ex)\right) \exp\left( \gamma\ln(\gamma) - \gamma\ln(ex)\right)
\end{align*}
Thus
\begin{align*}
    f'(\gamma) \geq 0 &\iff 1 + \ln(\gamma) - \ln(ex) \geq 0 \iff \gamma \geq \exp\left( \ln(ex) - 1\right) = x
\end{align*}
So $f$ is decreasing on $(0, x]$ and increasing on $[x, \infty)$. Moreover,
\begin{align*}
    f(x) = \left( \frac{x}{ex}\right)^x - \exp(-x) = \left(\frac{1}{e}\right)^x - \exp(-x) = 0
\end{align*}
and thus $f(\gamma) \geq 0$ for all $\gamma > 0$ which proves the lemma.
\end{proof}

\begin{thmbox}
\begin{lemmanew}
\label{lem:sum-prod-eq}
For any sequence $\alpha_k$
\begin{align*}
    \prod_{k=1}^T (1 - \alpha_k) + \sum_{k=1}^T \alpha_k \prod_{i=k+1}^T (1 - \alpha_i)  = 1 
\end{align*}
\end{lemmanew}
\end{thmbox}
\begin{proof}
We show this by induction on $T$. For $T = 1$,
\begin{align*}
    (1 - \alpha_1) + \alpha_1 = 1
\end{align*}
Induction step:
\begin{align*}
    \prod_{k=1}^{T+1}(1 - \alpha_k) + \sum_{k=1}^{T+1} \alpha_k \prod_{i=k+1}^{T+1} (1 - \alpha_i)  &= (1- \alpha_{T+1}) \prod_{k=1}^T (1- \alpha_k) + \left( \alpha_{T+1} + \sum_{k=1}^T\alpha_k \prod_{i=k+1}^{T+1} (1 - \alpha_i)\right) \\
    &= (1- \alpha_{T+1}) \prod_{k=1}^T (1- \alpha_k) + \left( \alpha_{T+1} + (1 - \alpha_{T+1})\sum_{k=1}^T\alpha_k \prod_{i=k+1}^{T} (1 - \alpha_i)\right)\\
    &= ( 1- \alpha_{T+1}) \left(\underbrace{ \prod_{k=1}^T (1- \alpha_k) + \sum_{k=1}^T\alpha_k \prod_{i=k+1}^{T} (1 - \alpha_i)}_{= 1}\right) + \alpha_{T+1} \tag{Induction hypothesis}\\
    &= (1 - \alpha_{T+1}) + \alpha_{T+1} = 1
\end{align*}
\end{proof}
\section{Upper-bound Proofs for~\cref{sec:adaptivity}}
\label{app:ub-proofs}

\subsection{Proof of~\cref{thm:sc-known}}
\label{app:sc-known-proof}
\myquote{\begin{thmbox}
\restatesck*
\end{thmbox} 
}
\begin{proof}
\begin{align*}
\normsq{w_{k+1}-w^{*}} &= \normsq{w_{k}-\eta_{k} \gradk{w_{k}} -w^{*}} \\
&= \normsq{w_{k}-w^{*}} - 2\eta_{k}\inner{\gradk{w_{k}}}{w_{k}-w^{*}} +\eta_{k}^2\normsq{\gradk{w_{k}}}\\
& = \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + \gamma_{k}^2 \alpha_{k}^2 \normsq{\gradk{w_{k}}} \\
\normsq{w_{k+1}-w^{*}} & \leq \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + \gamma_{k}^2 \alpha_{k}^2 \, 2 L [f_{ik}(w_{k}) - f_{ik}^*] & \tag{Smoothness} \\
& = \normsq{w_{k}-w^{*}} - \frac{2}{L} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + \frac{2}{L} \alpha_{k}^2 \, [f_{ik}(w_{k}) - f_{ik}(w^{*})] + \frac{2}{L} \alpha_{k}^2 \, [f_{ik}(w^{*}) - f_{ik}^*] & \tag{Since $\gamma_{k} = 1/L$.}\\
\intertext{Taking expectation w.r.t $i_k$,}
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \mathbb{E} \normsq{w_{k}-w^{*}} - \frac{2}{L} \alpha_{k} \inner{\grad{w_{k}}}{w_{k}-w^{*}} + \frac{2}{L} \alpha_{k}^2 \, [f(w_{k}) - f(w^{*})] + \frac{2}{L} \alpha_{k}^2 \sigma^2 \\
& \leq \mathbb{E} \normsq{w_{k}-w^{*}} - \frac{2}{L} \alpha_{k} \inner{\grad{w_{k}}}{w_{k}-w^{*}} + \frac{2}{L} \alpha_{k} \, [f(w_{k}) - f(w^{*})] + \frac{2}{L} \alpha_{k}^2 \sigma^2 & \tag{Since $\alpha_{k} \leq 1$}\\
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \left(1 - \frac{\mu \alpha_{k}}{L} \right) \mathbb{E} \normsq{w_{k}-w^{*}} + \frac{2}{L} \alpha_{k}^2 \sigma^2 & \tag{By $\mu$-strong convexity of $f$} \\
\intertext{Unrolling the recursion starting from $w_1$ and using the exponential step-sizes,}
\mathbb{E} \normsq{w_{T+1} - w^{*}} & \leq \normsq{w_{1} - w^{*}} \prod_{k = 1}^{T} \left(1 - \frac{\mu \alpha^k}{L} \right)  + \frac{2 \sigma^2}{L}  \sum_{k = 1}^{T} \left[\prod_{i = k+1}^{T} \alpha^{2k} \left(1 - \frac{\mu \alpha^i}{L} \right)  \right] \\
\intertext{Writing $\Delta_k = \mathbb{E} \normsq{w_{k} - w^{*}}$}
\Delta_{T+1} & \leq \Delta_1 \exp\bigg( -\frac{\mu}{L}
    \underbrace{\sum_{k=1}^T \alpha^k}_{:= A} \bigg) + \frac{2 \sigma^2}{L} \underbrace{\sum_{k=1}^T \alpha^{2k} \exp\bigg( -\frac{\mu}{L} \sum_{i=k+1}^T \alpha^i}_{:=B_t} \bigg) 
\end{align*}
Using~\cref{lemma:A-bound} to lower-bound $A$, we obtain $A \geq \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}$. The first term in the above expression can then be bounded as, 
\begin{align*}
    \Delta_1 \exp\left( -\frac{\mu}{L} A\right) &= \Delta_1 \, c_2  \exp\left( - \frac{T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right),
\end{align*}
where $\kappa = \frac{L}{\mu}$ and $c_2 = \exp\left( \frac{1}{\kappa} \, \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$.
Using~\cref{lemma:B-bound} to upper-bound $B_t$, we obtain $B_t \leq \frac{4 \kappa^2 c_2 (\ln(\nicefrac{T}{\beta}))^2}{e^2 \alpha^2 T}$, thus bounding the second term. Putting everything together, 
\begin{align*}
\Delta_{T+1} & \leq \Delta_1 \, c_2  \exp\left( - \frac{T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) + \frac{8 \sigma^2 c_2 \kappa^2}{L e^2} \frac{(\ln(\nicefrac{T}{\beta}))^2}{\alpha^2 T}  
\end{align*}
\end{proof}

\subsection{Proof of~\cref{thm:sc-unknown-correlated}}
\label{app:sc-unknown-correlated-proof}
\myquote{\begin{thmbox}
\restatescukc*
\end{thmbox} 
}
\begin{proof} 
\begin{align*}
\normsq{w_{k+1} - w^{*}} & \leq \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + \gamma_{k} \alpha_{k}^2 \left[\frac{f_{ik}(w_{k}) - f_{ik}^*}{c}\right] & \tag{By~\cref{lem:sls-bounds}} \\
\intertext{Setting $c = 1/2$,}
& = \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + 2 \gamma_{k} \alpha_{k}^2 \left[f_{ik}(w_{k}) - f_{ik}^*\right] \\
& = \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + 2 \gamma_{k} \alpha_{k}^2 \left[f_{ik}(w_{k}) - f_{ik}(w^{*}) \right] + 2 \gamma_{k} \alpha_{k}^2 \left[f_{ik}(w^{*}) - f_{ik}^*\right] \\
\intertext{Adding, subtracting $2 \gamma_{k} \alpha_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})]$,}
& = \normsq{w_{k}-w^{*}} + 2 \gamma_{k} \alpha_{k} \left[-\inner{\gradk{w_{k}}}{w_{k}-w^{*}} + [f_{ik}(w_{k}) - f_{ik}(w^{*})] \right] - 2 \gamma_{k} \alpha_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})] \\ & + 2 \gamma_{k} \alpha_{k}^2 \left[f_{ik}(w_{k}) - f_{ik}(w^{*}) \right] + 2 \gamma_{k} \alpha_{k}^2 \left[f_{ik}(w^{*}) - f_{ik}^*\right] \\
& \leq \normsq{w_{k}-w^{*}} + 2 \gamma_{\min} \alpha_{k} \left[-\inner{\gradk{w_{k}}}{w_{k}-w^{*}} + [f_{ik}(w_{k}) - f_{ik}(w^{*})] \right] - 2 \gamma_{k} (\alpha_{k} - \alpha_{k}^2) [f_{ik}(w_{k}) - f_{ik}(w^{*})] \\ & + 2 \gamma_{\max} \alpha_{k}^2 \left[f_{ik}(w^{*}) - f_{ik}^*\right] \\
\intertext{where we used convexity of $f_{ik}$ to ensure that $-\inner{\gradk{w_{k}}}{w_{k}-w^{*}} + [f_{ik}(w_{k}) - f_{ik}(w^{*})] \leq 0$. Taking expectation,}
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \normsq{w_{k}-w^{*}} + 2 \gamma_{\min} \alpha_{k} \left[-\inner{\grad{w_{k}}}{w_{k}-w^{*}} + [f(w_{k}) - f(w^{*})] \right] -  (\alpha_{k} - \alpha_{k}^2) \mathbb{E} \left[2 \gamma_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})]\right] \\ & +  2 \gamma_{\max} \alpha_{k}^2 \sigma^2 \\
\mathbb{E} \normsq{w_{k} - w^{*}} & \leq \left(1 - \alpha_{k} \gamma_{\min} \mu \right) \normsq{w_{k}-w^{*}} -  (\alpha_{k} - \alpha_{k}^2) \mathbb{E} \left[2 \gamma_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})]\right] + 2 \gamma_{\max} \alpha_{k}^2 \sigma^2 \\
\end{align*}
Since $\alpha_{k} \leq 1$, and $\alpha_{k} - \alpha_{k}^2 \geq 0$, let us analyze $-\mathbb{E} [[\gamma_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})]]$. 
\begin{align*}
- \mathbb{E} [[\gamma_{k} [f_{ik}(w_{k}) - f_{ik}(w^{*})]] & = - \mathbb{E} [[\gamma_{k} [f_{ik}(w_{k}) - f_{ik}^*]] - \mathbb{E} [[\gamma_{k} [f_{ik}^* - f_{ik}(w^{*})]] \\
& \leq - \mathbb{E} [[\gamma_{\min} [f_{ik}(w_{k}) - f_{ik}^*]] - \mathbb{E} [[\gamma_{\max} [f_{ik}^* - f_{ik}(w^{*})]] \tag{$\gamma_{k} \leq \gamma_{\max}$}\\
& = - \mathbb{E} [[\gamma_{\min} [f_{ik}(w_{k}) - f_{ik}^*]] + \gamma_{\max} \sigma^2 \\
& = - \mathbb{E} [[\gamma_{\min} [f_{ik}(w_{k}) - f_{ik}(w^{*})]] - \mathbb{E} [[\gamma_{\min} [f_{ik}(w^{*}) - f_{ik}^*]] + \gamma_{\max} \sigma^2 \\
& = -\gamma_{\min} [f(w_{k}) - f(w^{*})] - \gamma_{\min} \sigma^2 + \gamma_{\max} \sigma^2 \\
& \leq (\gamma_{\max} - \gamma_{\min}) \sigma^2
\end{align*}
Putting this relation back,
\begin{align*}
\mathbb{E} \normsq{w_{k} - w^{*}} & \leq \left(1 - \alpha_{k} \gamma_{\min} \mu \right) \normsq{w_{k}-w^{*}} 
+ 2 (\alpha_{k} - \alpha_{k}^2) \, (\gamma_{\max} - \gamma_{\min}) \sigma^2
+ 2 \gamma_{\max} \alpha_{k}^2 \sigma^2  \\
& \leq \left(1 - \alpha_{k} \gamma_{\min} \mu \right) \normsq{w_{k}-w^{*}} + 2 \alpha_{k} \, (\gamma_{\max} - \gamma_{\min}) \sigma^2 + 2 \gamma_{\max} \alpha_{k}^2 \sigma^2.  
\end{align*}
Setting $\kappa' = \max\{\frac{L}{\mu}, \frac{1}{\mu \gamma_{\max}}\}$ we get that $1 - \alpha_{k} \gamma_{\min} \mu \leq 1 - \frac{1}{\kappa'}$. 
Writing $\Delta_k = \mathbb{E} \normsq{w_{k} - w^{*}}$ and unrolling the recursion we get
\begin{align*}
    \Delta_{T+1} &\leq \left( \prod_{k=1}^T \left( 1 - \frac{1}{\kappa'} \alpha^k \right)  \right) \Delta_1 + 2 \gamma_{\max} \sigma^2 \sum_{k=1}^T \alpha^{2k} \prod_{i=t+1}^T \left( 1 - \frac{1}{\kappa'} \alpha^i \right) + 2 \, \sigma^2  \sum_{k=1}^T \alpha^{k} (\gamma_{\max} - \gamma_{\min}) \prod_{i=k+1}^T \left( 1 - \frac{1}{\kappa'} \alpha^i \right)\\
    &\leq \Delta_1 \exp\bigg( -\frac{1}{\kappa'}
    \underbrace{\sum_{k=1}^T \alpha^k}_{:= A} \bigg) + 2 \gamma_{\max}\sigma^2 \underbrace{\sum_{k=1}^T \alpha^{2k} \exp\bigg( -\frac{1}{\kappa'} 
    \sum_{i=k+1}^T \alpha^i}_{:=B_t} \bigg) \\ & + 2 \, \sigma^2 \, (\gamma_{\max} - \gamma_{\min}) \underbrace{\sum_{k=1}^T \alpha^{k} \exp\bigg( -\frac{1}{\kappa'} 
    \sum_{i=k+1}^T \alpha^i}_{:=C_t} \bigg) 
\end{align*}
Using~\cref{lemma:A-bound} to lower-bound $A$, we obtain $A \geq \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}$. The first term in the above expression can then be bounded as, 
\begin{align*}
    \Delta_1 \exp\left( -\frac{1}{\kappa'} A\right) &\leq \Delta_1 \, c_1  \exp\left( - \frac{T}{\kappa'} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right),
\end{align*}
where $c_1 = \exp\left( \frac{1}{\kappa'} \, \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$.
Using~\cref{lemma:B-bound} to upper-bound $B_t$, we obtain $B_t \leq \frac{4 (\kappa')^2 c_1 (\ln(\nicefrac{T}{\beta}))^2}{e^2 \alpha^2 T}$, thus bounding the second term. Using~\cref{lemma:C-bound} to upper-bound $C_t$, we obtain $C_t \leq c_1 \frac{\kappa' \ln (T / \beta)}{e \alpha}$, thus bounding the third term. Putting everything together, 
\begin{align*}
\Delta_{T+1} &\leq \Delta_1 \, c_1 \exp\left( - \frac{T}{\kappa'} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) + \frac{8 \sigma^2 c_1 (\kappa')^2 \gamma_{\max}}{e^2} \frac{(\ln(\nicefrac{T}{\beta}))^2}{\alpha^2 T} + \frac{2 c_1 \sigma^2 \kappa' \ln (T / \beta)}{e \alpha} \, \left(\gamma_{\max} - \frac{1}{L}\right)     
\end{align*}
\end{proof}

\clearpage
\subsection{Proof of~\cref{thm:sc-unknown-decorrelated}}
\label{app:sc-unknown-decorrelated-proof}
\myquote{\begin{thmbox}
\restatescukdc*
\end{thmbox} 
}
\begin{proof}
Following the steps from the proof of~\cref{thm:sc-known},
\begin{align*}
\normsq{w_{k+1} - w^{*}} & \leq \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + 2L \gamma_{k}^2 \alpha_{k}^2 \, [f_{ik}(w_{k}) - f_{ik}(w^{*})] + 2L \gamma_{k}^2 \alpha_{k}^2 \, [f_{ik}(w^{*}) - f_{ik}^*] \\
\intertext{Taking expectation wrt $i_k$, and since both $\gamma_{k}$ and $\alpha_{k}$ are independent of $i_k$,}
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\grad{w_{k}}}{w_{k}-w^{*}} + 2L \gamma_{k}^2 \alpha_{k}^2 \, [f(w_{k}) - f^*] + 2L \gamma_{k}^2 \alpha_{k}^2 \, \sigma^2 \\
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \left(1 - \mu \gamma_{k} \alpha_{k} \right) \normsq{w_{k}-w^{*}} +  2L \gamma_{k}^2 \alpha_{k}^2 \, \sigma^2 + [f(w_{k}) - f^*] \, (2L \gamma_{k}^2 \alpha_{k}^2 - 2 \gamma_{k} \alpha_{k}) & \tag{By strong convexity} \\
\end{align*}
Since $\gamma_{k} = \frac{\nu}{L}$ for some $\nu \geq 1$, we require $\alpha_{k} \leq \frac{1}{\nu}$ for the last term to be negative. By definition of $\alpha_{k}$, this will happen after $k \geq k_0 := T \frac{\ln(\nu)}{\ln(\nicefrac{T}{\beta})}$ iterations. However, until $k_0$ iterations, we observe that $(2L \gamma_{k}^2 \alpha_{k}^2 - 2 \gamma_{k} \alpha_{k}) \leq \frac{2 \nu \, (\nu - 1)}{L} \alpha_{k}^2$, meaning that for $k < k_0$, 
\begin{align*}
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \left(1 - \mu \gamma_{k} \alpha_{k} \right) \normsq{w_{k}-w^{*}} +  2L \gamma_{k}^2 \alpha_{k}^2 \, \sigma^2 + \max_{j \in [k_0]} \{ f(w_j) - f^* \} \, \frac{2 \nu \, (\nu - 1)}{L} \alpha_{k}^2  
\end{align*}
Writing $\Delta_k = \mathbb{E}\normsq{w_{k} - w^{*}}$, and unrolling the recursion for the first $k_0$ iterations we get
\begin{align*}
    \Delta_{k_0} &\leq \Delta_1 \prod_{k=1}^{k_0 - 1} (1 -  \frac{\mu \nu}{L} \alpha_k) + \left(\underbrace{ 2 L \frac{\nu^2}{L^2} \sigma^2 + \max_{j \in [k_0]} \{ f(w_j) - f^* \}  \frac{2 \nu (\nu - 1)}{L}}_{:= c_5} \right) \sum_{k=1}^{k_0 - 1} \alpha_k^2 \prod_{i= k+1}^{k_0 - 1} ( 1 - \frac{\mu \nu}{L} \alpha_i)
\end{align*}
Bounding the first term similar to~\cref{lemma:A-bound}, 
\begin{align*}
    \prod_{k=1}^{k_0 - 1} (1 -  \frac{\mu \nu}{L} \alpha_k) &\leq \exp \left( - \frac{\mu \nu}{L} \frac{\alpha - \alpha^{k_0}}{ 1- \alpha}\right)
\end{align*}
Bounding the second term similar to~\cref{lemma:B-bound},
\begin{align*}
    \sum_{k=1}^{k_0 - 1} \alpha_k^2 \prod_{i= k+1}^{k_0 - 1} ( 1 - \frac{\mu \nu}{L} \alpha_i) &\leq \sum_{k=1}^{k_0 - 1} \alpha_k^2 \exp\left( - \frac{\mu \nu}{L} \sum_{i = k+1}^{k_0 - 1} \alpha^i \right)\\
    &= \sum_{k=1}^{k_0 - 1} \alpha_k^2 \exp\left( - \frac{ \nu}{\kappa} \frac{\alpha^{k+1} - \alpha^{k_0}}{ 1 - \alpha} \right)\\
    &= \exp\left(\frac{\nu \alpha^{k_0}}{\kappa ( 1- \alpha)}\right) \sum_{k=1}^{k_0 - 1} \alpha_k^2 \exp\left( -\frac{\nu\alpha^{k+1}}{\kappa (1- \alpha)}\right)\\
    &\leq \exp\left(\frac{\nu \alpha^{k_0}}{\kappa ( 1- \alpha)}\right) \sum_{k=1}^{k_0 - 1} \alpha_k^2 \left( \frac{2(1- \alpha)\kappa}{\nu e\alpha^{k+1}}\right)^2\\
    &\leq \exp\left(\frac{\nu \alpha^{k_0}}{\kappa ( 1- \alpha)}\right) \frac{4(1-\alpha)^2 \kappa^2}{\nu^2e^2\alpha^2 } k_0\\
    &\leq \exp\left(\frac{\nu \alpha^{k_0}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{k_0 \ln(T/\beta)^2}{T^2}
\end{align*}
Putting everything together, we obtain, 
\begin{align*}
\Delta_{k_0} &\leq \Delta_1 \exp \left( - \frac{\mu \nu}{L} \frac{\alpha - \alpha^{k_0}}{ 1- \alpha}\right) + c_5 \exp\left(\frac{\nu \alpha^{k_0}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{k_0 \ln(T/\beta)^2}{T^2}   
\end{align*}

Now let us consider the regime $k \geq k_0$ where $\alpha_{k} \leq \frac{1}{\nu}$, so that we have
\begin{align*}
\mathbb{E} \normsq{w_{k+1} - w^{*}} & \leq \left(1 - \mu \gamma_{k} \alpha_{k} \right) \normsq{w_{k}-w^{*}} +  \frac{2 \nu^2 \sigma^2}{L} \alpha_{k}^2 \\
\intertext{Writing $\Delta_k = \mathbb{E}\normsq{w_{k} - w^{*}}$, and unrolling the recursion from $k = k_0$ to $T$,}
\Delta_{T+1} &\leq \Delta_{k_0} \prod_{k=k_0}^T (1 - \frac{\mu \nu}{L} \alpha_k) + \frac{2 \nu^2 \sigma^2}{L} \sum_{k=k_0}^{T} \alpha_k^2 \prod_{i=k+1}^T ( 1- \frac{\mu \nu}{L} \alpha_i)
\end{align*}
Bounding the first term similar to~\cref{lemma:A-bound}, 
\begin{align*}
    \prod_{k=k_0}^T (1 - \frac{\mu \nu}{L} \alpha_k) &\leq \exp\left( - \frac{\mu \nu}{L} \sum_{k= k_0}^T \alpha_k\right) = \exp \left( \frac{-\mu \nu}{L} \frac{\alpha^{k_0} - \alpha^{T + 1}}{1 - \alpha}\right)
\end{align*}
Bounding the second term similar to~\cref{lemma:B-bound},
\begin{align*}
\sum_{k=k_0}^{T} \alpha_k^2 \prod_{i= k+1}^{T} ( 1 - \frac{\mu \nu}{L} \alpha_i) &\leq \sum_{k=k_0}^{T} \alpha_k^2 \exp\left( - \frac{\mu \nu}{L} \sum_{i = k+1}^{T} \alpha^i \right)\\
&= \sum_{k=k_0}^{T} \alpha_k^2 \exp\left( - \frac{ \nu}{\kappa} \frac{\alpha^{k+1} - \alpha^{T+1}}{ 1 - \alpha} \right)\\
&= \exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \sum_{k=k_0}^{T} \alpha_k^2 \exp\left( -\frac{\nu\alpha^{k+1}}{\kappa (1- \alpha)}\right)\\
&\leq \exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \sum_{k=k_0}^{T} \alpha_k^2 \left( \frac{2(1- \alpha)\kappa}{\nu e\alpha^{k+1}}\right)^2\\
&= \exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \frac{4(1-\alpha)^2 \kappa^2}{\nu^2e^2\alpha^2 } (T - k_0 + 1)\\
&\leq \exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2}  
\end{align*}
Putting everything together, 
\begin{align*}
    \Delta_{T+1} &\leq \Delta_{k_0} \exp \left( \frac{-\mu \nu}{L} \frac{\alpha^{k_0} - \alpha^{T + 1}}{1 - \alpha}\right) + \frac{2 \nu^2 \sigma^2}{L} \exp\left(\frac{\nu \alpha^{T+1}}{ \kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2}  
\end{align*}
Combining the above bounds, we get, 
\begin{align*}
    \Delta_{T+1} \leq &\exp \left( \frac{-\mu \nu}{L} \frac{\alpha^{k_0} - \alpha^{T + 1}}{1 - \alpha}\right) \left( \Delta_1 \exp \left( - \frac{\mu \nu}{L} \frac{\alpha - \alpha^{k_0}}{ 1- \alpha}\right) + c_5 \exp\left(\frac{ \mu \nu \alpha^{k_0}}{L( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{k_0 \ln(T/\beta)^2}{T^2} \right)  \\
    & + \frac{2c^2 \sigma^2}{L}\exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2} \\
    & = \Delta_1 \exp \left( \frac{-\mu \nu}{L} \frac{\alpha - \alpha^{T + 1}}{1 - \alpha} \right) + c_5 \exp \left( \frac{\mu \nu}{L} \frac{\alpha^{T + 1}}{1 - \alpha}\right) \, \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{k_0 \ln(T/\beta)^2}{T^2} \\
    & + \frac{2\nu^2 \sigma^2}{L}\exp\left(\frac{\nu \alpha^{T+1}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2} 
\end{align*}
Using~\cref{lemma:A-bound} to bound the first term
\begin{align*}
    \Delta_{T+1} & \leq \Delta_1 \, c_2  \exp\left( -\frac{\nu \, T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) + c_5 \exp \left( \frac{\mu \nu}{L} \frac{\alpha^{T + 1}}{1 - \alpha}\right) \, \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{k_0 \ln(T/\beta)^2}{T^2} \\
    & + \frac{2\nu^2 \sigma^2}{L}\exp\left(\frac{\nu \alpha^{T}}{\kappa ( 1- \alpha)}\right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2} \\
    \intertext{where $\kappa = \frac{L}{\mu}$ and $c_2 = \exp\left( \frac{1}{\kappa} \, \frac{2\beta}{\ln(\nicefrac{T}{\beta})}\right)$.}
\end{align*}
For bounding the second and third terms, note that $\frac{\alpha^{T+1}}{1 - \alpha} \leq \frac{2\beta}{\ln(\nicefrac{T}{\beta})}$, and $k_0 = T \frac{\ln(\nu)}{\ln(\nicefrac{T}{\beta})}$. Using these relations and the fact that $\alpha \leq 1$, 
\begin{align*}
    \Delta_{T+1} & \leq \Delta_1 \, c_2  \exp\left( - \frac{\nu \, T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) + c_5 \exp \left( \frac{ \nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \, \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{\ln(\nu)\ln(T/\beta)}{T} \\
    & + \frac{2\nu^2 \sigma^2}{L}\exp\left(\frac{\nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{(T - k_0 + 1) \ln(T/\beta)^2}{T^2} 
\end{align*}
Putting in the value of $c_5$ and rearranging, we get
\begin{align*}
\Delta_{T+1} & \leq \Delta_1 \, c_2  \exp\left( - \frac{\nu \, T}{\kappa} \frac{\alpha}{\ln(\nicefrac{T}{\beta})}\right) + \frac{2\nu^2 \sigma^2}{L \, T}\exp\left(\frac{\nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \frac{4 \kappa^2 \ln(T/\beta)^2}{\nu^2e^2\alpha^2}  \\
& + \left[\max_{j \in [k_0]} \{ f(w_j) - f^* \}  \frac{2 \nu (\nu - 1)}{L}\right] \, \exp \left( \frac{\nu}{\kappa} \frac{2\beta}{\ln(\nicefrac{T}{\beta})} \right) \, \frac{4 \kappa^2}{\nu^2e^2\alpha^2 } \frac{\ln(\nu) \ln(T/\beta)}{T} 
\end{align*}
\end{proof}

\clearpage
\subsection{Proof of~\cref{thm:c-known}}
\label{app:c-known-proof}
\myquote{\begin{thmbox}
\restateck*
\end{thmbox} 
}
\begin{proof}
Following the proof of~\cref{thm:sc-known}, 
\begin{align*}
\normsq{w_{k+1}-w^{*}} & \leq \normsq{w_{k}-w^{*}} - 2 \gamma_{k} \alpha_{k} \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + 2L \gamma_{k}^2 \alpha_{k}^2 \, [f_{ik}(w_{k}) - f_{ik}(w^{*})] \\ & + \frac{2}{L} \gamma_{k}^2 \alpha_{k}^2 \, [f_{ik}(w_{k}) - f_{ik}^*] \\
\normsq{w_{k+1}-w^{*}} & \leq \normsq{w_{k}-w^{*}} - \frac{\alpha_{k}}{L}  \inner{\gradk{w_{k}}}{w_{k}-w^{*}} + \frac{\alpha_{k}^2}{2L} \, [f_{ik}(w_{k}) - f_{ik}(w^{*})] + \frac{\alpha_{k}^2}{2L}  \, [f_{ik}(w_{k}) - f_{ik}^*]  & \tag{$\gamma_{k} = \frac{1}{2L}$ for all $k$.} \\
& \leq \normsq{w_{k}-w^{*}} - \frac{ \alpha_{k}}{L} [f_{ik}(w_{k}) - f_{ik}(w^{*})] + \frac{\alpha_{k}^2}{2L} \, [f_{ik}(w_{k}) - f_{ik}(w^{*})] + \frac{\alpha_{k}^2}{2L}  \, [f_{ik}(w_{k}) - f_{ik}^*] & \tag{By convexity} \\
\intertext{Taking expectation,}
\mathbb{E} \normsq{w_{k+1}-w^{*}} & \leq \normsq{w_{k}-w^{*}} - \frac{ \alpha_{k}}{L} [f(w_{k}) - f(w^{*})] + \frac{\alpha_{k}^2}{2L} \, [f(w_{k}) - f(w^{*})] + \frac{\alpha_{k}^2}{2 L}  \sigma^2 \\
& \leq \normsq{w_{k}-w^{*}} - \frac{\alpha_{k}}{2 L} [f(w_{k}) - f(w^{*})] + \frac{\alpha_{k}^2}{2L}  \sigma^2 & \tag{Since $f(w_{k}) - f(w^{*}) \geq 0$ and $\alpha_{k} \leq 1$} \\
\intertext{Rearranging and summing from $k = 1$ to $T$,}
\sum_{k = 1}^{T} \alpha_{k} [f(w_{k}) - f(w^{*})] & \leq 2 L \normsq{w_1 - w^{*}} + \sigma^2 \sum_{k = 1}^{T} \alpha_{k}^2\\
\intertext{By averaging and using Jensen. Denote $\bar{w}_{T+1} = \frac{\sum_{k = 1}^{T} \alpha_{k} w_{k}}{\sum_{k = 1}^{T} \alpha_{k}}$,}
\mathbb{E} [f(\bar{w}_{T+1}) - f(w^{*})] &\leq \frac{2L \, \normsq{w_1 - w^{*}}}{\sum_{k = 1}^{T} \alpha_{k}} + \sigma^2 \frac{\sum_{k = 1}^{T} \alpha_{k}^2}{\sum_{k = 1}^{T} \alpha_{k}} 
\end{align*}
Next, we bound $\sum_{k = 1}^{T} \alpha_{k}$ and $\sum_{k = 1}^{T} \alpha_{k}^2$ for the exponentially-decreasing $\alpha_{k}$ sequence, when $\alpha_{k} = \left[\frac{\beta}{T}\right]^{k/T}$. From~\cref{lemma:A-bound}, we know that, 
\begin{align*}
\sum_{k = 1}^{T} \alpha_{k} \geq \frac{\alpha T}{\ln(\nicefrac{T}{\beta})} - \frac{2\beta}{\ln(\nicefrac{T}{\beta})}.
\end{align*}
Bounding the ratio $\frac{\sum_{k = 1}^{T} \alpha_{k}^2}{\sum_{k = 1}^{T} \alpha_{k}} = \frac{\sum_{k = 1}^{T} \alpha^{2k}}{\sum_{k = 1}^{T} \alpha^{k}}$ where $\alpha = \left[\frac{\beta}{T}\right]^{1/T}$,
\begin{align*}
\frac{\sum_{k = 1}^{T} \alpha^{2k}}{\sum_{k = 1}^{T} \alpha^{k}} & \leq \frac{\alpha^2}{1 - \alpha^2} \, \frac{1 - \alpha}{\alpha - \alpha^{T+1}} \\
& = \frac{\alpha}{1 + \alpha} \frac{1}{1 - \alpha^T} \leq \frac{1}{1 - \alpha^T} = \frac{T }{T - \beta}\\
\end{align*}
Putting everything together, 
\begin{align*}
\mathbb{E} [f(\bar{w}_{T+1}) - f(w^{*})] &\leq \frac{2L \, \ln(T/\beta) \, \normsq{w_1 - w^{*}}}{\alpha T - 2 \beta} + \sigma^2 \frac{T }{T- \beta}
\end{align*}
\end{proof}

\subsection{Additional lemmas for upper-bound proofs}
\label{app:ub-lemmas}
\begin{thmbox}
\begin{lemmanew}
For $\alpha = \left( \frac{\beta}{T}\right)^{1/T}$ and any $\kappa > 0$,
\begin{align*}
\sum_{k=1}^T \alpha^{k} \exp \left(-\frac{1}{\kappa} \sum_{i=k+1}^T \alpha^i \right) \leq c_2 \frac{\kappa \ln (T / \beta)}{e \alpha} 
\end{align*}
for $c_2 = \exp\left( \frac{1}{\kappa} \frac{2\beta}{\ln(T/\beta)}\right)$
\label{lemma:C-bound}
\end{lemmanew}
\end{thmbox}
\begin{proof}
Proceeding in the same way as~\cref{lemma:B-bound}, we obtain the following inequality, 
\begin{align*}
\sum_{k=1}^T \alpha^{k} \exp\left( - \frac{1}{\kappa} \sum_{i=k+1}^T \alpha^i \right) & \leq c_2 \sum_{k=1}^T \alpha^{k} \exp\left(-\frac{1}{\kappa} \frac{\alpha^{k+1}}{1- \alpha} \right) 
\end{align*}
Further bounding this term, 
\begin{align*}
\sum_{k=1}^T \alpha^{k} \exp\left( - \frac{1}{\kappa} \sum_{i=t+1}^T \alpha^i \right) & \leq c_2\sum_{k=1}^T \alpha^{k} \frac{(1 - \alpha) \kappa}{e \alpha^{k+1}}  & \tag{Lemma \ref{lem:ineq2}} \\
& \leq c_2 (1 - \alpha) \frac{\kappa T}{e \alpha}  \\
& \leq c_2 \ln(1/\alpha) \frac{\kappa T}{e \alpha}  \\
& = c_2\frac{\kappa \ln (T / \beta)}{e \alpha} 
\end{align*}
\end{proof}

\begin{thmbox}
\begin{lemmanew}
\label{lem:sls-bounds}
If $f_i$ is $L_i$-smooth, stochastic lines-searches ensures that
\aligns{
    \gamma \norm{\nabla f_i(w)}^2 \leq \frac{1}{c}(f_i(w) - f_i^*),
    &&\text{and}&&
    \min\left\{
        \gamma_{\max},
        \frac{2 \, (1-c)}{L_{i}}
    \right\}
    \leq \gamma \leq \gamma_{\max}.
}
Moreover, if $f_i$ is a one-dimensional quadratic,
\begin{align*}
    \gamma = \min\left\{
        \gamma_{\max},
        \frac{2 \, (1-c)}{L_{i}}
    \right\}
\end{align*}
\end{lemmanew}
\end{thmbox}
\begin{proof}
Recall that if $f_i$ is $L_i$-smooth, then for an arbitrary direction $d$,
\begin{align*}
f_i(w - d) \leq f_i(w) - \lin{\nabla f_i(w), d} + \frac{L_i}{2} \normsq{d}.    
\end{align*}
For the stochastic line-search, $d=\gamma\nabla f_i(w)$. The smoothness and the line-search condition are then
\begin{align*}
\text{Smoothness: } f_i(w - \gamma \nabla f_i(w)) - f_i(w) &\leq \, \left(\frac{L_i}{2}\gamma^2-\gamma \right) \norm{\nabla f_i(w)}^2, \\
\text{Line-search: } f_i(w - \gamma \nabla f_i(w)) - f_i(w) &\leq -c \gamma \norm{\nabla f_i(w)}^2.
\end{align*}
The line-search condition is looser than smoothness if 
\begin{align*}
\textstyle
\left(\frac{L_i}{2}\gamma^2-\gamma \right)\norm{\nabla f_i(w)}^2 &\leq -c \gamma \norm{\nabla f_i(w)}^2.    
\end{align*}
The inequality is satisfied for any $\gamma \in [a, b]$, 
where $a, b$ are values of $\gamma$ that satisfy
the equation with equality,
$a = 0, b = \nicefrac{2(1-c)}{L_i}$,
and the line-search condition holds for $\gamma \leq \nicefrac{2(1-c)}{L_i}$. As the line-search selects the largest feasible step-size, $\gamma \geq \nicefrac{2(1-c)}{L_i}$. If the step-size is capped at $\gamma_{\max}$, we have $\eta \geq \min\{\gamma_{\max}, \nicefrac{2(1-c)}{L_i}\}$, and the proof for the stochastic line-search is complete. 

From the previous discussion, observe that if $\gamma > \frac{2(1-c)}{L_i}$, then we have
\begin{align*}
\textstyle
\left(\frac{L_i}{2}\gamma^2-\gamma \right)\norm{\nabla f_i(w)}^2 > -c \gamma \norm{\nabla f_i(w)}^2.    
\end{align*}
If $f$ is a one-dimensional quadratic, the smoothness inequality is actually an equality, and thus
\begin{align*}
    f_i(w - \gamma \nabla f_i(w)) - f_i(w) &= \, \left(\frac{L_i}{2}\gamma^2-\gamma \right) \norm{\nabla f_i(w)}^2
\end{align*}
So if $\gamma  > \frac{2(1-c)}{L_i}$, 
\begin{align*}
    f_i(w - \gamma \nabla f_i(w)) - f_i(w) &\geq -c \gamma \norm{\nabla f_i(w)}^2
\end{align*}
and the line-search condition does not hold. This implies that for one-dimensional quadratics $\gamma = \min\{ \gamma_{\max}, \frac{2(1-c)}{L_i}\}$
\end{proof}

\section*{Organization of the Appendix}
\begin{itemize}

   \item[\ref{app:definitions}] \nameref{app:definitions}
   
   \item[\ref{sec:additional-theory}] \nameref{sec:additional-theory}
   
   \item[\ref{app:acceleration-proof}] \nameref{app:acceleration-proof}
    
   \item[\ref{app:ub-proofs}] \nameref{app:ub-proofs}
   
   \item[\ref{app:lb-proofs}] \nameref{app:lb-proofs}    
  \item[\ref{app:helper-lemmas}] \nameref{app:helper-lemmas}      
 
\end{itemize}

\section{Definitions}
\label{app:definitions}
Our main assumptions are that each individual function $f_i$ is differentiable, has a finite minimum $f_i^*$, and is $L_i$-smooth, meaning that for all $v$ and $w$, 
\aligns{
    f_i(v) & \leq f_i(w) + \inner{\nabla f_i(w)}{v - w} + \frac{L_i}{2} \normsq{v - w},
    \tag{Individual Smoothness}
    \label{eq:individual-smoothness}
}
which also implies that $f$ is $L$-smooth, where $L$ is the maximum smoothness constant of the individual functions. A consequence of smoothness is the following bound on the norm of the stochastic gradients,
\aligns{
    \norm{\nabla f_i(w)}^2 
    \leq
    2 L (f_i(w) - f_i^*).
}
We also assume that each $f_i$ is convex, meaning that for all $v$ and $w$,
\aligns{
    f_i(v) &\geq f_i(w) - \lin{\nabla f_i(w), w-v},
    \tag{Convexity}
    \label{eq:individual-convexity}
    \\
}
Depending on the setting, we will also assume that $f$ is $\mu$ strongly-convex, meaning that for all $v$ and $w$,
\aligns{
f(v) & \geq f(w) + \inner{\nabla f(w)}{v - w} + \frac{\mu}{2} \normsq{v - w},
\tag{Strong Convexity}
\label{eq:strong-convexity}
}


\section{Problem setup and Background}
\label{sec:background}

We will assume that $f$ and each $f_{i}$ are differentiable and lower-bounded by $f^*$ and $f_{i}^*$, respectively. Throughout the main paper, we will assume that $f$ is $\mu$-strongly convex, and each $f_i$ is convex. Furthermore, we assume that each function $f_{i}$ is $L_i$-smooth, implying that $f$ is $L$-smooth with $L := \max_{i} L_i$. We include definitions of these properties in~\cref{app:definitions}. 

We use stochastic gradient descent (SGD) or SGD with Nesterov acceleration~\citep{nesterov2013introductory} (referred to as ASGD) to minimize $f$ in~\cref{eq:objective}. In each iteration $k \in [T]$, SGD selects a function $f_{ik}$ (typically uniformly) at random, computes its gradient and takes a descent step in that direction. Specifically, 
\begin{align}
w_{k+1} = w_{k} - \gamma_{k} \alpha_{k} \gradk{w_{k}},
\label{eq:sgd}    
\end{align}
where $w_{k+1}$ and $w_{k}$ are the SGD iterates, and $\gradk{\cdot}$ is the gradient of the loss function chosen at iteration $k$. Each stochastic gradient $\gradk{w}$ is unbiased, implying that $\mathbb{E}_i \left[ \gradi{w} \vert w_{k} \right] = \grad{w}$. The product of scalars $\eta_{k} := \gamma_{k} \alpha_{k}$ defines the \emph{step-size} for iteration $k$. The step-size consists of two parts - a problem-dependent scaling term $\gamma_{k}$ that captures the (local) smoothness of the function, and a problem-independent term $\alpha_{k}$ that controls the decay of the step-size. Typically, $\alpha_{k}$ is a decreasing sequence of $k$, and $\lim_{k \rightarrow \infty} \alpha_{k} = 0$. The $\alpha_{k}$ sequence depends on the properties of $f$, for example, for convex functions, $\alpha_{k} = O(\nicefrac{1}{\sqrt{k}})$ while for strongly-convex functions, $\alpha_{k} = O(\nicefrac{1}{k})$. 

Throughout the paper, we will assume that $T$ is known in advance (this requirement can be relaxed via the standard doubling trick), and consider exponentially decreasing step-sizes~\citep{li2020second} 
where $\alpha := \left[\frac{\beta}{T}\right]^{1/T} \leq 1$ for some parameter $\beta \geq 1$ and $\alpha_{k} := \alpha^{k}$.

Unlike SGD, ASGD has two sequences $\{w_{k}, y_{k} \}$ and an additional extrapolation parameter $b_{k}$. ASGD computes the stochastic gradient at the extrapolated point $y_{k}$ and takes a descent step in that direction. Specifically, the update in iteration $k$ of ASGD is:
\begin{align}
y_{k} &= w_{k} + b_{k} \, (w_{k} - w_{k-1}), \label{eq:extrapolation} \\
w_{k+1} &= y_{k} - \gamma_{k} \alpha_{k} \gradk{y_{k}}. \label{eq:sgd-update}    
\end{align}

In the next section, we will analyze the convergence of ASGD with exponentially decreasing step-sizes for smooth, strongly-convex functions.







\section{Conclusion}
\label{sec:conclusion}
In this paper, we first developed a variant of SGD with Nesterov acceleration and exponentially decreasing step-sizes, and proved that it achieves the near-optimal convergence rate in both the deterministic and stochastic regimes. We then considered two strategies for making SGD both noise-adaptive and problem-adaptive. Using upper and lower-bounds, we showed that there is always a price to pay for problem-adaptivity -- estimating the smoothness constant in an online fashion results in convergence to a neighbourhood of the solution, while an offline estimation results in a slower convergence to the minimizer. We empirically demonstrated the effectiveness of a noise-adaptive, problem-adaptive method that uses exponential step-sizes coupled with a novel variant of stochastic line-search. In the future, we hope to develop a problem-adaptive variant of ASGD. 
\section{Experiments}
\label{sec:experiments}
\begin{figure*}[h!]
\centering     
\subfigure[Squared loss]{\label{fig:squared}\includegraphics[scale = 0.33]{squared.pdf}} 
\subfigure[Logistic loss]{\label{fig:logistic}\includegraphics[scale = 0.33]{logistic.pdf}} 
\vspace{-2ex}
\caption{Comparison of step-size strategies for (a) squared loss and (b) logistic loss. Observe that (i) exponentially decreasing step-sizes result in more stable performance compared to using a constant step-size (for both SGD and ASGD) and (ii) consistently outperform the noise-adaptive method in~\citep{khaled2020better} and (iii) the stochastic line-search in~\cref{eq:armijo-ls-conservative} matches the performance of the variant with known smoothness.}
\label{fig:exps}
\end{figure*}
For comparing different step-size choices, we consider two common supervised learning losses -- squared loss for regression tasks and logistic loss for classification. With a linear model and an $\ell_2$ regularization equal to $\frac{\lambda}{2} \normsq{w}$, both objectives are strongly-convex. We use three standard datasets from LIBSVM~\citep{libsvm} -- \textit{mushrooms}, \textit{ijcnn} and \textit{rcv1}, and use $\lambda = 0.01$. For each experiment, we consider $5$ independent runs and plot the average result and standard deviation. We use the (full) gradient norm as the performance measure and plot it against the number of gradient evaluations.

For each dataset, we fix $T = 10n$, use a batch-size of $1$ and compare the performance of the following optimization strategies: (i) the noise-adaptive ``constant and then decay step-size'' scheme in~\citet[Theorem 3]{khaled2020better} (denoted as \texttt{KR-20} in the plots). Specifically, for $b=\max\{\frac{2L^2}{\mu},2\rho L\}$, we use a constant step-size equal to $1/b$ when $T<b/\mu$ or $k < \ceil{T/2}$. Otherwise we set the step-size at iteration $k$ to be $ \frac{2}{\mu((2b/\mu) + k - \ceil{T/2})}$, (ii) constant step-size SGD with $\gamma_{k} = \frac{1}{L}$ and $\alpha_{k} = 1$ for all $k$ (denoted as \texttt{K-CNST} in the plots) (iii) SGD with an exponentially decreasing step-size with knowledge of smoothness~\citep{li2020second} i.e. $\gamma_{k} = \frac{1}{L}$ and $\alpha_{k} = \alpha^k$ for $\alpha = \left(\frac{\beta}{T}\right)^{1/T}$ (denoted as \texttt{K-EXP}) (iv) Accelerated SGD (ASGD) with a constant step-size ($\alpha_{k} = 1$ for all $k$)~\citep{vaswani2019fast, cohen2018acceleration} (denoted as \texttt{ACC-K-CNST}) and (v) ASGD with exponentially decreasing step-sizes, analyzed in~\cref{sec:acceleration} and denoted as \texttt{ACC-K-EXP}. 

None of the above strategies are problem-adaptive, and all of them require the knowledge of the smoothness constant $L$. Additionally, \texttt{KR-20} and the ASGD variants also require knowledge of $\rho$, the parameter of the growth condition in~\cref{eq:growth-condition} and $\mu$, the strong-convexity parameter. If $x_i$ is the feature vector corresponding to example $i$, then we obtain theoretical upper-bounds on the smoothness and set $L = \max_i \normsq{x_i} + \lambda$ for the squared-loss and $L = \max_i \frac{1}{4} \normsq{x_i} + \lambda$ for the logistic loss. Similarly, we set $\mu = \lambda$ for both the squared and logistic loss. To set $\rho$, we use a grid search over $\{10,100,1000\}$ and plot the variant that results in the smallest gradient norm.

Using a stochastic line-search (SLS) can result in convergence to the neighbourhood (\cref{sec:sc-unknown-correlated}) because of the correlations between $i_k$ and $\gamma_{k}$. To alleviate this, and still be problem-adaptive, we design a \emph{decorrelated conservative} variant of SLS: at iteration $k$ of SGD, we set $\gamma_{k}$ using a stochastic line-search on the \emph{previously sampled function} $i_{k-1}$ (we can use a randomly sampled $j_k$ as well). This ensures that there is no correlation between $i_k$ and computing $\gamma_{k}$, but requires computing the gradient of two functions - one for the update and the other for the line-search. The overall procedure can be described as follows: starting with a backtracking line-search from $\gamma_{k-1}$ (the conservative aspect) (with $\gamma_{0} = \gamma_{\max}$)  for a random or previously sampled functio n ($j_k$), find the largest step-size $\gamma_{k}$ that satisfies
\begin{align}
f_{j_{k}}(w_{k} - \gamma_{k} \nabla f_{j_{k}}(w_{k})) & \leq f_{j_{k}}(w_{k}) - c \gamma_{k} \normsq{\nabla f_{j_{k}}(w_{k})}, 
\label{eq:armijo-ls-conservative}    
\end{align}
and update $w_{k}$ according to~\cref{eq:sgd}. The above procedure with $c = \nicefrac{1}{2}$ ensures that $\gamma_{k} \in \left[\min \{\gamma_{k-1}, \nicefrac{1}{L}\}, \gamma_{k-1} \right]$. Since $\gamma_{k}$ is fixed before computing $\gradk{w_{k}}$, this strategy can be analyzed using the framework in~\cref{sec:sc-unknown-decorrelated}. Specifically, it results in $\gamma_{k} = \frac{\nu_{k}}{L}$ for some sequence of $\nu_{k} \geq 1$. The conservative aspect ensures that $\nu_{k} \leq \nu_{k-1}$. Hence, the convergence rate can be analyzed according to~\cref{thm:sc-unknown-decorrelated} with $\nu = \nu_1$ and the initial line-search controlling the misestimation error. We use this variant of SLS with exponentially decreasing step-sizes and denote it as \texttt{SLS-EXP} in the plots. We emphasize that this strategy is both noise-adaptive and problem-adaptive. 

From~\cref{fig:exps}, we observe that exponentially decreasing step-sizes (i) result in more stable performance compared to the constant step-size variants (for both SGD and ASGD) and (ii) consistently outperform the noise-adaptive method in~\citep{khaled2020better}. We also observe that (iii) the stochastic line-search in~\cref{eq:armijo-ls-conservative} (\texttt{SLS-EXP}) matches the performance of the variant with known smoothness (\texttt{K-EXP}) and (iv) ASGD does not result in improvements over SGD. This is because these methods are quite sensitive to their parameter values and we set these parameters by using loose theoretical upper-bounds on both $L$ and $\mu$.











\section{Introduction}
\label{sec:introduction}
We study unconstrained minimization of a finite-sum objective $f:\mathbb{R}^d\rightarrow\mathbb{R}$ prevalent in machine learning,  
\begin{align}
\min_{w \in \mathbb{R}^d} f(w) := \frac{1}{n}\sum_{i=1}^n f_i(w).    
\label{eq:objective}
\end{align}
For supervised learning, $n$ represents the number of training examples and $f_i$ is the loss of example $i$. Throughout the main paper, we assume $f$ to be a smooth, strongly-convex function and denote $w^{*}$ to be the unique minimizer of the above problem. We consider broader function classes in~\cref{sec:additional-theory}.    

We study stochastic gradient descent (SGD) and its accelerated variant for minimizing $f$~\citep{robbins1951stochastic, NemYudin1983book, nesterov2013introductory, bottou2018optimization}. The empirical performance and the theoretical convergence of SGD is governed by the choice of its step-size, and numerous ways of selecting it have been studied in the literature. For example,~\citet{moulines2011non,gower2019sgd} use a \emph{constant} step-size for convex and strongly convex functions. A constant step-size only guarantees convergence to a neighborhood of the solution. In order to converge to the exact minimizer, a common technique is to decrease the step-size at an appropriate rate, and such decreasing step-sizes have also been well-studied in the literature~\citep{robbins1951stochastic,ghadimi2012optimal}. The rate at which the step-size needs to be decayed depends on the function class under consideration. For example, when minimizing smooth, strongly-convex functions using $T$ iterations of SGD, the step-size is decayed at an $O(1/k)$ rate where $k$ is the iteration number. This results in an $\Theta(1/T)$ convergence rate for SGD and is optimal in the stochastic setting~\citep{nguyen2018tight}. On the other hand, when minimizing a smooth, strongly-convex function with condition number $\kappa$, deterministic (full-batch) gradient descent (GD) with a \emph{constant} step-size converges linearly and has an $O(\exp(-T/\kappa))$ convergence rate. Augmenting constant step-size GD with Nesterov acceleration can further improve the convergence rate to $\Theta(\exp(-T/\sqrt{\kappa}))$ which is optimal in the deterministic setting~\citep{nesterov2013introductory}. Hence, the stochastic and deterministic variants of gradient descent use a different step-size strategy to obtain the optimal rates in their respective settings. 


\textbf{Towards noise adaptivity}: Ideally, we want a
\emph{noise-adaptive} algorithm such that (i) it obtains the optimal rates in both the deterministic and stochastic settings (ii) its convergence rate depends on the noise in the stochastic gradients and (iii) the resulting algorithm does not require  knowledge of the stochasticity (e.g. an upper bound on the variance in stochastic gradients). 

There have been three recent attempts to obtain such an algorithm. For smooth, strongly-convex functions, if $\sigma^2$ is the noise level in the stochastic gradients,~\citet{stich2019unified} achieves an $\tilde{O} \left(\exp(-T/\kappa) + \frac{\sigma^2}{T} \right)$ convergence rate using SGD that switches between two carefully designed step-sizes. When $\sigma = 0$, the resulting algorithm achieves the deterministic GD rate, whereas for a non-zero $\sigma$, its rate is governed by the $\sigma^2/T$ term. Unfortunately, setting the algorithm parameters requires the knowledge of $\sigma$ and hence, it is not noise-adaptive. On the other hand,~\citet{khaled2020better} and~\citet{li2020second} do not require knowledge of $\sigma$, and can obtain the same rate for smooth functions satisfying the Polyak-Lojasiewicz (PL) condition~\citep{karimi2016linear}, a generalization of strong-convexity. For this,~\citet{li2020second} use an exponentially decreasing sequence of step-sizes, while~\citet{khaled2020better} use a constant then decaying step-size. However, neither of these methods match the optimal $\sqrt{\kappa}$ dependence in the linear convergence term.

\textbf{Contribution}: Since we consider the easier (compared to PL) strongly-convex setting, it is unclear if we can achieve the above rate by using the conventional polynomially decreasing step-sizes~\citep{robbins1951stochastic}. Unfortunately, in~\cref{lemma:polynomial-lb-1,lemma:polynomial-lb-2}, we prove that no polynomially decreasing step-size of the form $O\left(\frac{1}{k^{\delta}}\right)$ for $\delta \in [0,1]$ can achieve the desired $\tilde{O} \left(\exp(-T/\kappa) + \frac{\sigma^2}{T} \right)$ rate\footnote{Note that this result does not cover step-size sequences that switch between two values of $\delta$, for example in~\citep{khaled2020better}}. Consequently, we will use an exponentially decreasing step-size.

\textbf{Contribution}: In~\cref{sec:acceleration}, we use SGD with an exponentially decreasing step-size and a stochastic variant of Nesterov acceleration~\citep{vaswani2019fast}. Under a growth-condition similar to~\citet{li2020second, khaled2020better, bottou2018optimization}, we prove that the resulting algorithm achieves the near-optimal $\tilde{O} \left(\exp(-T/\sqrt{\kappa}) + \frac{\sigma^2}{T} \right)$ convergence when minimizing smooth, strongly-convex functions. Our algorithm thus achieves the near-optimal rate in both the stochastic and deterministic settings and its rate smoothly varies between the two regimes. Furthermore, our algorithm does not require knowledge of $\sigma^2$ and hence satisfies three desiderata outlined above. To the best of our knowledge, this is the first such result.   

\textbf{Towards noise and problem adaptivity}: Typically, SGD also requires the knowledge of problem-dependent constants (such as smoothness or strong-convexity) to set the step-size. In practice, it is difficult to estimate these problem-dependent constants, and one can only obtain loose bounds on them. Consequently, there have been numerous methods~\citep{duchi2011adaptive, li2018convergence, kingma2014adam, bengio2015rmsprop, vaswani2019painless, loizou2021stochastic} that can adapt to the problem parameters, and adjust the step-size on the fly. We term such methods as \emph{problem-adaptive}. Unfortunately, it is unclear if such problem-adaptive methods can also be made noise-adaptive. On the other hand, all the noise-adaptive methods~\citep{li2020second,khaled2020better,stich2019unified} including the algorithm proposed in~\cref{sec:acceleration} require the knowledge of problem-dependent constants and are thus not problem-adaptive. 

In order to make progress towards an SGD variant that is both noise-adaptive and problem-adaptive, we only consider algorithms that can achieve the (non-optimal) $\tilde{O} \left(\exp(-T/\kappa) + \frac{\sigma^2}{T} \right)$ convergence rate. We note that the noise-adaptive algorithm in~\citet{li2020second} only requires knowledge of the smoothness constant and we try to relax this requirement. 

\textbf{Contribution}: In~\cref{sec:sc-unknown-correlated}, we use stochastic line-search~\citep{vaswani2019painless} to estimate the smoothness constant on the fly. We prove that SGD in conjunction with exponentially decreasing step-sizes and stochastic line-search (SLS) converges at the desired noise-adaptive rate but only to a \emph{neighbourhood of the solution}. This neighbourhood depends on the noise and the error in estimating the smoothness. We prove a corresponding lower-bound that shows the necessity of this neighbourhood term. Our lower-bound shows that if the step-size is set in an online fashion (using the sampled function like in SLS), no decreasing sequence of step-sizes can converge to the minimizer.

\textbf{Contribution}: In~\cref{sec:sc-unknown-decorrelated}, we consider estimating the smoothness constant in an offline fashion (before running SGD). SGD with an offline estimate of the smoothness and exponentially decreasing step-sizes converges to the solution, though its rate is slowed down by a factor proportional to the estimation error in the smoothness. Our upper-bound shows that even if we misestimate the smoothness constant by a multiplicative factor of $\nu$, the convergence can slow down by a factor as large as $O(\exp(\nu))$. We complement this result with a lower-bound that shows that such a misestimation in the smoothness necessarily slows down the rate by a potentially exponential factor.

Our results thus demonstrate the difficulty of obtaining noise-adaptive rates while being adaptive to the problem-dependent parameters. 

\textbf{Contribution}: In~\cref{sec:experiments}, we compare the performance of different step-size schemes on convex, supervised learning problems. Furthermore, we propose a novel variant of SLS that guarantees converges to the minimizer and demonstrate its practical effectiveness. 

\textbf{Contribution}: Finally, in~\cref{sec:additional-theory}, we prove matching results for SGD on strongly star-convex functions~\citep{hinder2020near}, a class of structured non-convex functions. We also show the explicit dependence of our results on the mini-batch size. Finally, we prove upper-bounds for (non-strongly-) convex functions, showing that even when the smoothness constant is known, exponentially decreasing step-sizes converge to a neighbourhood of the solution. We give some justification as to why any polynomial/exponentially decreasing step-size sequence is unlikely to be noise-adaptive in this setting. 


 






\subsubsection*{\bibname}}

\input{header}
\input{symbols}

\begin{document}

\runningtitle{Towards Noise-adaptive, Problem-adaptive Stochastic Gradient Descent}



\twocolumn[

\aistatstitle{Towards Noise-adaptive, Problem-adaptive \\ Stochastic Gradient Descent}

\aistatsauthor{ Sharan Vaswani$^\star$ \And Benjamin Dubois-Taine \And Reza Babanezhad }

\aistatsaddress{ Amii, University of Alberta \And  Universit\'e Paris-Saclay \And SAIT AI lab, Montreal } ]

\input{Abstract}
\input{Introduction}
\input{Background}
\input{Acceleration}
\input{Adaptivity}
\input{Experiments}
\input{Conclusion}
\input{Acknowledgements}
\bibliographystyle{apalike}

