acceptodds
Under review as a conference paper at ICLR 2027

An Adaptive Stochastic Trust-Region Method With Variance Reduction

Abstract

We introduce a class of stochastic trust-region methods for unconstrained nonconvex optimization that integrates variance reduction techniques to accelerate convergence. Specifically, we develop two algorithmic variants, TR-SVRG and TR-SpiderBoost, by incorporating the stochastic variance-reduced gradient (SVRG) (Johnson & Zhang, 2013) and SpiderBoost (Wang et al., 2019) estimators, respectively, into a trust-region framework. Unlike classical trust-region approaches, our methods operate exclusively with stochastic gradient information and eliminate the need for function value evaluations. The trust-region radius is adaptively determined using a radius-control parameter and the variance-reduced gradient estimate. Under standard assumptions, we establish convergence in expectation to a first-order stationary point. Notably, our methods attain iteration and sample complexity bounds that match those of SVRG and SpiderBoost combined with stochastic gradient descent (SGD), while accommodating stochastic Hessian approximations that may be correlated with the gradient estimates, a regime beyond the scope of existing variance-reduction theory. Numerical experiments demonstrate that variance reduction techniques and trust-region methods mutually enhance performance, proper Hessian choice benefits algorithmic performance, and careful tuning of batch size and inner-loop parameters is vital for algorithm efficiency.

Primary area:
optimization
Keywords:
stochastic optimization, trust-region methods, variance reduction

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_gb6VOpenReview ↗
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 Λmin⁡\Lambda_{\min} in Appendix B.1 (particularly lines 860–867)? Since b=μ1Nγb=\mu_1N^\gamma, the stated expression for v0v_0 appears to become negative as NN increases for fixed positive μ0\mu_0 and μ1\mu_1. Would retaining the N−3γ/2N^{-3\gamma/2} 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?

Reviewer_Kp2TOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper combine variance reduction (VR) techniques with Trust-Region (TR) optimization methods for solving machine learning problems. More specifically, the authors leverage existing SVRG (for finite sum setting) and SpiderBoost (for online learning) VR algorithm initially introduced to reduce the variance of SGD.

The paper provides theoretical convergence guarantees of the proposed methods in the non-convex and smooth setting. They also provide numerical experiments on CIFAR10 and MNIST.

Critical strengths

The paper is clear and well written.

The analysis looks (I did not check the proofs) sounds and the numerical experiments looks reasonable and their setting are correctly documented.

Remark: the study of the correlation between the Hessian approximation and the gradient reference is an interesting point.

Critical weaknesses

I want to first of all recognize the work of the authors who submitted a clear and sound work. Unfortunately, I have major criticism against the proposed submission that I will detail below, but I am willing to be corrected or contradicted by the authors or the other reviewers/ACs.

