acceptodds
Under review as a conference paper at ICLR 2027

Optimal Momentum Methods for Stochastic Multilevel Compositional Optimization

Abstract

This paper investigates stochastic multi-level optimization where the objective is a nested composition of several smooth non-convex functions. We assume that only stochastic estimates of the gradient and function values for each level are accessible. Consequently, obtaining an accurate estimate of the overall gradient is challenging due to the nested structure. To address this, we employ a momentum-based estimator with mini-batches to track the function values of each level, which are subsequently used to construct momentum gradient estimators. We establish an optimal sample complexity of for finding an -stationary point, avoiding the stronger average smoothness assumption commonly relied upon in prior literature. Furthermore, by employing a normalization technique, we attain the same rate without requiring problem-dependent constants to set hyperparameters. To achieve the optimal rate without mini-batches, we further develop a batch-free method that incorporates a first-order approximation and a clipping technique for function value estimation. Finally, we validate the effectiveness of our proposed methods through experiments on risk-averse portfolio optimization and hierarchical tilted empirical risk minimization.

Primary area:
optimization
Keywords:
Multi-level Optimization, nonconvex optimization, stochastic compositional optimization

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_rZnVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies smooth, non-convex objectives formed by composing several expectation-valued functions. It proposes momentum estimators for the intermediate function values and the composite gradient, together with standard and normalized updates. The mini-batch methods claim an optimal sample complexity of O(ϵ−4)O(\epsilon^{-4}) without mean-squared smoothness of the stochastic oracles. A further method, MMLFA, combines a linearized value update with clipping to obtain the same complexity with a constant batch size, under an additional boundedness condition.

Critical strengths
  1. Clipping provides a useful way to control the linearization error. In Lemma 4.1 and Appendix F, bounded tracker error controls the cross term with the Taylor remainder using a second moment of the iterate displacement, rather than requiring a fourth moment. This changes the tracking recursion's displacement coefficient from order 1/α21/\alpha^2 to 1/α1/\alpha, which is central to the constant-batch result.
  2. The normalized variant has a simple parameter prescription. Theorem 3.8 specifies the step, momentum, and batch sizes without problem-dependent constants.
Critical weaknesses
  1. The gradient proof removes a cross term that need not be nonpositive. In Appendix C, page 15, lines 770–786, the squared gradient-estimation error is split into two squared terms without their cross term. Equations (2) and (3) use the same samples to update the value trackers and construct the Jacobian product. Consequently, a Jacobian noise factor can be correlated with the input to a later-level Jacobian; individual oracle unbiasedness does not justify the split.
  2. The scope and novelty of the optimality claim need a more precise comparison. The mini-batch results use B1=Θ(K)B_1=\Theta(K), whereas Theorem 4.4 additionally requires ∥fi(ui−1k)∥≤C\|f_i(u_{i-1}^k)\|\leq C along the trajectory. The latter condition is essential for the projection argument and is not implied by the three general assumptions.
Questions for authors
  1. How can the trajectory bound used in Theorem 4.4 be guaranteed from problem assumptions, and how should the clipping radius be selected when that bound is unknown?
  2. What benefit does momentum provide in the large-batch regime, compared with independently sampled nested estimates without moving averages? A matched analysis or ablation would clarify its role.
2 comments
AuthorsOpenReview ↗

Response to Reviewer rZnV

We thank the reviewer for the careful reading and helpful comments! We have uploaded a revised paper that addresses your concerns. Below, we respond to each comment in detail.


W1. The omitted cross term in the gradient-estimation proof

Thank you for pointing this out. The samples used to construct the function estimators and the gradient estimator are different and independently drawn. To make this distinction clear, we use ξ\xi for the function estimators and ζ\zeta for the gradient estimator in the revised paper.

Regarding lines 770–786, we apologize for omitting the proof steps here. Expanding the squared norm does produce a cross term, but its expectation equals zero, which is why it does not appear in the subsequent expression. Specifically, fix xk+1x^{k+1}, zkz^k, and the current function estimates before taking the expectation over the newly drawn samples ζ\zeta. By unbiasedness and independence across levels, we have

Eζ[1B1∑j=1B1∏i=1T∇fi(ui−1k+1;ζi,jk+1)−∏i=1T∇fi(ui−1k+1)]=0\displaystyle \mathbb E_{\zeta}\left[\frac{1}{B_1}\sum_{j=1}^{B_1}\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1};\zeta_{i,j}^{k+1})-\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1})\right]=0.

