acceptodds
Withdrawn from ICLR 2027

When stochastic memoryless BFGS meets nonmonotone line search: A way for efficient over-parameterized learning

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Most existing stochastic L-BFGS methods employ constant or diminishing step-size schedules, which may limit their capability to exploit curvature information and adapt to the local geometry effectively. In this work, we propose SMBFGS, a stochastic memoryless BFGS method that incorporates the nonmonotone line search for over-parameterized learning problems. The method employs a damped quasi-Newton update to preserve the positive definiteness of the inverse Hessian approximation, thereby ensuring the descent property of resulting search directions. Its step size is then selected adaptively through the stochastic nonmonotone line search. We establish the linear convergence of SMBFGS in the general nonconvex setting under suitable interpolation assumptions. Numerical experiments on training deep neural networks demonstrate that SMBFGS outperforms representative stochastic L-BFGS methods and widely used optimizers, including Adam and AdamW, in most cases.

Primary area:
optimization
Keywords:
Over-parameterized learning, Stochastic L-BFGS, Adaptive learning rate, Linear convergence, Deep neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_h3W4OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper proposes a stochastic memoryless BFGS method (SMBFGS) combining a same-batch curvature pair, Powell damping, and a stochastic nonmonotone line search. A capped stochastic Polyak step initializes the search, while a reset counter carries backtracking information between iterations. Retaining one curvature pair gives linear storage complexity in the number of parameters. The paper claims linear convergence under smoothness, conditional unbiasedness, strong growth, a direction–gradient covariance condition, common-minimizer interpolation, and a global PL condition. Experiments compare SMBFGS with SGD, Adam, AdamW, SLS, and PBQN-FO on seven image-classification configurations, reporting training loss, test accuracy, gradient norms, and runtime over five independent runs.

Critical strengths
  1. The paper addresses a meaningful practical optimization problem with a lightweight construction. Combining inexpensive curvature information with adaptive step selection is well motivated. The same-batch gradient difference reduces contamination from changing batches, and damping preserves positive definiteness for nonzero displacement vectors. Retaining only one curvature pair makes the approach attractive when optimizer storage matters.
  2. The experiments provide useful evidence of optimization benefits within the evaluated setup. The evaluation covers several architectures and five independent runs, with both epoch-based and runtime-based comparisons. Including runtime is valuable given the additional gradient and trial-loss evaluations. Some predictive gains are encouraging: on CIFAR-10 with DenseNet-121, SMBFGS achieves 94.35% ± 0.17% test accuracy, compared with 93.54% ± 0.46% for SLS and 93.51% ± 0.28% for Adam.
Critical weaknesses
  1. The main convergence theorem is false as stated.

Section 4.2 defines

