- 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 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
- 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 to , which is central to the constant-batch result.
- The normalized variant has a simple parameter prescription. Theorem 3.8 specifies the step, momentum, and batch sizes without problem-dependent constants.
Critical weaknesses
- 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.
- The scope and novelty of the optimality claim need a more precise comparison. The mini-batch results use , whereas Theorem 4.4 additionally requires along the trajectory. The latter condition is essential for the projection argument and is not implied by the three general assumptions.
Questions for authors
- 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?
- 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
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.
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.
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 ξ for the function estimators and ζ 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+1, zk, and the current function estimates before taking the expectation over the newly drawn samples ζ. By unbiasedness and independence across levels, we have
Eζ[B11j=1∑B1i=1∏T∇fi(ui−1k+1;ζi,jk+1)−i=1∏T∇fi(ui−1k+1)]=0.
Meanwhile, (1−α)(zk−∇F(xk+1))+α(∏i=1T∇fi(ui−1k+1)−∇F(xk+1)) is fixed when averaging over these samples. Therefore, the omitted cross term satisfies
2αE⟨(1−α)(zk−∇F(xk+1))+α(i=1∏T∇fi(ui−1k+1)−∇F(xk+1)),B11j=1∑B1i=1∏T∇fi(ui−1k+1;ζi,jk+1)−i=1∏T∇fi(ui−1k+1)⟩=0.
This justifies the equality in lines 770–786. We have added these steps to Appendix C in the revised paper.
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−ηzk. Under Assumptions 3.1–3.3 and the same independent sampling scheme, choosing α=K−1/2 and η=cK−1/2, where c>0 is a fixed constant, gives K−1∑k=1KE∥∇F(xk)∥=O(K−1/4). Thus, MMLFA preserves the O(ϵ−4) sample complexity with a constant batch size without the additional boundedness condition.
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 C, 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.
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.