Meanwhile, (1−α)(zk−∇F(xk+1))+α(∏i=1T∇fi(ui−1k+1)−∇F(xk+1))(1-\alpha)(z^k-\nabla F(x^{k+1}))+\alpha(\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1})-\nabla F(x^{k+1})) is fixed when averaging over these samples. Therefore, the omitted cross term satisfies

2αE⟨(1−α)(zk−∇F(xk+1))+α(∏i=1T∇fi(ui−1k+1)−∇F(xk+1)),1B1∑j=1B1∏i=1T∇fi(ui−1k+1;ζi,jk+1)−∏i=1T∇fi(ui−1k+1)⟩=0.\displaystyle 2\alpha\mathbb E\left\langle(1-\alpha)(z^k-\nabla F(x^{k+1}))+\alpha\left(\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1})-\nabla F(x^{k+1})\right),\frac{1}{B_1}\sum_{j=1}^{B_1}\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1};\zeta_{i,j}^{k+1})-\prod_{i=1}^T\nabla f_i(u_{i-1}^{k+1})\right\rangle=0.

This justifies the equality in lines 770–786. We have added these steps to Appendix C in the revised paper.


W2. The additional boundedness condition

Thank you for pointing this out. The original analysis indeed relied on clipping and the additional function-value boundedness condition. To address your concern, we have now improved the analysis and removed both requirements. The complete revised proof is provided in the appendix M.

Apart from removing clipping, the method retains the original function-tracking and gradient-momentum updates, together with the parameter update xk+1=xk−ηzkx^{k+1}=x^k-\eta z^k. Under Assumptions 3.1–3.3 and the same independent sampling scheme, choosing α=K−1/2\alpha=K^{-1/2} and η=cK−1/2\eta=cK^{-1/2}, where c>0c>0 is a fixed constant, gives K−1∑k=1KE∥∇F(xk)∥=O(K−1/4)K^{-1}\sum_{k=1}^K\mathbb E\Vert\nabla F(x^k)\Vert=\mathcal O(K^{-1/4}). Thus, MMLFA preserves the O(ϵ−4)\mathcal O(\epsilon^{-4}) sample complexity with a constant batch size without the additional boundedness condition.


Q1. Guaranteeing the trajectory bound and selecting the clipping radius

As explained in our response to W2, the revised analysis removes both clipping and the function-value boundedness condition. Consequently, no clipping radius needs to be specified. For the original algorithm, we had already noted in the manuscript: “For the clipping threshold CC, we observe that a sufficiently large value works well in practice, avoiding the need for tuning.” This empirical observation is supported by the clipping-threshold ablation results in Appendix K of the original paper.


Q2. The role of momentum

Thank you for this suggestion. We have conducted an ablation study to clarify the role of momentum. Specifically, on the Hierarchical Tilted Empirical Risk Minimization task, we remove momentum estimation and update the model using only the current stochastic gradient estimate. As shown in the newly added table, removing momentum leads to a clear decrease in classification accuracy, supporting the practical benefit of momentum-based estimation on this task.

MethodAustralian: rare classAustralian: overallBreast-cancer: rare classBreast-cancer: overallSvmguide1: rare classSvmguide1: overall
MML without momentum0.724 ± 0.0130.779 ± 0.0080.703 ± 0.0120.852 ± 0.0060.751 ± 0.0050.863 ± 0.003
MML0.813 ± 0.0040.823 ± 0.0060.805 ± 0.0040.913 ± 0.0030.782 ± 0.0020.884 ± 0.002

Dear Reviewer,

Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.

As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.

Reviewer_94ckOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper investigates stochastic multi-level optimization without relying on the stronger average smoothness assumption. The author first proposed the MML method, obtaining an O(ϵ−4)O(\epsilon^{-4}) rate with large batch sizes. They further introduce MML-v2, which employs a normalization technique to remove the dependence on problem-specific constant. In addition, they develop MMLFA, which incorporates a first-order approximation to avoid large batches. Experiments on different tasks show the effectiveness of the proposed methods.

Critical strengths
  1. Their theoretical analysis avoids the stronger average smoothness assumption, which shows the theoretical novelty of this work.
  2. The first-order approximation estimator further eliminates the need for large batches while preserving the same sample complexity, providing an additional algorithmic novelty.
  3. The experiments cover different tasks and include hyperparameter sensitivity studies.
