Stochastic Reweighted Gradient Descent
Authors: Ayoub El Hanchi
Chris J. Maddison
David Alan Stephens
Venue: ICLR 2022 Submitted (2022)
Keywords: Stochastic gradient descent
Finite-sum optimization
Variance reduction
Importance sampling

Abstract: Importance sampling is a promising strategy for improving the convergence rate of stochastic gradient methods. It is typically used to precondition the optimization problem, but it can also be used to reduce the variance of the gradient estimator. Unfortunately, this latter point of view has yet to lead to practical methods that  improve the asymptotic error of stochastic gradient methods. In this work, we propose stochastic reweighted gradient (SRG), a variance-reduced stochastic gradient method based solely on importance sampling that can improve on the asymptotic error of stochastic gradient descent (SGD) in the strongly convex and smooth case. We show that SRG can be extended to combine the benefits of both importance-sampling-based preconditioning and variance reduction. When compared to SGD, the resulting algorithm can simultaneously reduce the condition number and the asymptotic error, both by up to a factor equal to the number of component functions. We demonstrate improved convergence in practice on $\ell_2$-regularized logistic regression problems.

Under review as a conference paper at ICLR 2022
STOCHASTIC REWEIGHTED GRADIENT DESCENT
Anonymous authors Paper under double-blind review
ABSTRACT
Importance sampling is promising strategy for improving the convergence rate of stochastic gradient methods. It is typically used to precondition the optimization problem, but it can also be used reduce the variance of the gradient estima- tor. Unfortunately, this latter point of view has yet to lead to practical methods that provably improve the asymptotic error of stochastic gradient methods. this work, we propose stochastic reweighted gradient (SRG), a variance-reduced stochastic gradient method based solely on importance sampling that can improve the asymptotic error of stochastic gradient descent (SGD) in the strongly con- vex and smooth case. We show that SRG can be extended to combine the ben- efits of both importance-sarmplingg baaddliin---eedd preconditioning and variance reduction. When compared to SGD, the resulting algorithm can simultaneously reduce the condition number and the asymptotic error, both by up factor equal the number of component functions. We demonstrate improved convergence in prac- tice on fz-regularized logistic regression problems.
INTRODUCTION
Unconstrained optimization of finite-sum objectives is core algorithmic problem in machine learn- ing. The prototypical way of solving such problems is by viewing them through the lens of stochastic optimization, where the source of stochasticity resides in the choice of the index in the sum. Stochas- tic gradient descent (SGD) (Robbins & Monro 1951 remains the standard al algorithm for this class of problems.
A natural way to improve on SGD is by considering importance sampling schemes. This idea is not new and dates back to (Needell et al. 2014) who uses importance sampling as a preconditioning technique. They propose sampling the indices with probabilities proportional to the smoothness constants of the corresponding component functions, and show that this sampling scheme provably reduces the condition number of the problem.
In another line of work, variance-reducee methods were found to achieve lincar convergence in the strongly convex and smooth case (Roux al. 2012 Schmidt et al.] 2017). Many of these methods rely on control variates to reduce the variance of the gradient estimator used by SGD (Johnson & Zhang 2013) Defazio al., (0144). While very successful, the applicability of these methods is limited by the large memory overhead that they introduce, or the periodic full-gradient recomputation that they require (Defazio & Bottou 2019). Despite strong progress in this research area, an importance- inportance-sampling based analogue to these algorithms, which is potentially free from these drawbacks, has yet to emerge.
In this work, we propose such an analogue. We introduce stochastic reweighted gradient (SRG), an importance-sampling-bae
variance-reduced optimization algorithm. Similar SGD, SRG re- quires a single gradient oracle call per iteration, and only requires ((n) additional memory, and Olog nı) additional floating point operations per iteration. We analyze the convergence rate of SRG in the strongly-convex and smooth case, and show that it can provably improve the asymptotic error of SGD. Finally, we show how our importance sampling strategy can be combined with smoothness- based importance sampling, and prove that the resulting algorithm simultaneously performs variance reduction and preconditioning. We demonstrate improved convergence in practice on Ez fz-regularized logistic regression problems.

---

