- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes two methods for stochastic nonconvex composite optimization in geometry (). SPL-MB uses proximal updates with a stochastic Armijo line search, while SPL-VR adds SPIDER variance reduction. Both methods reuse the same batch when testing different stepsizes.
The authors prove that the line search terminates and establish convergence guarantees without assuming bounded gradients or strong growth conditions. The oracle complexity is for SPL-MB and for SPL-VR. The paper also discusses geometry close to , inexact proximal updates, and experiments on Rosenbrock problems and logistic regression.
Critical strengths
1. Convergence guarantees under weaker assumptions.
The paper addresses the dependence arising from using the same minibatch to compute the proximal direction and select the stepsize. By analyzing the possible trial steps and the stability of the proximal updates, the authors establish convergence guarantees without assuming bounded gradients or strong growth conditions. This relaxes some of the assumptions required by SLAM and represents a useful theoretical extension.
2. Convergence analysis of variance reduction in geometry.
The paper combines SPIDER variance reduction with stochastic Armijo linesearch for nonconvex composite optimization. The analysis controls the errors introduced by the stochastic function evaluations and the recursive gradient estimates, despite their dependence on the accepted steps. The resulting oracle complexity in geometry is a meaningful theoretical result.
Critical weaknesses
1. The paper does not clearly establish the significance of its new contributions.
Several main ideas have appeared in earlier work. SPL-MB reduces to SLAM (Wang et al., 2025) when . Jiang and Stich (2023) studied stochastic linesearch with variance reduction and used corrected stochastic objectives. Xie et al. (2025) studied variance reduction in non-Euclidean geometry.
The paper does provide new analysis for combining these ideas in nonconvex composite optimization. However, it does not make clear what broader insight this analysis offers beyond the proposed methods. Since the main oracle complexity orders are already known, I find it difficult to assess the contribution as a sufficiently significant advance. This is my main reason for leaning toward rejection.
2. The experiments do not test the main combination proposed in the paper.
All SPL-VR experiments use , so they do not show whether non-Euclidean geometry improves the variance reduction method. The experiments with use SPL-MB on Rosenbrock problems, which do not satisfy the smoothness and variance assumptions of the theory, as the authors acknowledge. As a result, the experiments provide limited evidence for the value of combining non-Euclidean geometry, linesearch, and variance reduction. This matters because that combination is central to the paper's claimed contribution.
Questions for authors
1. What is the main new insight in the analysis compared with SLAM, Jiang and Stich (2023), and Xie et al. (2025)?
Please identify which part of the proof cannot be obtained by a direct extension of existing arguments, and explain why it is important beyond the specific algorithms studied here.
2. Can the authors compare SPL-VR with and under the same experimental settings?
This would help show whether non-Euclidean geometry offers a practical benefit when combined with variance reduction and linesearch.
3 comments
Response to Reviewer EoCB (2/3)
Response to CW2 (continued)
We now test the combined non-Euclidean, variance-reduced linesearch method in three experiments: smooth logistic regression (Section 6.2 and Appendix F.2), logistic regression with (Appendix F.3), and the high-dimensional News20 box-constrained regression model (Section 6.3 and Appendix F.5). Each compares SPL-VR with and against the two corresponding SpiderBoost baselines. The logistic models have bounded sample Hessians and gradient-noise variance; the deterministic convex term leaves these oracle bounds unchanged. Appendix F.5 verifies dimension-uniform bounds for News20 regression. Our response to Q2 details the matched settings and the non-Euclidean VR advantages over the Spider baselines and, on high-dimensional News20, over .
Response to Q1: New proof insights for minibatching and variance reduction
For the minibatch proof (Appendix A.1-A.4), the function-increment error defined in (45) as a function is key to the analysis and different from previous analytical approaches. This error function evaluated at the actual step discrepancy needs to be effectively controlled to guarantee one-step function value improvement. At a history-measurable displacement, this error is conditionally unbiased and has bounded second moment; as a function of the displacement, it is Lipschitz smooth, as shown in Lemma 4. These properties combined with the candidate stability argument (Lemma 3) facilitate the analysis. Via this approach, we can remove the assumptions on bounded true gradient and Lipschitz continuous regularization in Wang et al. (2025), and we do not need to enforce the monotonic stepsize sequence. Treating the function-increment error as a function is a useful view for analysis of general stochastic iterative algorithms; Lemma 4 holds if we have samplewise Lipschitz smoothness, bounded variance on the gradient noise, and independent sampling, which are standard assumptions in literature on the study of stochastic first-order methods. Therefore, this technique has the potential to be applied to more general settings beyond algorithms considered in this paper.
For VR (Appendix B.1), we separate the fresh centered increment from the historical error, retain the latter in the comparison candidates, and exploit cancellation of the affine correction in the centered Taylor remainder (equation (63)). A compensated finite-candidate bound then connects the selected model error to descent and the SPIDER recursion. The subsequent compensation argument (Appendices B.2-B.3) yields a bound for every under the prescribed schedule. Neither the convex function-gap argument in Jiang and Stich (2023) nor the prescribed-stepsize VR analysis in Xie et al. (2025) provides these adaptive-selection controls. As a consequence, we can derive the state-of-the-art complexity guarantees in the nonconvex setting for parameter-free stochastic linesearch, and the stepsize can be reset at arbitrary frequency thus potentially non-monotone. The choice of the centered Taylor remainder provides useful insights to analyze same-batch linesearch with recursive, conditionally biased estimators and the analysis has the potential to be applied to other non-Euclidean methods.
Response to Q2: Matched Euclidean and non-Euclidean VR comparisons
We now provide three SPL-VR comparisons with and under matched SPL-VR settings. All use , , , and stepsize resets every iterations; within each experiment, initialization, batches, estimator refreshes, budgets, and random streams are shared.
Smooth nonconvex logistic regression (Section 6.2,
Appendix F.2, Figure 2).
On a9a and w8a, we compare both SPL-VR
geometries with SpiderBoost and SpiderBoost-M, using
full-gradient refreshes, , and
. Median first recorded refresh epochs
to gap over five paired runs are:
| Method | a9a (epochs) | w8a (epochs) |
|---|---|---|
| SPL-VR | 2.25 | 2.25 |
| SPL-VR | 3.75 | 4.25 |
| SpiderBoost | 15.50 | 11.00 |
| SpiderBoost-M | 11.25 | 7.50 |
Both SPL-VR variants reach this target in fewer epochs than
either baseline. On a9a, SPL-VR with also has a lower
median time to this target than both baselines. This tests
non-Euclidean VR on real classification data, with complete
gap-versus-epoch and gap-versus-time curves in Figure 2.
Response to Reviewer EoCB (3/3)
Response to Q2 (continued)
Nonsmooth composite logistic regression (Appendix F.3, Figure 4). We add and rerun all four methods with the preceding data and matched settings, using Prox-SpiderBoost and Prox-SpiderBoost-M as baselines. For SPL-VR with , the nonsmooth trial subproblem is solved by a scalar consistency equation with the full dual-norm KKT check. Median first recorded iterations to composite gap are:
| Method | a9a (iterations) | w8a (iterations) |
|---|---|---|
| SPL-VR | 64 | 97 |
| SPL-VR | 191 | 195 |
| Prox-SpiderBoost | 510 | 584 |
| Prox-SpiderBoost-M | 255 | 389 |
Every method reaches the target in all five runs. Non-Euclidean SPL-VR uses fewer recorded iterations than either proximal baseline and has a lower median algorithm time than Prox-SpiderBoost on both data sets. The comparison demonstrates the non-Euclidean VR method with a nonzero nonsmooth regularizer, including its proximal computation.
The two logistic-regression data sets have and features. To better illustrate the advantages of non-Euclidean geometry, we further consider a larger-scale experiment on News20, with substantially more features and a different nonconvex regression model.
High-dimensional News20 regression (Section 6.3, Appendix F.5, Figures 3 and 6). The model combines News20 squared loss, a smooth coordinate penalty, and a quadratic coupling, with . Appendix F.5 verifies dimension-uniform bounds on smoothness, variance, and the initial objective gap. We compare SPL-VR with and , Prox-SpiderBoost, and Prox-SpiderBoost-M. All share full-gradient refreshes, , , and an initial vector with its first coordinates equal to one and the rest zero. The Spider stepsizes are selected by independent short pilots. Since is unknown, the fixed-step Spider baselines are tuned separately at each dimension. We therefore report iteration and gradient-call comparisons rather than wall-clock comparisons for this News20 VR experiment.
Figure 3 compares six feature dimensions at , with five paired runs. SPL-VR with maintains near-reference accuracy across the tested dimensions, exhibiting reduced sensitivity to dimension relative to SPL-VR with and the Spider baselines at the larger dimensions. Figure 6 gives the individual dimension-wise trajectories; SPL-VR with reaches gap in fewer recorded iterations at every tested dimension.
The full-feature comparison uses , , and three paired runs, with a common gradient-call budget of . Median endpoint gaps and first recorded gradient-call counts to gap are:
| Method | Endpoint gap | Target hits | Gradient calls to target |
|---|---|---|---|
| SPL-VR | 580264 | ||
| SPL-VR | 169528 | ||
| Prox-SpiderBoost | 97.2 | - | |
| Prox-SpiderBoost-M | - |
Thus SPL-VR with attains both a smaller final gap and the target with fewer gradient calls than SPL-VR with , while the two baselines remain above the target within the common budget. Figure 3 shows the full-feature gap-versus-gradient-call curves.
Together, the three experiments show that non-Euclidean SPL-VR is effective on smooth and nonsmooth composite objectives and offers iteration or gradient-call advantages over the compared baselines. The benefit relative to Euclidean SPL-VR is particularly evident on the high-dimensional News20 problem.
References
-
Vaswani et al. (2019). Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates. NeurIPS 2019.
-
Wang, Shanbhag, and Xie (2025). A Parameter-Free Stochastic LineseArch Method (SLAM) for Minimizing Expectation Residuals. arXiv:2512.14979. https://arxiv.org/abs/2512.14979
-
Jiang and Stich (2023). Adaptive SGD with Polyak Stepsize and Line-search: Robust Convergence and Variance Reduction. NeurIPS 2023.
-
Xie, Bi, and Liu (2025). On Tackling High-Dimensional Nonconvex Stochastic Optimization via Stochastic First-Order Methods with Non-smooth Proximal Terms and Variance Reduction. arXiv:2509.13992. https://arxiv.org/abs/2509.13992
Response to Reviewer EoCB (1/3)
Thank you for the constructive suggestions on clarifying our contributions and evaluating non-Euclidean variance reduction. Section, appendix, equation, and figure numbers below refer to the revised manuscript.
This response continues in the comments below; references are listed in Part 3.
Response to CW1: Algorithmic and theoretical contributions
The paper is beyond simple combination of ideas.
It removes restrictive assumptions in existing CRN-enabled stochastic linesearch methods such as strong growth conditions (Vaswani et al. 2019), bounded true gradients and Lipschitz continuity of the regularization function (Wang et al. 2025). Jiang and Stich (2023) focus on the convex regime and assume compact feasible region, which is not needed in our analysis either. Removing these assumptions are challenging even in the Euclidean and minibatch setting and requires new analysis.
The linesearch rule for SPL-VR is different from the AdaSVRLS in Jiang and Stich (2023), even in the Euclidean setting. The former uses an affinely corrected sample function to conduct linesearch and the Armijo-returned stepsize is used directly. The latter needs an additional quadratic term to build the sample function and requires rescaling the Armijo-returned stepsize, clipping it with the previous stepsize before using. Therefore, the AdaSVRLS has monotonically nonincreasing stepsizes. In contrast, SPL-VR allows resetting the intial trial stepsize with arbitrary frequency and acquires potentially nonmonotonic stepsize sequence. This is due to the different analysis we use in the proof compared to the previous works.
Without mentioning adaptive and problem-parameter-free stepsize, the non-Euclidean geometry considered in this paper is more general and the distance function design is simpler than Xie et al. (2025). We consider ℓp/ℓp∗ (1<p≤2) settings and the results under ℓ1/ℓ∞ setting can be recovered to the same order in ϵ by letting p≈1, while Xie et al. (2025) only considers the ℓ1/ℓ∞ setting. Xie et al. (2025) employs mixed norm square (∣⋅∣12+∣⋅∣22) as the proximal term (coefficient omitted) while we use ∣⋅∣p2 directly.
Note that for stochastic linesearch methods, it is unknown before this work if a sample complexity guarantee of O~(ϵ−3) can be derived in the Euclidean smooth nonconvex regime to our best knowledge. The stochastic errors introduced by stochastic stepsizes are not easy to control, regardless of the underlying geometry. We derive this result while maintaining the parameter-free property, standard assumptions and extend it to the non-Euclidean setting.
More details about proof insights are in answer to Q1.
Response to CW2: Assumption-matched tests of non-Euclidean variance reduction
Note that the contribution applies in Euclidean geometry already as indicated in the response to CW1. Nevertheless, we further conduct more numerical experiments to demonstrate our contributions. The revised benchmarks satisfy the paper's smoothness, variance, and lower-boundedness assumptions on their respective feasible domains. We have replaced Rosenbrock with the box-constrained nonconvex regularized quadratic family in Section 6.1 and Appendix F.1, where smoothness, noise variance, and the initial objective gap are bounded uniformly in dimension. Its non-Euclidean SPL-MB variants attain smaller gaps and squared residuals at the larger tested dimensions (Figure 1).
The added News20 SPL-MB experiment uses all 1355191 features (Appendix F.4, Figure 5). Logistic sample losses have bounded Hessians for the finite data, the deterministic smooth penalty has bounded second derivative, and the gradient-noise variance is bounded by the feature norms. The appendix gives L1,∞≤0.450023, σ∞2≤1.000092, and initial gap at most log2. At a common budget of about 100n gradient calls, SPL-MB with either p=1.5 or the near-ℓ1 choice attains smaller median objectives and squared residuals than SPL-MB with p=2 and SLS2. Thus the non-Euclidean minibatch evidence is no longer limited to Rosenbrock.