Critical weaknesses
  1. A clear drawback of the proposed MMLFA method is its reliance on a clipping operation, which requires an upper bound on the gradient and is impractical. If the authors could remove the clipping operation or justify its necessity, it would substantially improve the assessment of the paper.
  2. For the proposed MMLFA method, unlike Theorem 3.8, the analysis of Theorem 4.4 still requires the use of problem-dependent constants when setting the hyperparameters.
  3. The presentation of Eq. (4) could be improved for better readability. Since this estimator is a key component of MMLFA, the statement “combine these two estimators” could be made more explicit. In particular, the authors could assign distinct names to the two estimators, such as the standard unbiased stochastic estimator for fi(ui−1k;ξik)f_i(u_{i-1}^k;\xi_{i}^k), and the first-order corrected estimator for the second term. Using \underbrace{} in Eq. (4) to label these two components and consistently referring to them by their names throughout the surrounding discussion would make the construction of the proposed estimator easier to follow.
  4. Although α\alpha is selected via grid search, it would be helpful to provide a sensitivity analysis with respect to α\alpha. Since α\alpha balances two estimators, such an analysis would help assess its impact on convergence and provide practical guidance on its selection.
Questions for authors

See the Weaknesses above.

4 comments
AuthorsOpenReview ↗

Response to Reviewer 94ck (Part 1)

We thank the reviewer for the careful reading and helpful comments! We have uploaded a revised paper that addresses your concerns. Below, we respond to your concerns individually.


W1. Necessity and practicality of clipping

Thank you for raising this concern. Following your suggestion, we have revisited the analysis and established that clipping can be removed without introducing additional assumptions or changing the other algorithmic updates. Moreover, the additional condition ∥fi(ui−1k)∥≤C\Vert f_i(u_{i-1}^k)\Vert\le C is no longer required. We have included the complete revised proof in the appendix.

The key change is in the analysis of the tracking error. We decompose eik=uik−fi(ui−1k)e_i^k=u_i^k-f_i(u_{i-1}^k) into a centered-noise component and an accumulated Taylor-remainder component. We control the former through its second moment and the latter through its first moment. The existing Lipschitz assumption on the population functions implies that their Jacobians, and hence their Jacobian products, are bounded. Combining this boundedness with the decomposition allows us to control the squared gradient-estimation error without requiring bounded tracker values, bounded stochastic gradients, or fourth-moment assumptions. In our new analysis, our method preserves the O(ϵ−4)\mathcal O(\epsilon^{-4}) sample complexity with a constant batch size while eliminating the clipping operation and the need to select its threshold. The complete proof is provided in Appendix M.


W2. Problem-dependent constants in Theorem 4.4

Thank you for pointing this out. The original Theorem 4.4 indeed requires the use of problem-dependent constants to set hyperparameters. However, we can further extend the analysis to a normalized variant of MMLFA. Specifically, retain its function-value and gradient estimators, and use xk+1=xk−ηzk/∥zk∥x^{k+1}=x^k-\eta z^k/\Vert z^k\Vert, with no update when zk=0z^k=0.

For any fixed batch size B1≥1B_1\ge1 and K≥4K\ge4, set α=K−1/2\alpha=K^{-1/2} and η=K−3/4\eta=K^{-3/4}. Eq. (24) in Appendix M.3 and ∥xk+1−xk∥≤η\Vert x^{k+1}-x^k\Vert\le\eta give K−1∑k=1KE∥zk−∇F(xk)∥2≤(A0/B1+A1)K−1/2K^{-1}\sum_{k=1}^K\mathbb E\Vert z^k-\nabla F(x^k)\Vert^2\le(A_0/B_1+A_1)K^{-1/2}, where A0,A1A_0,A_1 are positive constants. Thus, neither parameter choice requires problem-dependent constants, while the sample complexity remains O(ϵ−4)\mathcal O(\epsilon^{-4}). The proof is provided in Appendix M.5 (Corollary M.2).


W3. Clarifying the two estimators in Eq. (4)

Thank you for this helpful suggestion. Following your recommendation, we have explicitly labeled the standard unbiased stochastic estimator and the first-order corrected estimator in Eq. (4) and clarified the accompanying discussion in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer 94ck (Part 2)

W4. Sensitivity to the momentum parameter α\alpha

According to your suggestion, we have conducted additional sensitivity experiments on the hierarchical tilted empirical risk minimization task, varying α\alpha over 0.005,0.01,0.05,0.1,0.2,0.5\\{0.005,0.01, 0.05, 0.1, 0.2, 0.5\\} with other settings fixed. The experimental results indicate that the algorithm is not particularly sensitive to α\alpha within the tested range, and smaller values (such as α=0.01\alpha=0.01 or 0.050.05) generally yield slightly better performance.

