MCMC-like algorithms. We also remark that @hoffer2017train proposed a different way of injecting noise, multiplying the sampled gradient with a suitably scaled Gaussian noise.

[Satisfying the Assumptions]{}\[ss:example\_ass\]

Before presenting the experimental results, we remark on a particular way that a function $U(w)$ defined in , along with the stochastic sequence $w_k$ defined in , can satisfy the assumptions in Section \[ss:ass\].

Suppose first that we shift the coordinate system so that $\nabla U(0)=0$. Let us additionally assume that for each $i$, $U_i(w)$ has the form $$\begin{aligned}
U_i(w) = U_i'(w) + V(w),\end{aligned}$$ where $V(w):= m \lrp{\|x\|_2-R/2}^2$ is a $m$-strongly convex regularizer outside a ball of radius $R$, and each $U_i'(w)$ has $\LR$-Lipschitz gradients. Suppose further that $m \geq 4 \cdot \LR$. These additional assumptions make sense when we are only interested in $U(w)$ over $B_R(0)$, so $V(w)$ plays the role of a barrier function that keeps us within $B_R(0)$. Then, it can immediately be verified that $U(w)$ satisfies Assumption \[ass:U\_properties\] with $L=m+\LR$.

The noise term $\xi$ in satisfies Assumption \[ass:xi\_properties\].1 by definition, and satisfies Assumption \[ass:xi\_properties\].3 with $L_\xi = \lrp{\sqrt{s} + 2\sigma} L$. Assumption \[ass:xi\_properties\].2 is satisfied if $\zeta(w,\eta)$ is bounded for all $w$, i.e. the sampled gradient does not deviate from the true gradient by more than a constant. We will need to assume directly Assumption \[ass:xi\_properties\].4, as it is a property of the distribution of $\nabla U_i(w)$ for $i=1, \ldots, n$.

![Relationship between test accuracy and the noise covariance of SGD algorithm. In each plot, the dots with the same color correspond to SGD runs with the same batch size but different step sizes.[]{data-label="fig:const_lr_acc_vs_var"}](sgd_runs.pdf){width="1\linewidth"}

[Experiments]{}\[subsection:experiments\]

![image](lr_matching){width="1.0\linewidth"}

![image](batch_matching){width="1.0\linewidth"}

In