acceptodds
Under review as a conference paper at ICLR 2027

On Stochastic Proximal Linesearch Methods in Geometry

Abstract

In this work we focus on stochastic nonconvex composite optimization and stochastic linesearch frameworks with each backtracking search reusing a fixed batch of samples (common random number-enabled). Prevailing stochastic linesearch methods of this type are formulated in Euclidean geometry and afflicted by restrictive assumptions or prior knowledge of problem dependent parameters. Motivated by these observations, we develop stochastic Armijo linesearch methods with a non-Euclidean proximal term (-norm square with ), under unbiased stochastic zeroth- and first-order oracles. They allow the algorithm inputs such as stepsizes and batchsizes to be selected without knowledge of problem dependent parameters, and the analysis is free of restrictive assumptions such as strong growth conditions and bounded gradient. Both minibatch and variance-reduced variants are considered and corresponding complexity guarantees are derived with first-order stationarity residual measured in the dual norm. The results include the Euclidean case and a near- specialization, extend to controlled inexact subproblem solves, and are supported by numerical comparisons with stochastic linesearch and variance-reduced baselines.

Primary area:
optimization
Keywords:
stochastic nonconvex composite optimization, stochastic linesearch, non-Euclidean geometry, variance reduction, Lipschitz-agnostic 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_EoCBOpenReview ↗
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 ℓp\ell_p geometry (1<p≤21<p\leq 2). 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 O(ε−4)\mathcal{O}(\varepsilon^{-4}) for SPL-MB and O(ε−3log⁡(1/ε))\mathcal{O}(\varepsilon^{-3}\log(1/\varepsilon)) for SPL-VR. The paper also discusses geometry close to ℓ1/ℓ∞\ell_1/\ell_\infty, 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 ℓp\ell_p 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 O(ε−3log⁡(1/ε))\mathcal{O}(\varepsilon^{-3}\log(1/\varepsilon)) oracle complexity in ℓp\ell_p 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 p=2p=2. 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 p=2p=2, so they do not show whether non-Euclidean geometry improves the variance reduction method. The experiments with p<2p<2 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 p=2p=2 and p<2p<2 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
AuthorsOpenReview ↗

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.

  1. 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.

  2. 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.

  3. 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∗\ell_p/\ell_{p^*} (1<p≤21 < p \le 2) settings and the results under ℓ1\ell_1/ℓ∞\ell_\infty setting can be recovered to the same order in ϵ\epsilon by letting p≈1p \approx 1, while Xie et al. (2025) only considers the ℓ1\ell_1/ℓ∞\ell_\infty setting. Xie et al. (2025) employs mixed norm square (∣⋅∣12+∣⋅∣22\\| \cdot \\|_1^2 + \\| \cdot \\|_2^2) as the proximal term (coefficient omitted) while we use ∣⋅∣p2\\| \cdot \\|_p^2 directly.

  4. Note that for stochastic linesearch methods, it is unknown before this work if a sample complexity guarantee of O~(ϵ−3)\tilde{\mathcal{O}}(\epsilon^{-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 13551911355191 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.450023L_{1,\infty}\leq0.450023, σ∞2≤1.000092\sigma_\infty^2\leq1.000092, and initial gap at most log⁡2\log2. At a common budget of about 100n100n gradient calls, SPL-MB with either p=1.5p=1.5 or the near-ℓ1\ell_1 choice attains smaller median objectives and squared residuals than SPL-MB with p=2p=2 and SLS2. Thus the non-Euclidean minibatch evidence is no longer limited to Rosenbrock.

AuthorsOpenReview ↗

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 r(w)=0.1∣w∣1r(w)=0.1\\|w\\|_1 (Appendix F.3), and the high-dimensional News20 box-constrained regression model (Section 6.3 and Appendix F.5). Each compares SPL-VR with p=2p=2 and p=1.5p=1.5 against the two corresponding SpiderBoost baselines. The logistic models have bounded sample Hessians and gradient-noise variance; the deterministic convex ℓ1\ell_1 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 p=2p=2.

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 K≥2K\geq2 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 p=2p=2 and p=1.5p=1.5 under matched SPL-VR settings. All use s=1s=1, c=0.1c=0.1, β=0.9\beta=0.9, and stepsize resets every 5050 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, b=256b=256, and q=⌈2n/256⌉q=\lceil2n/256\rceil. Median first recorded refresh epochs to gap 10−610^{-6} over five paired runs are:

Methoda9a (epochs)w8a (epochs)
SPL-VR p=2p=22.252.25
SPL-VR p=1.5p=1.53.754.25
SpiderBoost15.5011.00
SpiderBoost-M11.257.50

Both SPL-VR variants reach this target in fewer epochs than either baseline. On a9a, SPL-VR with p=1.5p=1.5 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.

AuthorsOpenReview ↗

Response to Reviewer EoCB (3/3)

Response to Q2 (continued)

Nonsmooth composite logistic regression (Appendix F.3, Figure 4). We add r(w)=0.1∣w∣1r(w)=0.1\\|w\\|_1 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 p=1.5p=1.5, 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 10−310^{-3} are:

Methoda9a (iterations)w8a (iterations)
SPL-VR p=2p=26497
SPL-VR p=1.5p=1.5191195
Prox-SpiderBoost510584
Prox-SpiderBoost-M255389

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 123123 and 300300 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 r=δ[−3,3]dr=\delta_{[-3,3]^d}. Appendix F.5 verifies dimension-uniform bounds on smoothness, variance, and the initial objective gap. We compare SPL-VR with p=2p=2 and 1.51.5, Prox-SpiderBoost, and Prox-SpiderBoost-M. All share full-gradient refreshes, b=256b=256, q=157q=157, and an initial vector with its first 100100 coordinates equal to one and the rest zero. The Spider stepsizes are selected by independent short pilots. Since LL 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 K=250K=250, with five paired runs. SPL-VR with p=1.5p=1.5 maintains near-reference accuracy across the tested dimensions, exhibiting reduced sensitivity to dimension relative to SPL-VR with p=2p=2 and the Spider baselines at the larger dimensions. Figure 6 gives the individual dimension-wise trajectories; SPL-VR with p=1.5p=1.5 reaches gap 10−710^{-7} in fewer recorded iterations at every tested dimension.

The full-feature comparison uses d=1355191d=1355191, K=1000K=1000, and three paired runs, with a common gradient-call budget of 648388648388. Median endpoint gaps and first recorded gradient-call counts to gap 10−710^{-7} are:

MethodEndpoint gapTarget hitsGradient calls to target
SPL-VR p=2p=21.38×10−81.38\times10^{-8}3/33/3580264
SPL-VR p=1.5p=1.52.71×10−92.71\times10^{-9}3/33/3169528
Prox-SpiderBoost97.20/30/3-
Prox-SpiderBoost-M3.81×10−73.81\times10^{-7}0/30/3-

Thus SPL-VR with p=1.5p=1.5 attains both a smaller final gap and the target with fewer gradient calls than SPL-VR with p=2p=2, 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

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

The paper studies stochastic nonconvex composite optimization with a smooth expectation objective and a proper closed convex regularizer. It proposes proximal Armijo methods using the normalized squared ℓp\ell_p norm, for 1<p≤21<p\le 2, with minibatch and SPIDER-type variance reduction. Each iteration reuses its current batch to construct a direction and evaluate all trial points. An affine correction aligns the gradient of the variance-reduced Armijo model with the recursive gradient estimator at the current iterate.

Under uniform samplewise Lipschitz smoothness, unbiased oracles and bounded gradient-noise variance, the authors establish bounds on the expected squared dual-norm subdifferential residual. The oracle complexities are O(ε−4)O(\varepsilon^{-4}) for minibatching and O(ε−3log⁡(e+1/ε))O(\varepsilon^{-3}\sqrt{\log(e+1/\varepsilon)}) for variance reduction, with problem parameters fixed. Further results cover a near-ℓ1\ell_1/ℓ∞\ell_\infty specialization and explicit proximal computations for unconstrained and box-constrained problems. Finally, numerical experiments compare the proposed methods with stochastic linesearch and variance-reduced baselines.

Critical strengths
  1. For 1<p≤21<p\le2, both the minibatch and SPIDER-type methods have convergence and sample complexity guarantees without requiring bounded gradients, interpolation, or strong growth conditions. The proofs account for reuse of the same batch during backtracking. Under matched Euclidean settings, the minibatch update coincides with that of SLAM, but convergence no longer requires bounded true gradients or Lipschitz continuity of rr on its domain.

  2. Under the stated assumptions, the near-ℓ1\ell_1 specialization yields sample complexity bounds with only polylogarithmic dependence on the dimension, providing a theoretical benefit for high-dimensional problems.

Critical weaknesses
  1. Although the analysis does not assume bounded gradients, interpolation, or strong growth conditions, Assumption 1 still requires a common global Lipschitz constant for almost all sample gradients. This is stronger than the mean-squared smoothness condition used in the variance-reduced analysis of Xie et al. (2025) in the corresponding norm geometry. The paper should clarify which assumptions are relaxed and which stronger requirements remain.

  2. The polylogarithmic dependence on dd requires L1,∞L_{1,\infty}, σ∞2\sigma_\infty^2, and the initial objective gap to remain uniformly bounded as dd grows. Although these conditions are explicitly stated, the paper does not demonstrate them through a concrete problem family. The Rosenbrock experiment falls outside the global smoothness and variance assumptions, as acknowledged in Appendix F.1, while the logistic-regression experiments use p=2p=2. Thus, the predicted dimension dependence is not illustrated under the theoretical assumptions.

  3. The non-Euclidean norm is normally used to capture the geometric structure of the problem. However, the advantages of using the ℓp\ell_p norm instead of the ℓ2\ell_2 norm have not been thoroughly explored in this paper. Nor are sufficient numerical experiments provided to demonstrate its effectiveness. Experiments with p<2p<2 are limited to Rosenbrock; comparisons on more structured and real-data problems would better support this contribution.

  4. In the Rosenbrock experiments, SPL-MB and SLAM use different Armijo parameters (c=0.7c=0.7 and c=0.1c=0.1, respectively). Since both pp and cc differ, the performance gap cannot be attributed to geometry alone.

Questions for authors
  1. Which parts of the analysis require a common Lipschitz constant for almost all sample gradients? Please explain the obstacles to using mean-squared smoothness instead, and clarify how the assumptions compare with those of Xie et al. (2025).

  2. Can the authors provide a concrete problem family for which L1,∞L_{1,\infty}, σ∞2\sigma_\infty^2, and the initial objective gap remain uniformly bounded as dd increases? How does its structure guide the choice of pp, and do comparisons with p=2p=2 support the predicted dimension advantage?

  3. Does SPL-MB retain its advantage over SLAM when both methods use the same Armijo constant? Please report comparisons at c=0.1c=0.1 and c=0.7c=0.7, keeping the remaining linesearch settings fixed to isolate the effect of the choice of pp.

6 comments
AuthorsOpenReview ↗

Response to Reviewer 12K1 (1/3)

We appreciate the reviewer's detailed feedback on our assumptions, dimension dependence, and experimental comparisons. 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 Weakness 1: Assumption comparison with existing methods.

Note that the samplewise L-smoothness is a common assumption and employed in many existing common random number enabled stochastic linesearch methods (see Vaswani et al. (2019); Tsukada and Iiduka (2025); Wang et al. (2025); Jiang and Stich (2023)). It is stronger than the mean-squared smoothness condition used in Xie et al. (2025) in the corresponding norm geometry but the latter does not consider adaptive stepsizes nor the stochastic linesearch. Now we have added the following sentences in Section 2 to emphasize these:

In particular, we do not need bounded true gradient or Lipschitz continuity of rr as in Wang et al. (2025), or the strong growth conditions as in Vaswani et al. (2019) to derive the results in this work. The samplewise L-smoothness is more restrictive than the mean-square smoothness conditions in Fang et al. (2018) and Xie et al. (2025) and is essential and ubiquitous in the analysis of CRN-enabled stochastic linesearch methods. Note that the recursive variance reduced algorithms in Fang et al. (2018) and Xie et al. (2025) are not equipped with adaptive stepsizes or stochastic linesearch.

Response to Weakness 2: Assumption-matched experiments across dimensions.

We have replaced the Rosenbrock experiment with a box-constrained nonconvex regularized quadratic family (Section 6.1 and Appendix F.1), and added a box-constrained nonconvex regression family with real data News20 (Section 6.3 and Appendix F.5). Both have smoothness, variance, and initial-gap bounds uniform in the dimension. Figures 1 and 3 compare non-Euclidean and Euclidean configurations across six dimensions; the models, bounds, and results are detailed in our response to Q2.

Response to Weakness 3: Structured and real-data evidence for non-Euclidean geometry.

The revised News20 experiments separately compare the minibatch method SPL-MB and the variance-reduced method SPL-VR in Euclidean and non-Euclidean geometries on high-dimensional real data. Both problems satisfy the oracle and lower-boundedness assumptions, with matched settings across the SPL geometries and common gradient-call budgets. The dimension-wise comparisons are detailed in our response to Q2.

SPL-MB on News20 (Appendix F.4, Figure 5). On all 1999619996 samples and 13551911355191 features of news20.binary, we compare SPL-MB with p=2p=2, 1.51.5, and 1+1/(2log⁡d)1+1/(2\log d) against SLS2. The SPL-MB configurations share all settings except pp, with five paired runs and the common budget NG=1999616≃100n\mathcal N_G=1999616\simeq100n. At this budget, both non-Euclidean SPL-MB choices attain smaller median objectives and squared residuals than SPL-MB with p=2p=2 and SLS2:

MethodObjectiveSquared ℓ∞\ell_\infty residual
SPL-MB p=2p=20.7025353.459×10−53.459\times10^{-5}
SPL-MB p=1.5p=1.50.6926652.734×10−62.734\times10^{-6}
SPL-MB near-ℓ1\ell_10.6926536.662×10−76.662\times10^{-7}
SLS20.7091046.209×10−56.209\times10^{-5}

Figure 5 gives the complete curves and interquartile ranges.

SPL-VR on News20 (Section 6.3, Appendix F.5, Figures 3 and 6). We also compare SPL-VR with p=2p=2 and 1.51.5, Prox-SpiderBoost, and Prox-SpiderBoost-M on the box-constrained News20 regression model. The model, dimension-uniform bounds, matched settings, and six-dimension results are detailed in our response to Q2. At all six tested dimensions, SPL-VR with p=1.5p=1.5 has the smallest median first recorded iteration to gap 10−710^{-7} among the four methods.

On all 13551911355191 features, three paired runs use K=1000K=1000 and a common gradient-call budget of 648388648388. Median endpoint gaps and first recorded calls to gap 10−710^{-7} are:

MethodEndpoint gapTarget hitsGradient calls to target
SPL-VR p=2p=21.38×10−81.38\times10^{-8}3/33/3580264
SPL-VR p=1.5p=1.52.71×10−92.71\times10^{-9}3/33/3169528
Prox-SpiderBoost97.20/30/3-
Prox-SpiderBoost-M3.81×10−73.81\times10^{-7}0/30/3-

Thus SPL-VR with p=1.5p=1.5 achieves a smaller final gap and reaches the target with about 7171\\% fewer gradient calls than SPL-VR with p=2p=2, while both baselines remain above the target. The full curves and protocols are in the cited sections and appendices.

Response to Weakness 4: Matched Armijo parameters.

The replacement and added experiments use a common Armijo constant c=0.1c=0.1 for linesearch methods. Within every comparison of SPL geometries, all other algorithmic settings are matched, so changing pp is not confounded with changing cc. See our response to Q3 and the matched comparison in Section 6.1 and Appendix F.1.

AuthorsOpenReview ↗

Response to Reviewer 12K1 (2/3)

Response to Q1: Samplewise versus mean-squared smoothness.

Our samplewise smoothness assumption is stronger than the mean-squared smoothness used by Xie et al. (2025) in the corresponding geometry, but the latter does not consider adaptive stepsizes nor the stochastic linesearch. Their complexity-achieving parameter choices use problem constants, including a stepsize η=1/L\eta=1/L and variance-dependent batch sizes. Our methods instead select stepsizes by same-batch linesearch and prescribe batch sizes without knowing LL or the variance (hence problem-parameter-free), given an external iteration budget. Note that these constants may remain in the analysis, but are not algorithm inputs, in contrast to the algorithms by Xie et al. (2025).

As is indicated in the response to Weakness 1, the samplewise L-smootheness is a common assumption in many existing CRN-enabled stochastic linesearch methods.

The samplewise L-smootheness is essential to our current proof: it provides uniform stepsize and trial-count bounds, controls Taylor-remainder differences between candidates, and enables the concentration estimate for the VR model error. Mean-squared smoothness suffices for the SPIDER variance recursion, but does not directly provide these controls for adaptive same-batch Armijo linesearch. Extending the analysis to this weaker condition may require substantially different analysis and is left for future work.

Response to Q2: Dimension-uniform problem families and geometry comparisons.

We have replaced Rosenbrock with a nonconvex regularized quadratic family in Section 6.1. We minimize f(x)f(x) over [−3,3]d[-3,3]^d, where

f(x) & =\frac12(x-x_{\rm true})^\top\Sigma(x-x_{\rm true}) +2.5\sum_{i=1}^d\frac{x_i^2}{1+x_i^2} \\\\ & \quad+0.05\left(\sum_{i=1}^d(x_i-x_{{\rm true},i})\right)^2, \\\\ F(x;\xi,\eta) & =f(x)+\frac12\sum_{i=1}^d\xi_i x_i^2+\eta^\top x. \end{aligned}$$ Here $x_{\rm true}=(\mathbf1_{100},0,\ldots,0)^\top$, $\Sigma$ is symmetric tridiagonal with diagonal entries $1$ and adjacent entries $1/4$, and the coordinates of $\xi,\eta$ are independent Rademacher variables. With $r=\delta_{[-3,3]^d}$, Appendix F.1 verifies $$L_{1,\infty}\leq7.1,\qquad \sigma_\infty^2\leq16,\qquad \Phi(0)-\Phi_{\inf}\leq574.75,$$ uniformly in $d$. These follow from the sample Hessian's maximum absolute entry bound, $\\|G-\nabla f\\|_\infty\leq4$ on the box, and $f\geq0$ with $f(0)=574.75$, respectively. The family therefore satisfies the smoothness, variance, and initial-gap requirements of the near-$\ell_1/\ell_\infty$ result. We compare SPL-MB with $p=2$ (matched SLAM), $1.5$, and $1+1/(2\log d)$, projected SLS, and tuned projected SGD at $d\in\\{5000,10000,15000,20000,25000,30000\\}$. All methods use $x_0=0$, batch size $128$, $K=400$, and five paired sample streams. All linesearch methods share $s=1$, $c=0.1$, and $\beta=0.9$; the three SPL-MB variants also share the normalization $h(z)=\\|z\\|_p^2/[2(p-1)]$ and stepsize resets every $50$ iterations, differing only in $p$. The coupled quadratic has $\ell_1$-to-$\ell_\infty$ Hessian norm $0.1$ and Euclidean Hessian norm $0.1d$. This motivates the near-$\ell_1$ choice, which retains bounded norm-conversion factors as described in Section 5.1. Figure 1 shows that SPL-MB with the near-$\ell_1$ choice has the smallest median endpoint gap among all five methods for $d\geq15000$ and the smallest median squared $\ell_\infty$ stationarity residual for $d\geq20000$, at the tested dimensions. The endpoint numerical gaps at $K=400$ are: | $d$ | SPL-MB $p=2$ | SPL-MB $p=1.5$ | SPL-MB near-$\ell_1$ | Projected SLS | Tuned projected SGD | | --- | --- | --- | --- | --- | --- | | 5000 | 1.0584 | 0.1241 | 0.0827 | 0.0334 | 0.2543 | | 10000 | 7.1657 | 0.1548 | 0.1007 | 0.0518 | 0.2498 | | 15000 | 0.3520 | 0.3618 | 0.1122 | 0.1449 | 0.2552 | | 20000 | 22.5995 | 0.2308 | 0.1222 | 0.4296 | 11.0339 | | 25000 | 36.0615 | 0.1415 | 0.1320 | 0.8081 | 11.0331 | | 30000 | 42.6989 | 0.1690 | 0.1391 | 1.3843 | 11.0328 | In timing runs capped at $3200$ iterations, SPL-MB with $p=1.5$ has the shortest median time to gap $0.5$ at all six dimensions, and both non-Euclidean variants have $5/5$ hits throughout. The near-$\ell_1$ SPL-MB variant is also faster than projected SLS from $d=15000$ onward. Figure 1 and Appendix F.1 give the full gap, squared-stationarity, and time comparisons. **SPL-VR on News20 (Section 6.3 and Appendix F.5).** We additionally use the real-data family $$\min_{w\in[-3,3]^d}\\; \frac1{2n}\sum_{i=1}^n(x_i^\top w-y_i)^2 +2.5\sum_{j=1}^d\frac{w_j^2}{1+w_j^2} +0.005\left(\sum_{j=1}^d w_j-100\right)^2.$$ All $19996$ observations are retained, the feature vectors are scaled to $\\|x_i\\|_1\leq1$, and six nested feature sets use the same dimensions as above.
AuthorsOpenReview ↗

Response to Reviewer 12K1 (3/3)

Response to Q2 (continued)

The initial point has its first 100100 coordinates equal to one and the rest zero. Appendix F.5 verifies, uniformly in dd,

\Phi(w_0)-\Phi_{\inf}\leq127.$$ The stochastic sample selects a data point uniformly and includes both deterministic penalties. These bounds follow from the sample Hessian's maximum absolute entry, the variance bound on the box, and the nonnegative objective with $f(w_0)\leq127$. Its quadratic coupling similarly has $\ell_1$-to-$\ell_\infty$ Hessian norm $0.01$ and Euclidean Hessian norm $0.01d$. We compare SPL-VR with $p=2$ and $1.5$, Prox-SpiderBoost, and Prox-SpiderBoost-M. All share the same initial point, five paired streams, full-gradient refreshes, $b=256$, and $q=157$; the SPL-VR variants also share $s=1$, $c=0.1$, $\beta=0.9$, and reset period $50$. Since $L$ 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. At the common checkpoint $K=250$, every method has $\mathcal N_G=166968$. Median gaps are: | $d$ | SPL-VR $p=2$ | SPL-VR $p=1.5$ | Prox-SpiderBoost | Prox-SpiderBoost-M | | --- | --- | --- | --- | --- | | 5000 | $1.78\times10^{-15}$ | $-1.78\times10^{-15}$ | $4.44\times10^{-15}$ | $3.55\times10^{-15}$ | | 10000 | $-1.78\times10^{-15}$ | $-1.78\times10^{-15}$ | $4.69\times10^{-13}$ | $2.22\times10^{-15}$ | | 15000 | $1.47\times10^{-13}$ | $2.22\times10^{-15}$ | $7.29\times10^{-8}$ | $1.15\times10^{-10}$ | | 20000 | $2.06\times10^{-12}$ | $1.55\times10^{-15}$ | $1.33\times10^{-5}$ | $3.76\times10^{-6}$ | | 25000 | $1.31\times10^{-10}$ | $1.73\times10^{-14}$ | $3.04\times10^{-5}$ | $4.15\times10^{-6}$ | | 30000 | $6.63\times10^{-8}$ | $7.35\times10^{-14}$ | $2.38\times10^{-4}$ | $4.47\times10^{-6}$ | Entries are raw numerical gaps, including roundoff-level values. SPL-VR with $p=1.5$ maintains near-reference accuracy as the dimension increases, while SPL-VR with $p=2$ and the Spider configurations have larger fixed-budget gaps at the larger dimensions. The two dimension-wise experiments therefore exhibit reduced sensitivity to dimension for the non-Euclidean configurations, with direct $p=2$ comparisons. Figure 3 gives the fixed-budget comparison; Figure 6 gives the dimension-wise trajectories. **Response to Q3: Geometry comparisons with a common Armijo constant.** The Armijo constant $c\in(0,1)$ is a user-chosen parameter that can be adjusted for each problem. In all revised experiments, we use the basic choice $c=0.1$ without problem-specific tuning of $c$, keeping it common across linesearch methods. We have replaced the Rosenbrock benchmark with the new bounded nonconvex regularized quadratic family in Section 6.1 and Appendix F.1. In this replacement experiment, all linesearch methods use the same $c=0.1$, $s=1$, and $\beta=0.9$. In particular, SPL-MB with $p=2$ is matched SLAM, and the $p=1.5$ and near-$\ell_1$ variants use exactly the same reset period, batches, initialization, budget, and paired random streams. Thus the comparison changes $p$ without changing the Armijo parameter. With these matched settings, the near-$\ell_1$ variant has smaller median gaps than matched SLAM at every tested dimension (Figure 1). Our response to Q2 gives the gap table, stationarity comparison, and time-to-gap results. News20 SPL-MB and SPL-VR likewise keep $c=0.1$ and all other SPL settings fixed within each geometry comparison (Appendices F.4-F.5). **References** - 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 - Vaswani et al. (2019). Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates. NeurIPS 2019. - Fang et al. (2018). SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator. NeurIPS 2018. - 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 - Tsukada and Iiduka (2025). Relationship Between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent Using Armijo-Line-Search Learning Rate. Transactions on Machine Learning Research. https://openreview.net/forum?id=pqZ6nOm3WF - Jiang and Stich (2023). Adaptive SGD with Polyak Stepsize and Line-search: Robust Convergence and Variance Reduction. NeurIPS 2023.
Reviewer_h9f4OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies stochastic nonconvex composite optimization and develops stochastic proximal linesearch methods in ℓp\ell_p geometry for 1<p≤21<p\leq 2. Under uniform samplewise smoothness and bounded gradient variance, SPL-MB achieves an O(ϵ−4)O(\epsilon^{-4}) stochastic oracle complexity, while SPL-VR combines a SPIDER-type estimator with a linesearch model to obtain O(ϵ−3log⁡(e+1/ϵ))O(\epsilon^{-3}\sqrt{\log(e+1/\epsilon)}). The analysis also covers near-ℓ1/ℓ∞\ell_1/\ell_\infty stationarity and inexact proximal computations.

Critical strengths

The paper provides a theoretically supported integration of SPIDER-type variance reduction with stochastic proximal linesearch. Also, SPL-VR introduces an affine correction that aligns the Armijo model with the recursive gradient estimator.

This paper gives an analysis of stochastic proximal linesearch methods for ℓp\ell_p geometry with 1<p≤21<p\le 2.

Critical weaknesses

The analysis requires smoothness of all individual sample gradients (Assumption 1, Eq. (3)), which is stronger than the average smoothness assumed in SPIDER. It restricts the applicability of the results, particularly in online stochastic settings where samplewise Lipschitz constants may be unbounded.

The stochastic oracle complexity bounds do not account for the computational cost of solving the ℓp\ell_p proximal subproblems. Thus, the overall computational efficiency for general composite objectives is less clear.

Questions for authors

Is samplewise smoothness essential for the proposed linesearch framework, or can the convergence guarantees be extended to the average smoothness assumption?

For general convex regularizers, what is the computational cost of solving the ℓp\ell_p proximal subproblems, and how does it affect the overall computational complexity?

3 comments
AuthorsOpenReview ↗

Response to Reviewer h9f4

We thank the reviewer for the careful reading and helpful questions about the smoothness assumption and proximal computational cost. Section, appendix, equation, and figure numbers below refer to the revised manuscript.

Response to Weaknesses: Samplewise smoothness and proximal computational cost

Note that the samplewise L-smoothness is a common assumption and employed in many existing common random number enabled stochastic linesearch methods (see Vaswani et al. (2019); Tsukada and Iiduka (2025); Wang et al. (2025); Jiang and Stich (2023)). It can be verified for a host of machine learning models including ones in the form of finite sums. Indeed, if every component function in the finite sum is LiL_i-smooth, then samplewise L-smoothness naturally follows (L=max⁡iLiL = \max_i L_i). The test problems in our numerical experiments now satisfy this assumption. It is essential for deriving a uniform stepsize lower bound and other theoretical properties in our analysis (see Q1) and other stochastic linesearch methods in literature.

Note that we have closed-form solutions when r≡0r \equiv 0 and efficient solutions for the box-constrained case. Both have O(d)O(d) computational cost to obtain exact or highly accurate solution per iteration, so the overall computational cost is incremental compared to the Euclidean case. Note that for the most general composite objectives, the overall computational cost is not our main focus in this paper. It may depend on the specific structure of the proximal subproblem and the solver used, and requires comprehensive and detailed discussion even in the Euclidean case. Nevertheless, we manage to derive the bound under certain assumption on the subproblem solver (see Q2).

Response to Q1: The role of samplewise smoothness

Note that samplewise smoothness is a common assumption in literature as is indicated in the response to the critical weakness. Samplewise smoothness with a common constant LL is essential to our current proof. It gives uniform stepsize and trial-count bounds (Proposition 1 and 2) and the samplewise function-increment error/Taylor-remainder bounds needed to control adaptive same-batch Armijo selection (Lemma 4 and Lemma 6).

Extending our convergence guarantees to mean-squared smoothness as used for SPIDER's variance recursion may require substantially different analysis and is left for future work.

Response to Q2: Computational cost of proximal subproblems

We have supplemented the computational-cost discussion in Sections 3.2 and 5.2, with detailed bounds in Appendices D.3 and E.4.

For a box, p=2p=2 gives coordinatewise clipping, whereas 1<p<21<p<2 requires a scalar root search using clipped coordinate formulas. Each root-function evaluation and KKT check costs O(d)\mathcal O(d). For fixed geometry and initial bracket data, tightening the KKT tolerance adds only logarithmic work. Thus the dimension factor remains linear, with bracketing and accuracy costs included in Lemma 9. The inner search uses the supplied gradient estimator without further stochastic oracle queries.

For general convex regularizers, Appendix E.4 derives a solver-dependent proximal work bound, including rejected backtracking trials.

Under an uniform logarithmic certificate-cost bound, the new Corollary 4 gives total proximal work bound of O(Klog⁡(e+K))\mathcal O(K\log(\mathrm e+K)) (KK is the outer iteration budget), with dimension-, geometry- and solver-dependent factors retained. Indeed, for the tolerances ηk=η0/(k+1)\eta_k=\eta_0/(k+1) with η0>0\eta_0>0, the stated solver-cost bound gives logarithmic growth of the accuracy-dependent work per call. For fixed problem and solver parameters, K=O(ε−2)K=\mathcal O(\varepsilon^{-2}) suffices for expected squared stationarity at most ε2\varepsilon^2, so the additional proximal work is O(ε−2log⁡(e+1/ε))\mathcal O(\varepsilon^{-2}\log(\mathrm e+1/\varepsilon)). Appendix E.4 also adds this term to the work of gradient evaluations, function evaluations, and the remaining vector operations.

References

  • Vaswani et al. (2019). Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates. NeurIPS 2019.

  • Tsukada and Iiduka (2025). Relationship Between Batch Size and Number of Steps Needed for Nonconvex Optimization of Stochastic Gradient Descent Using Armijo-Line-Search Learning Rate. Transactions on Machine Learning Research. https://openreview.net/forum?id=pqZ6nOm3WF

  • 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.

Thank you for the detailed response. I will maintain the score.

Thank you for taking the time to review our response. We appreciate your careful consideration of our arguments and explanations. Your constructive feedback has been helpful in strengthening our work.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses and Manuscript Revisions

We thank all reviewers, the Area Chairs, and the Program Chairs for their time and constructive feedback. We have made the following manuscript revisions in response to the reviews. Revised manuscript text is highlighted in blue.

1. Added an explicit account of the contributions (EoCB, CW1/Q1). The Introduction now compares SPL-VR directly with AdaSVRLS: our affinely corrected sampled model uses the accepted stepsize without rescaling or clipping it by the previous step, allowing prescribed resets and potentially nonmonotone stepsizes. The revised analysis overview identifies the function-increment error map for minibatching, the Taylor-remainder function for recursive VR, and candidate stability for both. It also states that the VR design and both analyses already contribute in Euclidean geometry.

2. Specified which assumptions are relaxed and which remain (h9f4, CW1/Q1; 12K1, CW1/Q1). Section 2 now explicitly compares our assumptions with SLAM, SLS, SPIDER, and Xie et al. (2025). We remove bounded-gradient, growth, and globally Lipschitz-regularizer requirements, but retain common-constant samplewise smoothness. Our responses explain its use in finite backtracking and adaptive same-batch error control, and leave extension to mean-squared smoothness for future work. Section 6.2 now also explains why its logistic models satisfy the smoothness, variance, and lower-boundedness assumptions.

3. Added proximal-work bounds, not only oracle counts (h9f4, CW2/Q2). We added Lemma 9 in Appendix D.3, bounding the scalar iterations needed for the full box KKT criterion under bisection and safeguarded Newton, with initial bracketing work included. New Appendix E.4 counts the actual inner work over accepted and rejected trials and combines it with gradient, function, and auxiliary costs. Its Corollary 4 gives O(Klog⁡(e+K))\mathcal O(K\log(\mathrm e+K)) proximal work under the stated logarithmic certificate-cost condition, retaining dimension-, geometry-, and solver-dependent factors. Sections 3.2 and 5.2 now point to these bounds.

4. Replaced Rosenbrock with an assumption-matched dimension study (12K1, CW2/Q2; EoCB, CW2). Section 6.1 and Appendix F.1 now define a box-constrained nonconvex regularized quadratic family with correlated curvature and state-dependent noise, and verify L1,∞≤7.1L_{1,\infty}\le7.1, σ∞2≤16\sigma_\infty^2\le16, and initial gap at most 574.75 uniformly in dimension. Figure 1 was replaced by six-dimension comparisons of three SPL-MB geometries, projected SLS, and tuned projected SGD. The near-ℓ1\ell_1 choice has the smallest median gap from d=15000d=15000 and squared residual from d=20000d=20000 onward. The new bounded families meet the dimension-uniform conditions stated in Section 5.1 and Appendix C.

5. Added high-dimensional real-data minibatching (12K1, CW3; EoCB, CW2). New Appendix F.4 and Figure 5 compare SPL-MB with p=2p=2, p=1.5p=1.5, and near-ℓ1\ell_1 against SLS2 on all 1,355,191 News20 features. Both non-Euclidean choices attain smaller median objectives and squared stationarity residuals at the common budget of about 100n100n gradient calls. Section 6.1 now summarizes this additional real-data result.

6. Added non-Euclidean SPL-VR to all three studies (12K1, CW3; EoCB, CW2/Q2).

  • Section 6.2, Appendix F.2, and Figure 2 add SPL-VR with p=1.5p=1.5 on a9a and w8a; it reaches gap 10−610^{-6} in fewer refresh epochs than both SpiderBoost baselines.
  • Appendix F.3 and Figure 4 add SPL-VR with p=1.5p=1.5 and r(w)=0.1∣w∣1r(w)=0.1\\|w\\|_1; it reaches composite gap 10−310^{-3} in fewer recorded iterations than both proximal baselines.
  • Section 6.3, Appendix F.5, and Figures 3 and 6 verify dimension-uniform bounds for bounded News20 regression and compare SPL-VR with p=2p=2 and 1.51.5 against proximal Spider baselines across six dimensions and on all features. Full-feature median gradient calls to gap 10−710^{-7} are 169,528 for SPL-VR with p=1.5p=1.5 versus 580,264 for SPL-VR with p=2p=2; neither baseline reaches the target within budget. With unknown LL, Spider steps are tuned per dimension; timing is omitted for this study.

7. Removed the Armijo-parameter mismatch (12K1, CW4/Q3). All replacement and added linesearch experiments use c=0.1c=0.1, with the remaining SPL settings matched when varying pp. Section 6 and Appendix F specify the shared starts, batches, budgets, and random streams. Our response explains that cc is tunable; the reported comparisons use the basic choice 0.1.

8. Expanded and reordered the proofs. Appendices A-E now supply intermediate derivations for minibatch error bounds, the VR recursion and compensation argument, and inexact proximal analysis. Supporting bounds are placed closer to their use. The supplementary code has also been updated to reproduce the revised experiments and figures.

We look forward to the reviewers' feedback and would be happy to discuss any remaining questions and 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.