Results for the MML method

αAustralian:rare classAustralian:overallBreast-cancer:rare classBreast-cancer:overallSvmguide1:rare classSvmguide1:overall
0.0050.797 ± 0.0060.811 ± 0.0070.793 ± 0.0060.899 ± 0.0050.779 ± 0.0030.882 ± 0.003
0.010.813 ± 0.0040.823 ± 0.0060.787 ± 0.0070.904 ± 0.0040.782 ± 0.0020.884 ± 0.002
0.050.802 ± 0.0070.816 ± 0.0050.805 ± 0.0040.913 ± 0.0030.778 ± 0.0040.883 ± 0.003
0.10.807 ± 0.0050.812 ± 0.0080.782 ± 0.0080.895 ± 0.0060.780 ± 0.0020.882 ± 0.002
0.20.782 ± 0.0090.794 ± 0.0090.794 ± 0.0060.903 ± 0.0040.772 ± 0.0050.876 ± 0.004
0.50.790 ± 0.0080.803 ± 0.0070.778 ± 0.0090.885 ± 0.0070.778 ± 0.0030.882 ± 0.003

Results for the MMLFA method

αAustralian:rare classAustralian:overallBreast-cancer:rare classBreast-cancer:overallSvmguide1:rare classSvmguide1:overall
0.0050.823 ± 0.0090.803 ± 0.0060.812 ± 0.0040.908 ± 0.0040.777 ± 0.0020.881 ± 0.002
0.010.829 ± 0.0080.810 ± 0.0050.824 ± 0.0020.920 ± 0.0020.777 ± 0.0030.881 ± 0.002
0.050.838 ± 0.0070.817 ± 0.0040.804 ± 0.0050.912 ± 0.0030.778 ± 0.0010.882 ± 0.001
0.10.815 ± 0.0100.798 ± 0.0070.814 ± 0.0040.905 ± 0.0050.777 ± 0.0020.881 ± 0.003
0.20.821 ± 0.0090.805 ± 0.0060.793 ± 0.0060.890 ± 0.0060.771 ± 0.0040.875 ± 0.004
0.50.805 ± 0.0110.791 ± 0.0080.801 ± 0.0050.900 ± 0.0040.774 ± 0.0030.878 ± 0.003

Thank you for your rebuttal. I think the revised version has improved significantly. In particular, the discussion on eliminating the clipping threshold and the removal of problem-dependent constants in Theorem 4.4 strengthen both the theoretical rigor and novelty of the paper, while improving the practical applicability of the proposed algorithm. The clarification around Eq. (4) also improves the readability of the paper. Additionally, I appreciate the sensitivity analysis of the hyperparameter α\alpha. Overall, the authors have adequately addressed all my concerns, and I am willing to raise my rating.

AuthorsOpenReview ↗

Thank you for recommending clear acceptance!

Thank you for your very positive assessment and for increasing the score! We appreciate your constructive feedback, which has helped us improve our paper.

Reviewer_6hF8OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper claims an optimal sample complexity of O(ϵ−4)O(\epsilon^{-4}) for stochastic compositional optimization without using strong average smoothness of the constituent functions and average Lipschitz assumptions on their respective gradients.

To achieve this, the paper considers (under standard assumptions such as Lipschitz continuity of the member functions and their gradients and their bounded variance) a momentum-based update scheme of the function values which induces reasonable control over corresponding momentum updates of the function gradients. Then the stochastic update using SGD or normalized SGD using a suitable learning rate delivers the desired sample complexity. This scheme is named Momentum-based Multi-level method (MML). A major issue with MML is the additional batch-size dependent term in the gradient estimation error, which dictates an iteration-dependent value for the batch size to preserve long-run control.

To cure this, the paper then proposes a first-order approximation variant of MML called MMLFA, where first order Taylor approximation of function values undergo a momentum style update to yield control that is independent of batch sizes, but dependent only on a decaying learning rate and a suitable hyperparameter α\alpha. However this is obtained by paying the price of sequential dependence of the first-order approximates on gradients from previous-composition-levels.

Experiments on mean-deviation risk-averse portfolio optimization and tilted empirical optimization problems show that the proposed methods achieve faster rates of both function value decrease and gradient norm decrease.

Supplementary material contains analysis details. A crucial error in a previous analysis in Balasubramanian et al (2022) is clarified in the appendix.

