L-SVRG and L-Katyusha with Adaptive Sampling
Authors: Boxin Zhao
Boxiang Lyu
mladen kolar
Venue: Accepted by TMLR ()

Abstract: Stochastic gradient-based optimization methods, such as L-SVRG and its accelerated variant L-Katyusha (Kovalev et al., 2020), are widely used to train machine learning models. Theoretical and empirical performance of L-SVRG and L-Katyusha can be improved by sampling the observations from a non-uniform distribution Qian et al. (2021). However, to design a desired sampling distribution, Qian et al. (2021) rely on prior knowledge of smoothness constants that can be computationally intractable to obtain in practice when the dimension of the model parameter is high. We propose an adaptive sampling strategy for L-SVRG and L-Katyusha that learns the sampling distribution with little computational overhead, while allowing it to change with iterates, and at the same time does not require any prior knowledge on the problem parameters. We prove convergence guarantees for L-SVRG and L-Katyusha for convex objectives when the sampling distribution changes with iterates. These results show that even without prior information, the proposed adaptive sampling strategy matches, and in some cases even surpasses, the performance of the sampling scheme in Qian et al. (2021). Extensive simulations support our theory and the practical utility of the proposed sampling scheme on real data.

Published in Transactions on Machine Learning Research (03/2023)
L-SVRG and L-Katyusha with Adaptive Sampling
Boxin Zhao
bosina Couzinzuuchhcago.. eduu blyu@chicaggboothh edu mkolar Aiholar@chicaggbooott edu
Boxiang Lyu
Mladen Kolar
The University of Chicago Booth School of Business
Reviewed on OpenReview: https: // openreview. net/ ftt//form? id- 9lygt3rbDe
Abstract
Stochastic gradient-based optimization methods, such as L-SVRG and its accelerated vari- ant L-Katyusha (Kovalev et al. 2020), are widely used to train machine learning models. The theoretical and empirical performance of T-SVRG and L-Kattusha can be improved by sampling observations from non-uniform distribution (Qian et al., 2021). However, designing a desired sampling distribution requires prior knowledge of smoothness constants, which can be computationally intractable to oblain in practice when the dimension of the model parameter is high. To address this issue, propose adaptive sampling strategy for L-SVRG and L-Katyusha that can learn the sampling distribution with little computa- tional overhead, while allowing it to change with iterates, and at the same time does not require any prior knowledge the problem parameters. We prove convergence guarantees for L-SVRG and L-Katyusha for convex objectives when the sampling distribution changes with iterates. Our results show that even without prior information, the proposed adap- tive sampling strategy matches, and in some cases even surpasses, the performance of the sampling scheme in Qian al. (2021) Extensive simulations support theory and the practical utility of the proposed sampling scheme real data.
1 Introduction
We aim to minimize the following finite-sum problem:
1 Σ f((x),
min F(x) ZER
(1)
where each fe convex, differentiable, and I,-smooth see Assumptions 1 and 2 Section The mini- mization problem in (1) ubiquitous in machine learning applications, where fa(z) typically represents the loss function the i-th data point of model parameterized by We denote the solution to (1) as x* However, due to computational concerns, it is typically solved via a first-order method [Bottou et al. 2018
When the sample size n is large, computing the full gradient FF(x)) can be computationally expensive, and stochastic first-order methods, such as stochastic gradient descent (SGD) (Robbins & Monro 1951), are the modern tools of choice for minimizing
Since SGD itcrates cannot converge to the minimizer without decreasing the stepsize due to nonvanishing variance, number of variance-reduced methods have been proposed, such SAG (Schmidt al.) 2017) SAGA (Defazio et al., 2014), SVRG (Johnson & Zhang 2013), and Katyusha (Allen-Zhh 2017). Such methods can converge to the optimum of (1) even with a constant stepsize. In this paper, we focus on L-SVRG and L-Katyusha (Kovalev et al. 2020), which improve on SVRG and Katyusha by removing the outer loop in these algorithms and replacing it with a biased coin-flip. This change simplifies parameter selection, leads to better practical performance, and allows for clearer theoretical analysis.
Stochastic first-order methods use computationally inexpensive estimate of the full gradient VF(x:) when minimizing [1. For example, at the beginning of round SGD randomly selects [n] according to

---

Published in Transactions on Machine Learning Research (03/2023)
sampling distribution p' over [n], and forms an unbiased estimate Vi, (z) of VF(z). Typically, the sampling distribution p' is the uniform distribution, p'= =1/n,,.... ............... 1//),, for all L. However, using a non- uniform sampling distribution can lead to faster convergence (Zhao & Zhang 2015 Needell et al. 2016 Qian
ict al. 2019 Hanzely & Richtárik, 2019 Qian et al. 2021h. For instance, when the sampling distribution is ps ( ". with p!º = 1 4,)= = L, (nb), the convergence rale L.-VRR and L-Katyusha can be shown to depend on the average smoothness I. == (1/n) Ei= Li, instead of the mazimum smoothness Lixx= = maxigisn Li (Kovalev et al., 2020). Sampling from a non-uniform distribution is commonly referred to as importance sampling (IS).
While sampling observations from pS can improve the speed of convergence, p depends on the smoothness constants {Li)semn] In general, these constants are not known in advance and need to be estimated, for example, by computing sup=eR" ( (V)), E [x], where Amax(.) denotes the largest eigenvalue of a matrix. However, when the dimension is large, it is computationally prohibitive to estimate the smoothness constants, except in some special cases such as linear and logistic regression. In this paper, we develop a method to design a sequence of sampling distributions that leads to the convergence rate of L-SVRG and L-Katyusha that depends L, instead of Lmax, without prior knowledge of {Li)een).
Instead of designing a fized sampling distribution, where p' = p for all t, we design dynamic sampling distribution that can change with iterations of the optimization algorithm. We follow a recent. line of work that formulates the design of the sampling distribution as an online learning problem (Salehi et al. 2017] Borsos et al., 2019: Namkoong et al. 2017 Hanchi & Stephens] 2020 Zhao et al.) 2021). Using the gradi- ent information obtained in each round, we update the sampling distribution with minimal computational overhead. This sampling distribution is subsequently used to adaptively sample the observations used to compute the stochastic gradient. When the sequence of designed distributions is used for importance sam- pling, we prove convergence guarantees for L-SVRG, under both strongly convex and weakly convex settings, and for L-Katyusha under the strongly convex setting. These convergence guarantees show that it is pos- sible to design a sampling distribution that not only performs as well as p but can also improve over it without using prior information. We focus on comparing with pd as it is the most widely used fixed sampling distribution (Qian et al. 2021) and leads to the best-known convergence rates with fixed sampling distribution (Zhao& & Zhang] 2015 Needell et al. 2016).
Contributions. Our paper makes the following contributions. We propose an adaptive sampling algorithm for L-SVRG and L-Katyusha that does not require prior information, such as smoothness constants. This is the first practical sampling strategy for these algorithms. We prove convergence guarantees for L-SVRG under both strong and weak convexity, and for L-Katyusha under strong convexity, using a sequence of sampling distributions that changes with iterations. These theoretical results show when the sequence of sampling distributions performs as well as p'S, and even outperforms it in some cases. Our numerical experiments support these findings. We also show that the control variate technique in SVRG and adaptive sampling reduce variance from different aspects, as demonstrated in a simulation. We conduct extensive simulations to provide empirical support for various aspects of our theory and real data experiments to demonstrate the practical benefits of adaptive sampling. Given its low computational cost and superior empirical performance, we suggest that our adaptive sampling should be considered as the default alternative to the uniform sampling used in L-SVRG and L-Katyusha.
Related work. Our paper contributes to the literature on non-uniform sampling in first-order stochastic optimization methods. Previous work, such as Zhao & Zhang (2015), Needell et al.) (2016), and Qian et al. (2021), studied non-uniform sampling in SGD, stochastic coordinate descent, and L-SVRG and L- Katyusha, respectively, but focused on sampling from a fixed distribution. In contrast, we allow the sampling distribution to change with iterates, which is important as the best sampling distribution changes with iterations. Shen et al. (2016) studied adaptive sampling methods for aariance-reducing stochastic methods, such as SVRG and SAGA, but their approach requires computing all gradients (a')] at each step, which is impractical. Our method only requires computing the stochastic gradient ff. (z'). The sampling distribution can be designed adaptively using an online learning framework (Namkoong et al. 2017: Salehi
et al. 2017 Borsos et al. 2018 2019; Hanchi & Stephens, 2020 Zhao et al.) 2021j. We call this process adaptive sampling, and its goal is to minimize the cumulative sampling variance, which appears in the convergence rates of L-SVRG and L-Katyusha (see Section
3 More specifically, Namkkong et al. (011))
2

---