Under review as a conference paper at ICLR 2022
2 PRELIMINARIES
We consider the finite-sum optimization problem:
min EER
F(x)
Σ M(x))
(I)
where F is j--strongyy convex for μ > 0, and for all E [n]. ft is convex and L.-smooth for Lg O. Note that by strong-convexity, F has unique minimizer x" R. We define the maximum Trmux == max]c[m] [4 and average := ΣØ= Li/n smoothness constants. Similarly, we define the maximum Mmaax T-max/ y and average x T/ condition numbers.
The classical way of solving (1) is by viewing it as a stochastic optimization problem where the randomness comes from the choice of the index [n]. Starting from some zo g and for an iteration number A E N, stochastic gradient descent (SGD) performs the following update:
Fk+1 = 2s ag V (1x)
for step size og and random index in drawn uniformly from [n]]
The idea behind importance sampling for SGD is to instead sample the index in according to chosen distribution pk on (n], and to perform the update (Needell et al. 2014):
1 npk
Sia (T+)
(2)
where pl. is the hh component of the probability vector Pk- is immediate to verify that the impor- tance sampling estimator of the gradient is unbiased long pk >> 0.
The question that we address in this paper is how to design a sequence {p=) that produces more efficient gradient estimators than the ones produced by uniform sampling. One way to design such a sequence is by adopting a greedy strategy: at each iteration we choose ps to minimize the conditional variance of the gradient estimator, which is given by, up to an additive constant:
1
o² (Ik,P) = iump
Ippi (Fu
(1
f
(3)
n
This conditional variance is minimized at (Zhao & Zhang 2015):
V V(((F))ll
arg min o (Tt, PEA
(4)
Ideally, we would like to set pa to this minimizer. However, this requires knowledge of the gradient norms V f(w))ll)) which, in general, requires gradient evaluations per iteration.
ALGORITHM
In this section, we show how to design tractable sequence of importance sampling distributions for SGD that approximate the efficient approximations of the conditional variances (3). We then state a simple bound on the approximation errors and use it to motivate our choice of importance sampling distributions.
waaaaaal-vvaiieemmiiiiiiii distributions (4). First we construct
To approximate the conditional variances, we follow the strategy of certain variance-reduced meth- ods (Roux et al.) 2012] Schmidt et al. [2017, Defazio et al.) 2014). These methods maintain table (gf) that tracks the component gradients (Vi(()))) and updates itself each iteration at the index i used to update the iterates IA (2). Our method instead maintains array of gradient norms, from which we construct an approximation of the conditional variance of the gradient estimator:
(2( ==
Σ i=1
gh
n²
pd
2

---

Under review as a conference paper at ICLR 2022
Algorithm SRG
1: Parameters: step sizes (ax) > O, mixture coefficients (0x) (0,
2: Initialization: Zo E Fd (119 2 E R
3: for = 0, ..... do
4: Pk (1 0 1x 0k/n
for is defined in S
5: by ~ Bernoulli (k))
6: if bu 1 then iN 1/n else qh
7:
1h+1 = Th Okk npk
V Sig (It)
[+x)))) h = 1 and i = i otherwise
8:
1ottalle 1
9: end for
which is minimized at:
n
1 j=1
4h arg min 8² (xx,p)
(5)
We do not directly use OK as an importance sampling distribution, because this approximation may be poor. In particular, we have the following bound on the conditional variance
(IK, n
Vf((ax) - g 2 25 (xx(p))
(6)
Recall that our goal is to pick Pk that minimizes ar p). minimizes the second term on the right-hand side, but we must ensure that both terms are small. Two conditions are needed keep the first term small. The first is to control the terms [((x)))
lll which we can do by making sure that the historical gradients s are frequently updated. The second is to ensure that the probabilities p are lower bounded. We achieve both of these properties, as well as approximately minimize the right-hand side of (6) by mixing q with the uniform distribution over [n]. This yields our final importance sampling distribution for given mixture coefficient 0g E (0, 1]:
Pk = (1 02)g
7
Our analysis clarifics the role the sequence mixture coefficients (0&) and relates to both the step size sequence (au) and the asymptotic enror of SRG in the constant step size setting.
Curiously, analysis requires performing the update of the array ([lg )r= only when the index & is drawn from the uniform mixture component.
not clear to us whether this constraint is an
artifact of the analysis property of the algorithm. We discuss this further after the statement of Lemma in section The pseudocode for our method is given in Algorithm
We briefly discuss how SRG can be efficiently implemented. To sample from Qk. store (1 1 in a binary indexed tree using ((n) memory, along with the normalizing constant A Σr Di= |1 The binary indexed tree be updated and maintained in (log opera- tions, while the normalizing constant can be maintained constant time. We can then sample from Ik using inverse transform sampling: multiply uniform random variable E [0, by Ag, then return the largest index whose corresponding prefix sum less than Agu. This procedure also requires only (log n) operations. The total overhead of SRG when compared SGD is therefore (nn) memory and Oloog n) floating point operations per iteration.
4 THEORY
In this section, we analyze the convergence rate of SRG, and show that can achieve a better asymptotic error than SGD. Two key constants are helpful in contrasting the asymptotic errors of
3

---

Under review as a conference paper at ICLR 2022
SRG and SGD. Recall the definition of ( pk) in 3 and define:
o² = , =
Σ
v f(((")) 2
2
0 min 02 p) PEA
1 n
Σ
n
is well known that the asymptotic error of SGD depends linearly on o² Needell et al. 2014). We here show that SRG reduces this linear dependence o², which can be up to times smaller.
To study the convergence rate of SRG, we use the following Lyapunov function, which is similar to the used study the convergence of SAGA (Hofmann et al. 2015 Defazio 2016):
T = Tirkk (ok) = Ork a
Ellot - V.i((>)) || x²112
(8)
Limax 1=1
for a constant a that we set during the analysis. The proofs of this section are Appendix B
4.1 INTERMEDIATE LEMMAS
Before proceeding with the main result, let us first state two intermediate lemmas. The first studies the evolution of (gh) == from one iteration to the next.
Lemma 1. Let l E N and suppose that (gf) evolves as in Algorithm ! respect to (bks ix), conditional on (be, 20) we have:
Taking expectation with
OK
E
19t+ Vf(('')
1 (((("))
20g Tomax (F(**) F(x""
n
The use of the Bernoulli random variable by in Algorithm to monitor the update of (g)) 1 is necessary for Lemma 1 to hold. In particular, without the use of bg, the elements of (g()) _ may have different probabilities of being updated. In that case, the second term of Lemma becomes weighted average of terms that are technically difficult deal with. When the importance sampling distribution does not depend the iteration, this issue can be fixed with slight modification of the Lyapunov function (8 (Schmidt et al. 2015). In our case however, we are dealing with time- varying importance sampling distributions, and this approach fails. This is why rely the Bernoulli random variable bą to ensure that the probability of updating any g is fixed to 0z/nz.
The second lemma is bound the conditional variance of the gradient estimator used by SRG. We intentionally leave as many free parameters as possible in the bound and optimize over them in the main result of section 4.2
Lemma 2. Let k E N and assume that On E (0, 1/2]. Taking expectation with respect to (bw,iz). conditional (be, ie 1=)==) we have, for all B, 8,7,6 8,,8n 0:
k-1
2D, Lmax
D2
E Spp
Vfn (Ix) (xx) npk
[F(*x)
F+I
11
Oun
where D1, D2 and D3 are positive functions of the free parameters 5.m.
4.2 MAIN RESULT
Our main result a bound on the evolution the Lyapunov function T along the steps SRG. Theorem 1. Suppose that (IR, (gh) 1) evolves according to Algorithm 1 Further, assume that for
all l E N: (i) ax/Og, (g is non non-increasing. (ii) 0₂ E 1/2). (iii) 0g S 0% T2Lmar Then:
E [ < (1 ] + + (1 + 20 ?o
4

---

Under review as a conference paper at ICLR 2022
for all l E N. and where:
0k 12n
Pk = min
The constants (1/12 in the bound the step size and in Pk. 6 in front of the of term) in this theorem are optimized under the following constraints. First, the parameterized form of the above bound shows that the largest allowable step size is given by e20k//Tma Using it we get:
Pk: = min { OK
4K
12
Fimax
for some constants C1: O2 O. As we do not know priori the relative magnitudes of n and Kmax and since e1 and (2 are inversely proportional, we impose the constraint e1 = C2- Similarly, our parameterized bound gives asymptotic error of the form (1 + 20g )c for constant e3- We chose to impose the constraint C3 6. C1, and are all functions of the free parameters of Lemma 2 and the constant of the Lyapunov function (8). Numerically maximizing c2 (and therefore the largest allowable step size) subject to these two constraints (cg = 6 and c = C2) with respect to these parameters yields the result Theorem [
To give the reader an idea of the sensitivity of the result to the choice of c3, note that setting C3 = 2 yields 02 x 1/20, whereas taking C3 > 1 yields C2 1/10. We have attempted to obtain the best bound possible on the largest step size allowable, but the rather small prefactor 02 seems to be an inevitable consequence of the multiple (but as far as we can tell necessary) uses of Young's inequality in our analysis. Our experiments suggest that the dependence the mixture coefficient 0 is real, but that the prefactor C2 = 1/12 may be an artifact the analysis.
For SRG with constant mixture coefficient and step size, its convergence rate and complexity are characterized by the following corollary of Theorem
Corollary 1. Suppose that (æk, (o)))=)) evolves according to Algorithm
I with a constant mixture Then for any E N:
coefficient 0g (0, 1/2] and constant step size a₁ S 0//12mmax =
6a
E E
S
T (1 20)
0
where p = Pke is as defined in Theorem 7
For any ε > 0 and 0 E (0, 1/2), choosing:
0 12
Eji
a min
(1 + 12) V
+ 20 144no?
and:
12n
27
h: 2 max
log
ap
||rrk x* "12 Se
guarantees
Comparing the convergence rate of SRG in Corollary [ with the standard result for SGD (Needell that they are of similar form. When p aj,, the bound of Corollary [ is better
et al. 2014), asymptotically. Indeed, in this case, and as k + oc, the iterates of SRG stay within a ball of radius o(vo?) of the minimizer, while those of SGD stay withing a ball of radius O(va2). The equality p ag holds when a < 1/mqu, which is for all allowable step sizes if the problem is dominated by its maximum condition number Kmax 2 n, and for small step sizes otherwise.
In terms of complexity, we have the following comparison. Up to constants, the complexity of SRG with a constant mixture coefficient and step size is of the form:
o (n
n 2
a²
n n
+ Kinax +
log
1125
We compare this to the complexity of SGD with constant step size (Needell et al. 2014):
0 Kmax +
log
1125
In the high accuracy regime, the e terms dominate the complexities of SRG and SGD. In this case, SRG enjoys better complexity than SGD since of & o²
5

---

Under review as a conference paper at ICLR 2022
Algorithm 2 SRG+
Parameters: step sizes (a+) =
O, mixture coefficients (0x) E [0,
Initialization: 20 Fd (11 R"
for 0, 0,1,2.... do
Pk (1 0 0&U
{qr is defined in 5 is defined in 11
by ~ Bernoulli (k)
if by then (ik. jis) V.sn (IR)
π else in qh
maximally couples (v, 1/n))
Th+1 2h an
[VVs( (xx)
by = and j = jk otherwise
gh+1
o2
end for
EXTENSION
In this section, we extend SRG combine its variance reduction capacity with the preconditioning ability of smoothness-basee importance sampling.
A straightforward way to generalize the argument given in the derivation of SRG in section 3 is to
consider the following bound on the conditional variance (3) of the gradient estimator, which can be derived from Young's inequality and the Li-smoothness of each fi:
2² (zk, S
3 n
n L4
(V)((z)) ffi(""), --)+
11st (C--((((=*) - n p
3 n
Σ
+332
1-322(xx) (#k.P)
While the motivating bound (6 seems more intuitive, because we think of of as tracking (a()),, turns out that this second bound better captures the evolution of of in relation to V (xx)). gets large. Similar to our approach in section 3 our goal is to pick Pk that minimizes the right-hand side of (9). We know that qu (5) minimizes the third term, but we need make sure that the first two are also small. To minimize the first term, knowing nothing about the relative sizes of the inner product terms, it makes sense to have probabilities proportional to the smoothness constants ! On the other hand, to keep the second term small, we need to ensure that the historical gradients (g) ) are frequently updated, which we can do by imposing uniform lower bound on the probabilities. These considerations motivate us to consider the following distributions:
high-level, this because of. tracks f((xx) indirectly; both hover around V fx("))
0%
Ph = Mi
6x)4s T
(10)
7 for positive mixture coefficients (0x, m)) satisfying O₂ + T)s E (0, 1]. and where u is given by:
L
a
(11)
1=1
Using these probabilities, we able to show that the resulting algorithm does indeed achieve both variance reduction and preconditioning. However, in the worst case, its complexity is twice as much what would expect from simply replacing Imux with L in Corollary [] Intuitively, this is because the probability assigned to the uniform component in needs to be split between the uniform and the smoothness-bast components in 10
5.1 CAREFULLY DECOUPLING THE UPDATES OF (g))) AND Fk
Here we show how to design our algorithm such that this additional factor of 2 (described above) in the complexity reduced to:
1 + ||u - 1/nllrv 2 - 2/1/n
Based on this argument alone, one would want them to be proportional to the square root of the smoothness constants. This however does not lead to nice averaging of the inner product terms, which is important for technical reasons related the strong-convexity of F but of the component functions fi-

---

Under review as a conference paper at ICLR 2022
Following (Schmidt al. 2013), method is based on the observation that can decouple the index used to update the historical gradients and the index used to update the iterates, which we refer to Jk and 8g. respectively. Intuitively, to minimize (10) we would ideally want Ja to be uniformly distributed and is to be distributed according to pt: = (1 Oz gk + 8gv. Unfortunately, sampling (jk, ix) independently with these marginals does not address our issue, because we would still require an average of approximately two gradient evaluations per iteration.
Luckily, we can use any coupling between (jk, ig), because the evolution of the Lyapunov function ( only depends on the marginal distributions and not the joint. In particular, we obtain the same bound on the evolution of T regardless of how i and ji are coupled. therefore makes sense to pick the coupling that maximizes the probability that d = ja since this minimizes the number of gradient evaluations required per iteration. Such couplings are known as maximal couplings in the literature (see, e.g., e.g.. Biswas et al. (2019)) and can easily be computed for discrete random variables. With maximal coupling, the expected number of gradient evaluations per iteration becomes + 1| 1/nll/nnl Using this idea we arrive at SRG+ described in Algorithm
Let us briefly discuss the implementation of SRG+, Sampling from r, the maximal coupling of and the uniform distribution, requires forming three probability vectors (see, e-g.. Biswas et al. (019)). As both v and 1/n are constant throughout the optimization process, we can form these vectors at the beginning of the algorithm along with their partial sums for total initial cost of ((n) operations. We can then sample from x in O(log n) time using binary search on the partial sums at each iteration. Adding this sampling therefore does not change the overhead of SRG.
5.2 ANALYSIS
The analysis of SRG+ is similar to that of SRG. In particular, the iterates of SRG+ also obey slight modification of Theorem where the bound on the largest allowable step size loosened to Ok 12I. We refer the reader Appendix C for more details. Due to this improvement, get that the complexity of SRG+ with constant mixture coefficient and step size is given by:
o on+ ME
no?
O II&E
+
log
This shows that SRG+ performs both variance reduction shown by the dependence of the com- plexity on of instead of o² and preconditioning as shown by the dependence on K instead of Kmax
6 RELATED WORK
At high-level, three lines of work exist that study the use of importance sampling with SGD, The first one considers fixed importance sampling distributions based on the constants of the problem (Needell et al. 2014 Zhao & Zhang, 2015), and shows that such strategy leads to improved condi- tioning of the problem. The second considers adaptive importance sampling and similar to our work targets the variance of the gradient estimator, but generally fails at providing strong convergence
rate guarantees under standard assumptions (Papa et al., 2015 Alain et al., 2016 Canevet et al. 2016 Stich et al.] 2017) Katharoppulos & Fleuret 2018 Johnson & Guestrin 2018). The third line of work frames the problem as an online learning problem with bandit feedback and provides guarantees the regret of the proposed distributions in terms of the variance of the resulting esti-
mators (Namkoong et 2017 Salehi et al. [017]] Borsos et al. 2018 2019 El Hanchi & Stephens 2020). Our method is closely related to the one proposed by (Papa et al. 2015): their analysis how- ever requires non-standard assumptions and their main result is asymptotic in nature. In contrast, our work the first to provide asymstttt guarantees on the suboptimality of the iterates for variance-reducing importance sampling under standard technical assumptions.
7 EXPERIMENTS
In this section, we empirically verify two main claims: (i) SRG performs variance reduction which can improve the asymptotic error of SGD. (ii) SRG+ performs both variance reduction and preconditioning, and can both reduce the asymptotic emor of SGD and allow the use of larger step
7

---

Under review as a conference paper at ICLR 2022
R2L 2e 2 3=622krm
107
SGD1
50D1
9901
10
(9 411
1012
21
0905
pradie calaacalaroo
Figure 1: Left: Linear dependence of ASGD/ ASCD/AgnG: the ratio of asymptotic errors of SGD and SRG, on o² / the ratio of the uniform and optimal variances the minimum. Right: SRG+ achieves smaller asymptotic error than both SGD with samsmiig (SGD+) and SGD with partially biased sampling (SGD++), while using large ()) step sizes just like SGD+ and SGD++.
sizes. We start with controlled synthetic experiments that provide direct support for our claims. We then compare SRG other baseline optimizers on fg-regularized logistic regression problems. In all experiments, we ran each algorithm 10 times and present the averaged result.
7.1 SYNTHETIC EXPERIMENTS
For our first experiment, we consider the following toy problem. We let x E TR and f((x) = {(r a;)² where a; 0 for E [n 1] and a, 1. In this case, x² 1/n, o² ze 1/n, and of R 4/n². We consider five instantiations of this problem with n E {8, 16, 32, 64, 128). yielding ratios o² /² approximately in {2, 4, 8, 16, 32}. For each instantiation, we ran SGD and SRG until
they reached stationarity and recorded their asymptotic errors lim E [ - x ||2 which we denote by ASGD and ASRG respectively. We experimented with three different step sizes, of them allowed by Corollary I and one larger one for which we can only prove that SRG has a similar convergence guarantee as SGD. For SRG, we used the mixture coefficient # 1/2.
We plot ASOD/ / ASRG against o²/oz / in Figure (left) for each of the three step sizes, from which we see that the relationship between the two ratios is linear, and very close identity. From an asymptotic error point of view, these results support our theory in that the improvement is seen to be directly proportional to the ratio a² /o?. On the other hand, the constant 6(1 + 20)/p Corollary would suggest that the proportionality constant is much smaller than 1, particularly when is large, but this is not what we observe in practice. This could be because the first term of the Lyapunov function (8) is quite large stationarity, because the constants in our bound are not sharp due to the multiple uses of Young's 's inequality. This latter possibility is further supported by the fact that a similar behaviour for SRG for step sizes larger than the ones allowed by our theory. We have consistently made these two observations in other experiments. It however unclear to us how analysis can be improved to match these observations.
For our second experiment, we considered the following problem. We let x E R and fa(x) = 20. Similar the first experiment, we take a; 0 for [n 1] and n[n-25 so that = 1, Lmax = n 1. this 1/n, o² ss 2/n², and of z 4/n3. We then ran SGD with Li-sampling (SGD+), SGD with partially biased sampling (SGD++. (SGD+=,,Needlll et al. (2014). and SRG+, all with the largest allowable step size a 0/12f. from our theory for SRG+, and the mixture coefficient 0 = 1/2 for both SRG+ and SGD++. We have obtained very similar results when using the larger step size a = 0/2L, which is the maximum allowable for SGD+.
Lx - az) and fixed
a, = We then set L1 = n 1 L, = 1/n, and L, = m-1
case, get x 1/n3, o. = =z
We plot the relative error || - x 111 / [|:o - 201 for each algorithm against the number of gradient oracle calls it makes in Figure I (right). We that all three algorithms are able to converge even when using the large (1)LE) step sizes. The theory of SGD+ allows for larger step sizes compared to SGD, but the asymptotic error of the algorithm depends of. (Needell et al. 2014), which can be up times bigger than o² To solve this problem. Needell et al. (2014) proposed
8

---

Under review as a conference paper at ICLR 2022
Jowa
Figure 2: Comparison of the evolution of the average relative error I| x 112 || x x=122 for different optimizers on fz-regularized logistic regression problems using the datasets ijcnnl, w8a, mushrooms, phishing. We compare SRG (orange) with SGD (blue), SGD with random shuffling (purple), and SGD with the optimal variance- variance-minimine minimizing distributions at each iteration (green).
partially biased sampling which mixes the smoothness-based distribution with uniform sampling, allowing the use of larger step sizes just like SGD+, but preserving the asymptotic error of SGD. SRG+ further improves on SGD++, and reduces the asymptotic error, making it proportional to o².
7.2 f- A2-REGULARIZED LOGISTIC REGRESSION
For our last experiment, we test SRG on éz-regularized logistic regression problems. In this case, the functions Si are given by:
[((x)) == log (1 + exp (-y:a
(=:)a(a)))))))))))))))) x)) + 1 ||01|
where ys E {0, 1} is the lahel of data point a; Rd. Each Ji is convex and I.; 0.25 | l smooth. Their average also j-sttoongy convex. As is standard, we select μ = 1/n.
We experiment with SRG four datasets from LIBSVM (Chang Lin 2011): ijenn/, w8a, mush- rooms and phishing. For each dataset, and to be able to efficiently run our experiments, we randomly select subset of the data of size n 1000. As the datasets normalized, we have that ||a for all i E [n]]. This makes L; L = 0.25 + μe, which reduces SGD+ to SGD, and SRG+ to SRG.
We tested the performance of SRG against three baselines, the first of which standard SGD. The second is SGD with the optimal auriance-miniminn allows us to compare SRG with the best possible variance-reducing importance sampling scheme. The last baseline is SGD with random shuffling, which is also known to improve the asymptotic error of SGD (under the additional assumption that each fi is also strongly convex), (Mishchenko) al. 2020). We evaluate the performance of the algorithms by tracking the average relative error
probabilities pi x |/ (2w))l22 which
I x "1 / I x² 11-- We used the mixture coefficient = 1/2 for SRG, and used the same step size a = 0/2L for all algorithms.
The results of this experiment are shown in Figure We observe that SRG consistently outper- forms SGD on all datasets, and that closely matches the performance SGD with the variance- minimizing distributions, which it tries to approximate. We also that SRG outperforms SGD with random shuffling on two datasets, and is competitive with it on the remaining two.
CONCLUSION
We introduced SRG, new aepportancc-samplinn based variance- variance-reduced reduced optimization algorithm for finite-sum problems. We analyzed its convergence rate in the strongly convex and smooth case, and showed that can improve on the asymptotic error of SGD. We also introduced SRG+, an extension of SRG which simultaneously performs variance reduction and preconditioning through importance sampling. We expect our algorithms to most useful in the medium accuracy regime, where the required accuracy is higher than the one achieved by SGD, but low enough that the overhead of classical variance reduced methods becomes significant. Finally, an interesting future direction would be to explore non non-greedy strategies for the design of importance sampling distributions for SGD that not only minimize the variance of the current gradient estimator, but also take into account the variance of the gradient estimators of subsequent iterations.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance Reduction in SGD by Distributed Importance Sampling. vrXiv:1511.0644 [cs, stat], April 2016.
URL htLhhtt://
//axxp org/ abs/ 1511. .6481 arXiv: 1511.06481.
Niloy Biswas, Pierre E. Jacob, and Paul Vanetti. Estimating Convergence of Markov chains with L--Lag Couplings. Advances in Neural Information Processing Sys- tems, 32, 2019. URL lattps: hnwpp///..ppeeeeeee...o...ooo... nwwriss.eeupp...
Awsttaatttstttttta..e. .tml
Zalan Borsos, Andreas Krause, and Kfir Y. Levy. Online Variance Reduction for Stochastic Optimization. In Conference On Learning Theory, pp- 324-357. PMLR, July 2018. URL ISSN: 2640-3498.
http:://rroceedings .mlr. htt.eaadn..........rs////sss www.p/rssssvvvv //os///ooos/// 8a hlmll
Zalán Borsos, Sebastian Curi, Kfir Yehuda Levy, and Andreas Krause. Online Variance Reduction with Mixtures. International Conference Machine Learning, pp. 705-714. PMLR, May 2019. URL htLttt//prrccceinnngg http://eeennnaa.....e.ee///////. 3498.
html,
ISSN: 2640-
Olivier Canevet, Cijo Jose, and Francois Fleuret. Importance Sampling Tree for Large-scale Em- pirical Expectation. In International Conference Machine Learning, pp. 1454-1462. PMLR, June 2016. URL http::/ppxoceedingg .orre.smrr..... www. httpa//ass.....eeeee/////////eee wtt.s///e////aaceeee1e1e html ISSN: 1938-7228.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM Trans. Intell. Syst. Technol., 2(3), May 2011. ISSN 2157-6904. doi: 10.1 10.1145/1961 (45/196111999 189.1961 199. URL
httpss:/6o...rg//...14444/
19611999999
Aaron Defazio. Simple Practical Accelerated Method for Finite Sums. Advances in Neural Infor-
mation Processing Systems, 29:676-6844 2016. URL https::/ppocceddinnn nips.co. .html
paper/2016/hash/aFF hat.:affff.....22222222222229923
Aaron Defazio and Leon Bottou. On the Ineffectiveness of Variance Reduced Opti- mization for Deep Learning. Advances in Neural Information Processing Systems, 32:
1755-1765, 2019. URL
nips ccc Saaper/2c19/hst. www.:999d-Abbstaaccc html
84
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. SAGA: Fast Incre- mental Gradient Method With Support for Non-Strongly Convex Composite Ob- jectives. Advances in Neural Information Processing Systems, 27:1646-1654,
2014.
URL
ede oet.
Ayoub El Hanchi and David Stephens. Adaptive Importance Sampling for Finite-Sum Opti- mization and Sampling with Decreasing Step-Sizes. Advances in Neural Information Process- ing Systems, 33, 2020. URL https::/pproceedinggs nips. http:/pcccppppp/////////aaaaaaaa
0aF .tml
Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, and Brian McWilliams. Variance Re- duced Stochastic Gradient Descent with Neighbors. Advances in Neural Information Processing Systems, 28:2305-2313, 2015. URL https:://tocceeeeeeeeeee ngs. .nps.. wttsseccpppppee hcc/paper/2015// Abst .tml
bash/effc299e0 ptt.::29lllladiia 2tt.a222...a..aa...0000092911111
Rie Johnson and Tong Zhang. Accelerating Stochastic Gradient Descent using Pre- dictive Variance Reduction.
Advances in Neural Information Processing Systems,
26:315-323, 2013. URL https:// .ip....n........... pttppaper//11////aaaaa ac oclo
Tyler B. Johnson and Carlos Guestrin. Training Deep Models Faster with Robust, Ap- proximate Importance Sampling. Advances in Neural Information Processing Systems, 31:7265-7275, 2018. URL https://broeeednggg.o https//a.p..c/app//////////////a 9 967999debb3accc787744444 http://acaaa.aaac44444a4.....-.0
10

---

Under review as a conference paper at ICLR 2022
Angelos Katharopoulos and Francois Fleuret. Not All Samples Are Created Equal: Deep Learning with Importance Sampling. In International Conference on Machine Learning,
pp. 2525-2534. PMLR, July 2018. URL http://prrocecinng. .ml.mngg..m......mmmmmmm.. htt.://mngg.ii....s/e/////// press/v8C/ katharopoul os 8a html ISSN: 2640-3498.
Konstantin Mishchenko, Ahmed Khaled Ragab Bayoumi, and Peter Richtarik. Random Reshuf- fling: Simple Analysis with Vast Improvements. Advances Neural Information Process- ing Systems, 33, 2020. URL http::://proccceiiinng.nn
html
Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, and John C. Duchi. Adaptive Sampling Probabilities for Non-Smooth Optimization. In International Conference on Machine Learn
ing. pp. 2574-2583 PMLR, July 2017. URL http:: http:://proceeeingg...o wtt.sngss........ssrrr.
namkoong17a. html
ISSN: 2640-3498.
Deanna Needell, Rachel Ward, and Nati Srebro. Stochastic Gradient Descent, Weighted Sam- pling, and the Randomized Kaczmarz algorithm. Advances in Neural Information Processing Systems, 27:1017-1025, 2014. URL htt.l: /tL/
ieppiinnsniiipp.pp..m......im..e cctpaper/p2/4//
Yurii Nesterov. Introductory Lectures on Convex Optimization: Basic Course. Applied Optimiza- tion. Springer US, 2004. ISBN 978- 17781-40200-7533-77 doi: 10.1007/978-1111 1-471988--41-- URL
https:/ www. springer. com/
Guillaume Papa, Pascal Bianchi, and Stephan Clémençon, Adaptive Sampling for Incremental Op- timization Using Stochastic Gradient Descent. In Kamalika Chaudhuri, CLAUDIO GENTILE, and Sandra Zilles (eds.), Algorithmic Learning Theory, Lecture Notes in Computer Science, pp. 317-331 Cham, 2015. Springer International Publishing. ISBN 978 978-3-319-24486- doi: 10.1007/978- 3-319---4886-6-
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. Annals of Mathematical Statistics, 22(3):400-400 September 1951. ISSN 0003-4851, 2168-8990. aoms/
doi: 10. (001214/0mm//1177725555 URL otct:::://pooeeettucl......o//e
1177729586 Publisher: Institute of Mathematical Statisties.
Nicolas Roux, Mark Schmidt, and Francis Bach. A Stochastic Gradient Method with Expo- nential Convergence rrate for Finite Training Sets. Advances in Neural Information Processing Systems, 25:2663-2671, 2012. URL (1t.eaaaaa4110445140 faae://b00bcaiaaldaaaa1aeeeeeeer Aasttt--bbtttttt
wwwpiinnnn.npp....m cc/ htc/paper/201//
Faroood Salchi, L. Elisa Celis, and Patrick Thiran. Stochastic Optimization with Bandit Sampling. arXiv preprint arXiv:1708.0253 02544, August 2017. URL http://p///axi..org////////// abspgg/ga/////.///
02544v2
Mark Schmidt, Reza Babanezhad, Mohamed Ahmed, Aaron Defazio, Ann Clifton, and Anoop Sarkar. Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields. In Artificial Intelligence and Statistics, pp. 819-828. PMLR, February 2015. URL. ISSN: 1938-7228.
http::/proceediin ngs www.mlr.p.... pre.ss.pps////............e....e /vtass/v//// w38/schmiideecc 15tmlll
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochas- tic average gradient. Mathematical P Programming, 162(1):83-112, March 2017. ISSN
1436-4646. doi: 10.1007//10107--06 1030-6.
URI. https:://dci httpss://dii..////////// 100./000.00077
110107-016-1 10055-003:2 1030-6
Sebastian U. Stich, Anant Raj, and Martin Jaggi. Safe Adaptive Importance Sam- pling. Advances in Neural Information Processing Systems, 30:4381-4391, 2017.
URL
Peilin Zhao and Tong Zhang. Stochastic Optimization with Importance Sampling for Regularized Loss Minimization. In International Conference Machine Learning, pp. 1-9. PMLR, June 2015. URL /tt.a//////caaaaaaaaaaaaaa////aa htmm1 ISSN: 1938- 7228.
mlr https///s.mmmmpppeee/////////aaa


Reviews:
[{"review_id": "o8THLhYtxp8", "reviewer": "Reviewer_F7eT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The importance sampling procedure is new, however there have been many similar works in the past and this paper's results maybe very incremental.", "summary_of_the_paper": "This paper uses importance sampling in SGD to improve performance.", "summary_of_the_review": "The importance sampling procedure is new, however there have been many similar works in the past and this paper's results maybe very incremental.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "X-8tmWkSmxd", "reviewer": "Reviewer_i1ZH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "There is a rich literature in the domain for SGD based on importance sampling and conditional variances approximation. The paper combines these two ideas, and I believe that it is useful for reducing the asymptotic error and computational complexities. I have some concerns as follows.\n1.\tI might be misunderstanding part of the proofs, but I hope the author could help me understand more on why Lemma 2 holds. In the algorithm, $p_k$ is calculated based on $q_k$, which is related to a binomial distribution with parameter $\\theta_k$. So the randomness of $q_k$ may have an impact on the expectation. However in the proof, the impact of $q_k$ is not involved, and $p_k$ seems to be treated as a constant. In other words, since the importance sampling process can be regarded as a kind of Bayes procedure, how does the distribution of the sampling probability impact the convergence?\n2.\tIn the experiments, the proposed method is compared with SGD+ (SGD with $L_i$-sampling) and SGD++ (SGD with partially biased sampling), how about comparing with importance sampling SGD with the optimal sample probabilities?\n", "summary_of_the_paper": "The authors propose the stochastic reweighted gradient (SRG) algorithm, which is based on importance sampling in SGD to reduce the variance for the SGD method. The authors also extend SRG to combine the benefits of both importance-sampling-based preconditioning and variance reduction. The convergence rate is studied and the authors show that the proposed method can achieve a better asymptotic error than SGD. ", "summary_of_the_review": "I believe the paper has its value in combining importance sampling SGD with conditional variances approximation to reduce the asymptotic error as well as the computational complexity. I just have one question on the technical soundness of the convergence results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "FqQDa6y6nto", "reviewer": "Reviewer_wvfK", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1- The paper is well-written and it is easy to follow and walk through the proofs. \n\n2- The major comment is that the analysis is for very limiting settings. It would be more practical to analyze the method for non-convex settings to see the effectiveness of the method in practice for training NNs. It would be useful to apply this method to NN training. \n\n3- For the experiments, it is not clear how many times each experiment has been run and if the result is the average of those.   \n\n", "summary_of_the_paper": "This paper considers minimizing the finite sum problem with SGD with non-uniform sampling. \nThe optimal sampling weight at a given point is achieved via minimizing the variance of stochastic gradient which needs the norm of the gradient of each function at that point. To approximate these sampling weights and also be efficient this paper proposes to take the approach similar to SAGA and use auxiliary memory with the size of number of functions and update one of the stored values in each iterate similar to SAGA. Using stale and stored gradient norms gives an upper bound to the stochastic gradient variance that could be minimized similarly. Since this new upper bound contains two terms, they propose a mixture of non-uniform and uniform sampling to make both terms small. They analyze SGD with the proposed sampling scheme and show that the sub-optimality upper bound is n (the number of functions)-times smaller than the upper bound of SGD with uniform sampling. They also propose another weighting scheme that mixes uniform and non-uniformes schemes proportioned with gradient norms and smoothness parameters of each function. \n", "summary_of_the_review": "The major comment is that the analysis is for very limiting settings. It would be more practical to analyze the method for non-convex settings to see the effectiveness of the method in practice for training NNs. It would be useful to apply this method to NN training. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4rAJlxML4l", "reviewer": "Reviewer_N3uR", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOne of the biggest challenge in this paper is the assumption for SRG+ that we know all the Lipschitz constants of f_i s. For linear & logistic regressions, I agree that we can know them. But for many problems, especially in real world scenarios, it will be difficult to either compute these values or use them to do sampling. More comments on this is needed in the paper.\n\nI would like to see more applications and experiments than those in the paper. The analysis does not convince me that importance sampling is truly helpful. Does this matter? Should I try to use this? Do I have any hope of using it in settings that are large-scale enough that I want to simply stream the data? \n\nSince there is extra computation at each iteration compared to SGD (computation of norms, updates....), then experiments with run time in x-axis make more sense?\n\nWhat about minibatch versions of your methods, do they support this? how? comments on this are needed.\n\nWhat is the sensitivity of your methods to theta?", "summary_of_the_paper": "This work proposes a variance-reduced method called stochastic reweighted gradient (SRG) method which is based on importance sampling.  SRG improves on the of stochastic gradient descent error for the strongly convex and smooth objective functions. The authors extended  also SRG to SRG+ to combine the importance-sampling-based preconditioning and variance reduction. Numerical experiments are provided to assess the numerical efficiency of these methods.", "summary_of_the_review": "See above", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC all find the presented approach interesting and promising. 

However, as pointed out in the reviews and as the authors recognized, the strongly convex + smooth objective setting considered is limited. Given the prevalence of non-convex settings in many practical applications and the rich related literature on the analysis of SGD and variants in the non-convex setting,  it would be highly desirable to (i) consider experiments on small NN architectures (since the method cannot accommodate larger architectures)  to gain some understanding of the value of the approach and (ii)  to try and extend the present analysis to the non-convex case. 

It would also be valuable to perform experiments illustrating the impact of theta indicated by the theory.
Decision: Reject