# Condition-number-aware restarted PAGE

- ID: 2960
- Canonical URL: https://synthcore.org/idea/2960/condition-number-aware-restarted-page
- API JSON: https://synthcore.org/api/idea/2960.json
- API Markdown: https://synthcore.org/api/idea/2960.md
- Verification status: unverified
- Source: [arXiv:2609.00045](https://arxiv.org/abs/2609.00045)
- Category: optimization
- Solves: speedup, stability
- ML areas: optimizer, training-dynamics, scheduler
- Math tags: optimization, stochastic-processes, dynamical-systems
- Ratings: usefulness 7/10; difficulty 5/10; novelty 5/10

## Idea description

Replace a fixed PAGE refresh schedule with a restart policy selected from the PL condition-number regime. For well-conditioned objectives, use frequent full-gradient refreshes and short inner phases; for ill-conditioned objectives, use the conventional condition-number-scaled PAGE phase length. The goal is lower component-gradient cost to a target loss while retaining PAGE's low-variance updates.

## Mathematical statement

Let F(x)=n^{-1}\sum_{i=1}^n f_i(x), where n is the number of component losses. Assume the global PL inequality \|
abla F(x)\|^2\ge 2\mu(F(x)-F^*) with \mu>0. Let L_{\rm ms} be the mean-squared smoothness constant and define \kappa_{\rm ms}=L_{\rm ms}/\mu; alternatively, under individual smoothness use \kappa_{\max}=L_{\max}/\mu, where \|
abla f_i(x)-
abla f_i(y)\|\le L_{\max}\|x-y\| for every component i. The paper proves the restarted PAGE complexity bounds O(n+n\log(\Delta/\varepsilon)/(1+\log(\sqrt n/\kappa_{\rm ms}))) for 1\le\kappa_{\rm ms}\le\sqrt n and O(n+\kappa_{\rm ms}\sqrt n\log(\Delta/\varepsilon)) for \kappa_{\rm ms}\ge\sqrt n, where \Delta=F(x_0)-F^* and \varepsilon is the target suboptimality. PAGE stores a reference estimator v_t and refreshes it exactly with probability p; otherwise it uses a component-gradient difference. The transferable result is the regime transition at \kappa=\sqrt n: using the high-condition-number schedule in the low-condition-number regime wastes oracle calls.

## Key formulas

- $$\operatorname{IFO}=O\!\left(n+\frac{n\log(\Delta/\varepsilon)}{1+\log(\sqrt n/\kappa_{\rm ms})}\right),\qquad 1\le\kappa_{\rm ms}\le\sqrt n,$$
- $$\operatorname{IFO}=O\!\left(n+\kappa_{\rm ms}\sqrt n\log(\Delta/\varepsilon)\right),\qquad \kappa_{\rm ms}\ge\sqrt n,$$
- $$v_t=\begin{cases}\nabla F(x_t),&\text{with probability }p,\\[2pt]\nabla f_{i_t}(x_t)-\nabla f_{i_t}(x_{t-1})+v_{t-1},&\text{with probability }1-p,\end{cases}$$
- $$x_{t+1}=x_t-\eta v_t.$$

## Implementation notes

Integrate this into an optimizer for a model trained on a finite dataset, treating each example or minibatch shard as a component function. Maintain x_prev and v_prev. At the start of each restart epoch compute the exact full-data gradient v=∇F(x); inside the epoch, either refresh exactly with probability p or sample a minibatch B and set v_t=v_{t-1}+|B|^{-1}Σ_{i∈B}[∇f_i(x_t)-∇f_i(x_{t-1})]. Then update x_{t+1}=x_t−ηv_t. Every K steps estimate the local PL parameter from recent checkpoints: μ_hat=median(||g_j||²/(2 max(F_j−F_best,δ))). Estimate mean-squared smoothness using random probes u_j and minibatch gradients G: L_hat_ms²=median(||G(x+u_j)−G(x)||²/||u_j||²). Set κ_hat=L_hat_ms/max(μ_hat,δ). If κ_hat≤√n, select a short restart phase T from a grid {1,2,4,...,√n}; if κ_hat>√n, select T from {√n,2√n,...,κ_hat√n}. Adjust p approximately as one full refresh per phase, while clipping η to a conservative smoothness-based bound such as 0.1/L_hat_ms. Use stop-gradient around all estimates so they do not alter model gradients. First test on a strongly convex quadratic with controlled κ, then CIFAR-10 ResNet-18 and a 50M-parameter Transformer. Compare AdamW, fixed-schedule PAGE, and adaptive PAGE at equal optimizer steps, component-gradient FLOPs, parameters, and memory. Pre-register: for κ<√n, adaptive PAGE must reduce calls to a fixed objective gap by at least 20% versus fixed PAGE; for κ>√n, its cost must be within 10% of fixed PAGE; and removing exact refreshes must increase measured estimator variance by at least 2x. Record loss-versus-component-calls, gradient variance, estimated κ, and selected T. Falsify the transfer if the low-κ advantage is absent on controlled quadratics or if adaptive scheduling increases high-κ cost by more than 10%.

## Disclaimer

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