Published in Transactions on Machine Learning Research (03/2023)
and Salehi et al. (2017) designed the sampling distribution by solving multi-armed bandit problem with the EXP3 algorithm. [oosss et al. (2018) took an online convex optimization approach and made updates to the sampling distribution using the follow-tte-regullaizeeeeee the class of distributions that is a lincar combination of a set of given distributions and used an online Newton method lo updale the weights. HHanchi Stephens (2020) and ZZhao et al. (2021) investigated non- stationary approaches to learning sampling distributions. Among these works, /Zhao et al. (2021) the only one that compared their sampling distribution to a dynamic comparator that can change with iterations without requiring stepsize decay. While our theory quantifies the effect of any sampling distribution on the convergence rate of T-SVRG and T--Katyusha, we use the OSMD sampler and AdaOSMD sampler from Zhao 2021p, as they lead to the best upper bound and yield the best empirical performance.
algorithm. [orsoss et al. (2019) considered
et al.
Notation. For a positive integer n, let [n] = fl....,,. .n). We use || to denote the 12-norm in the Euclidean space. Let Pn-1 {a E CR >i= =, 1; 2 0,J E [n]] be the (n 1)-dimensional simplex. Rddd we use (A) to denote its largest cigenvalue. For vector z E Rd, we
For symmetric matrix use xy or =[j]] to denote its j-th entry. For two sequences {an) and [bx]; an O(b)) if there exists C 0 such that la,//bl S C for all large enough; a, O(b,) if an O(b,) and 6, Oan)) simultaneously.
Organization of the paper. In Section 2 we introduce the algorithm for designing the sampling distribu- tion. In Section 3 we give the convergence analysis. Extensive simulations that demonstrate various aspects Section illustrates an application to real world data. Finally, we
of our theory are given in Section
!
conclude the paper with Section 6
2 AS-LSVRG and AS-LKatyusha
To solve ( using SGD, one iteratively samples i, uniformly at random from [n] and updates the model parameter by x=+1 + x' - ff, However, due to the non-vanishing variance f. (x'),, xf cannot converge to x² unless one adopts diminishing step size by letting - O. To address this issue, L- SVRG (Kovalev et al. 2020) constructs an adjusted estimated of the gradient g' = (x,"))) Vi, (i,("') VF(w"), where w' is a control variate that is updated to x' with probability p in each iteration. Note that g" is still an unbiased estimate of Fx("). Since both x' and w² converge to x², we have V[g"] + O, and thus x' can converge to x² even with constant step size. L-Katyusha incorporates a Nesterov-type acceleration to improve the dependency of the compulational complexity on the condition number under the strongly convex setting (Kovalev et al. 2020
Qian et al. (2021) investigated sampling & from [n] using non-uniform sampling distribution to achieve laster convergence. Given the model parameter x' at iteration 4, suppose that it is sampled from the distribution p' (of....,h)). Then
(V) VF(w") npt.
is an unbiased estimate of Fz(z'). The variance of g" is
v [ = V2 (p') - -
where
a V (p') = n Σ V/(xa* V
(2) We let V (p') = [gg]] be the sampling variance of the sampling distribution p', and V (p') be the effective variance. Therefore, in order to minimize the variance of g', we can choose p' to minimize (p'). Let p = arg min pep, Vi (p') be the oracle optimal dynamic sampling distribution at the b-th iteration, which has the closed form
[V/((²²)) Vi((w)) D'+,1= Ej (f) (xf) - (f())")
E [m].
However, we cannot compute P in each iteration, since computing it requires knowledge of all (z and (V]((w))] If that were the case, we could simply use full-gradient descent, and there would be
3

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm 1 AS-LSVRG
Input: stepsizes (1) P E (0,1).
Initialize: xº w p (1/n.-.. 1/n). for 1= 1,... - do
Sample is from [n] with p' = (pi. p()).
5: g" np: (Vi, - (w'))))) + F Fw")
ntt1 x² meg..
w+t ++ x²
with probability p.
7:
wt with probability 1 p.
8: Update p' to p by OSMD sampler (Algorithm 3 or AdaOSMD sampler (Algorithm
9: end for
Algorithm 2 AS- AS-LKatyusha
1: Input: stepsizes (nh21, E (0, 02,02 E 00,1),0x<<1, ~>0 Initialize: e w = 20
for t 1, 1.....,,,.. - do
x' = 012² 82w2 + 01 02)p'.
Sample is from [n] with p' (pi..... ,.))..
6: g' npi, (Vfi(x)) - fi, (w))) + F(w").
21 Itme (nex 2' ggg)
8: g+ = x² 10+00(22tt =²).
wt1 f(r
oz with probability A.
w² with probability 1
10: Update De to pt by OSMD sampler (Algorithm 3 or AdaOSMD sampler (Algorithm 4
11: end for
need for either sampling or control variate. Therefore, some kind of approximation of p is unavoidable for practical purposes.
Qian et al. 2021) proposed substituting each || V fx(')) V(((") with its upper bound. Based the
smoothness assumption (Assumption 2 in Section 3 we have | - S LiI|=' -|ll',=wl,, Thus, by substituting fx') - f((w")]] with L. LaIla* w in 2 we obtain an approximate sampling distribution ps = (p ....,... ......pp))) with P! L./(E L.) Li/ (nL). L-SVRG and L-Katyusha that use p can achiove faster convergence compared to using uniform sampling (Qian et al. 2021). However, one difficulty of applying SS in practice that we need to know L, for all == I,..., n. While such information can be easy access in some cases, such as in linear and logistic regression problems, it is generally hard to estimate, ospecially when the dimension of the model parameter is high. To circumvent this problem,
recent work has formulated the design of the sampling distribution as online learning problem (Salehi ett al. 2017 Borsos et al. 2019 Namkoong et al.] 2017 Hanchi & Stephens 2020 Zhao et al. 2021 More specifically, at each iteration f, after sampling & with sampling distribution p', we can receive information about (x') ff, (w")ll Although we cannot have [[Vf.(z'') f fw"))l for all illi= i n, the partial information obtained from ft, (x=*) ) Vfe, (w=))))== and (p*) {p=) helpful in constructing the sampling distribution r+1 minimize (p').. In this paper, we adapt the methods proposed in Zhao et al. (2021) for L-SVRG and L-Katyusha and apply them in our experiments; however, our analysis not restrictive to this choice and can fit other methods well.
We introduce our modifications of L-SVRG and L-Katyusha that use adaptive sampling, namely Adaptive Sampling L-SVRG (AS-LSVRG, Algorithm [ and Adaptive Sampling L-Kalyusha (AS- (AS-LKalyusha, Algo- rithm 2 The key change here that instead of using a fixed sampling distribution p' = p, 2 0, we allow the sampling distribution change with iterations and adaptively learn it. More specifically, Step g of Algorithm [ and Step 10 of Algorithm use use OSMD sampler or AdaOSMD sampler (Zhao et al. (021] update the sampling distribution, which described in Algorithm g and Algorithm respectively. While
4

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm 3 OSMD sampler
1: Input: Learning rate yi parameter a E (0, 1], A = Pa--1 Pa-in(a/M, number of iterations T.
2: Output: pl for = 1, I..
Initialize: p' (1/n....11/m) 1/m).
for t= 1, 1.
do
Sample it from [n]] by p². Let at, - (V) (w
6:
Compute the sampling loss gradient estimate (V. E RR: all entries are zero except for the i--th entry, which is
[Vd(D')] = n² (F..))
(4)
Solve p 1+ arg min 7(p, (P') + Do (pllp') using Algorithm 5 with the learning rate 7)-
8: end for PEA
Algorithm AdaOSMD sampler
1: Input: Meta-algorithm learning rate y; expert learning rates E {m S 722 S S 1 E (0.1);
A = 1 x Number of iterations T.
2: Output: pº for = I....,T.
3: Set 0% = (1 + 1//HH/((hhh +)), h [M].
Initialize: p/ (1/n,..,,1/n) for h [H].
for t= 1, 2, ..,, T do Compute p" >>== O/Pp,
Sample i, from [n]] by p¹. Let of, (V)x Via, (w0))2
8: for h = 1, ...... H do
9: Compute the sampling loss estimate
a
V. (ph:p') n² pi.ph.
(5)
10: Compute the sampling loss gradient estimate VV: p') E R": all entries are zero except for the 4- entry, which
(p'pp)'') = 1
of
(6)
n² vl, (wh.,,) )a
11:
Solve Ph arg min mh mA, VV. Do (p)) using Algorithm 5 with the learning rate Th
12:
end for
13: Update the weights of each expert
8% exp VV p')}
0++1
h e [M].
ΣM= 0g exp
D2 f (p)
14: end for
the OSMD sampler and AdaOSMD sampler allow for choosing a mini-batch of samples in each iteration, here we focus on choosing only one sample in each iteration. We choose & to be the unnormalized negative entropy, that is, ((x) Σn 2; log I; Er= Tie x (f),...,,,,) E [0, oo)", with 0 Ooo 0 defined as Additionally, Da (a () ((x) ((v)) (V x v) the Bregman divergence between any æ, y (0, oo)"
with respect. to the function T

---

Published in Transactions on Machine Learning Research (03/2023)
Algorithm OSMD Solver: Solve p ++1 arg ge n/q. ú') + (o(q
1: Input: p¹, û', A Pn- [a/n, oo)". Learning rate 17.
2: Output: pt+1
Let pt+1 ( Ji=1 in non-decreasing order: 1+ Pa(1) ... S
exp (-mū)) for [n].
Sort {F/
7+1
Pa(n)
5: Let v, 7(1)
.++1 (1 a for i E [n].
6: Let : E.E=iPat
g++1 for E [n].
Find the smallest such that > 24, denoted as i..
++1 aa/n
if (1) <4
8:
Let Ps
((1 ((i. ((t.-1)/aa 1)/n)a)p;"") / (E)=,. g++1
otherwise.
The key insight of the OSMD Sampler is to use Online Stochastic Mirror Descent 2020) to minimize the cumulative sampling loss Et (2(),, where V2(p") defined in 2 To apply OSMD.
Lattimore & Szepesvári
we first construct unbiased estimate of the gradient of (p'),, which is shown in (4
Then, in Step 7
we update the sampling distribution by taking a mirror descent. Intuitively, the optimization objective in Step/iinvolee two terms. The first term encourages the sampling distribution to fit the most recent history, while the second term ensures that it does not deviate loo far from the previous decision. By choosing a learning rate 77, we keep a trade-off between these two concerns. A larger learning rate implies a stronger fit towards the most recent history. To automatically choose the best learning rate, AdaOSMD uses a set of expert learning rates and combines them using exponentially weighted averaging. Note that the total number of iterations T is assumed to be known and used as input to AdaOSMD. When the number of iterations 7' is not known in advance, Zhao et al. 2021 proposed doubling trick, which could also be used here. The set of expert learning rates is given by
log 27
E
2h-1
h 1 ... H H
(7)
3
where
4 llo(mn/a)
H 11, loga
1+
(T (T-1))
(8)
logn
The learning rate in AdaOSMD is set to 7 Tat where a max4e[m) [[]]()))]] in this paper, we set a = 0.4.
For all experiments
The main computational bottleneck of both the OSMD sampler and the AdaOSMD sampler is the mirror descent step. Fortunately, Step 7 of Algorithm 3 and Step II of Algorithm A can be efficiently solved by Algorithm 5 The main cost of Algorithm comes from sorting the sequence {
be done with the computational complexity of Iog...). However, note that we only update one entry of p to get p'+1 and pe is sorted in the previous iteration. Therefore, most entries of p'+1 are also sorted. Using this observation, we can usually achieve a much faster running time, for example, by using an adaptive sorting algorithm [Estivill-Castro & Wood 1992).
J==1 f which
3 Convergence analysis
We provide convergence rates for AS-LSVRG (Algorithm D and AS-LKatyusha (Algorithm 2 for any sampling distribution sequence (p')r20 We begin by imposing assumptions on the optimization problem
[
Assumption (Convexity). For each E [n], the function Si(:) is conver and first-order continuously differentiable:
M(x) 2 ((()) (V x v) for all x. Rd.

---

Published in Transactions on Machine Learning Research (03/2023)
Assumption 2 (Smoothness). For each i E [n], the function fi is L--smooth:
[V/()) Vs(G))I T4Ilx vll for all x,y R
Furthermore, the function F Ly-smooth:
V - & LF 1 vll for all v, E Rd.
Recall that L (1/n) Ei=1 L, and Lmax = maxigisn Lg By the convexity of and Jensen's inequality, we have that Lp S L. For some results, we will assume that is strongly convex.
Assumption 3 (Strong Convexity). The function F(-) is p-strongly conver:
F(x) 2 ( x y) +
2 211z yl
for all v, R where p > 0.
Additionally, the optimization heterogeneity defined as
o [+
(9)
and the smoolhness helerogeneily is defined as Lmaxx! L.
3.1 Convergence analysis of AS-LSVRG
We begin by providing convergence rate for AS-LSVRG (Algorithm) 1
under strong convexity. Let
D' 1
L Vl((w') VA(+*))
(10)
Roughly speaking, D measures the weighted distance between control-variates w and the minimizer x where the weights the inverse of Lipschitz constants.
Theorem 1. Suppose Assumptions hold. Let Ntt n for all t, where n 1/(6Ž + LF), and let
01 max {1 mp1
2
Then
4n² 1²1 D
4n L
T
E |
<
1 - x11
D
+
T E [V.. (p')
V2 (p r)]
p
L=
See proof in Appendix distribution sequence should minimize the cumulative sampling variance Et=o dj - [V' (p')). This justifies the usage of AdaOSMD to design a sequence of sampling distributions, as its purpose is to minimize the cumulative sampling variance
A.1
From the convergence rate in Theorem
we observe that good sampling
(Zhao et al. 2021
When
of [v'
E
(p') - Ve 0
(11)
t=0
the iteration complexity achieve c-accuracy is O(1/(lo((1/a))) (g(() When = 1 and both L/μ and n are large, this bound is (oggL))) which recovers the complexity of L-SVRG when sampling from Is (Qian et al. 2021

---

Published in Transactions on Machine Learning Research (03/2023)
When 11 holds, can further compare the iteration complexity of AS-LSVRG with the iteration complex- ity of SGD with importance sampling from p which is ((()) (n/e) + 1/p) log(1/ /e)), where of is defined in 99 NNedelll et al. 2016), and the iteration complexity of L-SVRG, which is O((n + Lmax/ (u) log log(1/))) Kovalev et al.] 2020). First, we observe that the iteration complexitics of AS-LSVRG and L-SVRG do not depend on or, while the iteration complexity of SGD does. This shows that the control-variate improves upon optimization heterogeneity. Second, we observe that both itcration complexities of AS-LSVRG and SGD depend on L, while the iteration complexity of L-SVRG depends on Lmax. This shows that adaptive sampling improves upon smoothness heterogeneity. Based on these two observations, have the following important takeaway:
While both the control-variate and adaplive sampling are reducing the variance of stochastic gradient, the control-variate is improving upon optimization heterogeneity, and adoptive sampling is improving upon smoothness heterogeneity.
Another important observation is that when p' = pt, we have V2 (p.) < V2 (p'S). Therefore, the perfor- mance of the oracle optimal dynamic sampling distribution is at least good as the fixed sampling distribu- tion ptS. The gains from using dynamic sampling distribution can be significant, as show in experiments in Section ! and Section 5 While the closed form of 9 in (3) requires knowledge of ff((z") Vf((w'),
which is not available in practice, we minimize the cumulative sampling variance Σt= V. (p') sequen- tially using AdAOSMD, which results in the approximation p", without the need for prior information. We discuss in Section 3.3 below when this adaptive sampling strategy can perform better than p
The following result provides the convergence rate when F(x) is weakly convex.
Theorem 2. Suppose Assumptions and hold. Let ne n for all t, where n S 1/(6Lp), and let a
(1/T) Ei= x². Then
E [F(*") - F(*))] S (F(x")- - -)()))
T
5
1
11000 x² 211²+
12 PP) (F(w") -F(=)) T
37 }
> t=0
E V2 (p') V2' (p'))
T 2m
5p
See proof in Appendix A.2 In the weakly convex case, the cumulative sampling variance is defined as ΣT [V (p')), and a good sampling distribution sequence should minimize it. When n 1/(6L
p 0=1/n, and Σn E [V= (p') Va (p = O(T(LF + n)), the iteration complexity to reach e-accuracy is O(LL + ()/c/)) which recovers the rate of L-SVRG when sampling from p is Qian et al. 2021)
3.2 Convergence analysis of AS-LKatyusha
We prove a convergence rate for AS-LKatyusha (Algorithm under strong convexity. Let
z L(1 nett)
||2 12'-='11 112,
21/
V2 = (F('') - -F(x)),
(12)
0,
W 02 + +1)
(F(w*) F(**)),
p0,
and ve := 2t + Dc + W We then have the following theorem. See proof in Appendix A.3
Theorem 3. Suppose Assumptions hold. Let Te = n for all t, where r = ((1 + 0z) 02 and //T.
with L = L. Let 0₂ 1/2, 0, < 1/2, and
01
p0
02 = max
1 +
2
1 1 0
8

---

Published in Transactions on Machine Learning Research (03/2023)
Then
T-1
02 40
T r---1 Q2
-
V2 (p') V22 (D(S))
4L00
The cumulative sampling variance is defined as Σt= 02 op--tI (p')), and can be used as the minimization objective to design a sequence of sampling distributions. When = 1/n, 01 = Sain(22kn/ 1/2], and BB [v. (p') V (p [)] O(a²), then the iteration complexity to reach c-acouracy is O(
EnD 02 B
V (L//H) log(1/)), which recovers the rate of L-Katyusha when sampling from p rS Qian et al. (2021)
Additionally, when compared with the rate of L-Katyusha Kovalev et al. (2020), we see that the dependency Lmxx is improved to L, which is consistent with conclusion in Section 3.1 that adaptive sampling is responsible for improving smoothness heterogeneity.
3.3 Benefits of adaptive sampling
We analyze when adaptive sampling will improve over sampling from p We first emphasize that sampling from p requires knowledge of Lipschitz constants {Li [Lj))))) which, in general, are expensive to compute. On the other hand, the additional computational cost of adaptive sampling is usually comparable to the cost of computing a stochastic gradient.
In addition to computational benefits, there are certain settings where adaptive sampling may result in improved convergence, despite not using prior information. key quantity to understand is
AV (v""))
Σ t=
a B V2 VV' (p')),
where E {a1, 02 1), depending the algorithm used and the assumptions made. The larger AV 1:7) is, the more beneficial adaptive sampling is. In the following, we discuss when (V(p!:)) is large. Although p. is not available in practice, (V(p!:)) 1:?') can be used to understand when adaptive sampling methods that approximate pf, will be superior to using S for importance sampling.
(p)))
In many machine learning applications, f((z) has the form f.(x) (,). where & is the i-th data point. Let at E Rd be such that (,) 0. Then [[V[(()]]| [VV((,, Vi(a G)ll- This way, we see that the variability of norms of gradients of different data points has two sources: the first source is the difference between &'s, the second source is the difference between xt s. We name the first source as the contexl-shifi and the second source as the concept-shift.
When fz(z) is twice contimuuusy differcntiable, we have
Li sup Amax (V² sup Amax (V))( ZERd
ZER"
Thus, when we use SS to sample, we ignore the concept-shift and only leverage the context-shift with the sampling distribution. As result, Is is most usefull when the context-shift dominates. On the other hand, adaptive sampling takes both the concept-shift and contexi-shift into consideration. When the major source of gradient norm differences is the concept-shift, adaptive sampling can perform better than sampling from SS. This is illustrated in Section 4.3
4 Synthetic data experiment
We use synthetic data to illustrate our theory and compare several different stochastic optimization al- gorithms. We denole L-SVRG + uniform sampling as L-SVRG, L-SVRG + oracle optimal sampling as Optinal-LSVRG, and L-SVRG + sampling from p as IS- IS-LSVRG. Similarly, we define SGD, Optimal-SGD, IS-SGD, I-Katyusha, Optimal-LKatyusha,, and IS-LKatyusha. Additionally, AS-LSVRG and AS-LKatyusha refer to Algorithm D and Algorithm 2 with the AdaOSMD sampler (Algorithm 4 respectively, except in Section 4.4 where the OSMD Sampler (Algorithm 3

---

Published in Transactions on Machine Learning Research (03/2023)
We set p= p=1/n 1/n for all algorithms.
The algorithm parameters for L-Katyusha with all sampling strategies are set according to Theorem 3 where I, = I, for Optimal--KKatyusha and IS-L.aayusha, and I. Imax for L-SVRG. For AS-LKatyusha, we set L = 0.4Lmax + 0.6L. As for the parameters of AdaOSMD, they are configured as stated in Section
2 when choosing a mini- bni-batch of samples in cach iteration, we set them
according to Zhao el al. (202
Data generation: We generate data from linear regression model: b, -0", aa) + Co where as Ltd. s; s0,, Σ) with Σ diag(25~ .... 25 and 8, lid. eN(.2" St i.d. NO0, and the entries of 0 are generated i.i.d. from N(10.0, 3.0²). We let fi(x) = 1x;; az by), where 1a;;;; b.) = (1/2) (x. )²))² is the square error loss. In this setting, the variance o² controls the optimization heterogeneity in ( with larger o² corresponding to larger optimization heterogeneily, while v controls the smoothness heterogeneity, with larger y corresponding to larger smoothness heterogeneity. Under this model, the variability of the gradient norms primarily caused by the differences between b which corresponds to the context-shift. As result, we expect that sampling according to p would perform similarly to oracle optinal sampling, Note that in this setting, we have L, |a:11? set 100, d 10, and report results averaged across 10 independent runs.
set p! = [[)= ||a]ll²) for all = I....,n. We
4.1 SGD v.s. L-SVRG
We compare SGD and Optimal-SGD with L-SVRG and Optimal-LSVRG. From the results in Figure we have three main observations. First, with large optimization heterogeneity (rightmost column), Optimal- LSVRG converges faster and can achieve a smaller optimal value compared to Optimal-SGD. This observation is consistent with our conclusion in Section 3.1 that the control variate is responsible for improving opti- mization heterogeneity. Second, Optimal-LSVRG always improves the performance over L-SVRG, with the largest improvement observed when the smoothness heterogeneity is large (bottom row). This observation illustrates our conclusion that importance sampling can improve smoothness heterogeneity. Finally, we ob- serve that L-SVRG is more vulnerable to the smoothness heterogeneity compared to SGD, which can also be seen from the condition on the step size: we need 1) S 1/(6Lmax) for L-SVRG (Theorem 5 of Kovalev et al. (2020b) and we only need r) S 1/ Lmax for SGD (Theorem 2.1 of Ncodell et al. (2016) to ensure convergence.
4.2 Non-uniform sampling for L-SVRG and L-Katyusha
We compare L-SVRG and L-Katyusha with different sampling strategies. Figure shows results for L-SVRG. We observe that the performances of Optimal-LSVRG and IS-LSVRG are similar, since the context-shift dominates the variability of the gradient norms. Furthermore, we see that adaptive sampling improves the performance of L-SVRG compared to uniform sampling. The improvement most significant when the smoothness heterogeneity is large (bottom row).
Figure 3 shows results for L-Katyusha. We set the step size according to Theorem 3 The oracle optimal sampling distribution results in considerable improvement over sampling from p after adding acceleration. In addition, note that adaptive sampling efficiently improves over uniform sampling.
4.3 Importance sampling v.s. adaptive sampling
We provide an example where adaptive sampling can perform better than sampling from pT.. We generate data from a linear regression model 6; (0*,a) + Çi, where 4 iid. (00 0.5²) and, for each a, e Rd, we choose uniformly at random one dimension, denoted as supp(i) [d], and set it to a nonzero value, while the remaining dimensions are set to zero. The nonzero value d<(supp(i) is generated from N(100, 0.12). The entries of 0* are generated i.i.d. from N(0,22) Therefore, controls the variance of entries of 0*. We let = 300 and d = 30.
In this setting, we have L, = 1| = la. [s] ~ 1.0, and thus sampling from p will perform similarly to uniform sampling. On the other hand, we have
[V/(()]] = 1(x 0*)) (supp(i)) a as(supp(i)] Gil-
10

---

Published in Transactions on Machine Learning Research (03/2023)
5.4
4.5
v=0.0 Ir=0.1 log(
5.2
4.0
3.5
5.0
3.0
4.8
2.5
500
1000
0
500
1000
0
500
1000
v=0.5 Ir=0.05
5.5
log(loss)
5.0
500
1000
0
500
1000
0
500
1000
7
y=1.0 v=1.0 Ir=0.005
1oog cilosss
5
500
1000
0
500 t
1000
0
500
1000
t
t
0.0
o= 5.0
15.0
SGD
LSVRG
Optimal-LSVRG
Optimal-SGD
Figure Comparison of four methods: SGD, Optimal-SGD, L-SVRG, and Optimal-LSVRG. Columns correspond to different a values, while rows correspond to different v values. The stepsize the same for all algorithms, and is 0.1 when 0, is 0.05 when 0.5, and is 0.005 when 1.0.
Thus, the variability of the gradient norms is mainly determined by the variance of entries of 6*, For cach E [n], we can understand fi as separate univariate quadratic function with the minimizer (supp((i)) and the variance entries of can be understood as the concept-shift. this case, we expect that sampling from pS will not perform as well oracle optimal sampling or adaptive sampling.
We implement Optimal-LSVRG, IS-LSVRG, and AS-LSVRG with the stochastic gradient obtained from mini-batch of size 5, rather than choosing only one random sample, to allow adaptive sampling to explore more efficiently[T The step size is set to 0.3. Figure 4 presents the results. We see that as v increases, the gap between oracle optimal sampling and sampling from p increases as well, due to the concept-shift. In addition, we see that adaptive sampling also performs better than sampling from 'S despite the fact that it does not use prior knowledge, since adaptive sampling can asymptotically approximate oracle optimal sampling.
1 AddOSMD relies the feedback obtained by exploration update the sampling distribution. larger batch size will allow aduptive sampling explore efficiently (in other words, to 'sec' samples each iteration). Compared with the fixed sampling distribution, where larger batch size is only reducing the variance of stochastic gradient, larger batch size will also help adaptive sampling make faster updates strttgyy generally more sensitive batch size than sampling with fixed distribution.
sampling distribution. Therefore, the adaptive sampling
11

---

Published in Transactions on Machine Learning Research (03/2023)
5.4
v=0 Ir=0.1
5.2
logil N
log
5.0
4.8
500
1000
500
1000
500
1000
v=0.5 1r=0.05
5.5
log(ioss
5.0
500
1000
0
500
1000
0
500
1000
y=1.0 Ir=0.005
WA
(lo(ss))
BA
5
500
1000
0
500
1000
0
500
1000
t
t
0.0
0= 5.0
0= 15.0
LSVRG
Optimal-LSVRG
IS-LSVRG
AS-LSVRG
Figure 2: Comparison of four methods: L-SVRG, Optimal-LSVRG, IS-LSVRG, AS-LSVRG. Columns cor- respond to different a values, and rows correspond to different v values. The stepsize is the same for all algorithms, and is 0.1 when v = 0, 0.05 when v = 0.5, and 0.005 when v = 1.0.
4.4 Nonconvex Objective
In this section, we compare L-SVRG, IS-LVVR,, and AS-LSVRG with nonconvex objectives under similar setting as in Section 4.2 We increase d to 100 and n to 1000. Instead of fitting the data with linear regression, we use a two-layer neural network with 10 neurons in the hidden layer. While we still minimize the mean squared error loss, the objective function now nonconvex due the nonconvexity the neural network model. To estimate 18, we still set ! ||a; IP/ ||a,|? as Section 4.2 For AS-LSVRG. we use the OSMD Sampler (Algorithm 3) Both the optimization step size and the learning rate of the OSMD Sampler are tuned such that AS-LSVRG converges at the fastest speed.
The result is shown in Figure We see that adaptive sampling still obtains an advantage over uniform sampling and importance sampling, especially when the smoothness heterogeneily is large. It is worth noting that pS does not perform well in this case. We suspect that this because ||a;]| is poor estimate of L; in this case; however, is unclear if there exists an casy way to accurately estimate L, with nonconvex models. This result justifies the motivation of adaptive sampling since it can achieve advantagcous performance over uniform sampling without the need to estimate the smoothness constants.
12

---

Published in Transactions on Machine Learning Research (03/2023)
5.75
5
5.50
v=0.0 log(llos))
5.25
4
3
5.00
4.75
500
1000
500
1000
500
1000
6.0
5
log(loss)
v=0.5
5.5
4
5.0
3
500
1000
500
1000
500
1000
7
poglloss
6
2
0
500
1000
500
1000
500
1000
0.0
15.0
LKatyusha
Optimal-LKatyusha
15-LKatyusha
AS-
Comparison of four methods: L-Katyusha, Optimal-LKKttysha IS- 1S-LKKtyusha, AS-LKatyusha. Columns correspond different values, and rows correspond to different values. The stepsizes are set based Theorem
Figure 3:
Optim
IS-LSVRG
AS-LSVRG
-0.5
10.0
-1.0
7.5
(loss)
5.0
11.5
-1
2.5
-2.0
0.0
-2
22.5
0
1000
2000
0
1000
2000
1000
2000
0=0.0
1=1.0
v=3.0
Figure 4: Optimal-LSVRG v.s. IS-LSVRG v.s. AS-LSVRG. Columns correspond to different v values.
13

---

Published in Transactions on Machine Learning Research (03/2023)
6
6
6
log
v=0.0
4
4
2
2
4
0
20000
0
20000
20000
8
8
8
v=0.5
log
6
4
2
20000
0
20000
20000
8
8
8
v=1.0 log(loss)
w4
6
6
6
4
20000
0
20000
20000
t
0.0
1.0
5
LSVRG
AS-LSVRG
IS-LSVRG
Comparison of L-SVRG, IS-LSVRG and AS-LSVRG with nonconvex objective. Columns corre- spond different values, and rows correspond different values. The stepsize of each method is tuned such that the method converges in the fastest speed.
Figure 5:
5 Real data experiment
We use the waa dataset from LibSVM classification tasks Zeng et al. (2008); Chang & Lin 2011)p On real dataset, obtaining the theoretically optimal sampling distribution infeasible, while constructing p requires access to Lipschitz constants of each loss function. Therefore, here we only show the performance of L-SVRG and AS-LSVRG on the following logistic regression problem:
min
(u: log + (1- y:) log(1 - pt)),
where pz(z) = p: (1 + exp-272z) y {0.1} is the response variable, and 2 is the d- dimensional feature vector. The stepsizes for both L-SVRG and AS-SVRG are initially tuned over the grid {10-2 2 110-5,100155 1.5 ,..,,,,..0.. 102}. The initial search showed us that the optimal stepsize should be in the interval (0, 1). Therefore, we tune the stepsizes over a grid of 20 evenly spaced points on [0.05, 1]. The two algorithms are then used train the model for 1000 iterations, repeated 10 times, and the best stepsize is chosen by picking the one that corresponds to the lowest. loss at the 1000-th iteration.
14

---

Published in Transactions on Machine Learning Research (03/2023)
w8a, Batch Size
w8a, Batch Size
-0.4
-0.6
-0.6
-0.8
Avg. log(loss)
Avg. (oos)
-1.0
-1.0
-1.2
112
1.4
-1.4
-1.6
-1.6
-1.8
200
400
600
800
1000
200
400
600
800
1000
LSVRG
AS-LSVRG
Figure 6: LSVRG v.8. AS-LSVRG. Columns correspond to different batch sizes.
w8a, Batch Size
w8a, Batch Size 5
-0.4
-0.4
-0.6
-0.6
0.8
0.8
Avg. log(loss)
log
11.0
-1.2
1.2
-1.4
1.4
-1.6
1.6
0
200
400
600
800
1000
0
200
400
600
800
1000
LKatyusha
AS-LKatyusha
Figure 7: L-Katyusha v.s. AS-LKatyusha. Columns correspond to different batch sizes. The stepsizes are set according to Theorem 3.2 from (Qian et al. 2021 and Theorem 3 in this paper.
Figure corresponds the average log cross entropy loss over 10 runs against the number of itcrations. The shaded region corresponds the standard deviation of the loss. When the batch size is 1, AS-LSVRG and L-SVRG have similar convergence behaviour, but the standard deviation is reduced for AS-LSVRG. When the batch size is 5, AS-LSVR significantly outperforms I-SVRG.
We illustrate the performance of L-Kalyusha and AS-LKatyusha by solving the following lz-regularized optimization problem:
min 2E34
(ya log + (1 yi) log(1 pc)) + 2 ||/
71
where p. = (z) has the form as before and μ = 10 to ensure that the problem strongly convex. Figure 7 shows results over 10 runs. AS-LKatyusha significantly outperforms uniform sampling counterpart. While some of the improvement in performance could be attributed our superior dependence on the Lipschitz constant, the losses we obtain enjoy slightly reduced variances.
15

---

Published in Transactions on Machine Learning Research (03/2023)
6 Conclusion and future directions
We studied the convergence behavior of I-SVRG and L-Katyusha when non-uniform sampling with dy- namic sampling distribution used. Compared to previous research, we do not restrict ourselves to a fixed sampling distribution but allow it to change with iterations. This flexibility enables us to design the sampling distribution adaptively using the feedback from sampled observations. We do not need prior information, which can be computationally expensive to obtain in practice, design a well-performing sampling distribu- tion. Therefore, our algorithm is practically useful. We derive upper bounds on the convergence rate for any sampling distribution sequence for both L-SVRG and L-Katyusha under commonly used assumptions. Our theoretical results justify the usage of online learning to design the sequence of sampling distributions. More interestingly, our theory also explains when adaptive sampling with no prior knowledge can perform better than a fixed sampling distribution designed using prior knowledge. Extensive experiments on both synthetic and real data demonstrate our theoretical findings and illustrate the practical value of the methodology.
We plan to extend the adaptive sampling strategy to broader class of stochastic optimization algorithms. For example, stochastic coordinate descent (Zhu al. 2016) and stochastic non-convex optimization algo- rithms (Fang et al. 2018). In addition, exploring adaptive sampling with second-order methods, such as the stochastic Quasi-Newton method (Byrd et al. 2016), could be fruitful future direction.
16

---

Published in Transactions on Machine Learning Research (03/2023)
References
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18:221:1-221:55 2017.
Zalan Borsos, Andreas Krause, and Kfr Y. Levy. Online variance roduction for stochastic optimization. In Conference On Learning Theory, 2018.
Zalán Borsos, Scbastian Curi, Kfrr Yehuda Levy, and Andreas Krausc. Online variance reduction with mixtures. In International Conference on Machine Learning, 2019.
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Oplimization methods for large-scale machine learning. SIAM Review, 60(2):223-3) 221111111111-.1 2018.
Richard H. Byrd, S. L. Hansen, Jorge Nocedal, and Yoram Singer. A stochastic quasi-newton method for large-scale optimization. STAM Journal Optimization, 26(2):1008-1031, 2016.
Chih-Chung Chang and Chih-Jen Lin. Libsvm: a. library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3):1 27, 2011.
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Advances in Neural Information Processing Systems, 2014.
Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithmss ACM Compuling Surveys (CSUR), 24(4):441-47) 1992.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: near-optimal non-convex optimiza- tion via stochastic path-integrated diffcrential estimator. In Advances in Neural Information Processing Systems, 2018.
Ayoub El Hanchi and David A. Stephens. Adaptive importance sampling for finite-sum optimization and sampling with decreasing step-sizes. Advances in Neural Information Processing Systems, 2020.
Filip Hanzely and Peter Richtárik. Accelerated coordinate descent with arbitrary sampling and best rates for minibatches. In International Conference on Artificial Intelligence and Slatistics, 2019.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems, 2013.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: SVRG and katyusha are better without the outer loop. In Algorithmic Learning Theory, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, and John C. Duchi. Adaptive sampling probabilities for non-smooth optimization. In International Conference on Machine Learning, 2017.
Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Mathematical Programming, 155(1-2):549 573, 2016.
Yurii Nesterov.
Lectures on conver optimázation. Springer, 2018.
Xun Qian, Zheng Qu, and Peter Richtárik. SAGA with arbitrary sampling. In International Conference on Machine Learning, 2019.
Xun Qian, Zheng Qu, and Peter Richtárik. L-svrg and I-katyusha with arbitrary sampling, Journal of Machine Learning Research, 22(112):1-47, 2021.
Herbert Robbins and Sutton Monro. A stochastic approximation method. Annols of Mathematical Statistics, 22:400 407, 1951.
17

---

Published in Transactions on Machine Learning Research (03/2023)
Farnood Salchi, L Elisa Celis, and Patrick Thiran. Stochastic optimization with bandit sampling. arXiv preprint Xrvi 1788. 02544, 2017.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient. Mathematical Programming, 162((1-2::3--122 2017.
Zebang Shen, Hui Qian, Tengfei Zhou, and Tongzhou Mu. Adaptive variance reducing for stochastic gradient descent. In International Joint Conference on Artificial Intelligence, 2016.
Zhi-Qiang Zeng, Hong-Bin Yu, Hua-Rong Xu, Yan-Qi Xie, and Ji Gao. Fast training support vector machines using parallel sequential minimal optimization. In International Conference on Intelligent System and Knowleddge Engineering, 2008.
Boxin Zhao, Ziqi Liu, Chaochao Chen, Mladen Kolar, Zhiqiang Zhang, and Jun Zhou. Adaptive client sampling in federated learning via online learning with bandit leedback. Xiv preprint or arXix:21 1122 14332, 2021.
Peilin Zhao and Tong Zhang. Stochastic optimization with importance sampling for regularized loss mini- mization. In International Conference Machine Learning, 2015.
Zeyuan Allen Zhu, Zheng Qu, Peter Richtárik, and Yang Yuan. Even faster accelerated coordinate descent using non-uniform sampling. In International Conference on Machine Learning, 2016.
18

---

Published in Transactions on Machine Learning Research (03/2023)
A Proof of Main Theorems
A.1 Proof of Theorem 1
We use the proof technique from Theorem 5 of Kovalev et al. (020). The key step is to docompose the variance of the stochastic gradient. Let Fz = o (2o, wo, ,i, Wi, ....... de; wx) be the o-algebra generated by zo, Wo, F1, w1 2t, We, and let E+|+] = E Fil be the conditional expectation given Ft.
Note that [g V=(x'). By Assumption 3 we have
Es || 2² 211?² E, 1| "ng* x=1 [12]
= |,=0 - x= 112 - 20 ( (VF(x") x² - x²) + B, [1"011²]
I 1² 2¹1 - 2n (F(x') - F(x') 2 "|20*= =²(1(²) + n [|ss|]]]]
(1 mu) || - x² 1|2 2n (F(x*) - -Fx))) 2 [1|0011]]
(13)
Furthermore, we have
Ec |10 || = E. ||g* - E. [g [0]] + || [
Vi¹ (D') |VF(2') VF(W") |1
V.' (p')) ||VF(22) - VF(W ||//++IIF()))) + (p') Vo: (p's)
L, [/ii2' -
+ +||VF(b')| 12 + (D') - -V¹ (D's)
V v)(ww)) + +|V
+ V2d (p') Vo (p's).
(14)
n
By Assumption and Assumption
2 that F(-) is convex and L Lp-smooth, we have
||/(=>))]][[]()>>>>>>>>>>>>>>>)) -F())) 2LF (F(x') - F(x*))
(15)
With D' in
10
we have
L
Vf((z*) f(())11
21
|/i((')- - v/A''11 + 2L
Σ Vi((w') vf("2))1
i=1 Li
2L "
<
Σ
(2Lx) (Ji(1') - -i(00) (V]i x²)) + 2ID
n
i=1 T4
AL (F(x') F(x*)) +LD''
(16)
Combining
14
16 44 we have
E2
||000]
< 4L (F(x') F(x')) + 2Lr (F(x") - F(z")) + 2LD' + +V' (p') V/ (p))).
(17)
Combining
17 and 13 we have
E2 [1 x= [|]]
$ (1 mH1 ||0t - -x=1 2n(11 - 2n -1n(1-
TTr (F(x*) - -((x')
2n LD' + 172 [V2 (p') - V22 (p))
19

---

Published in Transactions on Machine Learning Research (03/2023)
Using Lemma 4 for any B > 0, we have
E, || x²1 |1|] , [D[+1]
S (1 - mp) || x² 1=(22-22n11
-2nL nbF) - 28p) (F(x") - F(x*))
(22)) L + 3(1 n)) D' +1² (Vē (D') V22 (p'
With 3 = =41/ we have
E, |1 - x=11²]= + 4nj² I. E, [Dr+1]
p
(1 mH) || - x111-
1111-1m(11 211(1 - 6nL nLF) -
(F(z')-((x")) -F(x))
+ A I (1- () D' + n²² [V² (p') - V22 (p
Since 7) S 1/(6L+ LF), we further have
4n Ee [DI+i]= s (1 - mp) 1| =111? + 4112L (1 (1- (1-2) P D' + 12 2)
Eg |||lt| =113]]
(p') - -V (p/))}-
2
Recalling that
@n max {1 11-7/1 17111
p
2
we have
Es | -0-t-==+10 2=1|²
4n1²L
Di+1
(1o-- x01
ArfL + (V: v. (p's))
S 01
P
P
Taking the full expectation on both sides and recursively repeating the above relationship from T to = 0, we have
4nj² L ==111== +
E
10""
DJ
P
21 DT-
S F.
|
x+1| 2=1] +
+ +1 [V_-1 (p"-1)) - V (p's)]
P
4nj
I Du
T
S aafB
E
|100
x=
+ n²
Σ
T T [V' (p') V2 (p's)]
p
t=
A.2 Proof of Theorem
2
We use the technique from Theorem 17 of Qian et al. of the variance of the stochastic gradient. Let
2021
The key difference here is the decomposition
1 217.
1|
112
6n, I( p) D'.
(18)
5p
Let F, = (2o, Wp, I1, W..... Ft, we) be the r-algebra generated by su, wD, 21, W1, Fe, we, and lot E,[1] E[ [F] be the conditional expectation given Fr.
Note that [g]g"] VF(x'). We have
F(**) 2 F(z') + (VF(x'), x²)
= F(x')) + E. ((g x² - x² 20)]
= =(('') + E. [60 x- - x x1
+ E, [9',, 1 - x²)]
F((')) + E, (6 x² - ,
+ E. (gg VF(x") x -
x0) + +E, (VF(('), x Itt1 - -x0)] (19)
20

---

Published in Transactions on Machine Learning Research (03/2023)
By Assumption and
we have
LF
F(z)) -2¹)
=z²) s
|x' xz1l
2
Thus,
LF
F(x') + (VF(2'), xt1 - x²) 2 F(x
12'11 - xz11
2
Combined with 19
we have
F(x*) 2 Ee [[
LF
Ee 2
||00|| - =-11²] x211?
+ Ee (g' x - x')|| + Be (g9 -
- (20)
Since (a. S 2/ [|||||2 + 2 |16l2 for all a, E IRd and B > 0 by Young's incquality, we have
Et - V xz - 2(t1)] s Le (
+
$23
1 Er
B> 0.
Equivalently,
Eg [(g' - FF(z")) x - z4] - ||o VF(=')]
2/ Be
1 2011²,
B> 0.
By Lemma 8 we then have
E, Kgg VF(x') ) x - =z²)
BL " 1 Σ
2 -28.. (F((t) - F(x'))
[Vi((w)) -VS(<*)]1
i=1 Li
8
[v: (p') - Vz (p'))
Es
- =01"]] - (21)
2
2,3
Combine 20 21
and noting that
(0' x (1) (1lt1 x², xx
||- x 2221 + 2n7
|| 201/
x² x²' 11.
2n
2n
we have
F(x)) 2 E. [F(xtt]]]
LF Eg [1 x² [13]
3L n
1
-
3 (V2 (p') - -V² (p
Er,
[| |1 - x=(1"]]
2
2
+ 21
Ee |1/1 - 11
+ 211
1
E,
1+1
x= x011]]
1
x0" - x11
2n
E. [2 + 2n
LF
1
E2
||
x
+2 +2
+
1
E,
||2041 - -=]
1
|at x² 11
2
23
2n
'n
23L (F(xt) - F(x*))
BL.
Σ
1
[i(ww')
3
(V22 (p') Vo' (1))
L
2
1=1
Therefore,
23L (F(x') - F(x')) + 1 {v= (p') - V²2 (p/s)}+
1|22 - 2²11
2
2n
2 E, [1) F(x*)+ +
(1
LF
E, ||a* - 2 11²]
2n
2/
+
1
E,
||
- x 20111]]
.3. 1
||VSi(w') - [)((t)))2
2n
n
L
21

---

Published in Transactions on Machine Learning Research (03/2023)
Then by definition of D' in
10 and Lemma 4 for any 0, we have
2(9L + ap) FFx)) + 2 (v2 (p') - V²2 (p'5)) +
| - -x11² + - p))
27
> E, [( F(x*) + 1
1
Ee |1 - - 11
LF
3
11
+
1
[|| ||22 - x² ||²] +
- (a-
Es [D'+1].
201
sL_ 1ng 5p-
Let B = nn and a
Since 17 - 6 we have
LF
LF S 0. Then
B
on
4 (F(x*) - -F(x*) + 3
5 (p') - Vo (p/5)} +
1
110 -1+1
Gn p) D'
5
2n
5p
24
3
1
|| =011 + G - p) D
2 nL (F(z*) - F(x))) + 5" [V22 (p') - V22 (p' + 2n
|-'-z"|1
5p
2 B4 (F( - F(x*)] + 27
E | - xz1 =-1 +
Gn
L1 p)
E, [Det]].
5p
From the definition of E, in 18 we have
E. [F(att)) F(=*)] E. " 4 (((x))-(=*))) + 5"
3 (v22 (p') - V¹ (D'))
Taking the full expectation on both sides and recursively repeating the above relationship from t= T to t = O, we have
T
T F(x)) " t=0
3 T EE (p') - V2 (p'5))
-F(((tt))F(("")
- +E + - ==9] <
ΣΣ
[(F('))
-55
1=0
which implies that
T E [F(x') - F(x*)]
5 1=1
$ E (F(oT -(x*)+++
+ + +
1 Σ
E [F(x²) F(x*)]
t=1
4 (F(a)) + +
3
T
$ 5
- F(x*))
5" Σ
E [ (p') - V/' (p
By convexity of F(-) and since at = =(1/T) Et= x², we have
4 EE ( s - (F(a))-E(x)))-)))
- F(x')(
-
T
52"
37 T T
Σ
E V2 (p') -v2 (p/s))
t=0
Finally, by Lemma
we have
ED
1
||20 - =11
+ 6nI(1- - p) DO
21
5p
< 2n
1
|1ا00
211
+ 6nI - p)
Σ
(2Ix) (fi(m9) - f1(xt) - (Vii(a'),at xx)))
5p
L
1=1
1
1/00
=0113
+ T. p) (F(w²) - ((x)))F(x'))
< 2m
5p
22

---

Published in Transactions on Machine Learning Research (03/2023)
Thus, we have
E [F((") - F(x*]] $ (F(x")-B3 - -F(x))
T
5 1
1100 x²11² 12 - p) (F(w")- F(x)))
-F(x))
}
3n T
Σ 1=
E
L22 (p')
-V²
V22(p) (p'))]
T 2m
5p
A.3 Proof of Theorem 3
We use the proof technique of Theorem 11 ion Kovalev et al. 2020 The key step is to decompose the variance of the stochastic gradient. We let F, = ( Wo, Co. 20. Ir., W2, 21,2,) 2)) be the o-algebra generated by Io, Wo, ub, 20, It. Wt, Uz, Ze, and let E.l- = E[ Fel be the conditional expectation given Fi
By Assumption we have
F(x)) 2 F(z') + (VF((")) - x²) + 1
2/2 || - x²1|
= F(x') + 11
2 ||0² - -x"1' 112+ [VF(x"),2"" - -2 + (VF(x"), -2)).
(22)
Note that
x' 012¹ + 0zww + (1 - 01 02)0'
Thus
02
01 02
2'
01 W
01
01
and
1 01
02
01
02
O2
01
O2
zº x²
81 w
(s*
w²) +
(x*
r²)
01
Q1
81
01
Since Eg[g'| = VF(x'), combining the above relationships with
22 we have
F(x") 2 F(x') + -0'-='11 (VF(x') x - ==")
2
02 (VF('') x² - -w²) 1 - O1 - O2 (VF(z'), x=='""- -0")
+ 0
Q1
0 (F((')) ), -w')
1- 01 O2 (VF(z'), -
F +
01
+ E,
14
10 x² 1 + (0")='~20)
-207]
2
82
1 1 01 02
= F(x') +
(VF(a ) x' - -w") +
(VF(="), 2²²)
01
01
1
| x= 12 + (g" xx - 211 + (g',2(+1 - 21)]
+ E.
By Lemma 5 we have
(0', 2(411)
x=1 2 2n
L
||" - 2111 =2t+1 1 2
2
+ 1/
Thus
02 F(x*) F(x*)+ (VF(z'), w¹)
1- 01 02
(VF(x)) x'
01
01
E,
2
zt
+ E,
(gr, (14,2(+1 - -2²)
|| - - (23)
1 1 17
2n
23

---

Published in Transactions on Machine Learning Research (03/2023)
By Lemma 6 we have
L
||
z²I1² + 2t1 - -
1 (((ft))FF(x))
2L(1 - ())) 1gg vF
77
27
81
Note that
1 (1+62)01
82 Thus 21.(1- (01) = 2T.11"
Then, by 23 we have
02
+ 1
01 02 (VF(x"), - -0y
F(x*) 2 F(x")
+
(VF(x"), )²=² - )²²
81
81
+ E2
z++1_
1
2t
+ E
1
(F(v - =(x1))
O2
l|g* - VF(O
++ 7K
01
2L01
02
01 82 (VF(a"), - -0)
= F(xx))
+
(VF(("), (==")=²² - -w²) +
01
01
+ E2
ge+l
+ E,
1
(F(vAt))) - F(a*))
+ 1/
01
02
82
V2d (p')
+ 200,
||VP(a') VF(W"))?
2L0
02 (VF(x"),>* - -w²)
1 01 02 (VF((')) -o!)
< F(xx) +
+
01
01
+ E,
zt+1
+ E
1
(F(vet)) - =((c))] - 2L01
Og
Vi' (p')
1 + Tyx
0
02 (VF (x'),
1- f1
02 (VF(''), -10)
=(4')
+
-w²) +
01
01
+ E2
ge+1
1
+ E2
1
(F(vtt))- - =(ani)]
1 1+10 1/15
01
02
02
Va (p!S)
15)
(V' (p') - Va {}
2L0,
200,
02 (VF(x') (1F((),, ),²² - -w²)
1- 01 02
F(x') +
+
(VF(x"), x²' - 04)
01
01
+ E,
z++1
1 zz
+ Ee
1
(E())t))- - =(o3))] -F((t)))((())
+ TyA
01
02
1
|V/((=')- - f((w\))2
O2
(v' (p') - V/' (p'
28
Lj
200,
By Assumption and and Lemma
we have
VV(('t) - s1(001)11
S 1
-
"
1 (2T) - ( - -(VS((a') w² =²
n
i=1 L,
=2 (F(w') - F(x') - (VF(("), w0 - -z²)).
On the other hand, note that (VF(x'), x² - w²) > F(x') - F(u'). Thus, we further have
F(x*) 2 F(x*) + 0g
1 1- -2 (VF(a")) x" - u²)
(VF(x"), x² - -w²) +
0,
01
1 nm zz + E,
1
1
(F(ett)) - -F(x'))
+ E,
01
02
(F(w') -F(x') - (VF(x²) ),''',, w² -za))=
(v² (p') V/" (p {)
0,
2L0,
1- 01 0g (F(x)) - F(60))
1
zt_ 0g
= F(x*)) +
(F(w²) - F(x'))
01
1 + m/
0
24

---

Published in Transactions on Machine Learning Research (03/2023)
1
02
+ Et
2
+
(F(ott)) - -F(2))
[V?2 (p') - V22 (D'5)}
01
2T0
01
82 F(u')
1
82
2'
F(w')
01
1 175
01
+ E2
z +
1
=(ultt)
02
(V22 (p') - Vi' (D'S))
01
2L0
= =F(**) - 1- 01 - 82 (F(v") - F(x²))
1 z' 02 (F(w*) - -F(x))
01
1 m/1i
01
+ Es
2
+
1 (F(ott))- - F(2*))
02
(V²' (p') - Vid (p*$)}
01
2L01
Recalling the definition of V in
12 we have
Ex [2 + vet s (1 - 01 - 02)
1
2z + 02 ([(w")-((x")
F(x*)) + 02
[V22 (D') - V² (D*S)}-
1 1715
01
2001
Since
Es (oo+t))=F((""))) = (1- (1- (F(w") - -F(x)) + + F(x"))
= (1 -) p) (F(w*) - F((*)) + +0,pV"
recalling the definition of W in
12
we have
E, [2 + vi+1 + Wi+11
1 2z +
02 (F(w")- - F(x*)) + (V22 (p') V² (p(
82
< (1 - 01 - -02)1' +
1 171
01
2L0
+ O2(1 + +1)
02
((1- - p) (F(w²) - F(x')) + 01101)) +
{V's (p') - v²' (p'S))
p01
2L01
p01
0g
z' - - (1-0 02)) V² + +
W"
+
(V²2 (p') - V² (p
1 01
2T.0
By the definition of ag in Theorem 3 and since 02 = 1/2, taking the full expectation on both sides, we have
E | + v++1 + W S a2E 2z + V2 + W
1
E V22 (p') V22 (p's)
4L0,
Recursively repeating the above relationship from T
to t
0, we have
E V S az2
( TT
E V (p T-1 - -TT (p'Ss)
4L01
T
S a yo +
02
T-t-1B
E
V82 (p') V¹¹ [1'
4001
B
Useful Lemmas
We state and prove technical lemmas that used prove the main theorems.
Lemma 1. Let F(-) be defined in ① Suppose Assumption | and Assumption hold. Then F(-) is conver and L-smooth, where L = (1/n) Ei L.
Proof. Under Assumption 1 F(.) is a linear combination of convex functions and, thus, is convex. To prove that it is L-smooth, we only need to note that
1 Σ (V/(()- - v
< 1 Σ Lillo - yll = -[/ - vll. I, M E R4,
[VF(x) VF <
1=1
where the first incquality follows from the Jensen's incquality and the second incquality follows from As- sumption 2
25

---

Published in Transactions on Machine Learning Research (03/2023)
Lemma 2. Assume that f(-) is differentiable conver function R and is L-smooth. Then, for all 2; 1/ E TRdd we have
0. f(v) - f()) -(=) -V) I. | yll?
(24)
(V 2L Vf(x) - vf(0)).
(25)
Proof.
See Theorem 2.1.5 of Nesterov 2018
Lemma 3. Suppose Assumplion 7 and Assumption 2 hold. Let xt, wt g and p² be defoned as in Algorithm
We have
E, - -F(x") [
F(x)) + aE (F(wo) F(x*)) + (p') - V22 (p
Proof. Note that E [[|x [[|x-11810 |[x]|[
EE [[xx|[]] ||[ for any random vector x E RRd, Thus we have
(Vii(x")) mi(w()) (VF(c)) (VF() -VF())))V((()) VF(w9)) |? VF(*'> - VF(W')12
E2 -110-~ VF(0-)]1)
EN
np!.
E₁
(Vf((=') f((w0))
npp.
V2 (p")
VF(x') VF(W"))
V (p')
Va (p')) + V22 (p') V: (s)
(26)
where Vi (p') is defined in
2 On the other hand, note that
L
12
(p"
Vf((a')
v
n
2T.
n
" 1 VVi((')) - V)(Ct)) [V,((aa)) V(((')) + Σ L,
n
L:
2L
n
(2T.) (fi(x') - 11(x)) (VI((")) -''(("))-'-='))) + Σ 1 Ls
[[ - -V(cw')-VA((>)]]
n
Li
2T. " Σ L, 1=1
< (F -
VVi(w') v
(27)
where the second incquality follows Assumption follows from that VF(x*)= = Combining
I
Assumption 2 and Lemma 2 and the last inequality
26 and
we have
E, - Vlg'-vr(>')'' < (F(x') - (F(z))-((x))
2L 1 V((((")) == (p') -3)--v10 Vz' (p L
Lemma 4. Suppose Assumption
and Assumption
2 hold. Let Dt be defined as in 10 We have
E, [Dt1] 2p (F(2)) F(x*)) +1 p)D'
26

---

Published in Transactions on Machine Learning Research (03/2023)
Proof. By the update rule of wt, we have
1
1 | V
E
n
L
1-
Vf((w( - V)((2))1
1 Σ Li [f((z²)) - V](
iml
P
(2L)) (Fi(z") - -i((a)) - (VIi(="), x² - x²)))
11--Pp Σ
[Vi((w") - -/(('=)]
Li
n
1=1 L
2p (F(x') F(x")) 1-- P a 1
Σ L n
Vf((w") V
where the second inequality follows Assumption equality follows from (F(=*)= = 0.
Assumption and 24 of Lemma 2 and the last in-
Lemma 5. Suppose the conditions of Theorem hold. Then
(g' - 21 + H
2/2 ||
x²11²
2 2n
L
20- 2111
+ +z
z
2
+ 178
where z' is defined in 12
Proof. Note that
++1
niat + - 700)
1 1 7/
where K = H/L. Thus,
L - (2' 21t-
g' = p (2'
(22 - 2²) +
"
which implies that
(0', 24 x²) = 11 (x²x - 1-1 , x²) + 77
(2" - - [+1 , - x²)
11
2 || - x²11 || - 21 || || - =²1)3)
L
(11=* x* 1|2 ||=" 2/ 2 || _ x0* 111))
2n
i. (11** x' !|? (1 1715) || | x² 201(²)
T.
1 1000 x²1 1|2 +
-
|||2 - 2
2
2n
21
Combining with the definition of zt, we then have the final result.
Lemma 6. Suppose that the conditions of Theorem 3 hold. Then
L || 2112 + (g', 2141 - =z/> 0,
(F(ott)) F(xt))
7 2L(1 n))) 11/ - VF(
2n
27

---

Published in Transactions on Machine Learning Research (03/2023)
Proof.
By the definition of v we have
L
2
z²11
+ ( 20 -2)
21
1
I
|10g (2 -²2) ||² (g', 01 (24t1- -2)-
8
2
1
L
1
-x 2/11 (g), ++ - x1))
01
2000
1
L
2012 111 (VF(z') wlt1 - =z²) + (g' (((x)) x5))
0
20101
1
L
|utt2 - =211 + (VF(x'), u - =²) ) +
L 1
-1) || - =211 + - x1))
0
2
1101
1
(((0tt) - F(x*)+
L
_/101 -1) -1)
1
+ ((g VF(("), - -
z0)).
01
2 1011
where the last inequality follows Lemma and Lemma 2 By Young's inequality, (a. b) 2
1| 23
||66
with
8 =
90
we have
081)
T.
1141 - -11 + 10 2t) -2
21
((u)42) F(x²) + L
[ ((11-1) -1) |10 - -001?=
n0 21.(1 - n 11gt VF(a")]?
2
01
\100,
I
1
1) 110 - =x(1l²)
(001
(F(btt)) -F(x'))
2L 2 11gt - VF(x')]1
77
01
28


Reviews:
[{"review_id": "V6wcOXTows", "reviewer": "Reviewer_kAr3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nConvergence rate analysis is provided, which justifies the importance of using adaptive sampling. Both synthetic experiments to highlight the intuition and real world experiments to demonstrate the advantage are provided. \n\nWeakness\nI am a little uncertain about the efficiency of the adaptive sampling in practice, since the sampling distribution is changing every iteration, how can you efficiently perform the sampling with time complexity comparable to computing a SGD step?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In finite sum optimization, the choice of  sampling distribution greatly affects the performance of stochastic algorithms such as L-SVRG and L-Katyusa. This paper contributes a novel and purely adaptive sampling strategy that does not rely on any prior information. Not only this adaptive sampling  provably improves the complexity of L-SVRG and L-Katyusa, it also has small memory footprint and computation cost. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Can you add a table to summarize the main complexity of ASLSVRG, AS-Katyusa and the prior algorithms.\nI am a bit confused about what more specific advantage in terms of complexity the proposed algorithms have compared with the state-of-the-art importance sampling algorithm.\n\n- Can you elaborate more about the intuition of AdaOSMD and algorithm 4? What is the difference between AdaOSMD and standard mirror descent? and why \"adaptive\" is necessary?", "broader_impact_concerns": "Not available. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3yloJjR4PS", "reviewer": "Reviewer_wK3b", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "My major concern about this paper is the lack of novelty. The algorithms proposed in this paper is the combination of existing methods, L-SVGD and L-Katyusha for the control variate technique, and AdaOMSD for maintaining the adaptive sampling probability. Using an adaptive sampling method to accelerate the convergence of stochastic gradient-based algorithms and their variants with the control variate technique is by no mean new, e.g. please see [1]. I acknowledge that using the oracle optimal dynamic sampling distribution in Eq.(8) improves the convergence of the importance-sampling based counterpart, but I do not think the current approximate implementation (Eq.(8) is impractical to obtain, and the authors used AdaOMSD to approximate it in an online learning manner) leads to any improvement in the worst-case scenario. \n\n\n\n\n\n[1] Adaptive Variance Reducing for Stochastic Gradient Descent. Z Shen, H Qian, T Zhou, T Mu - IJCAI, 2016", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of finite-sum minimization. Stochastic gradient-based algorithms with control variate technique have been the center of this research direction and provably achieve the optimal gradient access complexity, especially in the convex setting. This paper further improves two successful methods in this literature, namely L-SVGD and L-Katyusha, by replacing the importance sampling in existing procedures with adaptive sampling. The adaptive sampling probability is updated by the AdaOMSD method. The authors prove the convergence rate of the proposed methods, AS-LSVRG and AS-LKayusha.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the novelty of this paper is limited. Unless the oracle optimal dynamic sampling distribution in Eq.(8) can be exactly used for adaptive sampling, the improvement of this paper over the previous work is not justified. ", "broader_impact_concerns": "This is a theory paper. I see no concerns on the ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "vHw1MkDbMd", "reviewer": "Reviewer_dsDv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: I like the insights obtained from the convergence analysis that “the control-variate is improving upon optimization heterogeneity, and adaptive sampling is improving upon smoothness heterogeneity,” which highlights the improvement of the adaptive sampling coming from addressing the smoothness heterogeneity. The discussion on “context-shift” and “concept-shift” is also inspiring, and the authors constructed simulations to further validate these insights obtained from theoretical analysis in Sections 4.1 and 4.3.\n \nWeaknesses and Requested changes: \n \nThe discussion in section 3.3 is quite interesting. I understand it might be tricky, but is there a way to make the statement more concrete instead of just saying qualitatively?\n \nThe organization of the paper should be improved: Section 2 starts with a detailed description of the proposed algorithm without any high-level interpretation. I had a hard time understanding why the sampling distribution should minimize the proposed sampling loss function as in eq (4), and the explanations are in eq (8) and Theorem 1. Thus, I would recommend adjusting the flow of the paper by adding more background or adding more insights into algorithm design to improve the readability.  \n \nExperimental results on non-convex loss: I understand that due to the technical difficulty, analysis can only be conducted under convex conditions. However, one can always perform experiments to see what will happen in the non-convex case. The experiments provided in the paper are all convex optimization problems; how will the proposed algorithm perform for non-convex loss, like a simple neural network?\n\nMinor comments:\n1.   In the figures, it is best to distinguish different algorithms using both line style and colors. The meanings of red and blue curves in Figures 1 and 2 are different, and it is sometimes confusing. \n2.   Some background on L-SVRG and L-Katyusha, i.e., Qian et al. (2021) can be included to make the paper more self-contained. I referred to this paper multiple times during the review.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes an adaptive sampling strategy for L-SVRG (Loopless stochastic variance-reduced gradient) and L-Katyusha that learns the sampling distribution that changes with iterations, which does not require any prior knowledge of the problem parameters as in previous importance sampling-based method. Convergence guarantees for L-SVRG and L-Katyusha are established for convex objectives. Extensive simulations and the practical usage of the proposed sampling scheme on real data are provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See the above weakness discussion.\n\n", "broader_impact_concerns": "There is no such concern for this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes an adaptive sampling strategy for L-SVRG and L-Katyusha that learns the sampling distribution changing with iterates. Specifically, it synthesizes the techniques of adaptive sampling and online learning framework to obtain practical algorithms. Theoretical analyses establish the convergence rate for the proposed methods in the convex setting, and reveal some interesting insights (e.g., optimization/smoothness heterogeneity, context/concept-shift). The paper also conducts experiments on both synthetic and real-world data to demonstrate the intuition and advantages of the algorithms.

On the other hand, as there are many related work on adaptive sampling, the authors should revise their paper to emphasize the novelty and the significance of their results.

Decision: Accept (poster)