Ablations on MML with different batchsizesshow somewhat robust behavior of MML, while ablations using a clipping constant of MMLFA indicate dependence of MMLFA on a suitable value.

Critical strengths
  1. The paper is well-written and refreshingly interesting to read.
  2. The development of both MML and MMLFA are laid out in an intuitive manner in the paper and a glimpse of crucial results exposing the control factors on both function value estimation errors and gradient estimation errors is provided.
  3. Experiments on two conventional ML problems show the usefulness of the proposed MML and MMLFA. Experiments on tilted empirical estimation are interesting. The paper also includes extensive ablations on important factors guiding the convergence like batch size for MML followed by the clipping constant for MMLFA.
Critical weaknesses
  1. My major concern is with the analysis provided in the appendix. The analysis assumes that the reader would recall all facts mentioned in the main paper as well as standard analysis tricks from elsewhere. This is notable right at the start of appendix A in Proof of Lemma 3.4, where the second equality is left unjustified. The inequality arising after the second equality (step 3, lines 607--609) is also left as a challenge to be resolved by the reader. When the paper claims sample complexity predominantly based on extensive analysis, it is a moral responsibility of the paper to make the analysis transparent to the reader. At places where the details are skipped, it becomes extremely difficult for the reader to follow the rest of the proof. I would wish to compare this to the paper's own take on Balasubramanian et al's invalid analysis, where a simple erroneous assumption led to the invalid results. To avoid such undesirable situations, it becomes essential that the analysis presented in the present paper becomes completely transparent to the reader. For example, why a particular step follows a previous step in the analysis should be illustrated with as much sufficient details as possible. If standard analysis tricks are used, these tricks must be highlighted or cited. This issue repeats in the second part of proof of Lemma 3.4 as well as in all other future proofs in the supplement.

  2. In the analysis of both MML and MMLFA, E∥∥xk+1−xk∥∥2{\mathbb{E}}\|\|\mathbf{x}^{k+1} - \mathbf{x}^{k}\|\|^2 appear in the bounds. While remark after lemma 3.5 indicates an appropriate control on this term by using a suitable learning rate, it is unclear in general about explicit control on this term. It is important to include a detailed discussion on the controllability of this term in general.

  3. In MMLFA development, both the function and gradient estimators conveniently ignore batch-based setup. It is essential to formulate MMLFA under a proper mini-batch setup with a constant batch size and show that the analysis of MMLFA carries forward in a similar fashion to mini batch settings with constant batch size. Otherwise the claim of batch-size independence of MMLFA remains unjustified.

  4. In MMLFA, the learning rate η\eta and the momentum parameter α\alpha are both set to be O(K−0.5)O(K^{-0.5}). In practice, for a digital computer implementation, when KK becomes very large (e.g. >106>10^6, which is possible for larger datasets with small batches), this results in small values of η\eta and α\alpha resulting in almost no reasonable update in terms of digital precision. This fact is further compounded in both momentum and SGD updates. How does the method behave in such regimes? It seems that though the method is theoretically good, it is hard to reap these theoretical benefits in practice. Appropriate justifications on practical settings are required to show the practical usefulness of the proposed theoretical guarantees.

  5. The applications are chosen to showcase the supremacy of the proposed MML and MMLFA in terms of convergence behavior of function values and gradient norms. However suitable applications (more relevant to ICLR) should be used which provide insights into the nature of the working of MML and MMLFA. Specifically, if all the nested composite functions work on large dimensional spaces (e.g. >108>{10}^8) , what is the impact of MML and MMLFA on such applications? What is the cost of function value estimation and gradient estimation in these applications? How are the constants determined in these applications then? How does the different Lipschitz constants impact the progress of function value decay and gradient norm decay in such applications?

  6. As follow-up to my previous comment, for applications where each fif_i operates on large dimensional spaces, how much cost is spent by MMLFA in the sequential dependence of function values on previous composition level's gradients? These analysis would be essential to gauge the effectiveness of the method for practical setup.

Minor:

i) The paper can consistently call the main optimization problem of interest as a compositional optimization problem instead of a multi-level problem, since multi-level problem terminology is applied elsewhere in the optimization community.

ii) how does one verify the bounded variance assumption for the example applications and for general examples?

Questions for authors

Please address my comments given in Weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 6hF8 (Part 1)

We thank the reviewer for the helpful comments! We have uploaded a revised paper that addresses your concerns.


W1. Missing justifications in the appendix proofs

We apologize that the original paper did not make these proof steps sufficiently clear. In the revised paper, we have expanded the proofs to make them clearer. We also explain the two steps you mentioned in the proof of Lemma 3.4 below.

