# Gap-conditioned accelerated optimizer

- ID: 1814
- Canonical URL: https://synthcore.org/idea/1814/gap-conditioned-accelerated-optimizer
- API JSON: https://synthcore.org/api/idea/1814.json
- API Markdown: https://synthcore.org/api/idea/1814.md
- Verification status: unverified
- Source: [arXiv:2608.04884](https://arxiv.org/abs/2608.04884)
- Category: optimization
- Solves: speedup, stability
- ML areas: optimizer, fine-tuning, training-dynamics
- Math tags: optimization, convex-analysis, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 5/10

## Idea description

Replace a fixed global learning-rate estimate in an accelerated optimizer with a curvature envelope that depends on the current estimated optimality gap. Use phase restarts and a descent backtracking test so that the method remains safe when the gap or \(H_1\) estimate is inaccurate. The expected benefit is faster progress on objectives whose curvature is large early in training but decreases substantially near a good solution.

## Mathematical statement

The paper's defining \((H_0,H_1)\)-smoothness condition is \(\|\nabla^2 f(x)\|\le H_0+H_1(f(x)-f^*)\), where \(f\) is a convex objective, \(f^*\) is its minimum value, \(H_0\ge0\) is the residual curvature near the optimum, and \(H_1\ge0\) controls how curvature grows with suboptimality. Thus the local smoothness envelope is \(L(x)=H_0+H_1g(x)\), with gap \(g(x)=f(x)-f^*\). Since \(f^*\) is unavailable in a neural-network run, use a lower-bound or best-value proxy \(\hat g_t=\max(f(z_t)-f_{\mathrm{lb}},g_{\min})\), where \(z_t\) is the current phase anchor, \(f_{\mathrm{lb}}\) is a maintained lower bound, and \(g_{\min}>0\) is a numerical floor. The adapted step is \(\eta_t=1/\hat L_t\), \(\hat L_t=H_0+H_1\hat g_t\). A convex accelerated phase can use \(a_{k+1}=(1+\sqrt{1+4a_k^2})/2\), \(\beta_k=(a_k-1)/a_{k+1}\), \(y_k=x_k+\beta_k(x_k-x_{k-1})\), and \(x_{k+1}=y_k-\hat L_k^{-1}\nabla f(y_k)\). The paper's headline full-gradient complexity is \(\widetilde O(\sqrt{H_0\widetilde R^2/\varepsilon}+\sqrt{H_1\widetilde R^2}\log(F_0/\varepsilon))\), where \(\widetilde R\) is an effective initial distance, \(F_0\) is the initial gap scale, and \(\varepsilon\) is the target accuracy; this motivates restarting as the estimated gap enters successive smaller phases.

## Key formulas

- $$\left\lVert\nabla^{2}f(x)\right\rVert\leq H_{0}+H_{1}\bigl(f(x)-f^{*}\bigr),\qquad H_{0},H_{1}\geq 0.$$
- $$\hat g_t=\max\{f(z_t)-f_{\mathrm{lb}},g_{\min}\},\qquad \hat L_t=H_0+H_1\hat g_t,\qquad \eta_t=\frac{1}{\hat L_t}.$$
- $$a_{k+1}=\frac{1+\sqrt{1+4a_k^2}}{2},\qquad \beta_k=\frac{a_k-1}{a_{k+1}},\qquad y_k=x_k+\beta_k(x_k-x_{k-1}),\qquad x_{k+1}=y_k-\frac{\nabla f(y_k)}{\hat L_k}.$$
- $$\widetilde O\!\left(\sqrt{\frac{H_0\widetilde R^2}{\varepsilon}}+\sqrt{H_1\widetilde R^2}\log\frac{F_0}{\varepsilon}\right).$$

## Implementation notes

Integrate this as an optimizer for a parameter block whose loss is approximately convex: first the final classifier of a frozen transformer, then LoRA matrices or an embedding table, and only later the complete network. Maintain parameter vectors x_prev and x, a phase anchor z, the best observed objective, and a scalar curvature estimate. At every accelerated step compute y = x + beta*(x-x_prev), evaluate loss f_y and gradient g_y, form the estimated gap ghat = max(f_y - f_lb, g_min), and set Lhat = H0 + H1*ghat. Take x_trial = y - g_y/Lhat. Check the sufficient-decrease safeguard f(x_trial) <= f_y - c*||g_y||^2/Lhat with c between 0.25 and 0.5. If it fails, multiply Lhat by 2 and retry; if it succeeds for several consecutive steps, optionally divide Lhat by 1.2. Use a standard accelerated coefficient beta from the displayed a_k recursion, but restart the phase by setting x_prev = x whenever the objective increases, the gradient-direction inner product is positive, or the estimated gap falls below half its phase-start value. Estimate H0 and H1 from sampled Hessian-vector products: fit a nonnegative affine model ||H v|| approximately <= H0 + H1*(f-f_lb) using ridge regression over recent iterates, while retaining backtracking as the safety mechanism. The mathematics supplies the gap-dependent envelope and phase logic; H0, H1, and f_lb are empirical estimates. First test on logistic regression and a frozen-encoder linear head, comparing AdamW, fixed-L FISTA, and the proposed method at equal gradient evaluations. Measure loss versus evaluations, number of backtracking retries, and stability under a tenfold change in initialization scale. A useful signal is faster loss reduction than fixed-L acceleration with no increase in failed or exploding steps.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.