\qquad \chi=\frac{1}{\eta_{\min}}+A-2\sigma\mu.$$ However, Proposition A.1 only establishes $$\widetilde{\eta}=\min\{(\underline{\eta},\delta\eta_{\mathrm{low}})\},$$ where $\underline{\eta}$ bounds the effective initial trial step. The initial trial step can already be smaller than the sufficient-acceptance threshold. Equation (18) nevertheless identifies $1/\widetilde{\eta}+A+a-2\sigma\mu$ with $\chi+a$, without establishing the required equality. Consider the deterministic quadratic $$F(x)=f_k(x)=\tfrac12x^2,\qquad \text{with}~~ x_0=1.$$ The memoryless BFGS update maintains $H_k=1$, and all seven assumptions hold with $$L=L_{\max}=\mu=c_1=c_2=c_3=\rho=1,\qquad \sigma=1.$$ Choose $$c=\delta=\tfrac12,\quad c_p=0.1,\quad \eta_{\max}=0.1,\quad \xi=0,\quad a=1.$$ These parameters satisfy the theorem's stated restrictions and give $A=1$, $\eta_{\min}=0.5$, $\chi=1$, and $q=0.2$. The capped Polyak candidate is $0.1$, which satisfies Armijo without backtracking. Hence $x_1=0.9$ and $F(x_1)=0.405$. Algorithm 1 initializes $C_{-1}=f_0(x_0)=0.5$, giving $$\Psi_0=0.5+0.1(0.5)=0.55.$$ The theorem therefore predicts $$F(x_1)\le q\Psi_0=0.11,$$ which is false. This invalidates the stated convergence bound, although the algorithm itself converges on this example. Lemma A.1 concerns the raw Polyak candidate, whereas Proposition A.1 requires a lower bound on the effective candidate after multiplication by $\delta^{r_k}$. Remark A.1 clarifies the notation but does not establish this bound for Algorithm 1. The applicability of a corrected result also needs clarification. Interpolation does not establish global PL or positivity of $\sigma$, and local PL behavior alone does not justify a global guarantee. The experiments use $\xi=0.9999$, without demonstrating compatibility with the theorem's parameter restrictions. These issues affect the paper's central theoretical contribution. 2. The experiments do not isolate the contribution of curvature information, and the baseline protocol limits the broader performance claims. The most consequential missing comparison is PoNoS, which already combines a nonmonotone line search, capped Polyak initialization, and a reset mechanism (Galli, Rauhut, and Schmidt, “Don't Be So Monotone,” NeurIPS 2023). Comparing SMBFGS with monotone SLS changes both the direction and step-selection procedure. The resulting gains therefore cannot be attributed specifically to the proposed curvature update. The essential control is a gradient direction with the same nonmonotone search, Polyak initialization, and reset parameters. A complementary comparison using the BFGS direction with a monotone search would help separate the components. Without these controls, the results demonstrate a promising combination but do not establish the incremental benefit of curvature information. Appendix A.3 states that SGD, Adam, and AdamW use fixed learning rates without scheduling. A preliminary grid search is mentioned, but its ranges, validation protocol, selection criterion, and budget are not reported. The conclusions therefore apply to the evaluated configurations rather than establishing superiority over well-tuned scheduled baselines. PBQN-FO's 5.05% test accuracy on CIFAR-100 with ResNet-34 also warrants investigation, although this result alone does not establish an implementation error. Finally, improved training-objective minimization does not consistently improve prediction. On CIFAR-100 with ResNet-34, SLS achieves 74.69% ± 0.20% test accuracy, compared with 71.04% ± 0.47% for SMBFGS despite its lower training loss. The evidence is stronger for training-objective minimization than for consistently better predictive performance.
Questions for authors
  1. Can you provide a corrected theorem and proof addressing the quadratic counterexample, establishing a uniform step-size lower bound after resetting, and identifying a nonempty admissible parameter regime?

  2. How much improvement remains over PoNoS, or a gradient-direction control with matched nonmonotone search, Polyak initialization, and reset settings? Does the BFGS direction provide a measurable benefit under otherwise identical conditions?

  3. Do the main empirical conclusions hold with scheduled first-order baselines and a fully documented tuning protocol? What explains PBQN-FO's particularly poor results on the convolutional tasks, including its batch-growth behavior and tuning?

  4. Can you establish the direction bounds for the particular damped memoryless update and clarify the role of the covariance assumption? Since HkH_k is determined before sampling BkB_k, conditional unbiasedness gives Ek[dk]=−Hk∇F(xk)\mathbb{E}_k[d_k]=-H_k\nabla F(x_k). Can this structure support a more direct analysis or weaker assumptions?

1 comment

Thank you for your constructive feedback. We have corrected the constants and proof of Theorem 4.1. Manuscript changes are marked in red.

1. Corrected convergence analysis

(1) Corrected theorem and treatment of the quadratic counterexample. For the counterexample parameters, the revised bounds give h+=20h_{+}=20 and ηmin⁡=0.05≤ηk=0.1\eta_{\min}=0.05\le\eta_k=0.1, replacing the incorrect lower bound 0.50.5. These parameters give ω+=2\omega_{+}=2 and ϑ=0\vartheta=0, so they do not satisfy the revised strict contraction conditions. The revised theorem therefore does not make the invalid rate prediction for this setting.

The revised theorem establishes E[F(xk)−F∗]≤qkE[F(x0)−F∗]\mathbb{E}[F(x_k)-F^\ast]\le q^k\mathbb{E}[F(x_0)-F^\ast], where q=1−2μh−ϑ/(Lh+)∈[0,1)q=1-2\mu h_{-}\vartheta/(Lh_{+})\in[0,1). The proof uses a pathwise endpoint estimate to handle dependence between the accepted step size and the current gradient noise, without assuming independence.