1. The second equality.

Denote the stochastic estimation error by $ \varepsilon_i^k= \frac{1}{B_1}\sum_{j=1}^{B_1}f_i(u_{i-1}^k;\xi_{i,j}^k) -f_i(u_{i-1}^k). $ Note that the samples ξi,jk\xi_{i,j}^k are drawn independently of those used to construct uik−1u_i^{k-1} and ui−1ku_{i-1}^k. Since the estimation is also unbiased such that $\mathbb E[\varepsilon_i^k]= 0$, we can know that

u_i^{k-1}-f_i(u_{i-1}^k),\varepsilon_i^k \right\rangle=0.$$ As a result, expanding the squared norm yields $$\begin{aligned} \mathbb E\Vert u_i^k-f_i(u_{i-1}^k)\Vert ^2 =\mathbb E\Vert (1-\alpha)\bigl(u_i^{k-1}-f_i(u_{i-1}^k)\bigr) +\alpha\varepsilon_i^k\Vert ^2 =(1-\alpha)^2\mathbb E\Vert u_i^{k-1}-f_i(u_{i-1}^k)\Vert ^2 +\alpha^2\mathbb E\Vert \varepsilon_i^k\Vert ^2+2\alpha(1-\alpha)\mathbb E\left\langle u_i^{k-1}-f_i(u_{i-1}^k),\varepsilon_i^k \right\rangle, \end{aligned}$$ and the last term \$2\alpha(1-\alpha)\mathbb E\left\langle u_i^{k-1}-f_i(u_{i-1}^k),\varepsilon_i^k \right\rangle\$ equals zero according to our previous analysis. **2. The inequality after the second equality** For $0<\alpha\le1$, weighted Young's inequality gives $$\Vert a+b\Vert ^2\le(1+\alpha)\Vert a\Vert ^2 +(1+\alpha^{-1})\Vert b\Vert ^2.$$ Let $a=u_i^{k-1}-f_i(u_{i-1}^{k-1})$ and $b=f_i(u_{i-1}^{k-1})-f_i(u_{i-1}^k)$. Thus $u_i^{k-1}-f_i(u_{i-1}^k) = a+b$ and we have $$\begin{aligned} (1-\alpha)^2\mathbb E\Vert u_i^{k-1}-f_i(u_{i-1}^k)\Vert ^2 \le(1-\alpha)^2(1+\alpha) \mathbb E\Vert u_i^{k-1}-f_i(u_{i-1}^{k-1})\Vert ^2+(1-\alpha)^2(1+\alpha^{-1}) \mathbb E\Vert f_i(u_{i-1}^{k-1})-f_i(u_{i-1}^k)\Vert ^2. \end{aligned}$$ In addition, independence of the samples within the mini-batch and the bounded-variance assumption imply $$\mathbb E\Vert\varepsilon_i^k\Vert^2=\mathbb E\left[\Vert\frac{1}{B_1}\sum_{j=1}^{B_1}f_i(u_{i-1}^k;\xi_{i,j}^k)-f_i(u_{i-1}^k)\Vert^2\right]=\frac{1}{B_1^2}\sum_{j=1}^{B_1}\mathbb E\left[\Vert f_i(u_{i-1}^k;\xi_{i,j}^k)-f_i(u_{i-1}^k)\Vert^2\right]\le\frac{\sigma^2}{B_1}.$$ The second equality follows from the independence of the sample $\xi_{i,j}^k$ and unbiasedness $\mathbb E\left[f_i(u_{i-1}^k;\xi_{i,j}^k)-f_i(u_{i-1}^k)\right]=0$, such that all cross terms with distinct sample indices have zero expectation when expanding the squared norm, i.e., for $j\neq \ell$, $$\mathbb E\left[\left\langle f_i(u_{i-1}^k;\xi_{i,j}^k)-f_i(u_{i-1}^k),f_i(u_{i-1}^k;\xi_{i,\ell}^k)-f_i(u_{i-1}^k)\right\rangle\right]=0.$$ Combining these two bounds with the preceding equality gives exactly the stated inequality: $$\begin{aligned} \mathbb E\Vert u_i^k-f_i(u_{i-1}^k)\Vert ^2 =(1-\alpha)^2\mathbb E\Vert u_i^{k-1}-f_i(u_{i-1}^k)\Vert ^2 +\alpha^2\mathbb E\Vert \varepsilon_i^k\Vert ^2 \le(1-\alpha)^2(1+\alpha) \mathbb E\Vert u_i^{k-1}-f_i(u_{i-1}^{k-1})\Vert ^2 +(1-\alpha)^2(1+\alpha^{-1}) \mathbb E\Vert f_i(u_{i-1}^{k-1})-f_i(u_{i-1}^k)\Vert ^2 +\frac{\alpha^2\sigma^2}{B_1}. \end{aligned}$$ --- > W2. Control of the $\Vert x^{k+1}-x^k\Vert^2$ term For the normalized update $x^{k+1} = x^k - \eta \frac{z^k}{\Vert{z^k}\Vert}$, we can directly ensure that $\Vert x^{k+1}-x^k\Vert ^2\le \frac{\eta^2 \Vert z^k \Vert^2}{\Vert{z^k}\Vert^2}\le \eta^2,$which remains small when $\eta$ is small. (Note that when $z^k=0$, we have $x^{k+1} = x^k$) For the SGD-style updates, smoothness and $\eta\le1/(2L_F)$ give $$F(x^{k+1})\le F(x^k) -\frac\eta2\Vert \nabla F(x^k)\Vert ^2 -\frac\eta4\Vert z^k\Vert ^2 +\frac\eta2\Vert z^k-\nabla F(x^k)\Vert ^2,$$ whose detailed proof is shown in Appendix D. Summing up and rearranging, we have the **following descent inequality**: $$\frac1K\sum_{k=1}^K\mathbb E\Vert \nabla F(x^k)\Vert ^2 \le\frac{2\mathbb E[F(x^1)-F(x^{K+1})]}{\eta K}+\frac1K\sum_{k=1}^K \mathbb E\Vert z^k-\nabla F(x^k)\Vert ^2 -\frac{1}{2K}\sum_{k=1}^K\mathbb E\Vert z^k\Vert ^2.$$ Bounding \$\frac1K\sum_{k=1}^K \mathbb E\Vert z^k-\nabla F(x^k)\Vert ^2\$, we have $$\frac1K\sum_{k=1}^K \mathbb E\Vert z^k-\nabla F(x^k)\Vert ^2\le A_K+\frac{q}{\alpha^2}\frac1K\sum_{k=1}^K \mathbb E\Vert x^{k+1}-x^k\Vert ^2 \le A_K+\frac{q\eta^2}{\alpha^2}\frac1K\sum_{k=1}^K\mathbb E\Vert z^k\Vert ^2,$$ where $A_K$ collects the initialization and sampling terms, and $q$ is a positive constant. As a result, this $\frac{q\eta^2}{\alpha^2}\frac1K\sum_{k=1}^K\mathbb E\Vert z^k\Vert ^2$ term can be cancelled by the $-\frac{1}{2K}\sum_{k=1}^K\mathbb E\Vert z^k\Vert ^2$ in the previous descent inequality by choosing $q\eta^2/\alpha^2\le1/2$. So, a suitable learning rate to offset this bound would be $\eta \le \alpha/\sqrt{2q}$.
AuthorsOpenReview ↗

