Adaptive Variance Reduction for Stochastic Optimization under Weaker Assumptions

Authors: wei  jiang
sifan  yang
yibo  wang
lijun  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 12:39:44

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.

Main paper: 
 introduction: 
 This paper investigates the stochastic optimization problemEQUATIONwhere f : R d → R is a smooth non-convex function. We assume that only noisy estimations of its gradient ∇f (x) can be accessed, denoted as ∇f (x; ξ), where ξ represents the random sample drawn from a stochastic oracle such that E[∇f (x; ξ)] = ∇f (x).Problem (1) 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 a convergence rate of O(T -1/4 ), where T 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 a 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, a momentum-based variance reduction method -STORM [Cutkosky and Orabona, 2019] is introduced, which achieves a convergence rate of O(T -1/3 log T ).Although aforementioned methods are equipped with convergence guarantees, their analyses rely on delicate configurations of hyper-parameters, 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, the gradient upper bound G, and the variance upper bound σ, which are often unknown in practice. Specifically, most algorithms require the learning rate η t smaller than O(1/L), and for the STORM method, setting the momentum parameter to O(L 2 η 2 t ) 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 as L, G and σ. Based on the STORM method, Levy et al. [2021] develop the STORM+ algorithm, which attains the optimal O(T -1/3 ) convergence rate under the assumption of bounded function values and gradients. To remove the need for the bounded function values assumption, Liu et al. [2022] propose the META-STORM algorithm to attain an O(T -1/3 log T ) convergence rate, but it still requires the bounded gradients assumption and includes an additional O(log T ) term. In summary, despite advancements in this field, existing adaptive STORM-based methods either depend on strong assumptions or suffer an extra O(log T ) term compared with the lower bound [Arjevani et al., 2023] . Hence, a fundamental question to be addressed is:Is it possible to develop an adaptive STORM method that achieves the optimal convergence rate for non-convex functions under weaker assumptions?We give an affirmative answer to the above question by devising a novel optimal Adaptive STORM method (Ada-STORM). 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 to the property of stochastic gradients, and ensure a small learning rate in the beginning. Leveraging this strategy, Ada-STORM achieves an optimal convergence rate of O(T -1/3 ) for non-convex functions. Notably, our analysis does not require the function to have bounded values and bounded gradients, which is a significant advancement over existing methods [Levy et al., 2021 , Liu et al., 2022] . Additionally, our convergence rate does not contain the extra O(log T ) term, which is often present in STORM-based methods [Cutkosky and Orabona, 2019, Liu et 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., 2012] , 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 an optimal convergence rate of O(n -1/4 T -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 -1/4 T -1/2 log(nT )) 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 O(T -1/3 ) under more relaxed assumptions. Specifically, it 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. • Our learning rate design and the analysis exhibit broad applicability. We substantiate this claim by obtaining an optimal rate of O(T -1/3 ) for stochastic compositional optimization, using the technique proposed in this paper. • For non-convex finite-sum optimization, we further improve our adaptive algorithm to attain an optimal convergence rate of O(n 1/4 T -1/2 ), which outperforms the previous result by eliminating the O(log(nT )) factor.A comparison between our method and other STORM-based algorithms is shown in Table 1 . Numerical experiments on different tasks also validate the effectiveness of the proposed method.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 in 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 as long as it is clear that these goals are not attained by the paper. 