(2) Uniform step-size bounds after resetting. The revised Proposition A.1 proves 0≤rk≤R0\le r_k\le R and rk+ℓk≤Jr_k+\ell_k\le J by induction. It consequently establishes ηk,0≥uδR\eta_{k,0}\ge u\delta^R and ηk≥ηmin⁡:=max⁡uδJ,min⁡uδR,δηlow>0\eta_k\ge\eta_{\min}:=\max\\{u\delta^J,\min\\{u\delta^R,\delta\eta_{\mathrm{low}}\\}\\} > 0, with the constants defined in Section 4.2. Thus, both the effective trial and accepted step sizes are controlled, not just the raw Polyak candidate.

(3) Nonempty admissible parameter regime. For any finite admissible relative-noise constant τ≥0\tau\ge0, choose 0<ηmax⁡<min⁡1/(2cpLmax⁡),,2(1−c)/(Lmax⁡h+),,2/[(1+τ)Lh+]0 < \eta_{\max} < \min\\{1/(2c_pL_{\max}),\\,2(1-c)/(L_{\max}h_{+}),\\,2/[(1+\tau)Lh_{+}]\\}. Then J=R=0J=R=0 and ηmin⁡=ηmax⁡\eta_{\min}=\eta_{\max}. Writing ω=Lh+ηmax⁡\omega=Lh_{+}\eta_{\max}, we have ω−=ω+=ω\omega_{-}=\omega_{+}=\omega and 0<ω<2/(1+τ)0 < \omega < 2/(1+\tau). The definition of ϑ\vartheta therefore reduces to ϑ=ϕ(ω)−τω2/2=ω[1−(1+τ)ω/2]>0\vartheta=\phi(\omega)-\tau\omega^2/2=\omega[1-(1+\tau)\omega/2] > 0. This supplies an explicit nonempty sufficient parameter range without imposing a positive lower threshold on the PL constant for a fixed admissible noise bound.

The revised theorem appears in Section 4.2; the reset bounds and complete convergence proof are provided in Appendix A.2.

2. Benefit of the BFGS direction under matched line-search settings.

We have added PoNoS using the same training and evaluation framework, with matched nonmonotone search, capped Polyak initialization, and reset parameters (Appendix A.3, Table 4). PoNoS uses the negative stochastic gradient, whereas SMBFGS uses a damped memoryless BFGS direction.

Under these settings, SMBFGS achieves higher final mean test accuracy on five of the seven tasks. These results provide empirical evidence of benefits from the curvature-based direction under matched line-search settings.

The complete comparisons are reported in Section 5.2 and Appendix A.5, with terminal statistics in Table 2.

3. Scheduled baselines, tuning, and PBQN-FO.

We have added SGDM with momentum 0.9 and cosine learning-rate decay. SMBFGS achieves lower final mean training loss on six of the seven tasks and higher final mean test accuracy on five, with one accuracy tie. The settings and comparisons are provided in Appendix A.3 and Section 5.

For PBQN-FO, the optimization batch size starts at 512 and increases according to the IPQN test, capped at the full training-set size. The value 128 denotes only the computational microbatch size. Its algorithmic hyperparameters were adopted from the original paper without additional task-specific tuning. Section 5.2 and Appendix A.5 discuss possible explanations for its observed performance: variance-scaled initial steps and curvature-pair rejection may limit optimization progress, while batch growth increases the work per update.

4. Direction bounds and the covariance assumption.

(1) Direction bounds derived from the algorithm. Under smoothness, Lemma A.2 establishes h−I⪯Hk⪯h+Ih_{-}I\preceq H_k\preceq h_{+}I for SMBFGS's damped memoryless BFGS update with identity initialization. Consequently, ∣dk∣≤h+∣gk∣\\|d_k\\|\le h_{+}\\|g_k\\|, −gk⊤dk≥h−∣gk∣2-g_k^\top d_k\ge h_{-}\\|g_k\\|^2, and ∣dk∣2≤h+(−gk⊤dk)\\|d_k\\|^2\le h_{+}(-g_k^\top d_k). These are proved properties of the update, replacing the separate direction-quality assumption.