Response to Reviewer 6hF8 (Part 2)

W3. MMLFA with an arbitrary constant mini-batch size

Thank you for this suggestion. We have revised the MMLFA formulation and analysis to explicitly include the mini-batch size B1B_1 in both the estimator updates and initialization. The resulting convergence bound is 1K∑k=1KE∥∇F(xk)∥≤O((B1K)−1/4).\frac{1}{K}\sum_{k=1}^{K}\mathbb E\Vert\nabla F(x^k)\Vert\le O((B_1K)^{-1/4}). For any fixed B1=O(1)B_1=\mathcal O(1), including B1=1B_1=1, this recovers the O(K−1/4)\mathcal O(K^{-1/4}) convergence rate and O(ϵ−4)\mathcal O(\epsilon^{-4}) sample complexity for achieving an expected gradient norm of at most ϵ\epsilon.


W4. Small parameters and numerical precision at large horizons

Actually, even when K=106K=10^6, we have K−1/2=10−3K^{-1/2}=10^{-3}. This scale 10−310^{-3} does not imply an extremely small learning rate or numerically negligible updates. Moreover, the step-size restrictions in our analysis provide sufficient conditions for a worst-case convergence guarantee and can therefore be conservative for practical use. In practical applications, we can use the formulation η=cK−1/2\eta=cK^{-1/2} and perform a simple hyperparameter search over cc, whose search range can include larger constants.


W5. Relevance and scalability of the experiments

