Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions
Authors: Wei Jiang
Sifan Yang
Yibo Wang
Lijun Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Adaptive methods
variance reduction
finite-sum optimization
stochastic compositional optimization
Primary area: optimization

Abstract: This paper explores adaptive variance reduction methods for stochastic optimization based on the STORM technique. Existing adaptive extensions of STORM rely on strong assumptions like bounded gradients and bounded function values, or suffer an additional $\mathcal{O}(\log T)$ term in the convergence rate. To address these limitations, we introduce a novel adaptive STORM method that achieves an optimal convergence rate of $\mathcal{O}(T^{-1/3})$ for non-convex functions with our newly designed learning rate strategy. Compared with existing approaches, our method requires weaker assumptions and attains the optimal convergence rate without the additional $\mathcal{O}(\log T)$ term. We also extend the proposed technique to stochastic compositional optimization, obtaining the same optimal rate of $\mathcal{O}(T^{-1/3})$. Furthermore, we investigate the non-convex finite-sum problem and develop another innovative adaptive variance reduction method that achieves an optimal convergence rate of $\mathcal{O}(n^{1/4} T^{-1/2} )$, where $n$ represents the number of component functions. Numerical experiments across various tasks validate the effectiveness of our method.

A Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions
Wei Jiang', Sifan Yang! Yibo Wang 12, Lijun Zhang 1.2
National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China Schooo of Artificial Intelligence, Nanjing University, Nanjing, China {jiangu, yangsf, wangyb, zhangl jaangl)@@lamll .njiaa.jj .nju.eduuuu... edu.
Abstract
This paper explores adaptive variance reduction methods for stochastic optimization based on the STORM technique. Existing adaptive extensions of STORM rely strong assumptions like bounded gradients and bounded function values, suffer an additional Olog 7') term in the convergence rate. To address these limitations, introduce novel adaptive STORM method that achieves an optimal convergence rate of (133) for non-convex functions with newly designed learning rate strategy. Compared with existing approaches, our method requires weaker assumptions and attains the optimal convergence rate without the additional Ollog T) term. We also extend the proposed technique to stochastic compositional optimization, obtaining the same optimal rate of O Furthermore, we investigate the non-convex finite-sum problem and develop another innovative adaptive variance reduction method that achieves an optimal convergence rate On (/T-/1// where n represents the number component functions. Numerical experiments across various tasks validate the effectiveness of method.
Introduction
This paper investigates the stochastic optimization problem
min fxx, XER
(1)
where f RRd b+ TR. is smooth non-convex function. We assume that only noisy estimations of its gradient (x can be accessed, denoted as (xx E), where & represents the random sample drawn from stochastic oracle such that E [xx fx()..
Problem ( has been comprehensively investigated in the literature [Duchi et al. 2011 Kingma and Ba 2015, Loshchilov and Hutter 2017). and it is well-known that the classical stochastic gradient descent (SGD) achieves convergence rate of 1/4), where denotes the iteration number [Ghadimi and Lan 2013]. To further improve the convergence rate, variance reduction methods have been developed, and attain an improved rate of O(T-1/3) under slightly stronger smoothness assumption [Fang et al. 2018 Wang et al. 2019]. However, these methods necessitate the use of a huge batch size in each iteration, which is often impractical to use. To eliminate the need for large batches, momentum-bace variance reduction method - STORM [Cutkosky and Orabona 2019 introduced, which achieves a convergence rate of OTT-1/3 log
Although aforementioned methods are equipped with convergence guarantees, their analyses rely on delicate configurations of hyper-parametersy such as the learning rate and the momentum parameter. To set them properly, the algorithm typically needs to know the value of the smoothness parameter L,
"Lijun Zhang the corresponding author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

the gradient upper bound G, and the variance upper bound which are often unknown in practice. Specifically, most algorithms require the learning rate 7) smaller than (L) and for the STORM method, setting the momentum parameter to (1 is crucial for ensuring convergence [Cutkosky and Orabona 2019].
To overcome this limitation, many adaptive algorithms have been developed, aiming to obtain convergence guarantees without prior knowledge of problem-dependent parameters such L, G and Ø. Based on the STORM method. Levy et al. [02T]] develop the STORM+ algorithm, which
attains the optimal O(T-1/$) convergence rate under the assumption of bounded function values and gradients. To remove the need for the bounded function values assumption, Liu et al. [0222] propose the META-STORM algorithm to attain O(T log convergence rate, but still requires the bounded gradients assumption and includes an additional (log I') term. In summary, despite advancements in this field, existing adaptive STORM- --aaedd methods either depend on strong assumptions or suffer an extra (log T) term compared with the lower bound [Arjevani et al. 2023 Hence, a fundamental question to be addressed is:
Is possible develop an adaptive STORM method that achieves the optimal convergence rate for non-convex functions under weaker assumptions?
We give an affirmative answer the above question by devising novel optimal Adaptive STORM method Add--SOORM.. The learning rate of our algorithm is set to be inversely proportional to a specific power of the iteration number T in the initial iterations, and then changes adaptively based on the cumulative sum of past gradient estimations. In this way, we are able to adjust the learning rate dynamically according the property of stochastic gradients, and ensure small learning rate in the beginning. Leveraging this strategy, Ada-STORM achieves optimal convergence rate of ((T for non-convex functions, Notably, our analysis does not require the function to have bounded values and bounded gradients, which is significant advancement over existing methods (Levy et al.) 2021
Liu et al. 2022]. Additionally, our convergence rate does not contain the extra O (log 7 term, which often present in STORM-basee based methods [Cutkosky and Orabona 2019 Liu al. 2022 To highlight the versatility of our approach and its potential impact in the field of stochastic optimization, we further extend our technique to develop optimal adaptive methods for compositional optimization.
Finally, we investigate adaptive variance reduction for the non-convex finite-sum problems. Inspired by SAG algorithm [Roux et al. [012], we incorporate an additional term in the STORM estimator, which measures the difference of past gradients between the selected component function and the overall objective. By changing the learning rate according to the sum of past gradient estimations, we are able to obtain optimal convergence rate of 01n-1/4T-1/2) for finite-sum problems in an adaptive manner, where n is the number of component functions. Our result is better than the previous convergence rate of O(n 10--1/1 11/4T log(n'T)) obtained by adaptive SPIDER method [Kavis et al. 2022
In summary, compared with existing methods, this paper enjoys the following advantages:
For stochastic non-convex optimization, our method achieves the optimal convergence rate of (/3-1/33 under more relaxed assumptions. Specifically, it does not require the bounded function values or the bounded gradients, and does not include the additional Olog T') term in the convergence rate.
Our learning rate design and the analysis exhibit broad applicability. We substantiate this claim by obtaining an optimal rate of O for stochastic compositional optimization, using the technique proposed in this paper.
For non-convex finite-sum optimization, we further improve our adaptive algorithm attain an optimal convergence rate of Onn/4T 1/2), which outperforms the previous result by eliminating the (log(n(T)) factor.
A comparison between our method and other STORM-based algorithms is shown in Table [ Numeri- cal experiments on different tasks also validate the effectiveness of the proposed method.
2 Related work
This section briefly reviews related work on stochastic variance reduction methods and adaptive stochastic algorithms.

---

Table 1: Summary of results for STORM- methods. Here, NC denotes non-convex, Comp. indicates compositional optimization, FS represents finite-sum optimization, and BG/BF refers to requiring bounded gradients bounded function values assumptions. Adaptive means the method does not require to know problem-dependent parameters, i.e., L, G, and a.
Method
Setting
Convergence Rate
Adaptive
BG/BF
STORM Cutkosky and Orabona
2019
NC
0
T
1/3 log T
x
Super-ADAM [Huang et
2021
NC
T
1/3 log T
X
STORM+
Levy et al. 2021
NC
0
(T-1/3 1/3
V
/
META-STORM Liu et al.
2022
NC
T
1/3 log
T
V
Theorem
NC
0
T-1//
d
Theorem
NC & Comp.
0
T-1/3
/
Theorem
NC FS
0
(
nn
14/--11/
1/2
/
2.1 Stochastic variance reduction methods
Variance reduction has been widely used in stochastic optimization to reduce the gradient estimation error and thus improve the convergence rates. The idea of variance reduction can be traced back to the SAG algorithm [Roux et al. 2012]. which incorporates a memory of previous gradient values to ensure variance reduction and achieves linear convergence rate for strongly convex finite-sum optimization. To avoid the storage of past gradients, SVRG (Zhang et al. 2013 Johnson and Zhang 2013] proposes to calculate the full gradient periodically, obtaining the same convergence rate the SAG algorithm. Subsequent advancement has been made by the SARAH method [Nguyen et al. which derives better convergence for smooth convex functions.
2017
In the context of non-convex objectives, Fang al. 2018 introduce the SPIDER estimator, which im- proves the convergence rate from O77-1 (T in stochastic settings, and Onn 1/2) in finite-sum scenarios, with representing the number of components in the finite-sum. Following this, the SpiderBoost algorithm WWang et al., 2019 refines the SPIDER approach by employing a larger constant step size and adapting it for composite optimization problems. However, common limitation among these methods is their reliance on large batch sizes for each iteration, posing practi- cal challenges due to high computational demands. To mitigate this issue, Cutkosky and Orabonal [211 introduce the STORM method, a momentum-barn based technique that achieves an 1/3 log T') convergence rate without using large batches. Concurrently, Tran-Dinh et al. 2019 obtain the same result using a similar algorithm but through a different analysis.
2.2 Adaptive stochastic algorithms
For stochastic optimization, it is well-known that the SGD algorithm can obtain a convergence rate of (T14//4 for non-convex objective functions with well-designed learning rates [Ghadimi and Lan 2013]. Instead of using pre-defined iteration-based learning rates, many stochastic methods propose adjust the learning rate based on past stochastic gradients. One of the foundational works is the AdaGrad algorithm [Duchi et al. al. [001], which proves to be effective for sparse data. Further advancements include R.Spprpp [Tieleman and Hinton| 2012) and Adam [Kingma and Ba 2015). demonstrating broad effectiveness across wide range of machine learning problems. Later, the Super-Adam HHuag al. 2021] algorithm further improves the Adam algorithm via the variance reduction technique STORM [Cutkoskyy and Orabonal 2019] and obtains a convergence rate of OT7-1/3 log T). Nevertheless, to obtain the corresponding convergence rates, these methods still require knowledge of certain problem-dependen parameters to set
accurately, hence
3

---

Algorithm STORM Algorithm
1: Input: time step T, initial point
2: for time step t = to T do
3: Set hyper-parameters 3g and 7)
4: Compute v, according to equation
5: Update the decision variable: x Xt 1/6
6: end for
7: Choose uniformly random from (1,...,7)
8: Return X,
not adaptive To solve this problem, many research aims to develop fully adaptive SGD methods that maintain the optimal convergence rate without knowing problem-specific parameters OOraoona 2014
Chen et al. 2022 Carmon and Hinder
2022
Ivgi et al. 2023 Yang et al. 2023].
Recently adaptive adaptations of STORM have received considerable attention. A notable develop- ment is the introduction of STORM+ [Levy et al., 202T]. which presents fully adaptive version of STORM while attaining optimal convergence rate. To circumvent the bounded function values assumption STORM+, the META-STORM [Liu et 2022] approach is developed, equipped with nearly optimal bound. However, META-STORY
still requires the bounded gradients assumption, and includes an additional Olog 7) in the convergence rate. Consequently, adaptive STORM with the optimal convergence rate and under mild assumptions still needs further explorations.
3 Adaptive variance reduction for non-convex optimization
In this section, we develop an adaptive STORM method for non-convex functions. We first outline the assumptions used, and then present our proposed method and analyze its convergence rate.
3.1
Assumptions
We introduce the following assumptions, which are standard and commonly adopted in the stochastic optimization [Nguyen et al. 2017 Fang et al. 2018 Cutkosky and Orabona 2019 Li et al. 202
Assumption (Average smoothness)
[VV v((r:)) < L y11
Assumption (Bounded variance)
- <
Assumption f. infx f(x) 2 oo and f (x,) f. - A for the initial solution X1-
Note that some additional assumptions are required in other STORM based methods. Specifically, STORM [Cutkosky and Orabonal 2019]. STORM+ [Levy et al. 202T], and META-STORM (Liu al. 2022 assume the hounded gradients. Moreover, STORM+ makes additional assumption of the bounded function values.
3.2 The proposed method
In this subsection, aim develop adaptive STORM method that achieves optimal conver- gence rate for non-convex functions under weaker assumptions. Our algorithm framework is the same the original STORM [Cutkosky and Orabonal 2019). and the only difference the setup of the momentum parameter 3 and the learning rate First, we present the STORM algorithm in Algorithm
'In this paper, adaptive means the algorithm does not require syper-parameters such the learning rate and the momentum parameter.
parameters to set up

---

The core idea of STORM lies in a carefully devised variance reduced estimator vt, which effectively tracks the gradient V fxe). For the first iteration (t 1), we set V1 "i= Bo f Ei), which estimated within a batch Bg = T Note that we use large batch only in the first iteration, and constant batch size in other iterations. In subsequent iterations 2 2), estimator is defined as:
(2) where the first terms are similar the momentum SGD, and the last term serves as the error correction, which ensures the variance reduction effect. By choosing the values of 3r and ?e carefully, STORM ensures that the estimation error E[[ v. (x(xx)) would decrease gradually. In the original STORM paper, these parameters are set up as:
Vi = 3. + (xx) ()) + (+) (xx( vf((x-1:E)).
k
Br = =ep
E 1=1 (xxx 1/31
where k: OG w O and = O(12). The settings of these
are crucial to the convergence analysis of STORM. However, it is worth noting that I. is the smoothness parameter and G is the gradient upper bound, which are often difficult to determine practice.
To address this problem, our approach defines the
as follows:
1/1 min
l1vl1)))))) =
TI/3' T(1-a)/3
where 0 < a < 1/3. Notably, our method does not rely on the parameters L and G, and also does need the bounded gradients bounded function values assumptions that are common other methods. Although our formulation initially requires knowledge of the iteration number T. this can be effectively circumvented using the doubling trick, which will be explained later. The above learning rate can also be expressed in an alternative, more illustrative manner.
if E ||v.ll < T1/3;
71/3
T/t
else.
This formulation ensures that the learning rate starts sufficiently small in the initial stages and then changes dynamically based on the gradient estimator Vt. This design makes our learning rate setup and convergence analysis distinctly different from previous methods. Next, we present the following theoretical guarantee for our algorithm.
Theorem Under Assumptions guarantees that:
4 and
Algorithm
with hyper-parameters in equation
A 21
+o1-a L
E [|V]( S
T1/3
Remark: To ensure that |||l / (x,) e, the overall complexity ( which is known to be optimal up to constant factors Arjevani et al.) 2023] Compared with existing STORM-based algorithms [Cutkosky and Orabona 2019 Levy et al. 2021 Liu et al. 2022], our method does not have the extra Olog T') term in the convergence rate, and analysis does not require bounded gradients or bounded function values assumptions. Also note that the selection of a does not affect the order of T. and larger leads to better dependence parameter L and worse reliance on parameters and a. Considering we require that 0 < a < 1/3, we can simply set a = 0.3 practice.
3.3 The doubling trick
While we have attained the optimal convergence rate using the proposed adaptive STORM method, it requires knowing the total number of iterations T in advance. Here, we show that we can avoid this requirement by using the doubling trick, which divides the algorithm into several stages and increases
5

---

the iteration number in each stage gradually. Specifically, we design a multi-stage algorithm over k 21,2.... } stages. the beginning of each new stage, we reset x; Xp. each stage the STORM algorithm is executed for 2 iterations, effectively doubling the iteration numbers after each stage. In any step i, we first identify the current stage as 1 - [log { and then calculate the iteration number for this stage as I = 2 log Then, we can set the hyper-parameters as:
{
(Ei=,,1v lIve)))) }
T/ min
B. B==1, 2/3
1=221ort]]
I = 2
1//31 1 ((1-)/33
This approach eliminates the need to predetermine the iteration number T. By using the doubling trick, we can still obtain the same optimal convergence rate as stated in the following theorem.
Theorem Under Assumptions guarantees that:
7
and
Algorithm
7 with hyper-parameters in equation
A tora
L N
E [|V S SO
T1/3
4 Extension to stochastic compositional optimization
To demonstrate the broad applicability of our proposed technique, we extend it to stochastic composi-
tional optimization [Wang et al. b Yuan et al. 2019 Zhang and Xiao 2019 2021 Jiang et al. 2023 2024a formulated as:
min F(x) = f(((x)), xER
(5)
where f and g are smooth functions. We assume that we can only access to unbiased estimations of fx()). Vx(x) and g(x), denoted as ff(x Vg(x; () and (xx: (). Here & and Ç symbolize the
random sample drawn for a stochastic oracle such that E {)] = fx)),, B[g(x; {)] g(x),
and E[Vg [)] = Vg(x).
Existing variance reduction methods Huu et al. 2019 Zhang and Xiao 2019 Qi et al. 2021 are able
to obtain optimal (TT-1/3) convergence rates for problem ( but they require the knowledge of smoothness parameter and the gradient upper bound to set up hyper- parammerrametess.. In this section, aim to achieve the same optimal convergence rate without prior knowledge of problem-dependent parameters. We develop adaptive algorithm for this problem follows. In each step t, the algorithm maintains an inner function estimator u, in the style of STORM, i.e.,
u, (1 :) + 9(x;; (.) (1 (x Gt)
(6)
Then, we construct gradient estimator v, based on u, also in the style STORM:
V. 8) + Vf(u::
(1 fmm
After that, we apply gradient descent using the gradient estimator v, The whole algorithm presented
in Algorithm 2 and hyper-paranee paremeerrs are set the same as in equation 33) For the first iteration, we simply set u,
where B, 1// Next, we list common assumptions used in the literature of compositional optimization [Wang et al.
i=1 R, ((x:; Çi) and v
Be 1
Bo
(f
2017a b Yuan et al. 2019 Zhang and Xiao 2019 2021].
Assumption (Average smoothness and Lipschitz continuity)
E
V (xx:E) V < T y1 E [[((x)) f1 - <C'| - y1
E
[V Vgly; ()1l < 4||1 y11?: E
[[](xi() - s]1?
- C' -1Ix-11 y1
Assumption (Bounded variance)
E [|b((x () - s(x))1² S So;B (IVs(x)) - S
[V ( 50?

---

Algorithm 2 Compositional STORM
1: Input: time step T, initial point
2: for time step t = to T do
3: Compute u, according equation 6
4: Compute v, according to equation
5: Update the decision variable: x Xt 1/e V
6: end for
7: Choose uniformly random from (1,...,77) 73
8: Return X,
Assumption F. = infx F(x) 2 -0 and F (xx) F. S Ar for the initial solution X1-
Remark: In Assumption 4 further require standard Lipschitz continuity assumption, which is essential and widely required in the literature for stochastic compositional optimization (Wang et al.) 2017b Yuan al. 2009 Jiang et al. 2022a b). This assumption is inherently introduced by the compositional optimization itself rather than by our adaptive techniques.
With the above assumptions, our algorithm enjoys the following guarantee.
Theorem Under Assumptions
4
5 and our Algorithm ensures that:
Remark: This rate matches the state-of-the-art (SOTA) results in stochastic compositional opti- mization [Hu et al. 2019 Zhang and Xiao 2019) Qi et al. [202]. and our method achieve this in an adaptive manner. Note that our convergence rate aligns with the lower bound for single-level problems (Arjevani et al. 2023 and is thus unimprovable.
Adaptive variance reduction for finite-sum optimization
In this section, further improve our adaptive variance reduction method to obtain enhanced convergence rate for non-convex finite-sum optimization, which is in the form of
"
min F(x) XERE
Σ f(xx), T2
where each f-(-) is a smooth non-convex function. Existing adaptive method for this problem [Kavis et al. 2022] achieves a convergence rate of ( log(nT)) based on the variance reduction technique SPIDER (Fang et al. 2018), J suffering from extra Ollog(nT)) term compared with the corresponding lower bound [Fng et al. 2018 Li et al. 2021].
To obtain the optimal convergence rate for finite-sum optimization, we incorporate techniques from SAG algorithm [Roux al.) 2012) into the STORM estimator. Specifically, each step i, we start by randomly sample , from the set 21, .,,,, Then, we construct variance reduction gradient estimator as
,n].
V. = (1 - 3)v-1 fi, - (1 (x - (0
Σ
(8)
n
where the first three terms align with the original STORM method, and the last term, inspired by the SAG algorithm, deals with the finite-sum structure. Here, It tracks the gradient
(xx)
i= it
i d2
By such design, ensure that the estimation E[l[v, F reduces gradually. The whole algorithm is stated in Algorithm 3 In this case, we set the hyper-parameters as:
1
17p
8=
Σ lIvil lIvel2)
n

---

Algorithm 3 STORM for Finite-sum Optimization (SAG-type)
1: Input: time step T, initial point
2: for time step t to T do
3: Sample randomly from 21, .n.
4: Compute estimator v, according to equation (8)
5: Update Ut=1 according equation (9)
6: Update the decision variable: X X V
7: end for
8: Choose 7 uniformly at random from { T}
9: Return x,
where 0 < a 1/3. The learning rate Nee is non-increasing and changes according the gradient estimations, and the momentum parameter 3 remains unchanged throughout the learning process. Next, we show that our method enjoys the optimal convergence rate under the following assumptions. which are standard and widely adopted in existing literature [Fang et al. 2018 Wang et al. 2019 al. 202T]
Assumption (Smoothness) For each i (1,2, ,m,,,, J is L-smooth such that
(V) Vv)ily) S L|[x- - yll.
Assumption F, = -infx F(x) 2 - do and F (x1) Fx S Ap for the initial solution X1-
Theorem 4 Under Assumptions and g
our Algorithm
guarantees that:
1/1
VF
A
L
T1/2
Remark: Our result matches the lower bound for non-convex finite-sum problems [Fang et al. 2018 Li et al. 2021], and makes improvement over the existing adaptive method, i.e.,
AdaSpider Kavis et al. 2022]. Specifically, the convergence rate of the AdaSpider algorithm
is 1n44---172 (L² + AF) log (1 + nTLL) and our result is better than theirs when < <
We can avoid storing past gradients by following the SVRG method (Zhang et al. 2013 Johnson
and Zhang 2013) to compute the full gradient periodically and incorporate into STORM estimator. Instead of storing the past gradients as in SAG algorithm, we can avoid this storage cost by incorpo-
rating elements from the SVRG method. Specifically, we compute a full batch gradient the first
step and every iteration (we set I n):
1
vx(x,)
Σ (x(+)).
For other iterations, we randomly select an index i, from the set (1,2,.. ..., ,n] ,,,,,...,,,,
and compute:
V2 (1 - 31v=- fi, - (1 (x, - (V fú, (x,) ) v vx(x)))
(10)
Note that the first three terms match the original STORM estimator, and the last term, inspired from SVRG, deals with the finite-sum structure. Compared with equation that we use (V.s, (x,) Vx(x)) instead of (g E gi) in the last term. The detailed procedure is outlined in Algorithm This strategy maintains the same optimal rate, as stated below:
(8) in Algorithm the difference
Theorem Under Assumptions and g our Algorithm guarantees that:
1/4
[|F s O T1/2
A
The obtained convergence rate is in the same order as the results Theorem and Algorithm 4 does not require storing past gradients anymore.
Remark:

---

Algorithm 4 STORM for Finite-sum Optimization (SVRG-type)
1: Input: time step T, initial point X1
2: for time step t to T do
3: if mod I = 0 then
4: Set f = and compute ff(x,) - E (f((X;)
5: end if
6: Sample i, randomly from {1, 2.... .....1
7: Compute v, according equation (TO)
8: Update the decision variable: X XT 1/Vo
9: end for
10: Select uniformly at random from { T}
Return X+
Toining toocing sale
Tesinin ScCuTOC
Tostng las Uog aoale)
0.5
100
150
300
119 Fprach
150
302
190
300
100
20
Fpucc
Fpech
Fpoch
(a) Training loss
(b) Training accuracy
(c) Testing loss
(d) Testing accuracy
Adam
AdaRelief
SGD
STORM
STORM
META-STORM
Ad-SSTORM
Figure I: Results for CIFAR-10 dataset.
Experiments
In this section, we evaluate the performance of the proposed Ada-STORM method via numerical ex- periments on image classification tasks and language modeling tasks. the experiments. we compare our method with STORM [Cutkosky and Orabona 2019). STORM+ [Levy et al., 2021 and META-
STORM (Liu et al., 2022]. well as SGD, Adam [Kingma and Ba 2015 and Adaßelief (Zhuang et al. 2020 We use the default implementation of SGD and Adam from Pytorch [Paszke et al. 2019] For STORM+. we follow its original implementation" and build STORM, META-STORM and our Ada-STORM based on it. When it comes to hyper-pane parameter tuning, we simply set 0.3 for our algorithm. For other methods, we either set the hyper-paramen parameters as recommended in the original papers or tune them by grid search. For example, we search the learning rate of SGD, Adam and AdaBelief from the (le-5, 1e-4, 1e-3, 1e-2, 1e-1} and select the best one for each method. All the experiments are conducted on eight NVIDIA Tesla V100 GPUs.
Image classification task First, conduct numerical experiments multi-class image classifica- tion tasks to evaluate the performance the proposed method. Specifically, we train ResNet1 8 and ResNet34 models (He al., 2016) the CIFAR- 10 and CIFAR- datasets (Krizhevsky. 2009) respectively. For all optimizers, we set the batch size as 256 and train for 200 epochs. We plot the loss value and the accuracy against the epochs the CIFAR-10 10 and CIFAR-100 datasets in Figure [ and Figure [ is observed that, for training loss and training accuracy, our Ada-STORM algorithm achieves comparable performance with respect to other methods, and outperforms the others in terms of testing loss and thus obtains better testing accuracy.
Language modeling task Then, we perform experiments language modeling tasks. Concretely, we train 2-layer Transformer [Vaswani et al. [0177] over the WiKi-Text2 dataset [Merity] 2016). We use 256 dimensional word embeddings, 512 hidden unites and 2 heads. The batch size is set as 20 and all methods are trained for 40 epochs with dropout rate 0.1. We also clip the gradients by norm 0.25 in case of the exploding gradient. We report both the loss and perplexity versus the number of epochs in Figure From the results, we observe that our method converges more quickly than other
Phaps://gitubb.co//LLoss oatp://ii.ooootllloSPPPasAoooooo -EP-sssototoso--pu-uuooooo

---

Training loo (lg scal))
Traking acrrnay
1.25
Testing las flo
0.79
100 Epoch
150
200
100 Epoch
150
130
Epoct
Dpoch
(a) Training loss
(b) Training accuracy
(c) Testing loss
(d) Testing accuracy
Adam
AdaBelief
META-STORM
Figure 2: Results for CIFAR-I00 dataset.
Trininn Loos
Triming Thaming perplesity
Toxing toop
6.0
400
200
200
50
Fjoch
Epech
Epoch
(a) Training loss
(b) Training perplexity
(c) Testing loss
(d) Testing perplexity
Adam
AdaBelief
SGD
STORM
STORM
STORM
Ads.STORM
Figure Results for WikiText-2 dataset.
methods and obtains a slightly better perplexity compared with others, indicating the effectiveness of the proposed method.
7 Conclusion
In this paper, we propose an adaptive STORM method to achieve the optimal convergence rate for non- convex functions. Compared with existing methods, our algorithm requires weaker assumptions and does not have additional (log T) term the convergence rate. The proposed technique can also be employed to develop optimal adaptive algorithms for compositional optimization. Furthermore, we investigate an adaptive method for non-convex finite-sum optimization, obtaining an improved convergence rate of On
Given that STORM algorithm has already been used in many areas such as bi-level optimization Yang et al. (022], federated learning [Das et al.) [002]. min-max optimization [Xian al., 202T], sign-based optimization [Jiang et al., (024b), etc., the proposed methods may also inspire the development of adaptive algorithms in these fields.
Acknowledgements
This work was partially supported by National Key R&D Program of China (2021ZD01 12802). NSFC (62122037), and the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX24_0231)
References
Y. Arjevani, Y. Carmon, J. C. Duchi, D. J. Foster, N. Srebro, and B. Woodworth. Lower bounds for non-convex stochastic optimization. Mathematical Programming. 199(1):165-214, 2023.
Y. Carmon and O. Hinder. Making SGD parameter-free. In Proceedings of the 35rd Annual Conference on Learning Theory, pages 2360-2389, 2022.
K. Chen, J. Langford, and F. Orabona. Better parameter-free stochastic optimization with ODE updates for coin-betting. Proceedings of the 36th AAAI Conference on Artificial Intelligence, pages 6239-6247, 2022.
10

---

A. Cutkosky and F. Orabona. Momentum- based variance reduction in non-eonvex SGD. In Advances in Neural Information Processing Systems 32, pages 15210-15219, 2019.
R. Das, A. Acharya, A. Hashemi, S. Sanghavi, I. S. Dhillon, and U. Topeu. Faster non-convex federated learning via global and local momentum. In Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, pages 496-506, 2022.
J. Duchi, E. Hazan, and Y. Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61):2111-2159, 2011.
C. Fang, J. Li, Z. Lin, and T. Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Information Processing Systems 31, pages 689-699, 2018. 8.
Ghadimi and G. Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic program- ming. SIAM Journal on Optimization, 23(4):2341 1-2668, 2013.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 770-778, 2016.
W. Hu, C. J. Li, X. Lian, J. Liu, and H. Yuan. Efficient smooth non-convex stochastic composi- tional optimization via stochastic recursive gradient descent. Advances in Neural Information Processing Systems 32, pages 6543-6553, 2019.
Huang, J. Li, and Huang. Super-adam: Faster and universal framework of adaptive gradients. In Advances in Neural Information Processing Systems 34, pages 9074-9085, 2021.
M. Ivgi, O. Hinder, and Y. Carmon. Dog is SGD's best friend: A parameter-free dynamic step size schedule. In Proceedings of the 40th International Conference on Machine Learning, pages 14465-14499, 2023.
W. Jiang. G. Li, Y. Wang. L. Zhang, and T. Yang. Multi-block-sinn sinook--ingll-pobee variance reduced estimator for coupled compositional optimization. In Advances in Neural Information Processing Systems 35, pages 32499-32511 2022a.
W. Jiang, B. Wang, Y. Wang, L.. Zhang, and T. Yang. Optimal algorithms for stochastic multi-level compositional optimization. In Proceedings of the 39th International Conference on Machine Learning, pages 10195-10216, 2022b.
W. Jiang, J. Qin. L. Wu, C. Chen, Yang, and L. Zhang, Learning unnormalized statistical models via compositional optimization. In Proceedings of the 40th International Conference on Machine Learning, pages 15105-15124, 2023.
W. Jiang, S. Yang, W. Yang, Y. Wang, Y. Wan, and L. Zhang. Projection-free variance reduction methods for stochastic constrained multi-level compositional optimization. In Proceedings of the 41st International Conference on Machine Learning, pages 21962-21987, 2024a.
W. Jiang, S. Yang, W. Yang, and L. Zhang. Efficient sign-based optimization: Accelerating con- vergence via variance reduction. In Advances in Neural Information Processing Systems 37, 2024b.
R. Johnson and Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Advances in Neural Information Processing Systems 26, 2013.
A. Kavis, Skoulakis, K. Antonakopoulos, L. T. Dadi, and V. Cevher. Adaptive stochastic variance reduction for non-convex finite-sum minimization. In Advances in Neural Information Processing Systems 35, pages 23524-23538. 2022.
D. P. Kingma J.d I.. Ba. Adam: A method for stochastic optimization. International Conference Learning Representations, 2015.
A. Krizhevsky. Learning multiple layers features from tiny images. Masters Thesis, Deptartment of Computer Science, University of Toronto, 2009.

---

K. Y. Levy, A. Kavis, and V. Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. Advances Neural Information Processing Systems 34, pages 20571-20582, 2021.
Z. Li, H. Bao, X. Zhang, and P. Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning, pages 6286-6282 6295, 2021.
Z. Liu, T. D. Nguyen, T. H. Nguyen, Ene, and H. L. Nguyen. Meta-storm: Generalized fully- adaptive variance reduced SGD for unbounded functions. ArXiv e-prints, 1xXix:2299.14853 2022.
I. Loshchilov and Hutter. SGDR: Stochastic gradient descent with warm restarts. International Conference on Learning Representations, 2017.
H. B. McMahan and M. Streeter. Adaptive bound optimization for online convex optimization. In Proceedings of the 23rd Annual Conference on Learning Theory, 2010.
Merity, The wikitext long term dependency language modeling dataset. Salesforce Metamind, 9, 2016.
L. M. Nguyen, J. Liu, Scheinberg, and M. Takac. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Proceedings of the 34th International Conference on Machine Learning. pages 2613-2621, 2017.
Orabona. Simultaneous model selection and optimization through parameter- freee stochastic learning. In Advances in Neural Information Processing Systems 27, pages 11 1116-1124, 2014.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high high-performance deep
learning library. In Advances in Neural Information Processing Systems 32, 2019.
Q. Qi, Z. Guo, Y. Xu, R. Jin, and T. Yang. An online method for a class of distributionally robust optimization with non-convex objectives. In Advances Neural Information Processing Systems 34, pages 10067-10080, 2021.
N. L. Roux, M. Schmidt, and F. R. Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Advances in Neural Information Processing Systems 25, pages 2672-2680, 2012.
T. Tieleman and G. Hinton. Lecture 6.5-mmsprop: Divide the gradient by rumning average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 4, pages 26-31, 2012.
Q. Tran-Dinh, N. H. Pham, D. T. Phan, and L. M. Nguyen. Hybrid stochastic gradient descent algorithms for stochastic nonconvex optimization. ArXiv e-prints,
2019.
A. Vaswani, Shazeer, Parmar, J. Uszkoreit, Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention is all you need. In Advances in Neural Information Processing Systems 30, pages 5998 6008, 2017.
M. Wang, E. X. Fang, and H. Liu. Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions. Mathematical Programming, 161(1-2): 419, 2017a.
M. Wang, Liu, and E. X. Fang. Accelerating stochastic composition optimization. Journal of Machine Learning Research, 111105::111::3,,,.11 2017b.
Z. Wang, K. Ji, Y. Zhou, Liang, and V. Tarokh. SpiderBoost and momentum: Faster variance reduction algorithms. In Advances in Newral Information Processing Systems 32, pages 2406-2416, 2019.
W. Xian, Huang, Zhang and H. Huang. faster decentralized algorithm for nonconvex minimax problems. In Advances in Neural Information Processing Systems 34, pages 25865-25877, 2021. 2021.
12

---

J. Yang, K. Ji, and Y. Liang. Provably faster algorithms for bilevel optimization. In Advances in Neural Information Processing Systems 34, pages 13670-13682, 2021.
Yang, X. Li, I. Fatkhullin, and N. He. Two sides one coin: the limits of untuned SGD and the power of adaptive methods. In Advances in Neural Information Processing Systems 36, pages 1206-12166 1216, 2023.
H. Yuan, X. Lian, J., Liu, and W. Hu. Efficient smooth non-convex stochastic composi- tional optimization via stochastic recursive gradient descent. In Advances in Neural Information Processing Systems 32, pages 14905-14916, 2019.
J. Zhang and L. Xiao. A stochastic composite gradient method with incremental variance reduction.
In Advances Neural Information Processing Systems 32, pages 9075-9085, 2019.
Zhang and Xiao. Multilevel composite stochastic optimization via nested variance reduction. SIAM Journal on Optimization, 31(2):1131-1157, 2021.
L. Zhang, M. Mahdavi, and R. Jin. Linear convergence with condition number independent access of full gradients. In Advances Neural Information Processing Systems 26, pages 980-988 2013.
Zhuang, Tang, Ding, S. C. Tatikonda, N. Dvornek, X. Papademetris, and J. Duncan. Ad- abelief optimizer: Adapting stepsizes by the belief in observed gradients. In Advances in Neural Information Processing Systems 33, pages 18795-18806, 2020.
13

---

A Proof of Theorem 1
First, we introduce the following lemma, which frequently used in our proof.
Lemma Suppose ai is positive for i = {,,2, ... ,n,,, and let 0 <a <
1.
We can ensure that:
1-a
Σ
4
Σラ=
i=1
Proof The proof mainly follows McMahan and Streeter (010]) and a similar analysis also appears in Levy et al. (2027). First, we prove the right part by Induction.
JollowssMMMahan
(1) For n can easily show that the hypothesis holds:
1
=c--a S a
1-a
(2) Next, assuming that the hypothesis holds for n = 1, then we show that it also holds for n t.
Define Z = =ii= G and X Ct. For n t, we have
1-
C
Ci
Ct
Σ f==
Cj
a
i=1
2j=1
Cj
Cj
a
1-a
1
Ct
1
i=1
1
X
(7
x)
1-a
+
1(X).
7,
Taking the derivative concerning know that
dh(X)
dX
7 (Z - -)aa
which indicates that h(X) decreases as X increasing. Since 0 S X < Z,
1-0
max ((X) - h(0) = 1 z1-a OSXEZ
C
1 1 a
which implies that the hypothesis is true for Combining (1) and (2), we finish the proof for the right part. Then, we give the proof of the left part as follows:
1-a
Σ C2
Σ クー=ク
レ== Cj
Thus, we finish the proof of this lemma.
Next, we can obtain the following guarantee for our algorithm.
Lemma Our method enjoys the following guarantee:
Σ E nu [[]
1=1
21,2 T
s(2A, + 0 +E
Σ 7
2
L
7h
lvel"
+E
2,00
1/
13
(A)
(B)
(C)
14

---

Proof 2 According to the definition of estimator Vo, we can deduce that:
ge++
[V[(((+1)
Vetil1?]
Eg
[I(1 B)v, + V - (V((-=))))))(((( v
[||(1 (v V V (VI(x))) - V -
+39 (V. ((+1) v)(x))) [12]
S TRgit [(1 - ()) - V Re [1[][(x) v
+ V)((x; E + 8 (V](xx - Vf(x)))
S Ee [11 () V
+ 21b [xx) - v
|113 (V (--1) ([(((+ii(t)) - v
+ 21E
< (1 - B [[|v,- - VV +
-/
+ gE
-
< (1 B) V; - Vf(x) )| +28-02 21 Xx+11 - |
= (1 B) v +23 + 2T.3 vvel??
(11)
Note that Tp is independent of random variable E++1. So we can guarantee that:
EgCh The [[X(()) - ve - (1-)) - + 223002 + 2T,2, 1/vl1
After rearranging, we have:
Ne lIve [xx
T lIve fxx))) Eec+s
ae [[ - vf + 2802m m +
21
B m llvel
B
Letting H4 be the history time t, iee, Hi '.,, Eee, we ensure that
Ex, The Dollve-V/(Ee <EH.
Tt || (xxx))1
EHHL The 3
B
21
+ 2,8 ER, [nd +
En.
1/ lIvel lIvel]]]
3
By summing and noting that qi is non-increasing such that 1141 S Tt, we have:
T
EH,
||ve - [((x))1
1=1
(12)
2L
<En,
|
(VV--S((i)]))
+ 2,3 Σ En, [nx) +
Eh, 1 [vvll"]]
3
B
Since we use a large batch size in the first iteration, that is, Bo 1/3 we can now ensure that
Ex, | v [x(x))]
a² o² T T1/3. Due to the fact that m S T-133 and B T -2/3, the first
term of the above inequality is less than o², So, can finally have;
T
T
21 T
Σ E
Te
ll.
<0² + 280
E mm +
E m
V1 v.]
(13)
3
15

---

Also, due to the smoothness of fxx), we know that:
f(x++1) S f(xi) + (V (x:) X(+1 - -xx) + 2
|x++1 - -xil?
I l|v.12
= fx(x) au f (x1) ve)
/ (xx) ni (V/ (xx) vo)
The
|VV (x +
l|v, 1
1/e 2
|V (x
2
Ttt || 12 + 2 |/vel|
L
2
= f(x) + t
V (x+) - vel12
T1
[
7t
1vv11= 2 +
ni L
||ve| 2
2
2
2
2
By summing up and re-arranging, we have:
T Σ The lv.l1 -
T
Σ
1/t [[xx(x) vell + Σ
n L l/vell (14)
Then, by using equation
13 and the fact that f(x1) - fo S Dy we have:
EE[mivil'] $ + 0² + 2B
E [nd + 21
E
vell
2
+ L
E
m
tm1
which finishes the proof of Lemma 2
To effectively bound each term in the above lemma, we divide the algorithm into two stages. Suppose that starting from iteration & s. the condition Σ |[ 2 T begins to hold. We refer to iterations t = {1.2. .... - 1} as the first stage, and = {s, ... I as the second
second stage.
Bounding LHS: In the first stage, we know that
Σ Th Ivell
1 71/3
Σ
llv.l
For the second stage, our analysis leads to:
T
T
|
V
2
1=
1=
T
Ei ||
llv:ll?)
T
|/
T a
T Ei=e 11va
t=
T
T +
El= [|v:l13)
||v:11
1=
T
2 max
T
EEis l|v:l1 {
T
T Σ livel
1-a
min
2T -T
T
T
T
1-a
Ivell
min
2
T1/3
T1/3
1=8
16

---

where the first inequality stems from Σi=1
t= Vvel I T1/3, the second inequality results from
(x + y)th I x" + y² for positive æ, y and 0 < a 1/3, and the forth inequality applies Lemmal
Next, we bound (A); (B), (C) as follows.
Bounding (A): In the first stage, with T)t = T-1 3 = T 2/3 - and Eisl livel S T/3 derive:
1/3
we can
2L
2L s-1
Vv 2
vell s 21.
3
T1/3
For the second stage, the analysis gives:
21
T
|
21.
T
1-3a
nh 1vll
S 2L
I
Σ
Eien |
3a
T1/3
t=
where the second inequality uses Lemma
I Then we also have:
2L
T
1-3x
2L
1
T
1-30
llvell?
(8 - 24a) 1-30 30
lvel?
1 3a
71/3
1 - 3a
(8 - 24a) T1/3
1=8
1=
2L
T
33x
1 30
(8- 24xr)
24cr)
1-30
+
871/3
t=
where the inequality employs Young's inequality, such that ry S 3ax 30 + (1 - -3yy 1 for positive E, Very similarly, we have:
(1-3a)p
2L
T
1-3xx
1/
?
1 3a
71/3
t=a
21.2
( 8
24a
T
T
I-3a
T
1-3x
veel?
1 3a
1
8 - 24a
T1/3
t=s
20
2L
8
24a
+
1|
1 a
1
3a
1 a
T1/3
1=8
where the second inequality employs Young's ' inequality, such that zy for positive x, y. Combining all above, we know that
2a I-a
+
1-30
y 3-
1-a
2L
(A) <2L² + 3a
(8
24xx)
1-3a
1-30
30
1-a
1-3o
2a
2T2
8 24x
I-a
r
+
1
1 1- 3a
1
8
Bounding (B): In the first stage, with the learning rate set at 1/: = we observe:
1/3 113
and Σi=1
|V,
< 1T/33
L
L
vv
L.
72/3
71/3
For the second stage, our analysis reveals:
||v;||
L
T
1-2a
L
l|
2(اا T
Ei
l|v:13))
2a
1
1-20
2a
T1/3
1=
t=
3
t=
17

---

where the second inequality leverages Lemma and we have:
1-2a
T.
lvvel??
2a
T1/3
1-20
L
(8
16a)²
2a
llvell?
2a
(8
16a 1-2a
T1/3
(=
(8 16a)²
(6a))1-20))
20
22a
lvell
2a
871/3
where the inequality is due to Young's inequality, such that ry S 2ar + (1 positive z, y. Very similarly, have:
2ayy1
20 for
L
T
1-2a
l|ve 1
1 2a
11/3
1-20
1-20
L
8 - 16a
1 -
vell?
2a
8 16a
71/3
1-a
1-a
0
8
16a
1-n
|
1
1
2a
1
T1/3
where the second inequality employs Young's inequality, such that ay for positive v; y- Combining all the above, know that
T-a x
1-20
y/ 1-26
24
(8 16a)
L 8 16x
B < L + 2a
2a
1-20 1
Bounding (C): Given that 3 = 2/3 and ntt < T 1/3, we can easily know that (C) S 20
So far, bound all terms in Lemma 2 and deduce
T 2
LHS E
V
E
:
RHS
E
+
Coo,
T1/3
4
where
Co = (2A, + 30 + + 21.2) + 33
2L2
(8 - -24a) 1-3xx 2-
3u
30
2a
2L
8 24a
1-3n
(8 16a))
1 L
2a
(15)
3a
20x
1-0
@x
8 16a
+
1
20
1 a
These suggest that
e-1
E
Σ
||vel
2
S
C/T
E < 4Co.
With the definition of T, we know that
T
1-0
1
E
min
1v.12
llvel1?
4Co.
71/3
T1/3
t=s
18

---

which indicates the following by applying Jensen's 's inequality:
T
E
Ivll
S ma (4C6)
Also, because of Jensen's 's inequality, we have:
27
2
E
Ml
E
vell
=
llvell
T
T
8-1 1
E
1/211
E
lvvl
T
T
COTI/33
1OT
T
Summing up. we have proven that
Σ Ivll
S max maxx)3(Co) (C))) (4Cg) शा ms }7 1/3. 1/3
(16)
Finally, we finish our proof by introducing the following lemma.
Lemma 3 Suppose 0 < B < 1, our method ensures that
Σ [IM-
S 2/2
2L
th vz 2
B
Proof 3 First note that we have already proven the following in equation 77
E - [ S (1 V
2,3 2 + 2 [n> [[]]
After rearranging the items, we can get the following:
E lIve - (xxx))
_ E
[|v.
- vx(x)))
- EE | 11v+1--//1 -V(x++((((+)111)) + 2,30²
2L
+
E
vi [|ve112]
3
By summing up, we have:
21. T
Σ lIve- vs(x))) s F B [Iv [/(x))) + 2B80T
E "
[v.l]]]
(17)
B
Since we use a large batch size in the first iteration, that is, By 1/3
we can now ensure that
E 2l - ((xx)) s ²² d² Tm/a- Note that T2:3. first term equals 2T and the
second term reduces to 20 133 To this end, we ensure
T
2L T
Σ - 300
> E H
[=1
Thus we finish the proof for this lemma.
Here, we bound the term
21
EE= oi ||vell follows. In the first stage, with 7 7178. we have:
T
-1
B
21
th V. 2|
2L Σ
&
8
19

---

For the second stage, the analysis gives:
2L
Vell 2
3 ii | 2 <21212/3
T 2 E |/ 2
1-2a
2T,722033 ((1 - -2a)//// (2))/T)/--1 1.)1-20
1 1 2a ((1 (1-2a)) L)) 11-20
Σ
livell
21 2T,272033/ ((1 -2a)// 11)==-2a---
1/2xx
220
1 1
(2L 22)22///1/ -2x
2a T +
T
22a
L
||vell
1-26 2a
[=1
where the second inequality uses Lemma | and the third one employs Young's 's inequality, such that 20xyy --zz for positive x, We also know that
ay S 20x 2o
2L
vell
th vell 22L272/3
Σ
3
21,2T20/2
1 2a
T
1-20
T
1-20
Σ
llvell?
1-2a
1-2a
(1 - aL
2a
0
21,27a/33
(1 a T
1 - 20x
Ta
20
+ +T L
T
l|vell?
1-a
- 20
1=8
2L2
1 - 20
1-20
T-a
1-n
T2/3 + T L
Σ
T
llvell
1-a
a
1 2a
(1 a
where the second inequality uses Lemma [ and the third one employs Young's 's inequality, such that zy S I a + I-a y am for positive
As result, we have:
T
Σ E
live - [((x))]
t=1
1-a
30 4CoL + L 1420 2((1 - 2a)" 1-20
({1)2a)
2
1 - 2a
1-26
T-o
1/3
<
2x
1- 2a
1 1 a
By integrating these findings, we can finally have:
T
C'
E
(x:)ll
< E vell
Σ
V (x;:) - vell
5
T1/3
where
C'
m3x(33())+,(CC)) + (4Cn) hाー1j
302 + +C0LL +
1+20 20
2(1 2xx22
2a
+ [1!
20
1-a
1 - 2a
1 2a
0 A " + i0 + +
20

---

with Co defined in equation (15) We find that larger a leads to better dependence on L and worse reliance on parameters A and For + 3. we can obtain that
T
3/4
0 3/2 + L3/2
E
f(x)ll
S 5o
T
T1/3
Since we require 0 < a < in practice, we can use = 0.3 instead, which leads to a convergence to +1.
rate of O
7173
B Proof of Theorem 2
Since 2 + 21 +.... 2k-1 2* running the algorithm for T' iterations guarantees at least K- [log(T) complete stages. In the theoretical analysis, we can simply use the output of the last complete stage the analysis of Theorem [ leads to the following guarantee:
[Tog(T) which has been least run for 2 2 T/4 iterations. According to we have already known that running the Algorithm I for T iterations
to - + L
A m
+ T
+
L
[ SO
(T/4)
T1/3
which is on the same order of the original convergence rate.
C Proof of Theorem 3
According to equation
[4] we have already proven that
T < 2x(x)) 2F (x(x++1)
T Σ n L l|vell
Σ ne 1l.l
Te [VF
Then we bound the term
Σ 11t Vx( vlll as follows:
[VF(x)) v. < (
+2 2
$ 2C L [x: - / 2 + 1lve Vf(u))
Define that G2 VI then have:
E Ih Vx..))
vell 2C
E ne l1g(x))
u.
+
> E T palllv:
G+1l
For the term Σ E ne Ilv, G+ll3]
following the very similar analysis of equation 11). we have
the following guarantee:
B [ -
< (1 B) 10l1v=-Gh GGll
+ Be (
+ 22 V
- (oaa
< (1 - - -
+ 1 |v=l1]]] + 40 [1 - u.ll
21

---

That is to say:
E Te lIve
Gell
40 L
T 2
S
71
V1 G11l²
+ 1C
Σ 11
+
E
me lIve 12
3
3
12 T
?1 ||10411 - uel?
B
22 T
40 T
5(1 511+409)02
E vell +
E
|u+11 u uell"]
where the last inequality due to the fact that 3 = 2/33 T) S T 7
1/3
and we use a large batch size
1/e ur - First, T1/3 in the first iteration. Next, further bound the term Σ E
can ensure that:
Ee, [lu. - 11/
Ec, [18(g(xci (e) 1;-1) + (1 ()xxx: g(x)-1:)))1
Ecc [118(((()1) - -1,)) + (0(xx; (t) - g(x(-1: + 8(g(x1-1: - -
3 [19(x-11) n || + 33302.
So we know that
ne 11u11 - u.l
T
<33
We (g(()))) uell -
+ +380 P
Σ
So far, have
IVF()))
<660 L
E
Tht ||u, - s(x:))13
80 + 240 L T
+ (2+ 22422233000 |
me [Iv.l
3
Next, can bound Σ Me ||u 9(xx)1l following equation
11 as:
20
2,30² + |lu g(xx))1 < 3 (lue - -0x))l(x)1=== -Bç.. [luet] - s(x++1)1())
||ve|
B
So can have
T
T
20 T
E
Th - - 1xx))12
<
m
I|u - s(x1))12
+ 2,30 2E
Σ 1/1
R
1/5
3
3
20
< 2
E
mi
v. 11
3
t=
22

---

where the last inequality due to the fact that 3 = = S 1/3, and we use a large batch size T1/3 in the first iteration. Combining all, we have:
E To [voll] 2 + 82+ 1 L2)00
T
T t v:
(80 760
2
LE
2
Treating Ap. C, I, as constant, the above inequality is very similar to Lemma the very similar analysis after Lemma
Thus following
2
we can show that:
T
E
Σ
vill
=0(T-113)
T
==1
According to previous analysis, we also have that
T
E
[Vxx(x)) - vell?)
T
E |lue -(xx))1 8C + 24
T
2260² L
E
2
B
[=1
(2 + 8C2 + 2A
<(2+8C* 1020 102C
Σ
||
which is similar to Lemma and leads to Σ E [[) -vll
v.ll /T|
& O(T 1/3) following the
same analysis. Combing all these together, we can deduce that
VF(x)I s 1(T3)
T
which finishes the proof of Theorem
D Proof of Theorem 4
Due to the smoothness of F(x), have proven the following in equation
[4
T
T >
Σ Me 1|v.l1 < (x,) 2F (xT+1)
|V((x)) - vill +
m
L 1l
t=1
For the LHS, we have the following guarantee:
T
|vel
T
1-a
Σ Th 1v,
2
M
l|v
Elm ||
Then, we bound the terms in the RHS. First, we have the following lemma.
Lemma Define that ze = (x.) - g: + a El gi. we have:
T
T
T
E
Th [VF(x)) - voll2
< 2B3
Σ
The [V((())))) - 111
2L
||v.
23

---

Proof 4 According to the definition of Zt, the estimator Va can be expressed as
Vr (1 11--3vv--- 3)v + B2. + (1 (VJ, Vii, (xc-1)).
Note that Ex44 [2++]] F (xx+11) and we have:
Bi4+1 |VF((x+11) - 1(+1
Bitt1
[|(( 3)v, + 324+1 + (1 - (3) (V (1n11(4411 V (x.)) VF((x+1))]
[1I(1 B
8)(v, - VF(xx)) 3(1+11 VF((x+1))
+(1 3) (Vit, (x++1) - Vin+ (x,) VF(x)) VF(((+1)) [P]
[1 - 8)(v, (F(x,) 1|1 Bic,, [11 - VF(x++1))
+(1 9) (VS4+t (x++1) 7/i,,((()) Vx())) VF(x++1)
(1 - 8)8 |V, VF(x,)] 2,3 || V
(18)
2 - E). V (x(+1) Tftni(Xi + VF(x)) VF(x++1]
(1 8)3 IV. VF(x,)]1 + 2/3
|12++1-V VF((++1111?
+ 2(1 B ||V (x++1) (/icsi (x:)1
$ (1 8)3 1V, FF(x))1 )1 1,
|| (F(( 11
21. ||x+1 x.11?
(1 8) ||v. - VF(x))1 F.
|| - (F((++1) +
2T. ||v.|
Rearrange the items and multiply the both sides by mhy we can get the following:
Tl - VF(x)I1
<E The Ive
VF(x))]
E
T1t
V241
F )1
2L2
28E
|1:11 - Fx(++1))1
+ B
m/ vv 11
Note that 1/ is non-increasing, By summing up, we have:
T
E
ne lIve [F(x:)11
T
2T T
<
7/
v1 - VF(x1)11 + 2/3
E
VF
)11
Tre
||
B
3
Since a full batch in the first iteration, can finish the proof of this lemma.
Next, we bound two terms in the above lemma.
Lemma 5 We can ensure that
T
28
E
|VVF(x++)) - 2,41
<
121
V2
||
3
t=1
24

---

Proof 5
B
Th V [ 20-11
=Ba,11
1/
[F(x++1) Visces (xe-1)
96+1
211
1
n
=Bi++
71
V fint (x(+1)
91+1
i++1
VF
9
(19)
i=1
te-1 ||2]
<Bi++
V fittz (x++1) - 9i+1
([((((tt))))) - 16-1l1?
T1 1=1
where the last equation is due to the fact that it41 is randomly sample from {1,2, ... n). .., Note that we also have that
[f((x(-1) - - Bicts Te Viree (x(+((xx))))
gi+211²
2:11 1']
-9i+1
71
E E
(e + 2m) V/ (xc+1) Visces (xx)]] + 11 + 2n
|
Virets (x1)
92+1
8:13
1
Viii - git1 || |
<Eig
(1 + 2m) 12 ||ve|1 + (1+
2n
<li...
(1+ + 22) |vel1
+mc(1 + 2n
1 (a- V fict (xx) gt
t++1l"
+ 71
|
fi (xx) - V (xx: (xx [²²]
1)
V ( - gi 1 1"]
<Biei1
3nLL2 2 vel? + 11(1
<3nL2me I| (1-
1
Th [[(()))) - -9ill
2n
n
That is to say, we ensure that
T [[((((+1) - sizal
The [[[(((((++)) -
S3m13 /iell +
(1-
1
[f.(x,)) -:'l?"
Tt
2n
n
By rearranging and summing up, we have
T
T
n
me IVVf((x)) - sill 2 3nL
Σ
ll
Σ
[f(xx) g
m
2n
1=1
i=1
Since we use full batch n in the first iteration, the second term equals zero, and thus we obtain:
Σ Th [V)()) - oill = 6n
Σ
T
T
1v
61.2 T
m 1|
m
52
t=1
which leads to the result of this lemma.
Lemma 6 We have the following guarantee:
2L
T
V1
2a
21,2
(24 72a
1-30 30
1-a
1-a
20
T
||
2
1-a
1 3x
- (x
24
Vni
t=1
25

---

Proof 6
T
2T.2
||
B
1=1
Vz ||
=2L n Σ
M/ 2
lveel
2L
2
30
Ei=1 \vvl
1-3a
2L
1
voll?
3a
1=1
2L
224-70 - 72a
1-3e
1 - a
1-5n
T
1-30
l!vel
3a
1-a
24 72a
[=1
1-30
1-a
1-a
2 1- 1-a a
2a
2L
24 72a
1-n
+
1
|v.
???
1 1
3a
1 1 a
24
Vn
where the last inequality employs Young's 's inequality, such that xy positive T, y-
2a
30 T-a
y
3ta
for
Lemma 7 We can ensure the following guarantee:
T
a L
4 - 80
T
1-a7
E
L
1vv1??
s
+
E
1-a
1-20
1
t=1
Proof 7
L
=L Σ
2a
1--a
-i=1
||v:1]
1-2a
L
1
livel
2a n l-aa
1-20
L
1
20
1=1
L
4 - 8(x
1-2
1 -
To
T
1-2a
||
|
20
1 - (k
4 80
t=1
1-28
1-a
T
1-a
L
4 80
1-a
|| 2
1- 2a
1
VII
where the last inequality employs Young's inequality, such that zy < positive y. Combing all these, we have already proven that
2a T-a
2m
for
I-a
1
E
Σ nc 1vol
2
E
Vell
11
1-7
3
1
m llv 2 < C3
+
1
26

---

where
14a
2L
24 - 72a
T-o
C3 =2A +
1-0
- 30
1 -
1-2a
L
4 - 8a
1-a
1 a
2a
1 - a
So we can know that:
1-a7
1
E
Vvell ?
S 4C3.
which indicate that
1-a7
1-a
E
1
Σ
/vell
S S4C3
Vn
T
T
as well as
T
n/11
Σ
Ivel
(4C3)
T
71/22
To finish the proof, we also have to show the following lemma.
Lemma 8
T
E
[F(x))
voll?
ayn
14L2
2 - 4a
1-2a
I-n
n
L E
T
lvell
1-0
1-a
1- 2a
(1 L.
2
1=1
Proof 8 According to the previous proof, we know that:
T
Σ E
[VF((x)) -
-vel? vell2]
T E
T
2
T
23
[V(xx- m+t1l?]]
2T.
+
E
||vel?
s 14n1.3
E
12]
Also, we can deduce that:
T
T
||
14mL2 2
th 1lvll 2
=14I² n
Σ
||
1==1
1
T
1-20
Σ
|illl
1=1
1
2 4a
(1
(1 - a)n L
1=2a
I-a
T
1-2a
Σ
viell
1 2a
(1 - a) L L
2 - 4a
1-20
1-a
1-a
n²
2 - 4a
1-a
L
|vel
1 1 2x
(1- ann
2
where the last inequality employs Young's 's inequality, such that ay S positive x, y.
1-a
1-a
1-
1-a
y
1-20
for
27

---

As result, we can ensure that
T
T
T
(
|II
Vell
+ T
[x(x)
vell
T
1=1
1/4
14I?
2 4a
1-2
20 (4Cx) शांーo
(4Cx))
T1/2
1 2a
(1 aLL
((4
n//4
-0
|
+ L
71/2
E Proof of Theorem 5
The analysis is very similar to that of Theorem and the difference only appears in Lemma this new method, we can also prove the same lemma:
5 For
Lemma
T 23
E The [F(((+1)
- 11 I 12L
vv 2
Proof 9 This time, we have Z4+1 (1e41((441) V Viren (x+) + VF((x)) And we can know that:
E 11
|VFF(x++1) - 21+2
E E14
1t VF((++1 V fiees (xx-1) + V fires (x,, VF(x,))1
1/ | fi+z (x++1) fiots (x+))))
1m 2
||x++1 - x111
Sm T.21
||i+1 xx,12
t=
LmL'I
1
2 Th ||v11 s L22 Σ nh ||vel
im
By summing up, we have
T
23
E
2
-
1=1
<28E
La
2
Σ
lvel?
<
2
1|
The other analysis is exactly the same as that of Theorem
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims presented in the abstract and introduction accurately represent the contributions and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The theoretical results demonstrated in the paper rely specific assumptions, which have been clearly stated in the main text.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification:
The paper provides assumptions and proofs for each theoretical result.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: The paper discloses the information necessary to reproduce the main experi- mental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibilityy may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification:
Due to privacy concerns and ongoing research, do not include the code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /tti:///guideeeoooouuuuumbbbbi ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper describes the training and testing details.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports error bars.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
31

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided the relevant information.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification: Ethics.
The research conducted in the paper conforms with the NeurIPS Code of
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This is primarily theoretical paper with potential negative social impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The creators or original owners of assets used in the paper are properly credited and the license and terms of use explicitly are properly respected.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the batasets.papersstt paperswi thcode. cww/ datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "Wb19qfhb9L", "reviewer": "Reviewer_G4tN", "summary": "This paper studies adaptive variants of STORM, a variance reduction technique proposed by Cutkosky and Orabona (2019), for nonconvex stochastic minimization problems. Through introducing a novel adaptive parameter and step size tuning method, the authors aim to remove the bounded gradients and bounded function values assumptions in existing literatures while achieving the optimal convergence rate without an additional penalty of $O(\\log T)$ term due to adaptiveness. Based on the same techniques, they further propose Compositional STORM for compositional functions and STORM for finite-sum problems. They support their theoretical claims with numerical experiments on image classification and small-scale language modelling tasks.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. Their proposed method can achieve optimal convergence rate of $O(T^{-1/3})$ under more relaxed assumptions, namely by removing the need for bounded function values and bounded gradients. Their method does not incur a $\\log(T)$ term penalty like in other adaptive methods (Liu et al., 2022).\n2. They show that their learning rate design and analysis technique can be extended to stochastic compositional problems under further assumptions, namely Lipschitz continuity. \n3. Although rather unsurprising, they show that when the finite-sum structure is present, their method can be adapted to and showed improved convergence rates of a log factor over existing methods.", "weaknesses": "1. My understanding of the original non-adaptive STORM proposed by Cutkosky and Orabona (2019) does not have a log factor in their convergence rate when noise is present. Specifically their convergence rates in expectation is $O(\\log T / T^{1/2} + \\sigma^{1/3} / T^{1/3})$, thus the $\\log T$ term is dominated and should not appear in your big-O convergence rates in many places of the paper (e.g., Line 28, and Table 1). Can you please explain and check your comparisons?\n\n2. I am not sure about the significance of removing the bounded gradients and bounded function values assumption in practice. Cutkosky and Orabona (2019) proposed an adaptive $G_t$ approach to remove the bounded gradients assumption in their original paper, while bounded function values seems to be a very mild assumption under smoothness conditions when the final bounds all depend on the initial function value gap. Thus, I do not agree with the authors claiming them to be \"strong assumptions\". It would be useful if the authors can provide examples to justify why these assumptions can be problematic in practice.\n\n3. The authors should be clearer that their extension to stochastic compositional optimization is not exactly under weaker assumptions. They require standard Lipschitz continuity assumptions which have been standard in the literature, which in essence is same as bounded gradients.\n\nOverall I think this paper has potential but may benefit from addressing the above points.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for the constructive review!\n\n---\n\n**Q1:** My understanding of the original non-adaptive STORM proposed by Cutkosky and Orabona (2019) does not have a log factor in their convergence rate when noise is present. Specifically their convergence rates in expectation is $O(\\log T / T^{1/2} + \\sigma^{1/3} / T^{1/3})$, thus the $\\log T$ term should not appear in your big-O convergence rates.\n\n**A1:** Although the convergence rate presented in the paper [Cutkosky and Orabona, 2019] is indeed $O(\\log T / T^{1/2} + \\sigma^{1/3} / T^{1/3})$, it is not accurate after checking the proofs in detail. Specifically, at the end of Section 5 of their paper, they claim that \n\\begin{align}\n\\mathbb{E}\\left[\\sum\\_{t=1}^{T} \\frac{||\\nabla F\\left(\\mathbf{x}\\_{t}\\right)||}{T}\\right] \\leq \\frac{\\sqrt{2 M}\\left(w+2 T \\sigma^{2}\\right)^{1 / 6}+2 M^{3 / 4}}{\\sqrt{T}} \\leq \\frac{w^{1 / 6} \\sqrt{2 M}+2 M^{3 / 4}}{\\sqrt{T}}+\\frac{2 \\sigma^{1 / 3}}{T^{1 / 3}} ,  \n\\end{align}\nwhere they utilize $(a+b)^{1 / 3} \\leq a^{1 / 3}+b^{1 / 3}$ in the last inequality and $M$ is a complex term containing the $\\log T$ term. However, they neglect the $\\sqrt{M}$ factor in the last term, which should be:\n\\begin{align*}\n\\mathbb{E}\\left[\\sum_{t=1}^T \\frac{||\\nabla F\\left(\\boldsymbol{x}_{t}\\right)||}{T}\\right] \\leq \\frac{\\sqrt{2 M}\\left(w+2 T \\sigma^{2}\\right)^{1 / 6}+2 M^{3 / 4}}{\\sqrt{T}}\\leq \\frac{w^{1 / 6} \\sqrt{2 M}+2 M^{3/4}}{\\sqrt{T}}+\\frac{2 \\sigma^{1 / 3} \\color{red}{\\sqrt{M}}}{T^{1 / 3}} . \n\\end{align*}\nAs a result, the $\\log T$ term should appear in the big-O convergence rates.\n\n---\n\n**Q2:** I am not sure about the significance of removing the bounded gradients and bounded function values assumption in practice. Cutkosky and Orabona (2019) proposed an approach to remove the bounded gradients assumption in their original paper, while bounded function values seems to be a very mild assumption under smoothness conditions when the final bounds all depend on the initial function value gap. Thus, I do not agree with the authors claiming them to be \"strong assumptions\". It would be useful if the authors can provide examples to justify why these assumptions can be problematic in practice.\n\n**A2:** Thank you for your valuable comment! First, although Cutkosky and Orabona (2019) remove the bounded gradient assumption, their newly proposed algorithm introduces two new drawbacks: \n(1) As stated in their paper, this method requires knowledge of the true value of gradient variance $\\sigma$, which is impractical; (2) The learning rate of this new algorithm is deterministic, i.e., $\\eta_t = \\frac{k}{(w+\\sigma^2 t)^{1/3}}$, which cannot adjust according to the stochastic gradient anymore. Second, the bounded gradient assumption is still required in the STORM+ method [Levy et al., 2021], and it cannot be removed using the same technique as Cutkosky and Orabona (2019) due to the more complex analysis involved in STORM+. \n\nRegarding the bounded function value assumption, we believe it is indeed a strong assumption. The most commonly used linear and quadratic functions are both smooth but have unbounded function values. Furthermore, this assumption introduces an extra term related to the function value upper bound in the convergence rate. Specifically, STORM+ [Levy et al., 2021] achieves a convergence rate of $\\mathcal{O}\\left( \\left(B^{3/4} + L^{3/2} \\right) \\sigma^{1/3} T^{-1/3}\\right)$, where $B$ is the upper bound of the function value. The overall convergence rate can be significantly impacted when $B$ is large.\n\n---\n\n**Q3:** The authors should be clearer that their extension to stochastic compositional optimization is not exactly under weaker assumptions. They require standard Lipschitz continuity assumptions which have been standard in the literature, which in essence is same as bounded gradients.\n\n\n**A3:** We agree that in stochastic compositional optimization, the required Lipschitz continuity is equivalent to the bounded gradient assumption. However, this assumption is inherently introduced by the compositional optimization itself rather than by our adaptive techniques. Note that the bounded gradient assumption is essential and widely required in the literature for stochastic compositional optimization [Wang et al., 2017, Yuan et al., 2019, Zhang et al., 2019]. Additionally, we would like to emphasize that our method does not require the bounded function value assumption, which would be needed if we attempt to apply the same techniques from STORM+ [Levy et al., 2021] to stochastic compositional optimization. We will incorporate these clarifications into our revised paper to make it more clear. \n\n---\n\n**References:**\n\nA. Cutkosky and F. Orabona. Momentum-based variance reduction in non-convex SGD. NeurIPS, 2019.\n\nLevy et al. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. NeurIPS, 2021.\n\nWang et al. Accelerating stochastic composition optimization. JMLR, 2017.\n\nYuan et al. Efficient smooth non-convex stochastic compositional optimization via stochastic recursive gradient descent. NeurIPS, 2019.\n\nZhang et al. A stochastic composite gradient method with incremental variance reduction. NeurIPS, 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "vrAYFrmGNb", "reviewer": "Reviewer_qB9i", "summary": "This paper studies non-convex stochastic optimization under the assumption of mean-square smoothness. It introduces, Ada-STORM, a variant of the STORM algorithm, which achieves the optimal rate $O(T^{-1/3})$. Unlike vanilla STORM, Ada-STORM eliminates the $O(\\log T)$ factor and does not require the Lipschitz assumption. The algorithm's success hinges on a carefully designed adaptive learning rate schedule. Instead of the standard AdaGrad learning rate $\\eta_t \\approx (\\sum_{i=1}^t \\\\|g_i\\\\|^2)^{-1/3}$ used in STORM, Ada-STORM employs $\\eta_t = \\min\\\\{T^{-1/3}, T^{-(1-\\alpha)/3}(\\sum_{i=1}^t \\\\|v_i\\\\|^2)^{-\\alpha}\\\\}$ where $\\alpha < 1/3$ and $v_t$ is the STORM update.", "questions": "- Is there a specific reason why the authors prefer $\\alpha$ as large as possible in the trade-off of $\\Delta^{1/2(1-\\alpha)} + \\sigma^{1/(1-\\alpha)} + L^{1/2\\alpha}$. Is it due to the assumption (or some empirical observation) that the smoothness constant $L$ is usually the dominating parameter?\n\n- In the experiments, did the authors apply any learning rate scheduler (e.g., linear decay or cosine decay) on top of the adaptive learning rate? Although somewhat tangential, it would be interesting to compare the new adaptive scheduler with other popular schedulers.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The proposed algorithm, Ada-STORM, achieves the optimal rate $O(T^{-1/3})$ without the log factor. Unlike STORM+ which also eliminates the log factor, this algorithm does not assume $f$ to be Lipschitz and bounded above. This improvement represents a significant contribution. Moreover, the required modification is straightforward: it involves merely adjusting the learning rate scheduler $\\eta_t$ and the momentum factor $\\beta_t$. I particularly enjoy the constant momentum constant $\\beta_t\\equiv T^{-2/3}$ rather than time-varying and dependent on $\\eta_t$.\n\nIn addition, the proposed learning rate scheduler is of interest in its own right. The paper extends the application of this learning rate technique to related problems, achieving optimal rates in composite optimization and finite-sum optimization (ERM). Finally, empirical experiments also validate Ada-STORM's performance, which matches or outperforms existing STORM variants and other state-of-the-art optimizers.", "weaknesses": "One major concern pertains to the technical correctness of the proof of Theorem 1, in particular from line 440-444. I don't immediately see how $\\mathbb{E}[\\sum_{t=1}^{s-1} \\\\|v_t\\\\|^2] \\le C_0T^{1/3}$ implies $\\mathbb{E}[\\frac{1}{T}\\sum_{t=1}^{s-1}\\\\|v_t\\\\|] \\le \\sqrt{C_0}T^{-1/3}$, and similarly how the equation in line 441 implies line 442. My concern arise from the fact that $s$ is a random variable dependent on the entire history $\\mathcal{H}_T$. As a result, applying Jensen's inequality like $\\mathbb{E}[\\frac{1}{T}\\sum\\_{t=1}^s\\\\|v_t\\\\|] \\le \\sqrt{\\mathbb{E}[\\frac{1}{T}\\sum\\_{t=1}^s\\\\|v_t\\\\|^2]}$ seems to be inappropriate when $s$ is a random variable dependent $v_t$'s. It's likely that I miss something, and I encourage the authors to elaborate this part of the proof to make it clear. \n\nAnother concern is about the doubling trick. In each stage $k$, the guarantee is \n$$\\frac{1}{2^{k-1}} \\sum_{t=2^{k-1}}^{2^k} \\mathbb{E}\\\\|\\nabla f(x_t)\\\\| \\lesssim \\frac{\\Delta_f^{3/4}+O(1)}{(2^{k-1})^{1/3}}.$$ \nSince the algorithm is not resetting $x_t=x_0$ in the new stage, the parameter $\\Delta_f$ is not constant. In particular, in stage $k$, $\\Delta_f = \\mathbb{E}[f(x_{2^{k-1}}) - \\inf f(x)]$. Consequently, the doubling trick implicitly assumes $f$ has bounded function value in order to bound $\\Delta_f$ in all stages. \n\nIf the authors can address my major concerns, I am inclined to revise my score upwards, given the otherwise strong results of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments, and we will revise our paper accordingly! We have addressed the major concerns about the proof as outlined below. We sincerely hope that the reviewer can examine them and reevaluate our results.\n\n---\n\n**Q1:** One major concern pertains to the technical correctness of the proof of Theorem 1, in particular from line 440-444. I don't immediately see how $\\mathbb{E} [\\sum_{t=1}^{s-1} ||v_t||^2] \\leq C_0 T^{1/3}$ implies $\\mathbb{E}[\\frac{1}{T}\\sum_{t=1}^{s-1}||v_t||] \\leq \\sqrt{C_0}T^{-1/3}$, and similarly how the equation in line 441 implies line 442. My concern arise from the fact that $s$ is a random variable dependent on the entire history $\\mathcal{H}\\_T$. As a result, applying Jensen's inequality like $\\mathbb{E}[\\frac{1}{T}\\sum_{t=1}^s||v_t||] \\le \\sqrt{\\mathbb{E}[\\frac{1}{T}\\sum_{t=1}^s||v_t||^2]}$ seems inappropriate when $s$ is a random variable dependent on $v_t$'s.\n\n**A1:** Sorry for omitting the details. We provide a more detailed analysis as follows, which will be added to our revised paper. First, we use the inequality $\\mathbb{E} [X] \\leq \\sqrt{\\mathbb{E}[X^2]}$, which is due to Jensen's inequality. By setting $X = \\frac{1}{T} \\sum_{t=1}^s||v_t||$, we obtain $\\mathbb{E} \\left[ \\frac{1}{T}\\sum_{t=1}^s||v_t|| \\right] \\leq \\sqrt{ \\mathbb{E}\\left[\\left(\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right)^2\\right]}$. We think the above inequalities hold regardless of the fact that $s$ is a random variable dependent on $v_t$'s. Furthermore, even without using Jensen's inequality, we can still prove the same result as follows:\n\\begin{align}\n    0 \\leq& \\mathbb{E} \\left[ \\left( \\frac{1}{T}\\sum_{t=1}^s||v_t||  -  \\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right] \\right)^2\\right]\\\\\\\\\n    =& \\mathbb{E} \\left[  \\left(\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right)^2 \\right]  +\\left( \\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right] \\right)^2 - 2\\mathbb{E}\\left[\\left\\langle \\frac{1}{T}\\sum_{t=1}^s||v_t||, \\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right]\n \\right\\rangle\\right] \\\\\\\\\n =& \\mathbb{E} \\left[  \\left(\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right)^2 \\right]  -\\left( \\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right] \\right)^2,\n\\end{align}\nwhich indicates that $\\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right]  \\leq \\sqrt{\\mathbb{E} \\left[  \\left(\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right)^2 \\right]} $. We can complete the proof by noting that:\n\\begin{align*}\n    \\mathbb{E}\\left[\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right]  &\\leq \\sqrt{\\mathbb{E} \\left[  \\left(\\frac{1}{T}\\sum_{t=1}^s||v_t||\\right)^2 \\right]} = \\sqrt{\\mathbb{E} \\left[ \\frac{1}{T^2} \\left(\\sum_{t=1}^s||v_t||\\right)^2 \\right]} \\\\\\\\\n    &\\leq \\sqrt{\\mathbb{E} \\left[ \\frac{s}{T^2} \\sum_{t=1}^s||v_t||^2 \\right]} \\leq \\sqrt{\\mathbb{E} \\left[ \\frac{1}{T} \\sum_{t=1}^s||v_t||^2 \\right]} \\\\\\\\\n    &\\leq  \\sqrt{ \\frac{1}{T} C_0 T^{1/3}} = \\sqrt{C_0 }T^{-1/3}.\n\\end{align*}\n\n---\n\n**Q2:** Another concern is about the doubling trick. In each stage $k$, the guarantee is $\\frac{1}{2^{k-1}} \\sum_{t=2^{k-1}}^{2^k} \\mathbb{E}||\\nabla f(x_t)|| \\lesssim \\frac{\\Delta_f^{3/4}+O(1)}{(2^{k-1})^{1/3}}$. Since the algorithm is not resetting $x_t=x_0$ in the new stage, the parameter $\\Delta_f$ is not constant.\n\n**A2:** We apologize for the confusion. In the analysis, we actually reset $x_t=x_0$ at the beginning of each new stage, and we will clearly clarify it in the revised paper. This reset ensures that the initial gap can always be bounded.  Since the iteration number doubles with each new stage, we can guarantee that the last complete stage has at least $T/4$ iterations. According to the analysis of Theorem 1, running Algorithm 1 for $T/4$ iterations leads to the following guarantee:\n\\begin{align}\n    \\mathbb{E}\\left[ ||\\nabla f(\\textbf{x}_{\\tau})||^2 \\right] \\leq \\mathcal{O}\\left(\\frac{\\Delta_f^{\\frac{1}{2(1-\\alpha)}}+\\sigma^{\\frac{1}{1-\\alpha}} + L^{\\frac{1}{2\\alpha}}}{{(T/4)}^{1/3}}\\right)=\\mathcal{O}\\left(\\frac{\\Delta_f^{\\frac{1}{2(1-\\alpha)}}+\\sigma^{\\frac{1}{1-\\alpha}} + L^{\\frac{1}{2\\alpha}}}{{T}^{1/3}}\\right).\n\\end{align} \n\n---\n\n**Q3:** Is there a specific reason why the authors prefer $\\alpha$ as large as possible in the trade-off of $\\Delta^{1/2(1-\\alpha)} + \\sigma^{1/(1-\\alpha)} + L^{1/2\\alpha}$. Is it due to the assumption (or some empirical observation) that the smoothness constant is usually the dominating parameter?\n\n**A3:** No, there is no specific reason to prefer larger $\\alpha$ in the trade-off $\\Delta^{1/2(1-\\alpha)} + \\sigma^{1/(1-\\alpha)} + L^{1/2\\alpha}$. Whether the smoothness constant $L$ or the parameters $\\Delta$ and $\\sigma$ dominate usually depends on the specific problem. To avoid misunderstandings, We will change our expression from “larger $\\alpha$ leads to better dependence on parameter $L$” to “larger $\\alpha$ leads to better dependence on the parameter $L$ and worse reliance on parameters $\\Delta$ and $\\sigma$”. \n\n---\n\n**Q4:** In the experiments, did the authors apply any learning rate scheduler (e.g., linear decay or cosine decay) on top of the adaptive learning rate? Although somewhat tangential, it would be interesting to compare the new adaptive scheduler with other popular schedulers.\n\n**A4:** We did not apply learning rate scheduler on top of the adaptive learning rate in the experiments. Based on your suggestion, we conducted additional experiments comparing the STORM method with linear decay and cosine decay schedulers. The results are shown in **Global Response (Figure 2)**, which indicate that the performances of STORM with linear decay and cosine decay are still worse than our proposed method in terms of testing accuracy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "eFjr3Ovkss", "reviewer": "Reviewer_2239", "summary": "This paper proposes a novel adaptive STORM method that achieves an optimal convergence rate of $O(T^{-3})$ for nonconvex stochastic optimization, which requires weaker assumptions and attains the optimal convergence rate without the additional $O(\\log T)$ term.", "questions": "1.\tThe experimental part is relatively limited. The proposed algorithm is parameter free, so it is best to provide some experimental results to demonstrate whether these compared algorithms are sensitive to parameter changes.\n2.\tIn theory, the output {x_ \\tau} of the proposed algorithms is randomly selected from {1,..,T}. Is the output in the experiment randomly selected?", "limitations": "The authors discussed the limitations and there is no negative societal impact about this work.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "For stochastic non-convex optimization, this paper achieves the optimal convergence rate under more relaxed assumptions, which does not require the bounded function values or the bounded gradients and does not include the additional $O(\\log T)$ term in the convergence rate. The proposed technique has also been extended to stochastic compositional optimization with the same optimal rate. For non-convex finite-sum optimization, this papaer further improve the adaptive algorithm to attain an optimal convergence rate, which outperforms the previous result by $O(\\log(nT))$ factor.", "weaknesses": "Although this paper is theoretically sound in general, there are still some questions need to be discussed:\n1.\tThe experimental part is relatively limited. The proposed algorithm is parameter free, so it is best to provide some experimental results to demonstrate whether these compared algorithms are sensitive to parameter changes.\n2.\tIn theory, the output {x_ \\tau} of the proposed algorithms is randomly selected from {1,..,T}. Is the output in the experiment randomly selected?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments and suggestions.\n\n---\n\n**Q1:** The experimental part is relatively limited. The proposed algorithm is parameter-free, so it is best to provide some experimental results to demonstrate whether these compared algorithms are sensitive to parameter changes.\n\n\n**A1:** Following your suggestion, we have included additional experiments to assess whether the original STORM method is sensitive to changes in hyper-parameters. Specifically, we tested the initial learning rate from the set {$0.01, 0.1,1,10,50$}. The results are reported in the **Global Response (Figure 1)**, and we observe that the STORM method is sensitive to changes in hyper-parameters. \n\n---\n\n**Q2:** In theory, the output {$x_{\\tau}$} of the proposed algorithms is randomly selected from {$1,..,T$}. Is the output in the experiment randomly selected?\n\n**A2:** In the experiment, we simply use the output of the last iteration, i.e., $\\mathbf{x}_{\\tau} = \\mathbf{x}_T$. It is common practice to select the output randomly from {$1,\\cdots, T$} in theoretical analysis but use the output of the last iteration in practical experiments [Johnson et al., 2013, Cutkosky et al., 2019]. This is also the case for the original STORM paper. Specifically, in Line 14 of the STORM algorithm [Cutkosky et al., 2019], they state: \"Choose $\\hat{\\mathbf{x}}$ uniformly at random from {$\\mathbf{x}_1, \\cdots , \\mathbf{x}_T$} . (In practice, set $\\hat{\\mathbf{x}} = \\mathbf{x}_T $).\" \n\n---\n\n**References:**\n\nJohnson et al. Accelerating stochastic gradient descent using predictive variance reduction. NeurIPS, 2013\n\nCutkosky et al. Momentum-based variance reduction in non-convex SGD. NeurIPS, 2019.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RqbqRll3X3", "reviewer": "Reviewer_4Ggd", "summary": "This paper introduces novel adaptive variance reduction methods for stochastic optimization, building on the STORM technique. The proposed Ada-STORM method closes the $O(\\log T)$ gap and achieves an optimal convergence rate of $O(T^{-1/3})$ for non-convex functions under assumptions weaker than previous approaches. Furthermore, the paper extends the method to stochastic compositional optimization, maintaining a similar $O(T^{-1/3})$ convergence rate. For non-convex finite-sum problems, the authors develop another innovative adaptive algorithm that attains the optimal $O(n^{1/4}T^{-1/2})$ rate. Numerical experiments effectively demonstrate the effectiveness of the proposed method.", "questions": "1. Regarding Line 401, could the authors explain why the first inequality holds?\n2. In Theorem 4, is the dependency on $\\Delta_F$ and $L$ better or worse than that of previous methods?", "limitations": "This paper does not present any negative societal impacts.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "1. The proposed Ada-STORM method overcomes major limitations in existing adaptive STORM methods. It does not require bounded gradient and function value assumptions, and achieves the optimal convergence rates without the additional $O(\\log T)$ term. The problem investigated in the paper is challenging and the results are substantial.\n2. The theoretical analysis is novel and easy to follow. Extending the method to stochastic compositional and finite-sum optimization problems illustrates its flexibility and potential impact across a wide range of optimization tasks.\n3. The numerical experiments on various tasks (e.g., image classification, language modeling) validate the theoretical results and highlight the method's superior performance compared to other algorithms.", "weaknesses": "1. In Theorem 4, while the authors clearly state the convergence rate of the proposed method in terms of $T$, $\\Delta_F$, and $L$, they only present the convergence of previous adaptive finite-sum methods in terms of $T$. A comparison of other important constants such as $\\Delta_F$ and $L$ with existing methods could enhance the discussion.\n2. The content in Lines 240 to 242, especially Algorithm 4, should be included in the main body of the paper rather than being delayed to the Appendix.\n3. Some typos in the paper:\n- Line 145: $(t>2)$ should be $(t \\geq 2)$.\n- Line 516, the first equality in Proof 7: $L^2$ should be $L$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your constructive comments!\n\n---\n\n**Q1:** In Theorem 4, while the authors clearly state the convergence rate of the proposed method in terms of $T$, $\\Delta_F$, and $L$, they only present the convergence of previous adaptive finite-sum methods in terms of $T$. A comparison of other important constants such as $\\Delta_F$ and $L$ with existing methods would enhance the discussion.\n\n**A1:** According to Theorem 1 of the original paper [Kavis et al., 2022], the convergence rate of previous adaptive finite-sum methods is $\\mathcal{O}\\left(n^{1 / 4} T^{-1/2} \\left(L^2 + \\Delta_F \\right) \\cdot \\log \\left(1+n T L\\right)\\right)$. In contrast, our convergence rate obtained in Theorem 4 is $\\mathcal{O}\\left(n^{1 / 4} T^{-1/2} \\left(L^{\\frac{1}{2\\alpha}} + \\Delta_F^{\\frac{1}{2(1-\\alpha)}} \\right) \\right)$, where $\\alpha$ can be any constant within $(0,1/3)$. For example, if we set $\\alpha = 1/4$, the rate reduces to $\\mathcal{O}\\left(n^{1 / 4} T^{-1/2} \\left(L^2 + \\Delta_F^{{2}/{3}} \\right) \\right)$, which is better than the previous convergence rate.\n\n---\n\n**Q2:** The content in Lines 240 to 242, especially Algorithm 4, should be included in the main body of the paper rather than being delayed to the Appendix.\n\n**A2:** Thank you for your suggestion! We will move Algorithm 4 to the main body of the paper and add more discussion about this algorithm. \n\n---\n\n**Q3:** There are some typos in the paper.\n\n**A3:** Thank you for catching the typos. We will correct them in the revised version.\n\n---\n\n**Q4:** Regarding Line 401, could the authors explain why the first inequality holds?\n\n**A4:** To address your question, we provide a more detailed analysis here:\n\n  \\begin{align}\n        & \\mathbb{E}\\_{\\xi_{t+1}} \\left[ ||(1-\\beta)(\\mathbf{v}_t - \\nabla f(\\mathbf{x}_t)) + \\left(\\nabla f(\\mathbf{x}_t)-\\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) \\right)   + \\beta\\left(\\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t})  \\right) ||^2 \\right]\\\\\\\\\n         \\leq & \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[(1-\\beta)^2||\\mathbf{v}\\_{t} - \\nabla f(\\mathbf{x}\\_{t})||^2\\right]  + \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[|| \\left(\\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) \\right)   + \\beta\\left(\\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t})  \\right) ||^2 \\right] \\\\\\\\\n        \\leq & \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[(1-\\beta)^2||\\mathbf{v}\\_{t} - \\nabla f(\\mathbf{x}\\_{t})||^2\\right] + \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[2|| \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) ||^2  + 2|| \\beta\\left(\\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t})  \\right)||^2\\right] \\\\\\\\\n        \\leq & (1-\\beta)^2 \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[||\\mathbf{v}\\_{t} - \\nabla f(\\mathbf{x}\\_{t})||^2\\right] +2 \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[||\\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) ||^2\\right] + 2\\beta^2 \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[||\\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t})||^2\\right]\n    \\end{align}\nwhere the first inequality is due to the fact that\n\\begin{align}\n     \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[ \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1})    + \\beta\\left(\\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t})  \\right)  \\right] = 0,\n\\end{align}\nand the last inequality is due to:\n\\begin{align}\n& \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[|| \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}) + \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1})  ||^2\\right] \\\\\\\\\n\\leq & \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[|| \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}) ||^2\\right] + \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[||\\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1}) ||^2\\right]  +2 \\mathbb{E}\\_{\\xi\\_{t+1}} \\left\\langle \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1}), \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1})  \\right\\rangle\\\\\\\\\n \\leq & \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[|| \\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1})  ||^2\\right] - \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[|| \\nabla f(\\mathbf{x}\\_{t})-\\nabla f(\\mathbf{x}\\_{t+1})  ||^2\\right]\\\\\\\\\n\\leq & \\mathbb{E}\\_{\\xi\\_{t+1}}\\left[||\\nabla f(\\mathbf{x}\\_{t+1};\\xi\\_{t+1}) - \\nabla f(\\mathbf{x}\\_{t};\\xi\\_{t+1})||^2\\right]\n\\end{align}\n\n---\n\n**Q5:** In Theorem 4, is the dependency on $\\Delta_F$ and $L$ better or worse than that of previous methods?\n\n**A5:** As discussed in A1, our dependency on $\\Delta_F$ and $L$ is better than previous methods. \n\n---\n\n**Reference:**\n\nKavis et al. Adaptive stochastic variance reduction for non-convex finite-sum minimization. NeurIPS, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
## **Global Response** ##

---

In response to the request of reviewers, we provide additional experimental results in this part.

**Figure 1:** According to the suggestion of Reviewer 2239, we provide the performance of the STORM method with different initial learning rates. Specifically, we tested learning rates from the set {$0.01, 0.1, 1, 10, 50$}. The results demonstrate that the STORM method is sensitive to the choice of the hyper-parameters.

**Figure 2:** As requested by Reviewer qB9i, we include experiments on the STORM method with linear decay and cosine decay schedulers for comparison. The results indicate that the performances of STORM with linear decay and cosine decay are still worse than our Ada-STORM method in terms of testing accuracy.

Meta-review: This is a paper about stochastic optimization of nonconvex functions. The main results show that the STORM technique, which achieves variance reduction, can be shown to achieve optimal rates without overly restrictive assumptions (such as bounded gradients or bounded function values). In particular, log terms from previous work are avoided. The authors adapt the same techniques to compositional and finite-sum settings, also achieving state-of-the-art results (albeit under stronger assumptions). 

The reviewers' scores (6,7,7,7) strongly suggest acceptance, and I concur with their assessment. Although perhaps technical, it seems that the paper presents a cogent message and interesting new ideas. The discussion period was crucial in clarifying some misunderstandings and difficulties with the proofs, but the authors seem clear on which points of their manuscript need revision. Overall, I am happy to suggest that this paper be accepted to NeurIPS.
Decision: Accept (poster)