(2) Direct analysis without the covariance assumption. Lemma A.2 also proves that HkH_k is Fk\mathcal{F}_k-measurable. Conditional unbiasedness therefore gives Ek[dk]=−Hk∇F(xk)\mathbb{E}_k[d_k]=-H_k\nabla F(x_k) and hence ∇F(xk)⊤Ek[dk]≤−h−∣∇F(xk)∣2\nabla F(x_k)^\top\mathbb{E}_k[d_k]\le-h_{-}\\|\nabla F(x_k)\\|^2. We have removed the previous direction-gradient covariance assumption. The revised proof directly controls the gradient error in the metric induced by HkH_k, with Lemma A.4 providing a sufficient relative-noise bound under the strong growth condition.

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

This paper proposed a stochastic memoryless BFGS method with nonmonotone line search for empirical risk minimization problems. Specifically, the authors computed the memoryless BFGS direction following Wang et al. (2017), where they use the same batch to compute the curvature pair and apply Powell damping to ensure positive definiteness of the quasi-Newton matrix. Then they used the nonmonotone line search initialized by the stochastic Polyak rule from Galli et al. (2023) to choose the step size. Under interpolation and the Polyak-Łojasiewicz condition, they established a linear convergence rate in expectation. They also evaluated the proposed method on deep neural network training for image classification.

Critical strengths

For the proposed method, the paper provides both theoretical convergence analysis and numerical experiments to validate its empirical performance.

Critical weaknesses
  • In my understanding, this paper appears to be a relatively straightforward combination of the stochastic L-BFGS method in Wang et al. (2017) and the Polyak nonmonotone stochastic (PoNoS) line search in Galli et al. (2023). Specifically, the stochastic L-BFGS method in Wang et al. (2017) employs a prescribed decaying step size, while the PoNoS method in Galli et al. (2023) uses the stochastic gradient as the update direction. This paper instead takes the update direction from Wang et al. (2017) (using memory size 1) and the line search technique from Wang et al. (2017). Moreover, the convergence analysis seems to closely follow those in Galli et al. (2023) and Lapucci & Pucci (2025), with similar assumptions and a Lyapunov potential function. Hence, the technical novelty of the paper seems somewhat limited.

  • The theoretical results are not particularly strong. To begin with, in Section 4.1, Assumptions 4.2 and 4.6 concern the specific update direction used in the algorithm. It is unclear why these assumptions will hold for the memoryless BFGS direction, and additional justification is needed. Moreover, there are several inconsistencies/errors in the proof (see "Questions for Authors" below).

  • The empirical results also lack an important baseline: the PoNoS method from Galli et al. (2023). Currently, it is unclear whether the improved performance mainly comes from using a nonmonotone line search or using the curvature information in the BFGS direction.

Questions for authors
  • Can the authors clarify how their proposed method is related to Wang et al. (2017) and Galli et al. (2023)?
  • Regarding notation, η^k,0\hat{\eta}_{k,0} should be the Polyak rule in (7), while ηk,0\eta_{k,0} appears to be defined as η^k,0δrk\hat{\eta}_{k,0}\delta^{r_k}. As a result, the lower bound in Lemma A.1 only applies to η^k,0\hat{\eta}_{k,0}, and thus it is unclear whether the lower bound on ηk,0\eta_{k,0} in Proposition A.1 exists.
  • According to (18), χ=1/η~+A−2σμ\chi = 1/\tilde{\eta} + A - 2\sigma \mu, which is different from the definition used in Section 4.2.
  • It is not immediately clear to me whether the assumption 0<χ<1/ηmax0<\chi< 1/\eta_{max} in Theorem 4.1 can be satisfied. This seems to require the PL parameter μ\mu to be sufficiently large, which can limit the applicability of the convergence theorem.
  • How does the PoNoS method from Galli et al. (2023) compare to the proposed method in the numerical experiments?
6 comments