Thank you for this suggestion. Our Hierarchical Tilted Empirical Risk Minimization (TERM) experiment actually addresses a machine learning application directly relevant to ICLR. Specifically, hierarchical TERM simultaneously handles class imbalance and label noise, and is published at ICLR and JMLR.

To address your suggestion, we have extended this experiment to a larger dataset and a substantially larger model. Specifically, we train Wide-ResNet-101-2 on CIFAR-100, with approximately 1.25×1081.25\times10^8 model parameters. We compare our methods with A-TSCGD, NLASG, Nested-SPIDER, SCSC, momentum SGD, and Adam. To account for differences in computational cost per iteration, we evaluate all methods under the same wall-clock training budget. The results are reported below.

Table: Classification accuracy (mean ±\pm std) for Hierarchical TERM on CIFAR-100.

MethodRare classOverall
A-TSCGD0.518±0.0120.518 \pm 0.0120.668±0.0460.668 \pm 0.046
NLASG0.495±0.0210.495 \pm 0.0210.687±0.0040.687 \pm 0.004
Nested-SPIDER0.583±0.0030.583 \pm 0.0030.728±0.0410.728 \pm 0.041
SCSC0.567±0.0630.567 \pm 0.0630.704±0.0130.704 \pm 0.013
Momentum SGD0.619±0.0100.619 \pm 0.0100.747±0.0100.747 \pm 0.010
Adam0.602±0.0020.602 \pm 0.0020.761±0.0080.761 \pm 0.008
MML (ours)0.621±0.0160.621 \pm 0.0160.783±0.0310.783 \pm 0.031
MMLFA (ours)0.624±0.011\mathbf{0.624 \pm 0.011}0.792±0.004\mathbf{0.792 \pm 0.004}

As shown in the table, our methods outperform other multi-level optimization methods and also achieve higher classification accuracy than Adam. These results provide additional evidence of the practical effectiveness of our methods on a high-dimensional machine learning task.


W6. Sequential computation in MMLFA

Thank you for raising this concern. The sequential dependence arises from the nested composition itself and the chain-rule computation of its gradient. This dependence is therefore present even when using a plain SGD optimizer. MML adds momentum tracking of intermediate function values and gradients, while MMLFA additionally introduces a Jacobian-vector product at each level.


Minor comment (i). Terminology

Thank you for the suggestion. We have changed our terminology in the revised paper according to your suggestion.


Minor comment (ii). Bounded-variance assumption

Thank you for this comment. Bounded variance is a standard assumption in stochastic optimization, measuring the expected squared deviation of a stochastic gradient from the true gradient. Moreover, bounded stochastic gradients imply bounded variance. Also, if the unbiased stochastic estimator g(x;ξ)g(x;\xi) is bounded such that ∥g(x;ξ)∥≤G\Vert g(x;\xi)\Vert\le G, we can ensure the bounded variance via Eξ∥g(x;ξ)−∇f(x)∥2=Eξ∥g(x;ξ)∥2−∥∇f(x)∥2≤G2\mathbb E_\xi\Vert g(x;\xi)-\nabla f(x)\Vert^2=\mathbb E_\xi\Vert g(x;\xi)\Vert^2-\Vert\nabla f(x)\Vert^2\le G^2. Take the portfolio problem as an example. The variable xx belongs to the probability simplex such that ∥x∥2≤1\Vert x\Vert_2\le1. Denote R=max⁡1≤n≤N∥rn∥2R=\max_{1\le n\le N}\Vert r_n\Vert_2. Then, for the layer function f(x;n)=rn⊤xf(x;n)=r_n^\top x, its function-value variance satisfies En∥f(x;n)−f(x)∥2=En∣(rn−rˉ)⊤x∣2≤R2\mathbb E_n\Vert f(x;n)-f(x)\Vert^2=\mathbb E_n|(r_n-\bar r)^\top x|^2\le R^2. Writing JiJ_i for the Jacobian of fif_i, we similarly obtain En∥J(x;n)−J(x)∥F2=En∥rn−rˉ∥22≤R2\mathbb E_n\Vert J(x;n)-J(x)\Vert_F^2=\mathbb E_n\Vert r_n-\bar r\Vert_2^2\le R^2.

Dear Reviewer,

Thank you for your constructive comments, which have helped us improve our manuscript. We have addressed each point in our responses and uploaded a revised manuscript with all changes highlighted in blue.

As the discussion period draws to a close, we would appreciate your feedback on our responses and revisions. Please let us know if any concerns remain. We would be happy to provide further clarification.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.