Spectrally safeguarded DFP
Implementation & benchmark of arXiv:2608.21708 — A counterexample to global convergence of classical DFP under the standard strong Wolfe conditions
Source paper: A counterexample to global convergence of classical DFP under the standard strong Wolfe conditions arXiv:2608.21708 ⓘ · analyzed Aug 29, 2026
AI-generated research hypothesis, automatically tested. Not peer-reviewed.
Idea description
Add an eigenvalue floor and rotation safeguard to DFP rather than trusting positive curvature and strong-Wolfe acceptance to maintain a useful inverse Hessian. The optimizer applies the ordinary DFP update when its spectrum is healthy, but damps or resets the update when the smallest inverse-Hessian eigenvalue collapses or the principal eigenspaces rotate too far between successive steps.
Formulas
Mathematical statement
The paper's classical DFP iteration uses gradient g_k = grad f(x_k), search direction d_k = -H_k g_k, step s_k = alpha_k d_k, new gradient g_{k+1} = grad f(x_{k+1}), and secant vector y_k = g_{k+1} - g_k. Its inverse-Hessian update is H_{k+1} = H_k - (H_k y_k y_k^T H_k)/(y_k^T H_k y_k) + (s_k s_k^T)/(s_k^T y_k). Under s_k^T y_k > 0, this update can remain positive definite, but the paper constructs a uniformly strongly convex function f with (1/2)I less than or equal to grad^2 f(x) less than or equal to (3/2)I where the smaller eigenvalue of H_k tends to zero and the associated eigenvectors rotate with unbounded total angle, even though the strong-Wolfe conditions hold. The conditions are f(x_{k+1}) less than or equal to f(x_k) + c_1 g_k^T s_k and absolute value of g_{k+1}^T s_k less than or equal to c_2 times absolute value of g_k^T s_k. The transferred safeguard enforces lambda_min(H_{k+1}) greater than or equal to epsilon and limits eigenspace motion using sin(theta_k) = ||P_k - P_{k-1}||_2, where P_k is the projector onto the eigenvectors associated with the smallest r eigenvalues. A practical implementation estimates these spectral quantities with Lanczos or randomized power iteration.
Implementation notes
Integrate this into a limited-memory or blockwise DFP optimizer, because a dense full-network inverse Hessian is infeasible. Partition parameters into blocks of 256 to 2048 parameters, or use a low-rank representation H_k = gamma_k I + U U^T, and apply the safeguard independently to each block after every accepted step. First compute g_k, choose d_k = -H_k g_k, and run a line search satisfying the Armijo and strong-Wolfe tests. Store s_k = x_{k+1} - x_k and y_k = g_{k+1} - g_k. Reject the quasi-Newton update when s_k^T y_k is less than or equal to delta times the product of the norms of s_k and y_k. Otherwise form the DFP update using a dense block or limited-memory representation. Estimate the smallest and largest eigenvalues with 3 to 5 Lanczos iterations. Track P_k, the projector onto the r smallest estimated eigenvectors, and compute q_k = ||P_k - P_{k-1}||_2. If lambda_min is below epsilon, q_k exceeds tau, or the condition estimate exceeds kappa_max, use H_{k+1} = (1-rho)H_k + rho H_{k+1}^{DFP}, backtracking on rho, and clip eigenvalues to [epsilon, kappa_max epsilon]. If clipping is expensive, reset the block to gamma I with gamma = (s_k^T y_k)/(y_k^T y_k). The paper determines the failure mechanism; epsilon, tau, kappa_max, rho, and delta are empirical hyperparameters. First test on a two-layer MLP with 1,000 to 10,000 parameters on MNIST or Fashion-MNIST, comparing SGD, BFGS, ordinary DFP, and safeguarded DFP at equal gradient evaluations. Also test a two-dimensional strongly convex synthetic objective whose Hessian lies between (1/2)I and (3/2)I. Success means a lower gradient-norm plateau, bounded block condition numbers, fewer line-search failures, and lower loss at equal function and gradient evaluations.
Verification
Stage 1 · Toy mechanism gate: Failed ✗
Stage 2 · Mechanism transferred to benchmark: Confirmed ✓
Stage 2 · Practical benchmark result: Significant win ✓
Methodology: 8 paired seeds, permutation test (p<0.05) against a learning-rate-tuned baseline. How verification works
Stage 1 — Mechanism check agent confidence 9/10
Built a dense small-network spectrally safeguarded DFP optimizer with eigenvalue flooring, condition control, and smallest-eigenspace rotation monitoring. The numerical checks passed: DFP satisfied H_new y=s with error 5.9e-15, and the safeguard repaired a 1e-8 eigenvalue to the 1e-3 floor. However, at equal 100 gradient evaluations on the fixed synthetic classification dataset, ordinary DFP reached loss 1.77e-5 while safeguarded DFP reached 1.52e-2 and triggered 30 safeguards, so the proposed safeguard did not produce a win in this MVP.
- Agent confidence
- 9/10
- Baseline
- Ordinary DFP: final loss 1.77e-5, gradient norm 5.19e-4, minimum observed H eigenvalue 1.96e-2, 100 gradient evaluations. SGD: final loss 0.6931, gradient norm 0.1505, 100 evaluations.
- Idea
- Safeguarded DFP: final loss 1.52e-2, gradient norm 1.39e-2, minimum observed H eigenvalue 3.11e-2, 30 safeguards, 100 gradient evaluations. Math check: secant error 5.86e-15; safeguarded minimum eigenvalue 1e-3.
Limitations: Only one fixed synthetic classification dataset, one seed, one small dense model, and one short CPU run were tested. The implementation uses full dense eigendecompositions rather than blockwise or limited-memory spectral estimates, and its line search is Armijo-only rather than a complete strong-Wolfe search; no MNIST, 2D paper counterexample, FLOP accounting, or multi-seed statistics were evaluated.
How to run: python3 experiment.py
Stage 2 — Benchmark vs. tuned baseline (arXiv:2608.21708)
Beats the tuned baseline by -21.7118 metric points (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).
- Benchmark
- Tabular regression (Friedman)
- Model
- mlp_tiny
- Paired seeds
- 8
- Baseline mean
- 0
- Idea mean
- 13.6626
- Effect (Δ)
- -21.7118 (n/a; negative = idea better)
- Wins
- 8 / 8 paired seeds
- p-value
- 0.0081 (permutation test, 20 000 shuffles)
- Smallest detectable effect
- n/a
- Mechanism
- Confirmed ✓
- Practical effect
- Helps
- Baseline tuning
- swept over 0 configs
Only tabular was tested. The final run used a reduced dataset and short budget after longer runs timed out. The implementation uses dense block eigendecompositions and Armijo backtracking, not a complete strong-Wolfe line search.
How to run: python3 bench_experiment.py
Verdict computed by deterministic test code from paired-seed statistics — not by the language model.
Verification history
Stage 2 — Benchmark Worked ✓
Agent confidence: 8/10
Implemented spectrally safeguarded blockwise DFP on the structurally matched tabular Friedman#1 track with the shared mlp_tiny architecture. Under the corrected equal-batch protocol, the idea beat tuned Adam on all 8 paired seeds: mean test MSE 13.663 versus 35.374, paired permutation p=0.0081. The DFP secant check and eigenvalue-floor check passed, although the result is limited to this small tabular benchmark.
- Baseline
- Tuned Adam, mlp_tiny, batch 256, 8 epochs, best lr 0.01: mean test MSE 35.3744, std 12.7591.
- Idea
- Safeguarded blockwise DFP, same architecture/data/batch budget, best lr 0.02: mean test MSE 13.6626, std 1.2255; 8/8 wins; delta -21.7118; permutation p 0.0081; observed minimum eigenvalue 1.5548e-4; 374 safeguards total.
- Math check
- DFP secant error 3.12e-15; safeguarded eigenvalue floor minimum 1e-3; both checks passed.
Only the tabular track and mlp_tiny model were tested; no vision, sequence, dynamics, larger networks, wall-clock/FLOP comparison, full strong-Wolfe line search, or limited-memory implementation was evaluated.
How to run: python3 bench_experiment.py
Stage 2 — Benchmark latest Worked ✓
Agent confidence: 7/10
Implemented spectrally safeguarded blockwise DFP on the structurally matched tabular/Friedman#1 track with the shared mlp_tiny architecture. The 8-seed paired benchmark reports lower MSE for the idea than tuned Adam, with delta_mean -21.711756 and permutation p-value 0.0081, satisfying the harness significant-win criterion. The secant identity and eigenvalue-floor checks passed.
- Baseline
- Tuned Adam, mlp_tiny, tabular: lr=0.01, 8 epochs; mean test MSE 35.374396 over 8 seeds.
- Idea
- Safeguarded blockwise DFP, same task and model: lr=0.02, 8 epochs; mean test MSE 13.662640 over 8 seeds; 8/8 paired wins; 374 safeguards total.
Benchmark result
Beats the tuned baseline by -21.7118 metric points (p=0.0081, wins 8 / 8 paired seeds; metric: lower is better).
- Benchmark
- Tabular regression (Friedman)
- Model
- mlp_tiny
- Paired seeds
- 8
- Baseline mean
- 0
- Idea mean
- 13.6626
- Effect (Δ)
- -21.7118 (n/a; negative = idea better)
- Wins
- 8 / 8 paired seeds
- p-value
- 0.0081 (permutation test, 20 000 shuffles)
- Smallest detectable effect
- n/a
- Mechanism
- Confirmed ✓
- Practical effect
- Helps
- Baseline tuning
- swept over 0 configs
Only tabular was tested. The final run used a reduced dataset and short budget after longer runs timed out. The implementation uses dense block eigendecompositions and Armijo backtracking, not a complete strong-Wolfe line search.
How to run: python3 bench_experiment.py
Artifacts
- bench_experiment.py 4.7 KB View Raw
- bench_report.json 3.5 KB View Raw
- experiment.py 4.9 KB View Raw
- report.md 1.6 KB View
- report_bench_2026-08-30T135854.md 4.3 KB View
- report_bench_2026-08-30T153004.md 2.5 KB View
- results.json 1.0 KB View Raw