We sincerely thank you for these constructive and helpful comments, which have greatly improved the quality of our work. We have provided point-to-point responses below. Changes made in the manuscript are marked in red. We genuinely hope that these corrections are satisfactory.

  1. Relationship to the existing methods. We have added Table 1 in the Related Work Section, which compares SMBFGS with SdLBFGS and PoNoS. SMBFGS is a natural extension of PoNoS: it retains the stochastic nonmonotone line-search framework but replaces the negative stochastic gradient direction with a damped quasi-Newton direction, incorporating curvature information into the search. Moreover, compared with SdLBFGS, which uses a prescribed step-size schedule (i.e., a diminishing step-size rule), SMBFGS selects its step size adaptively via line search.

    We want to emphasize that SMBFGS is not merely a trivial or aimless combination of existing methods, but rather a necessary advancement in stochastic nonmonotone line-search techniques. More detailed changes can be found in Table 1, which is shown in Section 2.

  2. Raw and effective candidates. Your notation concern is correct. Lemma A.1 applies to the raw candidate η^k,0\widehat{\eta}_{k,0}, whereas the backtracking input is ηk,0=η^k,0δrk\eta_{k,0}=\widehat{\eta}_{k,0}\delta^{r_k}. A raw lower bound alone does not justify Proposition A.1 for the effective candidate.

    Thus, in the revised version, we have carefully modified Proposition A.1 and presented a new proof. The new version supplies the missing argument for the actual algorithm. Detailed changes can be found in Proposition A.1.

  3. The coefficient in equation (18). Thank you for pointing out this inconsistency. We agree that the expression for χ\chi implied by the original Eq. (18) did not match its definition in Section 4.2.

    We have addressed this issue by revising the convergence theorem and its proof. We removed the previous condition and derivation involving χ\chi. The revised analysis consistently uses the uniform lower bound ηmin⁡\eta_{\min} on the accepted step sizes established in Proposition A.1, which accounts for the step-size reset rule. The convergence rate is now expressed through ϑ\vartheta and the contraction factor q=1−2μh−ϑLh+q=1-\frac{2\mu h_{-}\vartheta}{Lh_{+}}, whose definitions are consistent between the theorem in Section 4.2 and its proof in Appendix A.2.

  4. Applicability of the convergence theorem. Thank you for raising this concern. We agree that the original condition involving χ\chi was restrictive. We have replaced the original convergence theorem and its proof with a revised analysis based on uniform bounds on the accepted step sizes and an explicit relative gradient-noise condition.

    We have also removed the separate direction-quality and direction-gradient covariance assumptions. In particular, Lemma A.2 derives the uniform spectral bounds h−I⪯Hk⪯h+Ih_{-}I\preceq H_k\preceq h_{+}I directly from smoothness and SMBFGS's damped memoryless BFGS construction. The required direction bounds consequently follow from the algorithm itself.

    The revised conditions have a nonempty feasible range. For any finite admissible relative-noise constant τ≥0\tau\ge0, choosing 0<ηmax⁡<min⁡1/(2cpLmax⁡),,2(1−c)/(Lmax⁡h+),,2/[(1+τ)Lh+]0<\eta_{\max}<\min\\{1/(2c_pL_{\max}),\\,2(1-c)/(L_{\max}h_{+}),\\,2/[(1+\tau)Lh_{+}]\\} gives ηmin⁡=ηmax⁡\eta_{\min}=\eta_{\max}. With ω=Lh+ηmax⁡\omega=Lh_{+}\eta_{\max}, this yields ϑ=ω−(1+τ)ω2/2>0\vartheta=\omega-(1+\tau)\omega^2/2>0. Thus, for a fixed admissible noise bound, the revised conditions impose no positive lower threshold on the PL constant μ\mu. Detailed changes can be found in Section 4.2 (revised Theorem 4.1) and Appendix A.2, particularly Lemma A.2 (spectral and direction bounds), Proposition A.1 (step-size bounds), and the revised convergence proof.

  5. Comparison with PoNoS. Thank you for highlighting this missing baseline. We have added PoNoS using the authors’ released implementation, with the same line-search hyperparameters as SMBFGS (Appendix A.3, Table 4).

    Across the seven tasks, compared with PoNoS, SMBFGS achieves higher final mean test accuracy on five and lower final mean training loss on three. These comparisons support the practical value of incorporating curvature information within the nonmonotone line-search framework. Both epoch-wise and cumulative-runtime comparisons are provided in Section 5.2 and Appendix A.5, with terminal results summarized in Table 2.

We would like to express our sincere gratitude once again for your insightful suggestions. We hope that the revised manuscript now meets with your approval.

I thank the authors for their detailed response, revisions to the theoretical analysis, and additional experiments. Nevertheless, I still have reservations about the novelty of the proposed method relative to existing approaches and the experimental comparison with PoNoS.