Main concerns:

    1. No motivation is given beside mixing VR methods with TR optimization. No evidence that variance is a crucial element to correct in the case of TR methods. Also, TR methods are not known to be SOTA for training models (discussed below)
    1. Experimental comparisons are not fair as they do not compare added FLOPS of the proposed methods vs vanilla TR. The SVRG estimator : a) compute full gradient every S inner steps, b) requires 2 times more gradient computations than the standard SGD estimate
    1. In both the theoretical and numerical part, the analysis of the results, their interpretation and a link with previous assumptions or results is clearly missing (eg, section 5.3, Why are the different hessian rules behave differently?)
    1. Experimental results do not appear to perform fair comparison of vanilla TR vs TR-VR methods as the authors never mention the impact of VR techniques on the compute and memory cost of each step (S×KS\times K steps of SGD consume SKSK gradient computations vs N+2SKN + 2SK for SVRG for K outer loops)
    1. MNIST and CIFAR10 are very saturated benchmarks that do not inform at all about the usefulness of a method (Cf Defazio and Bottou 2018 for counter examples, and Liu et al's Sophia from 2024a for solid training experiments)

Minor concerns

  1. As pointed by the authors themselves, tuning of the inner loop length is important (and thus TR-SVRG adds a cumbersome parameter to tune
  2. A theoretical limitation I see in Theorem 4.5 are the constraints on the mini-batch and the inner loop size which are in O(N)O(\sqrt{N}). It is far from what is feasible in practice for the pretraining of large models. It also implies that the update of the reference full gradient is very rare and thus that he variance reduction which such parameters is limited.

Additional references (not necessarily to cite but to take into account in the next version of the paper):

  • Defazio & Bottou "On the ineffectiveness of variance reduced optimization for deep learning" (2019) -> No reasonable improvement of using VR in real (large scale for 2019) deep learning applications
  • SVRG hyperparameter discussions: Sebbouh et al "Towards closing the gap between the theory and practice of SVRG" (2019)
  • Existing combination of TR and VR techniques in this preprint: Zheng, "Trust-Region Stochastic Optimization with Variance Reduction Technique" (2024) -> Surprisingly not cited
Questions for authors
  • Q1) Why combining TR with SVRG and SpiderBoost and not SAGA ? or SARAH?
  • Q2) In (4) can you please remind the reader what is the value taken by ∇fi(xk,s−1)\nabla f_i (x_{k,s-1}) if ii did not belong to the mini-batch at the previous inner step Ik,s−1I_{k,s-1}?
  • Q3) Could you describe the Hessian approximations in line 204? Explicit definitions might be needed in appendix.
  • Q4) What is the precise definition of the Cauchy point/ Cauchy reduction?
  • Q5) (open question) How curcial is Assumption 4.2?
  • Q6) Are μ0,μ1,γ\mu_0, \mu_1, \gamma chosen or given in Theorem 4.4?
  • Q7) In Section 5.4, what is the consequence of these pairs of (b,S)(b, S) on the frequency at which the full gradient estimate is refreshed?
Reviewer_c1rhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper analyzes an algorithm that combines variance reduction techniques and trust region (TR) approaches. Specifically, they use a standard variance reduction scaffolding that can reduce to the Spider algorithm or SVRG depending on user choice, and augment that with a trust region step that modifies the update by solving a standard TR subproblem, potentially incorporating second order information. The analysis bounds both the convergence rate and the IFO complexity (# of gradients) needed to find an approximate stationary point. For both SVRG and Spider modes, the recovered rates matches the existing bounds proved for those algorithms in the standard, non-TR setting.

Critical strengths

It is novel to combine trust region with variance reduction approaches. Trust region and other techniques that modify a search direction based on solving an approximate quadratic inverse problem can be considered as a form of adaptivity, ala Adagrad and others, and it is of interest to see how these approaches combine and interact with each other.

The analysis in the paper makes clear that combining the trust region approach with variance reduction is not difficult, as the proof only uses the trust region inequalities in a couple of places, otherwise following the typical variance reduction convergence proof steps.

It's also notable that, generally, the TR versions of the variance reduced algorithms empirically outperformed their vanilla counterparts (Table 2)

Critical weaknesses

The end result, while seemingly correct, appear a little underwhelming because they only establish that the trust region does not hurt convergence, and the rates match those of the original variance reduced algorithms.

In the main text, it is mentioned that it is not required that the trust region problem (equation 6) is solved exactly. In the statement of the theorems, the nature of the approximation is not mentioned, and if one simply reads the statement of the theorems and takes the algorithm at face value, it would appear that the problems need to be solved exactly. Furthermore, the definition of Cauchy step and Cauchy point are not provided in the main text nor in the appendix. This requires clarification. By looking at the proof, it is indeed the case that the theoretical analysis allows for a relaxed form of solution (Lemma 3.3). The paper would benefit by specifying this precisely upfront.

Questions for authors

If approximate Hessian-vector products were available, would those be exploitable by these TR algorithms, in order to obtain improved convergence rates?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.