related work: 
 This section briefly reviews related work on stochastic variance reduction methods and adaptive stochastic algorithms. NC O T -1/3 log T ✗ ✓ Super-ADAM [Huang et al., 2021] NC O T -1/3 log T ✗ - STORM+ [Levy et al., 2021] NC O T -1/3 ✓ ✓ META-STORM [Liu et al., 2022] NC O T -1/3 log T ✓ ✓ Theorem 1, 2 NC O T -1/3 ✓ - Theorem 3 NC & Comp. O T -1/3 ✓ - Theorem 4 NC & FS O n 1/4 T -1/2 ✓ -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 a 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 as the SAG algorithm. Subsequent advancement has been made by the SARAH method [Nguyen et al., 2017] , which derives better convergence for smooth convex functions.In the context of non-convex objectives, Fang et al. [2018] introduce the SPIDER estimator, which improves the convergence rate from O(T -1/4 ) to O(T -1/3 ) in stochastic settings, and to O(n 1/4 T -1/2 ) in finite-sum scenarios, with n representing the number of components in the finite-sum. Following this, the SpiderBoost algorithm [Wang et al., 2019] refines the SPIDER approach by employing a larger constant step size and adapting it for composite optimization problems. However, a common limitation among these methods is their reliance on large batch sizes for each iteration, posing practical challenges due to high computational demands. To mitigate this issue, Cutkosky and Orabona [2019] introduce the STORM method, a momentum-based technique that achieves an O(T -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.For stochastic optimization, it is well-known that the SGD algorithm can obtain a convergence rate of O(T -1/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 to adjust the learning rate based on past stochastic gradients. One of the foundational works is the AdaGrad algorithm [Duchi et al., 2011] , which proves to be effective for sparse data. Further advancements include RMSprop [Tieleman and Hinton, 2012] and Adam [Kingma and Ba, 2015] , demonstrating broad effectiveness across a wide range of machine learning problems. Later, the Super-Adam [Huang et al., 2021] algorithm further improves the Adam algorithm via the variance reduction technique STORM [Cutkosky and Orabona, 2019] and obtains a convergence rate of O(T -1/3 log T ). Nevertheless, to obtain the corresponding convergence rates, these methods still require knowledge of certain problem-dependent parameters to set hyper-parameters accurately, hence Update the decision variable: x t+1 = x tη t v t 6: end for 7: Choose τ uniformly at random from {1, . . . , T } 8: Return x τ not adaptive. 2 To solve this problem, many research aims to develop fully adaptive SGD methods that maintain the optimal convergence rate without knowing problem-specific parameters [Orabona, 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 development is the introduction of STORM+ [Levy et al., 2021] , which presents a fully adaptive version of STORM while attaining an optimal convergence rate. To circumvent the bounded function values assumption in STORM+, the META-STORM [Liu et al., 2022] approach is developed, equipped with a nearly optimal bound. However, META-STORM still requires the bounded gradients assumption, and it includes an additional O(log T ) in the convergence rate. Consequently, adaptive STORM with the optimal convergence rate and under mild assumptions still needs further explorations.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 on specific assumptions, which have been clearly stated in the main text.Guidelines:• The answer NA means that the paper has no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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.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., 2021] .Assumption 1 (Average smoothness)E ∥∇f (x; ξ) -∇f (y; ξ)∥ 2 ≤ L 2 ∥x -y∥ 2 .Assumption 2 (Bounded variance)E ∥∇f (x; ξ) -∇f (x)∥ 2 ≤ σ 2 . Assumption 3 f * = inf x f (x) ≥ -∞ and f (x 1 ) -f * ≤ ∆ f for the initial solution x 1 .Note that some additional assumptions are required in other STORM-based methods. Specifically, STORM [Cutkosky and Orabona, 2019] , STORM+ [Levy et al., 2021] , and META-STORM [Liu et al., 2022] assume the bounded gradients. Moreover, STORM+ makes an additional assumption of the bounded function values.In this subsection, we aim to develop an adaptive STORM method that achieves an optimal convergence rate for non-convex functions under weaker assumptions. Our algorithm framework is the same as the original STORM [Cutkosky and Orabona, 2019] , and the only difference is the setup of the momentum parameter β t and the learning rate η t . First, we present the STORM algorithm in Algorithm 1.The core idea of STORM lies in a carefully devised variance reduced estimator v t , which effectively tracks the gradient ∇f (x t ). For the first iteration (t = 1), we setv 1 = B0 i=1 1 B0 ∇f (x 1 ; ξ i 1 ), which is estimated within a batch B 0 = T 1/3 . Note that we use large batch only in the first iteration, and constant batch size in other iterations. In subsequent iterations (t ≥ 2), estimator v t is defined as:EQUATIONwhere the first two terms are similar to the momentum SGD, and the last term serves as the error correction, which ensures the variance reduction effect. By choosing the values of β t and η t carefully, STORM ensures that the estimation error E[∥v t -∇f (x t )∥ 2 ] would decrease gradually. In the original STORM paper, these parameters are set up as:η t = k w + t i=1 ∥∇f (x t ; ξ t )∥ 2 1/3 , β t = cη 2 t ,wherek = O(G 2/3 L -1 ), w = O(G 2 ) and c = O(L 2). The settings of these hyper-parameters are crucial to the convergence analysis of STORM. However, it is worth noting that L is the smoothness parameter and G is the gradient upper bound, which are often difficult to determine in practice.To address this problem, our approach defines the hyper-parameters as follows:EQUATIONwhere 0 < α < 1/3. Notably, our method does not rely on the parameters L and G, and also does not need the bounded gradients or bounded function values assumptions that are common in 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 η t can also be expressed in an alternative, more illustrative manner:η t =      1 T 1/3 if t i=1 ∥v i ∥ 2 ≤ T 1/3 ; 1 T (1-α)/3 ( t i=1 ∥vi∥ 2 ) α else.This formulation ensures that the learning rate starts sufficiently small in the initial stages and then changes dynamically based on the gradient estimator v t . 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 1 Under Assumptions 1, 2 and 3, Algorithm 1 with hyper-parameters in equation (3) guarantees that:E [∥∇f (x τ )∥] ≤ O   ∆ 1 2(1-α) f + σ 1 1-α + L 1 2α T 1/3   .Remark: To ensure that E[∥∇f (x τ )∥] ≤ ϵ, the overall complexity is O(ϵ -3 ), 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 O(log T ) term in the convergence rate, and our analysis does not require bounded gradients or bounded function values assumptions. Also note that the selection of α does not affect the order of T , and larger α leads to better dependence on parameter L and worse reliance on parameters ∆ and σ. Considering we require that 0 < α < 1/3, we can simply set α = 0.3 in practice.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 the iteration number in each stage gradually. Specifically, we design a multi-stage algorithm over k = {1, 2, • • • , K} stages. At the beginning of each new stage, we reset x t = x 0 . In each stage k, the STORM algorithm is executed for 2 k-1 iterations, effectively doubling the iteration numbers after each stage. In any step t, we first identify the current stage as 1 + ⌊log t⌋ and then calculate the iteration number for this stage as I t = 2 ⌊log t⌋ . Then, we can set the hyper-parameters as:EQUATION)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 2 Under Assumptions 1, 2 and 3, Algorithm 1 with hyper-parameters in equation ( 4) guarantees that:E [∥∇f (x τ )∥] ≤ O   ∆ 1 2(1-α) f + σ 1 1-α + L 1 2α T 1/3   .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? 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 circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in 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 a theoretical paper with no potential negative social impact. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is 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 to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
extension to stochastic compositional optimization: 
 To demonstrate the broad applicability of our proposed technique, we extend it to stochastic compositional optimization [Wang et al., 2017a ,b, Yuan et al., 2019 , Zhang and Xiao, 2019 , 2021 , Jiang et al., 2023 , 2024a] , formulated as:EQUATIONwhere f and g are smooth functions. We assume that we can only access to unbiased estimations of ∇f (x), ∇g(x) and g(x), denoted as ∇f (x; ξ), ∇g(x; Existing variance reduction methods [Hu et al., 2019 , Zhang and Xiao, 2019 , Qi et al., 2021] are able to obtain optimal O(T -1/3 ) convergence rates for problem (5), but they require the knowledge of smoothness parameter and the gradient upper bound to set up hyper-parameters. In this section, we aim to achieve the same optimal convergence rate without prior knowledge of problem-dependent parameters. We develop our adaptive algorithm for this problem as follows. In each step t, the algorithm maintains an inner function estimator u t in the style of STORM, i.e.,EQUATIONThen, we construct a gradient estimator v t based on u t also in the style of STORM:EQUATIONAfter that, we apply gradient descent using the gradient estimator v t . The whole algorithm is presented in Algorithm 2, and hyper-parameters are set the same as in equation ( 3). For the first iteration, we simply setu 1 = B0 i=1 1 B0 g(x 1 ; ζ i 1 ) and v 1 = B0 i=1 1 B0 ∇f (u 1 ; ξ i 1 )∇g(x 1 ; ζ 1 ), where B 0 = T 1/3 . Next, we list common assumptions used in the literature of compositional optimization [Wang et al., 2017a ,b, Yuan et al., 2019 , Zhang and Xiao, 2019 , 2021] .Assumption 4 (Average smoothness and Lipschitz continuity)E ∥∇f (x; ξ) -∇f (y; ξ)∥ 2 ≤ L∥x -y∥ 2 ; E ∥f (x; ξ) -f (y; ξ)∥ 2 ≤ C∥x -y∥ 2 ; E ∥∇g(x; ζ) -∇g(y; ζ)∥ 2 ≤ L∥x -y∥ 2 ; E ∥g(x; ζ) -g(y; ζ)∥ 2 ≤ C∥x -y∥ 2 .Assumption 5 (Bounded variance)E ∥g(x; ζ) -g(x)∥ 2 ≤ σ 2 ; E ∥∇g(x; ζ) -∇g(x)∥ 2 ≤ σ 2 ; E ∥∇f (x; ξ) -∇f (x)∥ 2 ≤ σ 2 .Algorithm 2 Compositional STORM 1: Input: time step T , initial point x 1 2: for time step t = 1 to T do 3:Compute u t according to equation ( 6) 4:Compute v t according to equation ( 7)5:Update the decision variable: x t+1 = x tη t v t 6: end for 7: Choose τ uniformly at random from {1, . . . , T }8: Return x τ Assumption 6 F * = inf x F (x) ≥ -∞ and F (x 1 ) -F * ≤ ∆ F for the initial solution x 1 .Remark: In Assumption 4, we further require standard Lipschitz continuity assumption, which is essential and widely required in the literature for stochastic compositional optimization [Wang et al., 2017b , Yuan et al., 2019 , 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 3 Under Assumptions 4, 5 and 6, our Algorithm 2 ensures that:E [∥∇F (x τ )∥] ≤ O T -1/3 .Remark: This rate matches the state-of-the-art (SOTA) results in stochastic compositional optimization [Hu et al., 2019 , Zhang and Xiao, 2019 , Qi et al., 2021] , 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, we further improve our adaptive variance reduction method to obtain an enhanced convergence rate for non-convex finite-sum optimization, which is in the form ofmin x∈R d F (x) = 1 n n i=1 f i (x),where each f i (•) is a smooth non-convex function. Existing adaptive method for this problem [Kavis et al., 2022] achieves a convergence rate of O(n 1/4 T -1/2 log(nT )) based on the variance reduction technique SPIDER [Fang et al., 2018] , suffering from an extra O(log(nT )) term compared with the corresponding lower bound [Fang et al., 2018 , Li et al., 2021] .To obtain the optimal convergence rate for finite-sum optimization, we incorporate techniques from the SAG algorithm [Roux et al., 2012] into the STORM estimator. Specifically, in each step t, we start by randomly sample i t from the set {1, 2, • • • , n}. Then, we construct a variance reduction gradient estimator asEQUATIONwhere 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, g t tracks the gradient asEQUATIONBy such a design, we can ensure that the estimation error E[∥v t -∇F (x t )∥ 2 ] reduces gradually. The whole algorithm is stated in Algorithm 3. In this case, we set the hyper-parameters as:η t = 1 n 1-α 2 t i=1 ∥v i ∥ 2 α , β = 1 n , Algorithm 3 STORM for Finite-sum Optimization (SAG-type) 1: Input: time step T , initial point x 1 2: for time step t = 1 to T do 3: Sample i t randomly from {1, 2, • • • , n} 4:Compute estimator v t according to equation ( 8) 5:Update g t+1 according to equation ( 9) 6:Update the decision variable: x t+1 = x tη t v t 7: end for 8: Choose τ uniformly at random from {1, . . . , T } 9: Return x τ where 0 < α < 1/3. The learning rate η t is non-increasing and changes according to the gradient estimations, and the momentum parameter β 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 , Li et al., 2021] .Assumption 7 (Smoothness) For each i ∈ {1, 2, • • • , m}, function f i is L-smooth such that ∥∇f i (x) -∇f i (y)∥ ≤ L∥x -y∥. Assumption 8 F * = inf x F (x) ≥ -∞ and F (x 1 ) -F * ≤ ∆ F for the initial solution x 1 .Theorem 4 Under Assumptions 7 and 8, our Algorithm 3 guarantees that:E [∥∇F (x τ )∥] ≤ O n 1/4 T 1/2 ∆ 1 2(1-α) F + L 1 2α. Remark: Our result matches the lower bound for non-convex finite-sum problems [Fang et al., 2018 , Li et al., 2021] , and makes an improvement over the existing adaptive method, i.e., AdaSpider [Kavis et al., 2022] . Specifically, the convergence rate of the AdaSpider algorithm is O n 1/4 T -1/2 L 2 + ∆ F • log (1 + nT L) , and our result is better than theirs when 1 4 < α < 1 3 . 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 it into STORM estimator. Instead of storing the past gradients as in SAG algorithm, we can avoid this storage cost by incorporating elements from the SVRG method. Specifically, we compute a full batch gradient at the first step and every I iteration (we set I = n):∇f (x τ ) = 1 n n i=1 ∇f i (x τ ).For other iterations, we randomly select an index i t from the set {1, 2, • • • , n} and compute:EQUATION)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 (8) in Algorithm 3, the difference is that we use (∇f it (x τ ) -∇f (x τ )) instead of g it t -1 n n i=1 g i t in the last term. The detailed procedure is outlined in Algorithm 4. This strategy maintains the same optimal rate, as stated below:Theorem 5 Under Assumptions 7 and 8, our Algorithm 4 guarantees that:E [∥∇F (x τ )∥] ≤ O n 1/4 T 1/2 ∆ 1 2(1-α) F + L 1 2α.The obtained convergence rate is in the same order as the results in Theorem 4, and Algorithm 4 does not require storing past gradients anymore. Update the decision variable: x t+1 = x tηv t 9: end for 10: Select τ uniformly at random from {1, . . . , T } 11: Return x τ  
experiments: 
 In this section, we evaluate the performance of the proposed Ada-STORM method via numerical experiments on image classification tasks and language modeling tasks. In the experiments, we compare our method with STORM [Cutkosky and Orabona, 2019] , STORM+ [Levy et al., 2021] and META-STORM [Liu et al., 2022] , as well as SGD, Adam [Kingma and Ba, 2015] and AdaBelief [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 implementation3 , and build STORM, META-STORM and our Ada-STORM based on it. When it comes to hyper-parameter tuning, we simply set α = 0.3 for our algorithm. For other methods, we either set the hyper-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 set {1e-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, we conduct numerical experiments on multi-class image classification tasks to evaluate the performance of the proposed method. Specifically, we train ResNet18 and ResNet34 models [He et al., 2016] on the CIFAR-10 and CIFAR-100 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 on the CIFAR-10 and CIFAR-100 datasets in Figure 1 and Figure 2 . It is observed that, for training loss and training accuracy, our Ada-STORM algorithm achieves comparable performance with respect to other methods, and it outperforms the others in terms of testing loss and thus obtains a better testing accuracy.Language modeling task Then, we perform experiments on language modeling tasks. Concretely, we train a 2-layer Transformer [Vaswani et al., 2017] 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 3 . From the results, we observe that our method converges more quickly than other methods and obtains a slightly better perplexity compared with others, indicating the effectiveness of the proposed method. 
conclusion: 
 In this paper, we propose an adaptive STORM method to achieve the optimal convergence rate for nonconvex functions. Compared with existing methods, our algorithm requires weaker assumptions and does not have the additional O(log T ) term in 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 O(n 1/4 T -1/2 ). Given that STORM algorithm has already been used in many areas such as bi-level optimization [Yang et al., 2021] , federated learning [Das et al., 2022] , min-max optimization [Xian et al., 2021] , sign-based optimization [Jiang et al., 2024b] , etc., the proposed methods may also inspire the development of adaptive algorithms in these fields. 
safeguards: 
 Question: 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, or scraped datasets)?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 a 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 a 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 or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.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 package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: First, we introduce the following lemma, which is frequently used in our proof.Lemma 1 Suppose c i is positive for i = {1, 2, • • • , n}, and let 0 < α < 1. We can ensure that:n i=1 c i 1-α ≤ n i=1 c i i j=1 c j α ≤ 1 1 -α n i=1 c i 1-α .Proof 1 The proof mainly follows McMahan and Streeter [2010] and a similar analysis also appears in Levy et al. [2021] . First, we prove the right part by Induction.(1) For n = 1, we can easily show that the hypothesis holds:c 1 c α 1 = c 1-α 1 ≤ 1 1 -α c 1-α 1 .(2) Next, assuming that the hypothesis holds for n = t -1, then we show that it also holds for n = t. Define Z = t i=1 c i and X = c t . For n = t, we havet i=1 c i i j=1 c j α = t-1 i=1 c i i j=1 c j α + c t t j=1 c j α ≤ 1 1 -α t-1 i=1 c i 1-α + c t t j=1 c j α = 1 1 -α (Z -X) 1-α + X Z α := h(X).Taking the derivative concerning x, we know thatdh(X) dX = 1 Z α - 1 (Z -X) α , which indicates that h(X) decreases as X increasing. Since 0 ≤ X ≤ Z, max 0≤X≤Z h(X) = h(0) = 1 1 -α Z 1-α = 1 1 -α t i=1 c i 1-α, which implies that the hypothesis is true for n = t.Combining (1) and (2), we finish the proof for the right part. Then, we give the proof of the left part as follows:n i=1 c i i j=1 c j α ≥ n i=1 c i n j=1 c j α = n i=1 c i 1-α.Thus, we finish the proof of this lemma.Next, we can obtain the following guarantee for our algorithm.Lemma 2 Our method enjoys the following guarantee:T t=1 E η t ∥v t ∥ 2 ≤ 2∆ f + σ 2 + E 2L 2 β T t=1 η 3 t ∥v t ∥ 2 (A) +E L T t=1 η 2 t ∥v t ∥ 2 (B) +E 2βσ 2 T t=1 η t (C).Proof 2 According to the definition of estimator v t , we can deduce that:EQUATION)Note that η t is independent of random variable ξ t+1 . So we can guarantee that:E ξt+1 η t ∥∇f (x t+1 ) -v t+1 ∥ 2 ≤ (1 -β)η t ∥v t -∇f (x t )∥ 2 + 2β 2 σ 2 η t + 2L 2 η 3 t ∥v t ∥ 2 .After rearranging, we have:η t ∥v t -∇f (x t )∥ 2 ≤ η t β ∥v t -∇f (x t )∥ 2 -E ξt+1 η t β ∥v t+1 -∇f (x t+1 )∥ 2 + 2βσ 2 η t + 2L 2 β η 3 t ∥v t ∥ 2 .Letting H t be the history to time t, i.e., H t = {ξ 1 , • • • , ξ t }, we ensure thatE Ht η t ∥v t -∇f (x t )∥ 2 ≤E Ht η t β ∥v t -∇f (x t )∥ 2 -E Ht+1 η t β ∥v t+1 -∇f (x t+1 )∥ 2 + 2βσ 2 E Ht [η t ] + 2L 2 β E Ht η 3 t ∥v t ∥ 2 .By summing up and noting that η t is non-increasing such that η t+1 ≤ η t , we have:EQUATION)Since we use a large batch size in the first iteration, that is, B 0 = T 1/3 , we can now ensure thatE H1 ∥v 1 -∇f (x 1 )∥ 2 ≤ σ 2 B0 = σ 2 T 1/3 . Due to the fact that η 1 ≤ T -1/3 and β = T -2/3, the first term of the above inequality is less than σ 2 . So, we can finally have:EQUATION)Also, due to the smoothness of f (x), we know that:f (x t+1 ) ≤ f (x t ) + ⟨∇f (x t ) , x t+1 -x t ⟩ + L 2 ∥x t+1 -x t ∥ 2 = f (x t ) -η t ⟨∇f (x t ) , v t ⟩ + η 2 t L 2 ∥v t ∥ 2 = f (x t ) -η t ⟨∇f (x t ) , v t ⟩ + η t 2 ∥∇f (x t )∥ 2 + η t 2 ∥v t ∥ 2 - η t 2 ∥∇f (x t )∥ 2 - η t 2 ∥v t ∥ 2 + η 2 t L 2 ∥v t ∥ 2 = f (x t ) + η t 2 ∥∇f (x t ) -v t ∥ 2 - η t 2 ∥∇f (x t )∥ 2 - η t 2 ∥v t ∥ 2 + η 2 t L 2 ∥v t ∥ 2 .By summing up and re-arranging, we have:EQUATION)Then, by using equation ( 13) and the fact that f (x 1 )f * ≤ ∆ f , we have:T t=1 E η t ∥v t ∥ 2 ≤ 2∆ f + σ 2 + 2βσ 2 T t=1 E [η t ] + 2L 2 T t=1 E η 3 t β ∥v t ∥ 2 + L T t=1 E η 2 t ∥v t ∥ 2 ,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 t = s, the condition t i=1 ∥v i ∥ 2 ≥ T 1/3 begins to hold. We refer to iterations t = {1, 2, • • • , s -1} as the first stage, and t = {s, • • • , T } as the second stage.Bounding LHS: In the first stage, we know thats-1 t=1 η t ∥v t ∥ 2 = 1 T 1/3 s-1 t=1 ∥v t ∥ 2 .For the second stage, our analysis leads to:T t=s η t ∥v t ∥ 2 = T t=s ∥v t ∥ 2 T 1-α 3 t i=1 ∥v i ∥ 2 α ≥ T t=s ∥v t ∥ 2 T 1-α 3 T 1 3 + t i=s ∥v i ∥ 2 α ≥ T t=s ∥v t ∥ 2 T 1-α 3 T α 3 + t i=s ∥v i ∥ 2 α ≥ T t=s ∥v t ∥ 2 T 1-α 3 • 2 max T α 3 , t i=s ∥v i ∥ 2 α ≥ 1 2T 1-α 3 min    1 T α 3 T t=s ∥v t ∥ 2 , T t=s ∥v t ∥ 2 1-α    = 1 2 min    1 T 1/3 T t=s ∥v t ∥ 2 , 1 T 1/3 T t=s ∥v t ∥ 2 1-α    :=Γ, where the first inequality stems from s-1 t=1 ∥v t ∥ 2 ≤ T 1/3 , the second inequality results from (x + y) α ≤ x α + y α for positive x, y and 0 < α < 1/3, and the forth inequality applies Lemma 1. Next, we bound (A), (B), (C) as follows.Bounding (A): In the first stage, with η t = T -1/3 , β = T -2/3 , and s-1 t=1 ∥v t ∥ 2 ≤ T 1/3 , we can derive:2L 2 β s-1 t=1 η 3 t ∥v t ∥ 2 = 2L 2 T 1/3 s-1 t=1 ∥v t ∥ 2 ≤ 2L 2 .For the second stage, the analysis gives:2L 2 β T t=s η 3 t ∥v t ∥ 2 ≤ 2L 2 T t=s ∥v t ∥ 2 T 1-3α 3 t i=s ∥v i ∥ 2 3α ≤ 2L 2 1 -3α 1 T 1/3 T t=s ∥v t ∥ 2 1-3α, where the second inequality uses Lemma 1. Then we also have:2L 2 1 -3α 1 T 1/3 T t=s ∥v t ∥ 2 1-3α = 2L 2 1 -3α (8 -24α) 1-3α 1 (8 -24α) 1 T 1/3 T t=s ∥v t ∥ 2 ≤3α 2L 2 1 -3α (8 -24α) 1-3α 1 3α + 1 8T 1/3 T t=s ∥v t ∥ 2 ,where the inequality employs Young's inequality, such that xy ≤ 3αx1 3α +(1-3α)y 1 1-3αfor positive x, y. Very similarly, we have:2L 2 1 -3α 1 T 1/3 T t=s ∥v t ∥ 2 1-3α = 2L 2 1 -3α 8 -24α 1 -α 1-3α 1-α 1 -α 8 -24α 1-3α 1-α 1 T 1/3 T t=s ∥v t ∥ 2 1-3α ≤ 2α 1 -α 2L 2 1 -3α 8 -24α 1 -α 1-3α 1-α 1-α 2α + 1 8 1 T 1/3 T t=s ∥v t ∥ 2 1-α ,where the second inequality employs Young's inequality, such that xy ≤ 2α 1-α x1-α 2α + 1-3α 1-α y 1-α 1-3αfor positive x, y. Combining all above, we know that(A) ≤2L 2 + 3α 2L 2 1 -3α (8 -24α) 1-3α 1 3α + 2α 1 -α 2L 2 1 -3α 8 -24α 1 -α 1-3α 1-α 1-α 2α + Γ 8 .In the first stage, with the learning rate set at η t = T -1/3 and s-1t=1 ∥v t ∥ 2 ≤ T 1/3 , we observe: L s-1 t=1 η 2 t ∥v t ∥ 2 = L T 2/3 s-1 t=1 ∥v t ∥ 2 ≤ L T 1/3 ≤ L.For the second stage, our analysis reveals:L T t=s η 2 t ∥v t ∥ 2 ≤L T t=s ∥v t ∥ 2 T 2(1-α) 3 t i=s ∥v i ∥ 2 2α ≤ L 1 -2α 1 T 1/3 T t=s ∥v t ∥ 2 1-2α, where the second inequality leverages Lemma 1, and we have:L 1 -2α 1 T 1/3 T t=s ∥v t ∥ 2 1-2α = L 1 -2α (8 -16α) 1-2α 1 (8 -16α) 1-2α 1 T 1/3 T t=s ∥v t ∥ 2 1-2α ≤2α (8 -16α) 1-2α L 1 -2α 1 2α + 1 8T 1/3 T t=s ∥v t ∥ 2 ,where the inequality is due to Young's inequality, such that xy ≤ 2αxEQUATION1-2α for positive x, y. Very similarly, we have:L 1 -2α 1 T 1/3 T t=s ∥v t ∥ 2 1-2α = L 1 -2α 8 -16α 1 - 1-2α 1-α 1 -α 8 -16α 1-2α 1-α 1 T 1/3 T t=s ∥v t ∥ 2 1-2α ≤ α 1 -α L 1 -2α 8 -16α 1 -α 1-2α 1-α 1-α α + 1 8 1 T 1/3 T t=s ∥v t ∥ 2 1-α ,where the second inequality employs Young's inequality, such that xy≤ α 1-α x 1-α α + 1-2α 1-α y 1-α 1-2αfor positive x, y. Combining all the above, we know that(B) ≤ L + 2α (8 -16α) 1-2α L 1 -2α 1 2α + α 1 -α L 1 -2α 8 -16α 1 -α 1-2α 1-α 1-α α + Γ 8 .Bounding (C): Given that β = T -2/3 and η t ≤ T -1/3 , we can easily know that (C) ≤ 2σ 2 . So far, we bound all terms in Lemma 2, and we can deduceLHS ≥ E 1 T 1/3 s-1 t=1 ∥v t ∥ 2 + E Γ 2 ; RHS ≤ E Γ 4 + C 0 ,whereEQUATION)These suggest thatE s-1 t=1 ∥v t ∥ 2 ≤ C 0 T 1/3 ; E [Γ] ≤ 4C 0 .With the definition of Γ, we know thatE   min    1 T 1/3 T t=s ∥v t ∥ 2 , 1 T 1/3 T t=s ∥v t ∥ 2 1-α      ≤ 4C 0 ,which indicates the following by applying Jensen's inequality:E 1 T T t=s ∥v t ∥ ≤ max{(4C 0 ) 1 2 , (4C 0 ) 1 2(1-α) }T -1/3 .Also, because of Jensen's inequality, we have:E 1 T s-1 t=1 ||v t || ≤ E   1 T s-1 t=1 ||v t || 2   = E   1 T 2 s-1 t=1 ||v t || 2   ≤ E s T 2 s-1 t=1 ||v t || 2 ≤ E 1 T s-1 t=1 ||v t || 2 ≤ 1 T C 0 T 1/3 = C 0 T -1/3 .Summing up, we have proven thatEQUATION)Finally, we finish our proof by introducing the following lemma.Lemma 3 Suppose 0 < β < 1, our method ensures thatT t=1 E ∥v t -∇f (x t )∥ 2 ≤ 3σ 2 T 1/3 + E 2L 2 β T t=1 η 2 t ∥v t ∥ 2 .Proof 3 First note that we have already proven the following in equation ( 11).E ∥∇f (x t+1 ) -v t+1 ∥ 2 ≤ (1 -β)E ∥v t -∇f (x t )∥ 2 + 2β 2 σ 2 + 2L 2 E η 2 t ∥v t ∥ 2 .After rearranging the items, we can get the following:E ∥v t -∇f (x t )∥ 2 ≤ 1 β E ∥v t -∇f (x t )∥ 2 -E ∥v t+1 -∇f (x t+1 )∥ 2 + 2βσ 2 + 2L 2 β E η 2 t ∥v t ∥ 2 .By summing up, we have:EQUATION)Since we use a large batch size in the first iteration, that is, B 0 = T 1/3 , we can now ensure thatE ∥v 1 -∇f (x 1 )∥ 2 ≤ σ 2 B0 = σ 2 T 1/3 . Note that β = 1 T 2/3, so first term equals to σ 2 T 1/3 and the second term reduces to 2σ 2 T 1/3 . To this end, we ensureT t=1 E ∥v t -∇f (x t )∥ 2 ≤ 3σ 2 T 1/3 + 2L 2 β T t=1 E η 2 t ∥v t ∥ 2 .Thus we finish the proof for this lemma.Here, we bound the term 2L 2 β T t=1 η 2 t ∥v t ∥ 2 as follows. In the first stage, with η t = 1 T 1/3 , we have:2L 2 β s-1 t=1 η 2 t ∥v t ∥ 2 = 2L 2 β s-1 t=1 1 T 2/3 ∥v t ∥ 2 ≤ 2L 2 T 1/3 .For the second stage, the analysis gives:2L 2 β T t=s η 2 t ∥v t ∥ 2 ≤2L 2 T 2/3 T t=s ∥v t ∥ 2 T 2-2α 3 ( t i=s ∥v i ∥) 2α ≤ 2L 2 T 2α/3 1 -2α ((1 -2α)/L) 1-2α ((1 -2α)/L) 1-2α T t=s ∥v t ∥ 2 1-2α ≤2α 2L 2 T 2α/3 ((1 -2α)/L) 1-2α 1 -2α 1/2α + L T t=s ∥v t ∥ 2 ≤2α 2L 2 ((1 -2α)/L) 1-2α 1 -2α 1 2α T 1/3 + L T t=1 ∥v t ∥ 2 ,where the second inequality uses Lemma 1, and the third one employs Young's inequality, such thatxy ≤ 2αx 1 2α + (1 -2α)y 1 1-2αfor positive x, y. We also know that2L 2 β T t=s η 2 t ∥v t ∥ 2 ≤2L 2 T 2/3 T t=s ∥v t ∥ 2 T 2-2α 3 ( t i=s ∥v i ∥) 2α ≤ 2L 2 T 2α/3 1 -2α 1 -2α (1 -α)L T -α 3 1-2α 1-α 1 -α 1 -2α T α 3 L 1-2α 1-α T t=s ∥v t ∥ 2 1-2α ≤ α 1 -α 2L 2 T 2α/3 1 -2α 1 -2α (1 -α)L T -α 3 1-2α 1-α 1-α α + T α 3 L T t=s ∥v t ∥ 2 1-α ≤ α 1 -α 2L 2 1 -2α 1 -2α (1 -α)L 1-2α 1-α 1-α α T 1/3 + T α 3 L T t=s ∥v t ∥ 2 1-α, where the second inequality uses Lemma 1, and the third one employs Young's inequality, such thatxy ≤ α 1-α x 1-α α + 1-2α 1-α y 1-α1-2α for positive x, y. As a result, we have:T t=1 E ∥v t -∇f (x t )∥ 2 ≤   3σ 2 + 4C 0 L + L 1+2α 2α 2(1 -2α) 1-2α 1 -2α 1 2α + L 1 α 2 1 -2α 1 -2α 1 -α 1-2α 1-α 1-α α   T 1/3 .By integrating these findings, we can finally have:E 1 T T t=1 ∥∇f (x t )∥ ≤ 1 T E T t=1 ∥v t ∥ + 1 T T t=1 ∥∇f (x t ) -v t ∥ ≤ C ′ T 1/3 ,whereC ′ = max{3(C 0 ) 1 2 , (C 0 ) 1 2 + (4C 0 ) 1 2(1-α) } + 3σ 2 + 4C 0 L + L 1+2α 2α 2(1 -2α) 1-2α 1 -2α 1 2α + L 1 α 2 1 -2α 1 -2α 1 -α 1-2α 1-α 1-α α = O ∆ 1 2(1-α) f + σ 1 1-α + L 1 2α, with C 0 defined in equation ( 15). We find that larger α leads to better dependence on L and worse reliance on parameters ∆ and σ. For α → 1 3 , we can obtain thatE 1 T T t=1 ∥∇f (x t )∥ ≤ O ∆ 3/4 f + σ 3/2 + L 3/2 T 1/3 .Since we require 0 < α < 1 3 , in practice, we can use α = 0.3 instead, which leads to a convergence rate of O ∆ 5/7 f +σ 10/7 +L 5/3T 1/3 .Since2 0 + 2 1 + • • • + 2 K-1 < 2 K, 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 K = ⌊log(T )⌋, which has been at least run for 2 K-1 ≥ T /4 iterations. According to the analysis of Theorem 1, we have already known that running the Algorithm 1 for T /4 iterations leads to the following guarantee:E [∥∇f (x τ )∥] ≤ O   ∆ 1 2(1-α) f + σ 1 1-α + L 1 2α (T /4) 1/3   = O   ∆ 1 2(1-α) f + σ 1 1-α + L 1 2α T 1/3   ,which is on the same order of the original convergence rate.According to equation ( 14), we have already proven thatT t=1 η t ∥v t ∥ 2 ≤ 2F (x 1 ) -2F (x T +1 ) + T t=1 η t ∥∇F (x t ) -v t ∥ 2 + T t=1 η 2 t L ∥v t ∥ 2 .Then we bound the term T t=1 η t ∥∇F (x t )v t ∥ 2 as follows:∥∇F (x t ) -v t ∥ 2 ≤ 2 ∥∇f (g(x t ))∇g(x t ) -∇f (u t )∇g(x t )∥ 2 + 2 ∥∇f (u t )∇g(x t ) -v t ∥ 2 ≤ 2C 2 L 2 ∥g(x t ) -u t ∥ 2 + 2 ∥v t -∇f (u t )∇g(x t )∥ 2 .Define that G t = ∇f (u t )∇g(x t ), then we have:T t=1 E η t ∥∇F (x t ) -v t ∥ 2 ≤ 2C 2 L 2 T t=1 E η t ∥g(x t ) -u t ∥ 2 + 2 T t=1 E η t ∥v t -G t ∥ 2 .For the termT t=1 E η t ∥v t -G t ∥ 2, following the very similar analysis of equation ( 11), we have the following guarantee:E ξt+1,ζt+1 ∥v t+1 -G t+1 ∥ 2 ≤ (1 -β) ∥v t -G t ∥ 2 + 2β 2 E ξt+1,ζt+1 ∥∇f (u t+1 ; ξ t+1 )∇g(x t+1 ; ζ t+1 ) -∇f (u t+1 )∇g(x t+1 )∥ 2 + 2E ξt+1,ζt+1 ∥∇f (u t+1 ; ξ t+1 )∇g(x t+1 ; ζ t+1 ) -∇f (u t ; ξ t+1 )∇g(x t ; ζ t+1 )∥ 2 ≤ (1 -β) ∥v t -G t ∥ 2 + 4C 2 σ 2 β 2 + 4C 2 L 2 E η 2 t ∥v t ∥ 2 + 4C 2 L 2 E ∥u t+1 -u t ∥ 2 .That is to say:T t=1 E η t ∥v t -G t ∥ 2 ≤E η 1 β ∥v 1 -G 1 ∥ 2 + 4C 2 σ 2 βE T t=1 η t + 4C 2 L 2 β T t=1 E η 3 t ∥v t ∥ 2 + 4C 2 L 2 β T t=1 E η t ∥u t+1 -u t ∥ 2 ≤(1 + 4C 2 )σ 2 + 4C 2 L 2 β T t=1 E η 3 t ∥v t ∥ 2 + 4C 2 L 2 β T t=1 E η t ∥u t+1 -u t ∥ 2 ,where the last inequality due to the fact that β = T -2/3 , η t ≤ T -1/3 , and we use a large batch size T 1/3 in the first iteration. Next, we further bound the termT t=1 E η t-1 ∥u t -u t-1 ∥ 2 .First, we can ensure that:E ζt ∥u t -u t-1 ∥ 2 = E ζt ∥β(g(x t ; ζ t ) -u t-1 ) + (1 -β)(g(x t ; ζ t ) -g(x t-1 ; ζ t ))∥ 2 = E ζt ∥β(g(x t-1 ) -u t-1 ) + (g(x t ; ζ t ) -g(x t-1 ; ζ t )) + β(g(x t-1 ; ζ t ) -g(x t-1 ))∥ 2 ≤ 3β 2 ∥g(x t-1 ) -u t-1 ∥ 2 + 3C 2 η 2 t-1 ∥v t-1 ∥ 2 + 3β 2 σ 2 .So we know that1 β T t=1 E η t ∥u t+1 -u t ∥ 2 ≤3β T t=1 E η t ∥g(x t ) -u t ∥ 2 + 3C 2 E T t=1 η 3 t β ∥v t ∥ 2 + 3βσ 2 E T t=1 η t .So far, we haveT t=1 E η t ∥∇F (x t ) -v t ∥ 2 ≤26C 2 L 2 T t=1 E η t ∥u t -g(x t )∥ 2 + 8C 2 L 2 + 24C 4 L 2 β T t=1 E η 3 t ∥v t ∥ 2 + (2 + 8C 2 + 24C 2 L 2 )σ 2 .Next, we can bound T t=1 η t ∥u tg(x t )∥ 2 following equation ( 11), as:∥u t -g(x t )∥ 2 ≤ 1 β ∥u t -g(x t )∥ 2 -E ζt+1 ∥u t+1 -g(x t+1 )∥ 2 + 2βσ 2 + 2C 2 η 2 t β ∥v t ∥ 2 .So we can haveE T t=1 η t ∥u t -g(x t )∥ 2 ≤ E η 1 β ∥u 1 -g(x 1 )∥ 2 + 2βσ 2 E T t=1 η t + 2C 2 β T t=1 E η 3 t ∥v t ∥ 2 ≤ 3σ 2 + 2C 2 β T t=1 E η 3 t ∥v t ∥ 2 ,where the last inequality due to the fact that β = T -2/3 , η t ≤ T -1/3 , and we use a large batch size T 1/3 in the first iteration. Combining all, we have:T t=1 E η t ∥v t ∥ 2 ≤ 2∆ F + (2 + 8C 2 + 102C 2 L 2 )σ 2 + (8C 2 L 2 + 76C 4 L 2 )E T t=1 η 3 t β ∥v t ∥ 2 + LE T t=1 η 2 t ∥v t ∥ 2 .Treating ∆ F , C, L, σ as constant, the above inequality is very similar to Lemma 2. Thus following the very similar analysis after Lemma 2, we can show that:E 1 T T t=1 ∥v t ∥ ≤ O(T -1/3 ).According to previous analysis, we also have thatT t=1 E ∥∇f (x t ) -v t ∥ 2 ≤26C 2 L 2 T t=1 E ∥u t -g(x t )∥ 2 + 8C 2 L 2 + 24C 4 L 2 β E T t=1 η 2 t ∥v t ∥ 2 + (2 + 8C 2 + 24C 2 L 2 )σ 2 T 1/3 ≤(2 + 8C 2 + 102C 2 L 2 )σ 2 T 1/3 + 8C 2 L 2 + 76C 4 L 2 E T t=1 η 2 t β ∥v t ∥ 2 ,which is similar to Lemma 3, and leads toT t=1 E [∥∇f (x t ) -v t ∥ /T ] ≤ O(T -1/3) following the same analysis. Combing all these together, we can deduce that1 T T t=1 ∥∇F (x t )∥ ≤ O(T -1/3 ),which finishes the proof of Theorem 3.Due to the smoothness of F (x), we have proven the following in equation ( 14):T t=1 η t ∥v t ∥ 2 ≤ 2F (x 1 ) -2F (x T +1 ) + T t=1 η t ∥∇F (x t ) -v t ∥ 2 + T t=1 η 2 t L ∥v t ∥ 2 .For the LHS, we have the following guarantee:T t=1 η t ∥v t ∥ 2 = T t=1 ∥v t ∥ 2 n 1-α 2 t i=1 ∥v i ∥ 2 α ≥ 1 √ n T t=1 ∥v t ∥ 2 1-α.Then, we bound the terms in the RHS. First, we have the following lemma.Lemma 4 Define that z t = ∇f it (x t )g it t + 1 n n i=1 g i t , we have:E T t=1 η t ∥∇F (x t ) -v t ∥ 2 ≤ 2βE T t=1 η t ∥∇F (x t+1 ) -z t+1 ∥ 2 + 2L 2 E T t=1 η 3 t β ∥v t ∥ 2 .Proof 4 According to the definition of z t , the estimator v t can be expressed asv t = (1 -β)v t-1 + βz t + (1 -β) (∇f it (x t ) -∇f it (x t-1 )) .Note that E it+1 [z t+1 ] = ∇F (x t+1 ), and we have:EQUATION)Rearrange the items and multiply the both sides by η t , we can get the following:E η t ∥v t -∇F (x t )∥ 2 ≤E η t β ∥v t -∇F (x t )∥ 2 -E η t β ∥v t+1 -∇F (x t+1 )∥ 2 + 2βE η t ∥z t+1 -∇F (x t+1 )∥ 2 + 2L 2 β E η 3 t ∥v t ∥ 2 .Note that η t is non-increasing. By summing up, we have:T t=1 E η t ∥v t -∇F (x t )∥ 2 ≤E η 1 β ∥v 1 -∇F (x 1 )∥ 2 + 2β T t=1 E η t ∥z t+1 -∇F (x t+1 )∥ 2 + 2L 2 β T t=1 E η 3 t ∥v t ∥ 2 .Since we use a full batch in the first iteration, we can finish the proof of this lemma.Next, we bound two terms in the above lemma.Lemma 5 We can ensure that2β T t=1 E η t ∥∇F (x t+1 ) -z t+1 ∥ 2 ≤ 12L 2 T t=1 E η 3 t β ∥v t ∥ 2 .Proof 5EQUATIONwhere the last equation is due to the fact that i t+1 is randomly sample from {1, 2, • • • , n}. Note that we also have that1 n n i=1 η t ∇f i (x t+1 ) -g i t+1 2 = E it+1 η t ∇f it+1 (x t+1 ) -g it+1 t+1 2 ≤E it+1 η t (1 + 2n) ∇f it+1 (x t+1 ) -∇f it+1 (x t ) 2 + η t (1 + 1 2n ) ∇f it+1 (x t ) -g it+1 t+1 2 ≤E it+1 (1 + 2n)L 2 η 3 t ∥v t ∥ 2 + η t (1 + 1 2n ) ∇f it+1 (x t ) -g it+1 t+1 2 ≤E it+1 (1 + 2n)L 2 η 3 t ∥v t ∥ 2 +η t (1 + 1 2n ) (1 - 1 n ) ∇f it+1 (x t ) -g it+1 t 2 + 1 n ∇f it+1 (x t ) -∇f it+1 (x t ) 2 ≤E it+1 3nL 2 η 3 t ∥v t ∥ 2 + η t (1 - 1 2n ) ∇f it+1 (x t ) -g it+1 t 2 ≤3nL 2 η 3 t ∥v t ∥ 2 + 1 - 1 2n 1 n n i=1 η t ∇f i (x t ) -g i t 2 .That is to say, we can ensure that1 n n i=1 η t+1 ∇f i (x t+1 ) -g i t+1 2 ≤ n i=1 η t ∇f i (x t+1 ) -g i t+1 2 ≤3nL 2 η 3 t ∥v t ∥ 2 + 1 - 1 2n 1 n n i=1 η t ∇f i (x t ) -g i t 2.By rearranging and summing up, we have1 2n T t=1 1 n n i=1 η t ∇f i (x t ) -g i t 2 ≤ 3nL 2 T t=1 η 3 t ∥v t ∥ 2 + 1 n n i=1 η 1 ∇f i (x 1 ) -g i 1 2 .Since we use a full batch n in the first iteration, the second term equals zero, and thus we obtain:T t=1 1 n n i=1 η t ∇f i (x t ) -g i t 2 ≤ 6n 2 L 2 T t=1 η 3 t ∥v t ∥ 2 = 6L 2 β 2 T t=1 η 3 t ∥v t ∥ 2 ,which leads to the result of this lemma.Lemma 6 We have the following guarantee:2L 2 T t=1 η 3 t β ∥v t ∥ 2 ≤ 2α 1 -α 2L 2 1 -3α 24 -72α 1 -α 1-3α 1-α 1-α 2α + 1 24 1 √ n T t=1 ∥v t ∥ 2 1-α . Proof 6 2L 2 T t=1 η 3 t β ∥v t ∥ 2 =2L 2 n T t=1 η 3 t ∥v t ∥ 2 = 2L 2 T t=1 ∥v t ∥ 2 n 1-3α 2 t i=1 ∥v i ∥ 2 3α ≤ 2L 2 1 -3α 1 √ n T t=1 ∥v t ∥ 2 1-3α = 2L 2 1 -3α 24 -72α 1 -α 1-3α 1-α 1 -α 24 -72α 1-3α 1-α 1 √ n T t=1 ∥v t ∥ 2 1-3α ≤ 2α 1 -α 2L 2 1 -3α 24 -72α 1 -α 1-3α 1-α 1-α 2α + 1 24 1 √ n T t=1 ∥v t ∥ 2 1-α, where the last inequality employs Young's inequality, such that xy ≤ 2α 1-α x1-α 2α + 1-3α 1-α y 1-α1-3α for positive x, y.Lemma 7 We can ensure the following guarantee:E T t=1 η 2 t L ∥v t ∥ 2 ≤ α 1 -α L 1 -2α 4 -8α 1 -α 1-2α 1-α 1-α α + 1 4 E   1 √ n T t=1 ∥v t ∥ 2 1-α   Proof 7 T t=1 η 2 t L ∥v t ∥ 2 =L T t=1 ∥v t ∥ 2 n 1-α t i=1 ∥v i ∥ 2 2α ≤ L 1 -2α 1 n 1-α T t=1 ∥v t ∥ 2 1-2α ≤ L 1 -2α 1 √ n T t=1 ∥v t ∥ 2 1-2α = L 1 -2α 4 -8α 1 -α 1-2α 1-α 1 -α 4 -8α 1-2α 1-α 1 √ n T t=1 ∥v t ∥ 2 1-2α ≤ α 1 -α L 1 -2α 4 -8α 1 -α 1-2α 1-α 1-α α + 1 4 1 √ n T t=1 ∥v t ∥ 2 1-α, where the last inequality employs Young's inequality, such that xy≤ α 1-α x 1-α α + 1-2α 1-α y 1-α1-2α for positive x, y. Combing all these, we have already proven thatE T t=1 η t ∥v t ∥ 2 ≥ E   1 √ n T t=1 ∥v t ∥ 2 1-α   , T t=1 η t ∥v t ∥ 2 ≤ C 3 + 3 4 E   1 √ n T t=1 ∥v t ∥ 2 1-α   ,whereC 3 =2∆ F + 14α 1 -α 2L 2 1 -3α 24 -72α 1 -α 1-3α 1-α 1-α 2α + α 1 -α L 1 -2α 4 -8α 1 -α 1-2α 1-α 1-α α .So we can know that:E   1 √ n T t=1 ∥v t ∥ 2 1-α   ≤ 4C 3 . which indicate that E   1 T T t=1 ∥v t ∥ 2 1-α   ≤ 4C 3 √ n T 1-α .as well asE 1 T T t=1 ∥v t ∥ ≤ (4C 3 ) 1 2(1-α) • n 1/4 T 1/2 .To finish the proof, we also have to show the following lemma.Lemma 8E T t=1 ∥∇F (x t ) -v t ∥ 2 ≤ α √ n 1 -α 14L 2 1 -2α 2 -4α (1 -α)L 1-2α 1-α 1-α α + n α 2 L 2 E   T t=1 ∥v t ∥ 2 1-α   .Proof 8 According to the previous proof, we know that:T t=1 E ∥∇F (x t ) -v t ∥ 2 ≤2β T t=1 E ∥∇F (x ) -z t+1 ∥ 2 + 2L 2 T t=1 E η 2 t β ∥v t ∥ 2 ≤ 14nL 2 T t=1 E η 2 t ∥v t ∥ 2 .Also, we can deduce that:14nL 2 T t=1 η 2 t ∥v t ∥ 2 =14L 2 n α T t=1 ∥v t ∥ 2 t i=1 ∥v i ∥ 2 2α ≤ 14L 2 n α 1 -2α T t=1 ∥v t ∥ 2 1-2α = 14L 2 n α 1 -2α 2 -4α (1 -α)n α 2 L 1-2α (1-α) (1 -α)n α 2 L 2 -4α 1-2α 1-α T t=1 ∥v t ∥ 2 1-2α ≤ α 1 -α 14L 2 n α 1 -2α 2 -4α (1 -α)n α 2 L 1-2α 1-α 1-α α + n α 2 L 2 T t=1 ∥v t ∥ 2 1-αwhere the last inequality employs Young's inequality, such that xy ≤ α 1-α x1-α α + 1-2α 1-α y 1-α 1-2α for positive x, y.As a result, we can ensure that1 T T t=1 E [∥∇F (x t )∥] ≤ 1 T E T t=1 ∥v t ∥ + 1 T T t=1 ∥∇f (x t ) -v t ∥ ≤ n 1/4 T 1/2   14L 2 1 -2α 2 -4α (1 -α)L 1-2α 1-α 1-α 2α + 2C 3 L + (4C 3 ) 1 2(1-α)   =O ∆ 1 2(1-α) F + L 1 2α n 1/4 T 1/2 .The analysis is very similar to that of Theorem 4, and the difference only appears in Lemma 5. For this new method, we can also prove the same lemma:Lemma 2β T t=1 E η t ∥∇F (x t+1 ) -z t+1 ∥ 2 ≤ 12L 2 T t=1 E η 3 t β ∥v t ∥ 2 .Proof 9 This time, we have z t+1 = ∇f it+1 (x t+1 ) -∇f it+1 (x τ ) + ∇F (x τ ). And we can know that:E it+1 η t ∥∇F (x t+1 ) -z t+1 ∥ 2 =E it+1 η t ∇F (x t+1 ) -∇f it+1 (x t+1 ) + ∇f it+1 (x τ ) -∇F (x τ ) 2 ≤E it+1 η t ∇f it+1 (x t+1 ) -f it+1 (x τ ) 2 ≤η t L 2 ∥x t+1 -x τ ∥ 2 ≤η t L 2 I t i=τ ∥x i+1 -x i ∥ 2 ≤η t L 2 I t i=τ η 2 i ∥v i ∥ 2 ≤ L 2 I t i=τ η 3 i ∥v i ∥ 2 .By summing up, we have2β T t=1 E η t ∥∇F (x t+1 ) -z t+1 ∥ 2 ≤2βE T t=1 L 2 I t i=τ η 3 i ∥v i ∥ 2 ≤ 2βL 2 I 2 E T t=1 η 3 t ∥v t ∥ 2 ≤ 2L 2 E T t=1 η 3 t β ∥v t ∥ 2 .The other analysis is exactly the same as that of Theorem 4.In this paper, adaptive means the algorithm does not require problem-dependent parameters to set up hyper-parameters such as the learning rate and the momentum parameter.https://github.com/LIONS-EPFL/storm-plus-code 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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?