I appreciate the authors' clarification of the differences between SMBFGS, SdLBFGS, and PoNoS. However, it remains unclear to me what technical challenges arise when combining a damped quasi-Newton direction with a stochastic nonmonotone line search, and whether any nontrivial algorithmic modifications are required to make this combination work.

Moreover, based on the final test accuracies reported in Table 2(b), the performance differences between PoNoS and SMBFGS appear relatively modest and, in several cases, comparable to the reported standard deviations. Therefore, the results do not convincingly demonstrate a substantial advantage of SMBFGS over PoNoS, especially considering the additional computational overhead associated with SMBFGS.

AuthorsOpenReview ↗

Motivation for extending PoNoS with curvature information

Thank you for clarifying these concerns. PoNoS (Galli et al., 2023) is an effective first-order method for over-parameterized learning. It uses the negative stochastic gradient as its search direction and adapts the step size through a nonmonotone line search. This raises a natural question: can curvature information guide the choice of direction while keeping the additional storage and computation manageable?

SdLBFGS (Wang et al., 2017) incorporates curvature through a history of damped curvature pairs. In their RCV1 comparison with SGD, the authors used a memory length of 10 and a prescribed diminishing step size. Such a schedule can become overly conservative late in training. A longer history also increases both storage and the cost of computing each direction, and choosing how many pairs to retain requires heuristic choices when curvature estimates are noisy.

These considerations motivate the memoryless design of SMBFGS. We construct each quasi-Newton direction from the most recent curvature pair alone and use PoNoS’s nonmonotone search to select a step along that direction. Retaining one pair limits the cost of applying the BFGS update and removes the need to tune the history length. Damping plays a distinct role here. The line search tests the sampled loss along the proposed direction, while damping preserves the positive curvature needed for the next BFGS direction to be a descent direction. This extends PoNoS to a curvature-based search while keeping the curvature history to a single pair, thereby striking a balance between computational efficiency and memory overhead.

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

The paper proposes SMBFGS, a stochastic optimizer that combines:

  • a memoryless (one-pair) BFGS direction, built from a same-batch curvature pair (B_{k−1} evaluated at x_k and x_{k−1}) with Powell damping;
  • the stochastic nonmonotone Armijo line search of Galli et al. (2023), initialized with a stochastic Polyak step and a "reset counter" that carries backtracking information across iterations.

Under smoothness, interpolation, strong growth, a direction–gradient covariance condition, gradient-related directions, and global PL, the authors prove linear convergence in expectation of a Lyapunov function combining the optimality gap and the nonmonotone reference value.

Experiments on 7 image-classification tasks compare against SGD, Adam, AdamW, SLS and PBQN-FO. Tasks range from MNIST/MLP to CIFAR-100/DenseNet-121, with 200 epochs and 5 seeds. SMBFGS typically reaches the lowest training loss and the best test accuracy in 5 of 7 tasks; SLS wins on both CIFAR-100 tasks.

Critical strengths
  • Simple, cheap, practical design.
    • O(d) curvature storage with a single damped pair.
    • Damping guarantees s^T ȳ ≥ 0.25‖s‖², so H_k is always positive definite.
    • Avoids prescribed step-size schedules.
    • Results are consistent across 7 architecture/dataset pairs, with 5 seeds and both epoch-wise and wall-clock plots.
  1. Code is released.
  • Honest reporting of where the method does not win. The paper explicitly discusses the CIFAR-100 tasks, where SLS generalizes better, and VGG-11, where SLS gets lower loss. It also notes the per-epoch overhead.
