Provable and Practical Online Learning Rate Adaptation with Hypergradient Descent — Scientific Code Review

Paper: Ya-Chi Chu, Wenzhi Gao, Yinyu Ye, Madeleine Udell · published paper · arXiv 2502.11229
Code: udellgroup/osgm-best-hypergrad · commit f848bca25910

This review ran executable checks that compare the released code against what the paper states. Issues come first, grouped by importance: major, then minor. Where the released materials are too incomplete to check a claim, the finding says so in its text; such gaps are reproducibility limitations, not demonstrated errors. Findings whose fix is a direct revision of the paper's TeX or the released code include a Prompt to fix panel with a ready-to-use LLM prompt.

Major Findings

R1 [major] — Paper/Code Algorithm Inconsistency

The released implementation of HDM-Best, the paper's main practical algorithm, does not run the algorithm printed in the paper (Algorithm 3). There are two inconsistencies:

1. Sign of the preconditioner hypergradient. Algorithm 3 prints the preconditioner hypergradient with a positive sign, while Equation (3) defines it with a negative sign. The code uses the negative sign. This is an internal error in the pseudocode; the code and Equation (3) agree.
2. Denominator of the hypergradient step. Algorithm 3 divides by \lVert \nabla f(x) \rVert^2 + (\tau/2)\lVert x - x_{\mathrm{prev}} \rVert^2, where \tau is an algorithm parameter. The code has no \tau at all: it divides by \lVert \nabla f(x) \rVert^2 + 10^{-12} until a curvature estimate is available, and by \lVert \nabla f(x) \rVert^2 + 0.25\,L_{\mathrm{est}}^2 \lVert x - x_{\mathrm{prev}} \rVert^2 afterward. Both experiment drivers run this two-phase rule, so the algorithm behind the paper's benchmark results is not the algorithm the paper specifies.

A smaller undisclosed detail: the code adds 1e-12 inside the AdaGrad normalization, which defines the update for coordinates whose accumulated gradient is still zero, a case Algorithm 3 leaves unspecified. Everything else matches, including the projections, the function-value null step, and the seven persistent length-n state vectors.

Suggested fix: Correct the sign in Algorithm 3, then either document the implemented two-phase denominator or restore the published \tau rule and rerun the benchmarks.

You are working on the paper "Provable and Practical Online Learning Rate
Adaptation with Hypergradient Descent" (arXiv 2502.11229) and its code release
(osgm-best-hypergrad). Fix the paper/code inconsistency in HDM-Best:

1. Sign: in the LaTeX source of Algorithm 3, the preconditioner hypergradient
   is printed with a positive sign, but Equation (3) defines it with a negative
   sign and the released optimizer uses the negative sign. Correct Algorithm 3
   so its sign matches Equation (3).

2. Denominator: Algorithm 3 divides the hypergradient by
   ||grad f(x)||^2 + (tau/2)*||x - x_prev||^2 with tau as an algorithm
   parameter, but the released optimizer implements a two-phase rule with no
   tau: ||grad f(x)||^2 + 1e-12 before a curvature estimate exists, and
   ||grad f(x)||^2 + 0.25*L_est^2*||x - x_prev||^2 afterward. Pick one
   contract and make both sides agree: either rewrite Algorithm 3 and its
   surrounding text to state the implemented two-phase rule, or change the
   optimizer to the printed tau rule and flag that all benchmark results must
   be regenerated.

3. Epsilon: document the 1e-12 stabilizer the code adds inside the AdaGrad
   normalization, which Algorithm 3 leaves unspecified for coordinates whose
   accumulated gradient is still zero.

Keep the paper's notation consistent and do not change any other algorithm.

R2 [major] — Invalid Benchmark Problem Construction

Both benchmark objectives (SVM and logistic regression) assume the two class labels are -1 and +1, but the data loader passes raw labels through without remapping or validating them. Five of the 33 datasets use other encodings: liver-disorders_scale, phishing, and svmguide1 use {0, 1}, and mushrooms and skin_nonskin use {1, 2}.

