- 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
- 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.
- 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
- 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
-
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?
-
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?
-
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?
-
Can you establish the direction bounds for the particular damped memoryless update and clarify the role of the covariance assumption? Since is determined before sampling , conditional unbiasedness gives . Can this structure support a more direct analysis or weaker assumptions?
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+=20 and ηmin=0.05≤ηk=0.1, replacing the incorrect lower bound 0.5. These parameters give ω+=2 and ϑ=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∗], where q=1−2μh−ϑ/(Lh+)∈[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≤R and rk+ℓk≤J by induction. It consequently establishes ηk,0≥uδR and ηk≥ηmin:=maxuδJ,minuδR,δη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, choose 0<ηmax<min1/(2cpLmax),,2(1−c)/(Lmaxh+),,2/[(1+τ)Lh+]. Then J=R=0 and ηmin=ηmax. Writing ω=Lh+ηmax, we have ω−=ω+=ω and 0<ω<2/(1+τ). The definition of ϑ therefore reduces to ϑ=ϕ(ω)−τω2/2=ω[1−(1+τ)ω/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+I for SMBFGS's damped memoryless BFGS update with identity initialization. Consequently, ∣dk∣≤h+∣gk∣, −gk⊤dk≥h−∣gk∣2, and ∣dk∣2≤h+(−gk⊤dk). 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 Hk is Fk-measurable. Conditional unbiasedness therefore gives Ek[dk]=−Hk∇F(xk) and hence ∇F(xk)⊤Ek[dk]≤−h−∣∇F(xk)∣2. We have removed the previous direction-gradient covariance assumption. The revised proof directly controls the gradient error in the metric induced by Hk, with Lemma A.4 providing a sufficient relative-noise bound under the strong growth condition.