Critical weaknesses
  • The convergence theorem's conditions are restrictive. The theorem requires 0 < χ < 1/η_max, where χ = 1/η_min + A − 2σμ. This is equivalent to: 2σμ > A + (1/η_min − 1/η_max). The proof needs η_min ≤ η̃ ≤ η_k ≤ η_max, so the bracketed term is ≥ 0, and therefore 2σμ > A = L_max c₁²/(2c c₂). Now use three standard facts: σ ≤ c₂; c₂ ≤ c₁, which follows from c₂‖g‖² ≤ −gᵀd ≤ c₁‖g‖²; μ ≤ L ≤ L_max. Together these give the requirement μ/L > (c₁/c₂)²/(4c) ≥ 1/(4c). With the paper's c = 0.5, this means L/μ < 2, and d_k must be essentially −g_k (c₁ ≈ c₂). So the theorem applies only to almost perfectly conditioned problems, which is exactly where quasi-Newton curvature is unnecessary. Separately, the experiments use ξ = 0.9999 with η_max = 10. The condition ξ < a/(A+a), together with a < 1/η_max = 0.1, would require A < ~10⁻⁵. So the theory does not cover the reported runs. The abstract's claim of "linear convergence in the general nonconvex setting" should therefore be heavily qualified.

  • The closest baselines and the key ablation are missing, so the source of the gains is unclear.

    • SMBFGS is essentially PoNoS (Galli et al., 2023: nonmonotone line search plus Polyak initialization) with d = −H_k g_k. PoNoS with d = −g is not compared, so we cannot tell whether the gains come from the curvature direction or from the line search. Other stochastic QN baselines are absent: oLBFGS, SdLBFGS (Wang et al.), and the stochastic second-order methods under interpolation of Meng et al.

    • The only QN baseline, PBQN-FO, collapses (47% on CIFAR-10, 5% on CIFAR-100). This strongly suggests a tuning or implementation problem rather than a meaningful comparison.

    • SGD appears to be run without momentum or a schedule, and first-order baselines get only coarse grid-tuned constant learning rates.

    • The novelty claim ("first to combine stochastic L-BFGS with nonmonotone line search") is narrow: Bollapragada et al. (2018) already combine stochastic L-BFGS with a stochastic Armijo line search.

Questions for authors
  • What is the performance of PoNoS (same line search with d = −g) and of SMBFGS without the reset counter / with a monotone line search?
  • What are the average number of backtracks and function/gradient evaluations per iteration? SMBFGS needs at least 2 gradient evaluations per iteration, so per-epoch comparisons favor it. Time-to-target-accuracy numbers would help.
  • Why does PBQN-FO fail so badly? Was it tuned, and does it match the reported performance of Bollapragada et al.?
  • Were SGD with momentum and a standard schedule (e.g., cosine) considered?
1 comment

We sincerely thank you for your highly detailed assessment of the theoretical restrictions and empirical protocol. We acknowledge that the assumptions of our previous main convergence theorem were rather restrictive. We note that other reviewers also raised similar concerns and provided highly insightful suggestions. Guided by these suggestions, we have reconstructed the convergence theorems under milder assumptions and discussed the selection of key parameters. Furthermore, the experimental section has been thoroughly revised in accordance with your helpful suggestions. Changes made in the manuscript are marked in red. A detailed point-by-point response is provided below. We sincerely hope that these revisions meet your requirements.

  1. Comparison with PoNoS and ablation study. Thank you for this suggestion. We used the authors’ released implementation within the same training and evaluation framework, with the same line-search hyperparameters as SMBFGS (Table 4). Compared with PoNoS, SMBFGS achieves higher final mean test accuracy on five of the seven tasks.

    We have added an ablation study containing comparisons with two SMBFGS variants: one without resetting and one with a monotone line search. The ablations show that nonmonotone acceptance improves training loss and test accuracy on all seven tasks, while resetting consistently reduces backtracking.

    The PoNoS comparisons are presented in Section 5 and Appendix A.5 (Table 2; Figures 1–2 and 4–5). The ablation settings and results are detailed in Appendix A.4 (Figure 3 and Table 5).

  2. Computational cost and efficiency. Our ablation study reports backtracking counts per epoch and their totals over training (Figure 3 and Table 5). They directly quantify the line-search evaluation cost: ℓk\ell_k backtracks require ℓk+1\ell_k+1 loss-only trial evaluations, including the accepted trial.

    To account for the overall computational cost, we also report loss and test accuracy against cumulative runtime (Figures 2 and 5), thereby including the overhead of curvature construction and line search. SMBFGS achieves the highest mean test accuracy on four of the seven tasks. This demonstrates the favorable overall test performance of SMBFGS.

  3. Performance of PBQN-FO. We adopted the fixed parameter configuration from Bollapragada et al. (2018), as reported in Table 4, without additional task-specific tuning. Our network architectures and training protocols differ from those in the original study, so the reported results are not a direct reproduction of its benchmarks.

    We have expanded the discussion in Section 5.2 and Appendix A.5. In particular, variance-scaled initial steps and curvature-pair rejection may limit optimization progress, while batch-size growth and multi-pair operations introduce additional computational work. These provide possible explanations for the observed behavior. Our comparison therefore concerns PBQN-FO under the specified experimental settings.

  4. SGD with momentum and cosine scheduling. Yes. The revised experiments include SGDM with momentum 0.9 and cosine learning-rate decay over 200 epochs. Its settings are provided in Appendix A.3 (Table 4), and comparisons are reported in Section 5 and Appendix A.5.

    Compared with SGDM, SMBFGS achieves lower final mean training loss on six of the seven tasks and higher final mean test accuracy on five, with one accuracy tie. These results indicate that SMBFGS can achieve better overall performance compared with SGDM.

    Finally, we acknowledge that stochastic L-BFGS with stochastic Armijo search (Bollapragada et al.,2018) predates our work, as already discussed on manuscript page 3. However, that work is based on the monotone search, and the line search depends on a rigorous evaluation criterion, which is hard to calculate and also brings much computational burden. The contribution of our work is the nonmonotone acceptance mechanism with a memoryless direction, which is more computationally efficient and does not introduce excessive memory overhead. Indeed, it can be viewed as a crucial extension of stochastic nonmonotone line-search techniques.

    We sincerely hope that these revisions meet your requirements and that you are satisfied with the revised manuscript.