On those five datasets the two classes do not enter the objective with opposite signs, and the problem becomes degenerate: a point with every feature weight set to zero and only a bias term has a gradient of exactly zero. Such a point meets the solved criterion without learning any classifier, so the affected instances can be counted as trivially solved. This touches both tasks on all five datasets, that is, 10 of the 66 reported benchmark instances. The check inspected 31 of the 33 datasets; ijcnn1 and leu could not be examined from the available compressed files.

Suggested fix: Remap each label domain to {-1, +1} right after loading, validate that exactly two classes are present, then rerun all benchmark instances and republish the totals and curves.

In the code release for arXiv 2502.11229 (osgm-best-hypergrad), the SVM and
logistic-regression objectives assume labels in {-1, +1}, but the dataset
loader passes raw LIBSVM labels through unchanged. liver-disorders_scale,
phishing, and svmguide1 use {0, 1}; mushrooms and skin_nonskin use {1, 2}.

Fix the loader (the dataset/problem definitions in def_problems.py):
immediately after loading a dataset, detect the two distinct label values,
map them deterministically to -1 and +1, and raise an error if the dataset
does not contain exactly two classes. Add a regression test that loads each
affected dataset and asserts the resulting labels are exactly {-1.0, +1.0}.
Note in the experiment README that all 33 SVM and 33 logistic-regression
instances must be rerun after this change.

R3 [major] — Inconsistent Gradient-Oracle Accounting

The paper gives every method the same budget of 1000 gradient evaluations, and a method counts as solved only if it reaches the stopping threshold within that budget. The released implementations count gradient calls differently from method to method:

• AGD-CVX and AGD-SCVX evaluate the gradient twice per iteration but advance their counter once.
• BFGS and the four L-BFGS variants report SciPy's njev, which excludes the gradient evaluations made in the convergence callback.
• HDM-Best makes one gradient evaluation before its counted loop begins.

A probe with a five-call cap showed the effect directly: seven methods reported 5 calls after actually making 10, and 8 of the 12 methods exceeded the cap. The reported solved counts and convergence curves therefore compare methods under unequal budgets.

Suggested fix: Route every gradient evaluation through one budget-enforcing counter (including look-ahead, callback, initial, and line-search calls), stop at 1000 actual calls, and rerun the benchmark.

In the code release for arXiv 2502.11229 (osgm-best-hypergrad), gradient-oracle
calls are counted inconsistently across the 12 benchmark methods: AGD-CVX and
AGD-SCVX evaluate the gradient twice per counted iteration; BFGS and the four
L-BFGS variants report SciPy's njev, which misses gradient evaluations made in
the convergence callback; HDM-Best makes one gradient evaluation before its
counted loop begins.

Implement a single counting wrapper around grad_f that every method must use,
so that every evaluation (look-ahead, callback, initial, and line-search calls
included) increments one shared counter. Enforce the 1000-call budget inside
the wrapper by stopping the run when the counter reaches 1000, and report the
wrapper's count as the method's oracle usage. Add a test that runs each of the
12 methods under a small cap and asserts the reported count equals the true
number of grad_f invocations. Flag that all benchmark results must be
regenerated after this change.

R4 [major] — Paper/Code Evaluation Protocol Inconsistency

The paper and the code disagree on the two rules that produce the headline results: which runs count as solved, and which reference value the function-gap curves use.

• Solved rule. The paper counts a run as solved when it reaches \lVert \nabla f \rVert_\infty \le 10^{-4} within at most 1000 gradient calls. The code instead sets its success flag from a single condition, reported gradient evaluations < 999, and never checks the gradient norm. A run can therefore be marked solved while its final gradient norm is above the threshold, and a run that reaches the threshold at call 999 or 1000 is marked unsolved even though it satisfies the paper's rule.
• Reference value. The paper says the SVM function-gap reference comes from running BFGS to the same gradient threshold. The code runs SciPy L-BFGS at tolerance 1e-8, discards that result, and instead uses the smallest objective value among the compared runs minus 1e-10. The plotted gaps are measured against a best-of-run baseline, not the stated BFGS reference. The logistic driver builds its reference the same way, and the paper never states where its logistic references come from.