2. 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.

3. 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.

Overall I think this paper has potential but may benefit from addressing the above points.
questions: questions: See weaknesses.
limitations: limitations: Yes.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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. 

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. 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. 

If the authors can address my major concerns, I am inclined to revise my score upwards, given the otherwise strong results of the paper.
questions: 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?

- 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: Although this paper is theoretically sound in general, there are still some questions need to be discussed:
1.	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.
2.	In theory, the output {x_ \tau} of the proposed algorithms is randomly selected from {1,..,T}. Is the output in the experiment randomly selected?
questions: questions: 1.	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.
2.	In theory, the output {x_ \tau} of the proposed algorithms is randomly selected from {1,..,T}. Is the output in the experiment randomly selected?
limitations: limitations: The authors discussed the limitations and there is no negative societal impact about this work.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. Some typos in the paper:
- Line 145: $(t>2)$ should be $(t \geq 2)$.
- Line 516, the first equality in Proof 7: $L^2$ should be $L$.
questions: questions: 1. Regarding Line 401, could the authors explain why the first inequality holds?
2. In Theorem 4, is the dependency on $\Delta_F$ and $L$ better or worse than that of previous methods?
limitations: limitations: This paper does not present any negative societal impacts.

Comments: comment: Many thanks for your kind response and supports! We will revise our paper according to your constructive suggestions.
Thank you for detailed explanation, and upon further checking, I agree with the authors' claims regarding my W1 and W2. As such, I am increasing my score from 5 to 6.
Thanks for the response and I have no further questions.
Thank the authors for the rely. It addresses all my questions and concerns. I would keep my score.
Thank you very much for your kind reply! We will improve our paper according to your constructive reviews.

Best regards,

Authors
Thank the authors for the response. 

Regarding the technical details in Theorem 1, sorry for not making my point clear initially. I wasn't questioning the validity of Jensen's inequality. Rather, I was unclear about how to apply Jensen's inequality properly in this context. I appreciate that the authors have now clarified this.

Regarding the doubling trick, the authors resolved my misunderstanding. Please clarify this in later drafts. 

Regarding the additional experiments, I thank the authors for the extra efforts. Although tested on the rather simple dataset CIFAR-10, the additional results that the new adaptive rate still outperforms Storm with other learning rate schedulers (e.g. linear decay, cosine decay) strongly supports the validity of Ada-Storm. If time is allowed, I'd suggest the authors to repeat the experiments on larger tasks such as LLMs in the future version, and it will be an encouraging result if Ada-Storm also outperforms other optimizers on more complicated tasks.

Overall, the authors have addressed my major concerns. Given its concrete theoretical results and encouraging empirical results, I revised my score accordingly.