- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes two stochastic trust-region algorithms, TR-SVRG and TR-SpiderBoost, for nonconvex finite-sum optimization. The methods integrate variance-reduced gradient estimators into a trust-region framework, with the trust-region radius determined by the norm of the gradient estimator.
An interesting feature is that the analysis permits stochastic Hessian approximations that may be correlated with the gradient estimators, without requiring positive definiteness or invertibility. The paper provides first-order convergence guarantees with sample-complexity orders matching those of the corresponding variance-reduced first-order methods. Numerical experiments investigate the effects of variance reduction, trust-region steps, Hessian approximations, and parameter choices.
Critical strengths
1. Clear presentation and well-motivated algorithmic design.
The paper is generally well written and easy to follow. Combining trust-region methods with SVRG and SpiderBoost is a natural and interesting direction. The gradient-dependent trust-region radius provides a simple mechanism for incorporating curvature information without requiring objective function evaluations.
2. Flexible treatment of stochastic Hessian approximations.
I find it interesting that the framework allows stochastic Hessian approximations that can be correlated with the gradient estimators and need not be positive definite or invertible. Retaining the sample-complexity orders of the underlying variance-reduction methods under this flexibility is a potentially useful theoretical contribution.
Critical weaknesses
1. A possible issue in the proof of Theorem 4.4 (Appendix B.1).
I could not fully verify the derivation of the positive lower bound on Λ_min used in Eq. (7), particularly in lines 836–841 and 860–867.
In lines 862–865, the resulting constant v_0 contains a term proportional to μ_0 b + 1. Since b = μ_1 N^γ, this expression appears to become negative as N grows for fixed positive μ_0 and μ_1, so the displayed lower bound does not seem sufficient to establish a uniformly positive v_0.
It appears that retaining the N^(-3γ/2) factor in lines 860–863 may avoid this particular issue. In addition, the manipulation of ρ in lines 836–841 seems to require more careful tracking of μ_1 when b = μ_1 N^γ.
Could the authors clarify these steps and provide a valid positive lower bound on Λ_min under the stated parameter choices?
2. Separating the contributions of the trust-region mechanism and curvature approximation in Table 2.
In Section 5.2, the comparison between TR-SVRG and standard SVRG uses an Adam-diagonal Hessian approximation for the trust-region method. Consequently, the observed improvement may reflect both the trust-region mechanism and the additional curvature/preconditioning information.
Indeed, Appendix C.3 shows that when H = I, the exact trust-region step reduces to a standard gradient step with step size min{α, 1}. The Identity results in Table 3 also coincide with the SVRG baseline in Table 2.
Therefore, I am not entirely convinced that Table 2 isolates the benefit of the trust-region mechanism itself.
A potentially informative comparison would be with a preconditioned SVRG method using comparable curvature information but without the trust-region constraint. Alternatively, a discussion clarifying which components contribute to the empirical improvement would be helpful.
3. Clarification of the theoretical dependence on Hessian approximations.
The convergence analysis primarily depends on the uniform bound on the Hessian approximations through κ_H, without explicitly characterizing their approximation quality or how different curvature choices affect convergence efficiency.
While the main theoretical objective is to preserve the complexity orders of existing variance-reduction methods, the experiments indicate that different Hessian approximations can lead to substantially different performance.
It would be interesting to understand whether the analysis can provide further insight into these observations. In particular, is there a way to relate the approximation quality of H_{k,s} to the convergence behavior, beyond its operator-norm bound?
Questions for authors
Q1. Proof of Theorem 4.4.
Could the authors clarify the derivation of the positive lower bound on in Appendix B.1 (particularly lines 860–867)? Since , the stated expression for appears to become negative as increases for fixed positive and . Would retaining the factor resolve this issue? Does the claimed complexity bound remain valid under the corrected argument?
Q2. Contribution of the trust-region mechanism.
In Table 2, the trust-region variants use an Adam-diagonal Hessian approximation, making it difficult to distinguish the benefit of the trust-region mechanism from that of curvature-based preconditioning. Could the authors clarify how much of the observed improvement can be attributed to the trust-region mechanism itself, potentially through a comparison with a similarly preconditioned method without the trust-region constraint?
Q3. Theoretical role of Hessian approximations.
The convergence analysis primarily relies on the boundedness of the Hessian approximations, without explicitly characterizing their approximation quality. Meanwhile, the experiments suggest that different Hessian choices can substantially affect performance. Could the authors clarify whether the analysis provides any theoretical insight into these differences, or whether the theoretical contribution is primarily to preserve the sample-complexity orders of existing variance-reduced methods while allowing more general Hessian approximations?