Suggested fix: Compute solved status from the terminal gradient norm and an independently counted <= 1000 calls, keep the reference value the paper describes (or revise the paper), then rerun and republish the solved counts and curves.

In the code release for arXiv 2502.11229 (osgm-best-hypergrad), the experiment
drivers decide success and reference values differently from the paper. Fix
both:

1. Success flag: the drivers set success from
   reported_gradient_evaluations < 999 and never check the gradient norm.
   Change this to the paper's rule: a run is solved if and only if its
   terminal ||grad f||_inf <= 1e-4 and its independently counted gradient
   calls are <= 1000 (inclusive).

2. Reference value: the SVM driver runs SciPy L-BFGS at tolerance 1e-8 and
   maxiter 2000, discards that result, and instead uses the smallest objective
   among the compared runs minus 1e-10. Change it to retain the BFGS reference
   computed at the paper's stated threshold and use that value for the
   function-gap curves. Apply the same treatment to the logistic driver, or
   document its reference construction in the paper.

Flag that solved counts and curves must be regenerated after this change.

R5 [major] — Missing Reproduction Artifacts

The release cannot regenerate the paper's central benchmark:

• Only 3 of the 33 benchmark datasets are bundled (a1a, a2a, a3a).
• No raw trajectories or per-instance result rows sit behind the tables and figures, only rendered curve PDFs.
• HDM-AGD, the Nesterov-momentum variant, is not implemented.
• None of the four additional baselines from Appendix E.5 (GD-LS, AGD-CVX-LS, ADPGD, ADPGDACC) is implemented.

The 33-dataset solved counts, curves, and rankings therefore cannot be reproduced independently. This is a reproducibility gap, not evidence that the published numbers are wrong.

Suggested fix: Release all inputs (or retrieval manifests), raw per-instance results, the missing implementations, and scripts that regenerate every table and figure.

Minor Findings

R6 [minor] — Undisclosed Baseline Configuration

The paper states that BFGS and L-BFGS use SciPy's default settings, but the released L-BFGS sets ftol=1e-25, which effectively disables SciPy's default function-value stopping test. Beyond that, hyperparameter tuning runs the full grid for every problem instance and reports only the selected run's cost; the paper describes neither this selection rule nor how tuning cost is charged. Nothing in the evidence shows these choices changed rankings or solved counts, so the finding stays minor.

Suggested fix: Remove the nondefault ftol or document it, and state the per-instance selection rule and its cost accounting.

The paper for arXiv 2502.11229 states that BFGS and L-BFGS use SciPy's default
settings, but algorithms/lbfgs.py in the released code (osgm-best-hypergrad)
sets ftol=1e-25, which disables SciPy's default function-value stopping test.

Either delete the ftol override so the code matches the paper, or keep it and
amend the paper's algorithm-configuration paragraph to disclose ftol=1e-25.
Also add one sentence to the paper describing the tuning protocol the code
implements in HyperGrid: the full grid is run for every problem instance, the
configuration with the fewest reported iterations is selected, and only the
selected run's cost is reported. If the ftol change alters solver behavior,
flag that the four L-BFGS memory settings must be rerun on all benchmark
instances.

R7 [minor] — Missing Ablation Artifacts

Figure 6 attributes separate speedups to HDM-Best's null step and to its AdaGrad component. The release cannot support that comparison: it contains only the full method, with no switch to disable the null step, no switch to replace AdaGrad with the constant-stepsize update, no raw ablation curves, and only two of the four datasets used in the figure (a2a and a3a; w2a and w3a are absent). The ablation claim is unverifiable from the release; nothing here shows it is wrong.

Suggested fix: Release the ablation runner, the component switches, all four inputs, and the raw curves behind Figure 6.

R8 [minor] — Claims Without Checks

The two theoretical algorithms, vanilla HDM (Algorithm 1) and HDM with adaptive heavy-ball momentum (Algorithm 2), have no standalone implementation in the repository, and this review ran no executable check on either. The review offers no evidence for or against them. The released optimizer implements only their practical descendant, HDM-Best, which R1 covers.

Suggested fix: Extend the review with checks that compare Algorithms 1 and 2 against controlled implementations.