STOCHASTIC REWEIGHTED GRADIENT DESCENT
Year: 2021

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 provably 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 `2-regularized logistic regression problems.

text: 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 provably 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 `2-regularized logistic regression problems.

heading: 1 INTRODUCTION
text: Unconstrained optimization of finite-sum objectives is a core algorithmic problem in machine learning. 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. Stochastic gradient descent (SGD) (Robbins & Monro, 1951) remains the standard 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-reduced methods were found to achieve linear convergence in the strongly convex and smooth case (Roux et 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 et al., 2014). 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-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-based variance-reduced optimization algorithm. Similar to SGD, SRG requires a single gradient oracle call per iteration, and only requires O(n) additional memory, and O(log 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 smoothnessbased importance sampling, and prove that the resulting algorithm simultaneously performs variance reduction and preconditioning. We demonstrate improved convergence in practice on `2-regularized logistic regression problems.

heading: 2 PRELIMINARIES
text: We consider the finite-sum optimization problem:
min x∈Rd
{ F (x) := 1
n n∑ i=1 fi(x)
} (1)
where F is µ-strongly convex for µ > 0, and for all i ∈ [n], fi is convex and Li-smooth for Li > 0. Note that by strong-convexity, F has a unique minimizer x∗ ∈ Rd. We define the maximum Lmax := maxi∈[n] Li and average L := ∑n j=1 Li/n smoothness constants. Similarly, we define the maximum κmax := Lmax/µ and average κ := L/µ 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 i ∈ [n]. Starting from some x0 ∈ Rd, and for an iteration number k ∈ N, stochastic gradient descent (SGD) performs the following update:
xk+1 = xk − αk∇fik(xk)
for a step size αk > 0 and a random index ik drawn uniformly from [n].
The idea behind importance sampling for SGD is to instead sample the index ik according to a chosen distribution pk on [n], and to perform the update (Needell et al., 2014):
xk+1 = xk − αk 1
npikk ∇fik(xk) (2)
where pik is the i th component of the probability vector pk. It is immediate to verify that the importance sampling estimator of the gradient is unbiased as long as pk > 0.
The question that we address in this paper is how to design a sequence {pk}∞k=0 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 k we choose pk to minimize the conditional variance of the gradient estimator, which is given by, up to an additive constant:
σ2(xk, p) := E ik∼p [∥∥∥∥ 1npik∇fik(xk) ∥∥∥∥2
2
∣∣∣∣∣ (it)k−1t=0 ] = 1 n2 n∑ i=1 1 pi ‖∇fi(xk)‖22 , (3)
This conditional variance is minimized at (Zhao & Zhang, 2015):
arg min p∈∆
σ2(xk, p) = ( ‖∇fi(xk)‖2∑n j=1 ‖∇fj(xk)‖2 )n i=1
(4)
Ideally, we would like to set pk to this minimizer. However, this requires knowledge of the gradient norms (‖∇fi(xk)‖2) n i=1 , which, in general, requires n gradient evaluations per iteration.

heading: 3 ALGORITHM
text: In this section, we show how to design a tractable sequence of importance sampling distributions for SGD that approximate the conditional-variance-minimizing distributions (4). First we construct 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.
To approximate the conditional variances, we follow the strategy of certain variance-reduced methods (Roux et al., 2012; Schmidt et al., 2017; Defazio et al., 2014). These methods maintain a table (gik) n i=1 that tracks the component gradients (∇fi(xk))ni=1 and updates itself each iteration at the index ik used to update the iterates xk (2). Our method instead maintains an array of gradient norms, from which we construct an approximation of the conditional variance (3) of the gradient estimator:
σ̃2(xk, p) := 1
n2 n∑ i=1 1 pi ∥∥gik∥∥22
Algorithm 1 SRG 1: Parameters: step sizes (αk)∞k=0 > 0, mixture coefficients (θk)∞k=0 ∈ (0, 1] 2: Initialization: x0 ∈ Rd, (
∥∥gi0∥∥2)ni=1 ∈ Rn 3: for k = 0, 1, 2, . . . do 4: pk = (1− θk)qk + θk/n {qk is defined in (5)} 5: bk ∼ Bernoulli(θk) 6: if bk = 1 then ik ∼ 1/n else ik ∼ qk 7: xk+1 = xk − αk 1
np ik k
∇fik(xk) 8: ∥∥gik+1∥∥2 = {‖∇fi(xk)‖2 if bk = 1 and ik = i∥∥gik∥∥2 otherwise 9: end for
which is minimized at:
qk = arg min p∈∆
σ̃2(xk, p) =  ∥∥gik∥∥2∑n j=1 ∥∥∥gjk∥∥∥ 2 n i=1
(5)
We do not directly use qk as an importance sampling distribution, because this approximation may be poor. In particular, we have the following bound on the conditional variance (3):
σ2(xk, p) ≤ 2
n2 n∑ i=1 1 pi ∥∥∇fi(xk)− gik∥∥22 + 2σ̃2(xk, p) (6)
Recall that our goal is to pick pk that minimizes σ2(xk, p). qk minimizes the second term on the right-hand side, but we must ensure that both terms are small. Two conditions are needed to keep the first term small. The first is to control the terms ∥∥∇fi(xk)− gik∥∥22, which we can do by making sure that the historical gradients gik are frequently updated. The second is to ensure that the probabilities pik are lower bounded. We achieve both of these properties, as well as approximately minimize the right-hand side of (6) by mixing qk with the uniform distribution over [n]. This yields our final importance sampling distribution for a given mixture coefficient θk ∈ (0, 1]:
pk = (1− θk)qk + θk n
(7)
Our analysis clarifies the role of the sequence of mixture coefficients (θk)∞k=0, and relates it to both the step size sequence (αk)∞k=0 and the asymptotic error of SRG in the constant step size setting.
Curiously, our analysis requires performing the update of the array ( ∥∥gik∥∥2)ni=1 only when the index ik is drawn from the uniform mixture component. It is not clear to us whether this constraint is an artifact of the analysis or a property of the algorithm. We discuss this further after the statement of Lemma 1 in section 4. The pseudocode for our method is given in Algorithm 1. We briefly discuss how SRG can be efficiently implemented. To sample from qk, we store ( ∥∥gik∥∥2)ni=1 in a binary indexed tree using O(n) memory, along with the normalizing constant λk = ∑n i=1
∥∥gik∥∥2. The binary indexed tree can be updated and maintained in O(log n) operations, while the normalizing constant can be maintained in constant time. We can then sample from qk using inverse transform sampling: we multiply a uniform random variable u ∈ [0, 1) by λk, then return the largest index whose corresponding prefix sum is less than λku. This procedure also requires only O(log n) operations. The total overhead of SRG when compared to SGD is therefore O(n) memory and O(log n) floating point operations per iteration.

heading: 4 THEORY
text: In this section, we analyze the convergence rate of SRG, and show that it can achieve a better asymptotic error than SGD. Two key constants are helpful in contrasting the asymptotic errors of
SRG and SGD. Recall the definition of σ2(xk, pk) in (3), and define:
σ2 := σ2(x∗, 1/n) = 1
n n∑ i=1 ‖∇fi(x∗)‖22
σ2∗ := min p∈∆
σ2(x∗, p) = 1
n2 ( n∑ i=1 ‖∇fi(x∗)‖2 )2 It is well known that the asymptotic error of SGD depends linearly on σ2 (Needell et al., 2014). We here show that SRG reduces this to a linear dependence on σ2∗, which can be up to n times smaller.
To study the convergence rate of SRG, we use the following Lyapunov function, which is similar to the one used to study the convergence rate of SAGA (Hofmann et al., 2015; Defazio, 2016):
T k = T (xk, (g i k) n i=1) := αk θk a Lmax n∑ i=1 ∥∥gik −∇fi(x∗)∥∥22 + ‖xk − x∗‖22 (8) for a constant a > 0 that we set during the analysis. The proofs of this section are in Appendix B.

heading: 4.1 INTERMEDIATE LEMMAS
text: Before proceeding with the main result, let us first state two intermediate lemmas. The first studies the evolution of (gik) n i=1 from one iteration to the next.
Lemma 1. Let k ∈ N and suppose that (gik)ni=1 evolves as in Algorithm 1. Taking expectation with respect to (bk, ik), conditional on (bt, it)k−1t=0 , we have:
E [ n∑ i=1 ∥∥gik+1 −∇fi(x∗)∥∥22 ] ≤ ( 1− θk n ) n∑ i=1 ∥∥gik −∇fi(x∗)∥∥22 + 2θkLmax [F (xk)− F (x∗)] The use of the Bernoulli random variable bk in Algorithm 1 to monitor the update of (gik) n i=1 is necessary for Lemma 1 to hold. In particular, without the use of bk, the elements of (gik) n i=1 may have different probabilities of being updated. In that case, the second term of Lemma 1 becomes a weighted average of terms that are technically difficult to deal with. When the importance sampling distribution does not depend on the iteration, this issue can be fixed with a slight modification of the Lyapunov function (8) (Schmidt et al., 2015). In our case however, we are dealing with timevarying importance sampling distributions, and this approach fails. This is why we rely on the Bernoulli random variable bk to ensure that the probability of updating any gik is fixed to θk/n.
The second lemma is a bound on 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 ∈ N and assume that θk ∈ (0, 1/2]. Taking expectation with respect to (bk, ik), conditional on (bt, it)k−1t=0 , we have, for all β, γ, δ, η > 0:
E ik∼pk ∥∥∥∥∥ 1npikk ∇fik(xk) ∥∥∥∥∥ 2
2
 ≤ 2D1Lmax θk [F (xk)− F ∗]+ D2 θkn n∑ i=1
∥∥gik −∇fi(x∗)∥∥22+D3(1+2θk)σ2∗ where D1, D2 and D3 are positive functions of the free parameters β, γ, δ, η.

heading: 4.2 MAIN RESULT
text: Our main result is a bound on the evolution of the Lyapunov function T k along the steps of SRG. Theorem 1. Suppose that (xk, (gik)ni=1) evolves according to Algorithm 1. Further, assume that for all k ∈ N: (i) αk/θk is non-increasing. (ii) θk ∈ (0, 1/2]. (iii) αk ≤ θk/12Lmax. Then:
E [ T k+1 ] ≤ (1− ρk)E [ T k ] + (1 + 2θk)6α 2 kσ 2 ∗
for all k ∈ N, and where:
ρk := min
{ θk
12n , αkµ
}
The constants (1/12 in the bound on the step size and in ρk, 6 in front of the σ2∗ 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 c2θk/Lmax. Using it we get:
ρk = min { c1 θk n , c2 θk κmax } for some constants c1, c2 > 0. As we do not know a priori the relative magnitudes of n and κmax, and since c1 and c2 are inversely proportional, we impose the constraint c1 = c2. Similarly, our parameterized bound gives an asymptotic error of the form (1 + 2θk)c3α2kσ 2 ∗ for a constant c3. We chose to impose the constraint c3 = 6. c1, c2 and c3 are all functions of the free parameters of Lemma 2 and the constant a of the Lyapunov function (8). Numerically maximizing c2 (and therefore the largest allowable step size) subject to these two constraints (c3 = 6 and c1 = c2) with respect to these parameters yields the result in Theorem 1.
To give the reader an idea of the sensitivity of the result to the choice of c3, note that setting c3 = 2 yields c2 ≈ 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 c2 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 on the mixture coefficient θ is real, but that the prefactor c2 = 1/12 may be an artifact of the analysis.
For SRG with a constant mixture coefficient and step size, its convergence rate and complexity are characterized by the following corollary of Theorem 1: Corollary 1. Suppose that (xk, (gik)ni=1) evolves according to Algorithm 1 with a constant mixture coefficient θk = θ ∈ (0, 1/2] and a constant step size αk = α ≤ θ/12Lmax. Then for any k ∈ N:
E [ T k ] ≤ (1− ρ)k T 0 + (1 + 2θ)6α
2σ2∗ ρ
where ρ = ρk is as defined in Theorem 1. For any ε > 0 and θ ∈ (0, 1/2], choosing:
α = min
{ θ
12Lmax ,
εµ
(1 + 2θ)12σ2∗ ,
√ θ
1 + 2θ
ε
144nσ2∗ } and:
k ≥ max { 12n
θ ,
1
αµ
} log ( 2T 0
ε ) guarantees E [ ‖xk − x∗‖22 ] ≤ ε
Comparing the convergence rate of SRG in Corollary 1 with the standard result for SGD (Needell et al., 2014), we see that they are of similar form. When ρ = αµ, the bound of Corollary 1 is better asymptotically. Indeed, in this case, and as k → ∞, the iterates of SRG stay within a ball of radius O( √ σ2∗) of the minimizer, while those of SGD stay withing a ball of radius O( √ σ2). The equality ρ = αµ holds when α ≤ 1/nµ, which is true for all allowable step sizes if the problem is dominated by its maximum condition number κmax ≥ 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∗ µ2ε + κmax + σ2∗ µ2ε ) log ( 1 ε ) We compare this to the complexity of SGD with constant step size (Needell et al., 2014):
O ( κmax + σ2
µ2ε
) log ( 1
ε ) In the high accuracy regime, the ε−1 terms dominate the complexities of SRG and SGD. In this case, SRG enjoys a better complexity than SGD since σ2∗ ≤ σ2.
Algorithm 2 SRG+ Parameters: step sizes (αk)∞k=0 > 0, mixture coefficients (θk)∞k=0 ∈ (0, 1] Initialization: x0 ∈ Rd, (
∥∥gi0∥∥2)ni=1 ∈ Rn for k = 0, 1, 2, . . . do pk = (1− θk)qk + θkv {qk is defined in (5), v is defined in (11)} bk ∼ Bernoulli(θk) if bk = 1 then (ik, jk) ∼ π else ik ∼ qk {π maximally couples (v, 1/n)} xk+1 = xk − αk 1
np ik k ∇fik(xk)∥∥∥gjk+1∥∥∥ 2 = { ‖∇fj(xk)‖2 if bk = 1 and j = jk∥∥∥gjk∥∥∥
2 otherwise
end for

heading: 5 EXTENSION
text: In this section, we extend SRG to combine its variance reduction capacity with the preconditioning ability of smoothness-based 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(xk, p) ≤ 3
n2 n∑ i=1 Li pi 〈∇fi(xk)−∇fi(x∗), xk−x∗〉+ 3 n2 n∑ i=1 1 pi ∥∥gik −∇fi(x∗)∥∥22 +3σ̃2(xk, p)
(9)
While the motivating bound (6) seems more intuitive, because we think of gik as tracking ∇fi(xk), it turns out that this second bound better captures the evolution of gik in relation to ∇fi(xk). At a high-level, this is because gik tracks∇fi(xk) indirectly: both hover around∇fi(x∗) as k 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 qk (5) minimizes the third term, but we need to 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 1. On the other hand, to keep the second term small, we need to ensure that the historical gradients (gik) n i=1 are frequently updated, which we can do by imposing a uniform lower bound on the probabilities. These considerations motivate us to consider the following distributions:
p′k = (1− ηk − θk)qk + ηkv + θk n
(10)
for positive mixture coefficients (θk, ηk) satisfying θk + ηk ∈ (0, 1], and where v is given by:
v =
( Li
nL )n i=1
(11)
Using these probabilities, we are 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 as what we would expect from simply replacing Lmax with L in Corollary 1. Intuitively, this is because the probability assigned to the uniform component in (7) needs to be split between the uniform and the smoothness-based components in (10).
5.1 CAREFULLY DECOUPLING THE UPDATES OF (gik) n i=1 AND xk
Here we show how to design our algorithm such that this additional factor of 2 (described above) in the complexity is reduced to:
1 + ‖v − 1/n‖TV ≤ 2− 1/n 1Based 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 a nice averaging of the inner product terms, which is important for technical reasons related to the strong-convexity of F but not of the component functions fi.
Following (Schmidt et al., 2015), our method is based on the observation that we can decouple the index used to update the historical gradients and the index used to update the iterates, which we refer to as jk and ik, respectively. Intuitively, to minimize (10) we would ideally want jk to be uniformly distributed and ik to be distributed according to pk = (1 − θk)qk + θkv. Unfortunately, sampling (jk, ik) 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, ik), because the evolution of the Lyapunov function (8) only depends on the marginal distributions and not the joint. In particular, we obtain the same bound on the evolution of T k regardless of how ik and jk are coupled. It therefore makes sense to pick the coupling that maximizes the probability that ik = jk since this minimizes the number of gradient evaluations required per iteration. Such couplings are known as maximal couplings in the literature (see, e.g., Biswas et al. (2019)) and can easily be computed for discrete random variables. With a maximal coupling, the expected number of gradient evaluations per iteration becomes 1 + ‖v − 1/n‖TV . Using this idea we arrive at SRG+ described in Algorithm 2. Let us briefly discuss the implementation of SRG+. Sampling from π, the maximal coupling of v and the uniform distribution, requires forming three probability vectors (see, e.g., Biswas et al. (2019)). 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 a total initial cost of O(n) operations. We can then sample from π 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.

heading: 5.2 ANALYSIS
text: The analysis of SRG+ is similar to that of SRG. In particular, the iterates of SRG+ also obey a slight modification of Theorem 1 where the bound on the largest allowable step size is loosened to αk ≤ θk/12L. We refer the reader to Appendix C for more details. Due to this improvement, we get that the complexity of SRG+ with a constant mixture coefficient and step size is given by:
O ( n+ √ nσ2∗ µε + κ+ σ2∗ µ2ε ) log ( 1 ε ) This shows that SRG+ performs both variance reduction as shown by the dependence of the complexity on σ2∗ instead of σ 2 and preconditioning as shown by the dependence on κ instead of κmax.

heading: 6 RELATED WORK
text: At a 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 a strategy leads to improved conditioning 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; Katharopoulos & Fleuret, 2018; Johnson & Guestrin, 2018). The third line of work frames the problem as an online learning problem with bandit feedback and provides guarantees on the regret of the proposed distributions in terms of the variance of the resulting estimators (Namkoong et al., 2017; Salehi et al., 2017; 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 however requires non-standard assumptions and their main result is asymptotic in nature. In contrast, our work is the first to provide non-asymptotic guarantees on the suboptimality of the iterates for variance-reducing importance sampling under standard technical assumptions.

heading: 7 EXPERIMENTS
text: In this section, we empirically verify our 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 error of SGD and allow the use of larger step
sizes. We start with controlled synthetic experiments that provide direct support for our claims. We then compare SRG to other baseline optimizers on `2-regularized logistic regression problems. In all experiments, we ran each algorithm 10 times and present the averaged result.

heading: 7.1 SYNTHETIC EXPERIMENTS
text: For our first experiment, we consider the following toy problem. We let x ∈ R and fi(x) = 1 2 (x − ai)
2 where ai = 0 for i ∈ [n − 1] and an = 1. In this case, x∗ = 1/n, σ2 ≈ 1/n, and σ2∗ ≈ 4/n2. We consider five instantiations of this problem with n ∈ {8, 16, 32, 64, 128}, yielding ratios σ2/σ2∗ approximately in {2, 4, 8, 16, 32}. For each instantiation, we ran SGD and SRG until they reached stationarity and recorded their asymptotic errors limk→∞ E [ ‖xk − x∗‖22 ] , which we denote by ∆SGD and ∆SRG respectively. We experimented with three different step sizes, two of them allowed by Corollary 1, 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 ∆SGD/∆SRG against σ2/σ2∗ in Figure 1 (left) for each of the three step sizes, from which we see that the relationship between the two ratios is linear, and very close to 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 σ2/σ2∗. On the other hand, the constant 6(1 + 2θ)/ρ in Corollary 1 would suggest that the proportionality constant is much smaller than 1, particularly when n 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 at stationarity, or because the constants in our bound are not sharp due to the multiple uses of Young’s inequality. This latter possibility is further supported by the fact that we see 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 is however unclear to us how our analysis can be improved to match these observations.
For our second experiment, we considered the following problem. We let x ∈ R and fi(x) = 1 2Li(x− ai)
2, and fixed n = 20. Similar to the first experiment, we take ai = 0 for i ∈ [n− 1] and an = 1. We then set L1 = n−1, Ln = 1/n, and Li = n−1n(n−2) , so that L = 1, Lmax = n−1. In this case, we get x∗ = 1/n2, σ2+ = σ
2(x∗, v) ≈ 1/n, σ2 ≈ 2/n2, and σ2∗ ≈ 4/n3. We then ran SGD with Li-sampling (SGD+), SGD with partially biased sampling (SGD++, Needell et al. (2014)), and SRG+, all with the largest allowable step size α = θ/12L from our theory for SRG+, and we use the mixture coefficient θ = 1/2 for both SRG+ and SGD++. We have obtained very similar results when using the larger step size α = θ/2L, which is the maximum allowable for SGD+.
We plot the relative error E [ ‖xk − x∗‖22 ] / ‖x0 − x∗‖22 for each algorithm against the number of gradient oracle calls it makes in Figure 1 (right). We see that all three algorithms are able to converge even when using the large O(1/L) step sizes. The theory of SGD+ allows for larger step sizes compared to SGD, but the asymptotic error of the algorithm depends on σ2+ (Needell et al., 2014), which can be up to n times bigger than σ2. To solve this problem, Needell et al. (2014) proposed
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 σ2∗.
7.2 `2-REGULARIZED LOGISTIC REGRESSION
For our last experiment, we test SRG on `2-regularized logistic regression problems. In this case, the functions fi are given by:
fi(x) := log (1 + exp (−yiaTi x)) + µ
2 ‖x‖22
where yi ∈ {0, 1} is the label of data point ai ∈ Rd. Each fi is convex and Li = 0.25 ‖ai‖22 + µ smooth. Their average F is also µ-strongly convex. As is standard, we select µ = 1/n.
We experiment with SRG on four datasets from LIBSVM (Chang & Lin, 2011): ijcnn1, w8a, mushrooms and phishing. For each dataset, and to be able to efficiently run our experiments, we randomly select a subset of the data of size n = 1000. As the datasets are normalized, we have that ‖ai‖2 = 1 for all i ∈ [n]. This makes Li = L = 0.25 + µ, which reduces SGD+ to SGD, and SRG+ to SRG. We tested the performance of SRG against three baselines, the first of which is standard SGD. The second is SGD with the optimal variance-minimizing probabilities pik ∝ ‖∇fi(xk)‖2, which 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 et al., 2020). We evaluate the performance of the algorithms by tracking the average relative error E [ ‖xk − x∗‖22 ] / ‖x0 − x∗‖22. We used the mixture coefficient θ = 1/2 for SRG, and used the
same step size α = θ/2L for all algorithms.
The results of this experiment are shown in Figure 2. We observe that SRG consistently outperforms SGD on all datasets, and that it closely matches the performance of SGD with the varianceminimizing distributions, which it tries to approximate. We also see that SRG outperforms SGD with random shuffling on two datasets, and is competitive with it on the remaining two.

heading: 8 CONCLUSION
text: We introduced SRG, a new importance-sampling based variance-reduced optimization algorithm for finite-sum problems. We analyzed its convergence rate in the strongly convex and smooth case, and showed that it 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 be 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-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.

Review summaries:
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. 

This paper considers minimizing the finite sum problem with SGD with non-uniform sampling.  The 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.  

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.