Comments on the paper

1 comment

Dear Editors and Reviewers,

We would like to express our sincere gratitude to you for your valuable comments and suggestions. We truly appreciate your efforts in helping us improve the manuscript. We have carefully considered all the feedback and made point-by-point revisions accordingly. All changes are marked in red in the revised manuscript. The main revisions and their locations are summarized below.

CategoryMain revisionLocation
TheoryClarified the relationship to SdLBFGS and PoNoS, distinguishing curvature construction and step-size selection.Section 2; Table 1
Distinguished the raw Polyak candidate, reset-adjusted initial trial, and accepted step size; established uniform step-size bounds and finite backtracking.Section 3.2; Appendix A.2, Lemmas A.1/A.3 and Proposition A.1
Derived explicit spectral bounds for the damped memoryless BFGS matrix and the resulting descent and direction-norm bounds.Appendix A.2, Lemma A.2
Clarified conditional unbiasedness and matrix measurability, and established sufficient conditions for relative gradient-noise control.Section 4.1 and Remark 4.1; Appendix A.2, Lemmas A.2/A.4
Reworked the linear convergence theorem and proof under explicit step-size and noise conditions, and clarified a nonempty admissible parameter regime.Section 4.2, Theorem 4.1; Appendix A.2
ExperimentsAdded PoNoS and SGDM with cosine scheduling, and updated comparisons of training loss and test accuracy.Section 5; Table 2; Appendix A.3, Table 4
Added ablations removing the reset mechanism or replacing the nonmonotone search with a monotone search, assessing their effects on performance and search effort.Appendix A.4; Figure 3 and Table 5
Expanded cumulative-runtime comparisons and reported backtracking statistics to assess computational cost alongside final solution quality.Section 5, Figure 2; Appendix A.4, Table 5; Appendix A.5, Figure 5
Clarified PBQN-FO’s original-paper hyperparameters, progressive batching, and computational microbatching, and discussed mechanisms that may contribute to its observed performance.Appendix A.3, Tables 3–4; Appendix A.5

All theorems have been carefully formulated, and the proofs have been derived step-by-step and rigorously verified. We have ensured that the proofs are presented in sufficient detail to guarantee a smooth reading experience for the readers.

All our efforts are dedicated to improving the manuscript to meet the high standards of ICLR, which is an excellent platform for sharing our work with the community. We sincerely hope that these revisions meet your requirements. We would like to take this opportunity to re-emphasize that our work is not merely a simple combination of existing methods, but a crucial extension of stochastic nonmonotone line-search techniques.

Should you have any further questions, please feel free to reach out; we will be more than happy to respond promptly. Thank you for your time and consideration!

Best regards,

Anonymous Authors

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

Related papers

Discussion (0)

Sign in to comment.