# Division-free adaptive learning-rate ladder

- ID: 1562
- Canonical URL: https://synthcore.org/idea/1562/division-free-adaptive-learning-rate-ladder
- API JSON: https://synthcore.org/api/idea/1562.json
- API Markdown: https://synthcore.org/api/idea/1562.md
- Verification status: unverified
- Source: [arXiv:2607.28902](https://arxiv.org/abs/2607.28902)
- Category: optimization
- Solves: stability, sample-efficiency
- ML areas: optimizer, training, scheduler
- Math tags: optimization, stochastic-processes, computation
- Ratings: usefulness 5/10; difficulty 3/10; novelty 4/10

## Idea description

Convert unknown optimizer scales into a small parallel ladder of learning rates and training horizons whose values differ only by powers of two. Each worker runs stochastic gradient descent for a geometrically increasing budget, allowing one worker to land near both the correct step-size scale and the useful horizon without explicitly estimating smoothness or gradient variance.

## Mathematical statement

The paper emphasizes arithmetically simple stochastic-gradient methods in which every division is of the form x/2^t, while retaining adaptivity to unknown Lipschitz smoothness and stochastic-gradient characteristics such as variance and noise level. The transferable objects are integer exponents r and q, the learning-rate representation \eta=\eta_0/2^r=2^{-r}\eta_0, and the budget representation T=T_0 2^q. The stochastic-gradient update is x_{t+1}=x_t-\eta g_t, where x_t is the parameter vector, g_t is a stochastic gradient estimate, and \eta is selected from the power-of-two ladder. The scheduling guarantee supplies a worker whose stage budget covers the unknown sufficient horizon T while cumulative work is less than \alpha_pT. This extracted material does not include the paper's full nonconvex convergence theorem, so the implementation should treat the convergence benefit as an empirical hypothesis rather than claim a new formal guarantee.

## Key formulas

- $$x_{t+1}=x_t-\eta g_t,\qquad \eta=\frac{\eta_0}{2^r}=2^{-r}\eta_0,\quad r\in\mathbb{Z}_{\ge 0},$$
- $$T_{j,i}=T_0\,2^{q(j,i)},\quad q(j,i)\in\mathbb{Z}_{\ge 0},\qquad T^*_{j,i}=\sum_{t=0}^{i}T_{j,t},$$
- $$T\le T_{j,i}\le T^*_{j,i}<\left(1+\frac{1}{p}\right)(p+1)^{1/p}T.$$

## Implementation notes

(1) Integration point: modify optimizer hyperparameter initialization and the outer training scheduler, not the neural-network layers. For each worker, use SGD or momentum SGD with a learning rate selected from a power-of-two ladder eta0, eta0/2, eta0/4, and so on. Optionally use a second power-of-two ladder for gradient-clipping thresholds. (2) Pseudocode: choose eta0 from a deliberately aggressive upper bound and exponents r=0,...,R. For each worker j and stage i, assign `(r[j,i],q[j,i])` from a rotating grid; set `eta=eta0*(2**(-r))`, `budget=T0*(2**q)`, initialize the model from the same checkpoint, and execute `for t in range(budget): g=grad(loss(model,batch)); model=model-eta*g`. At the stage boundary compute an exponential moving average of training loss and a fixed validation loss. Keep the best checkpoint and allocate the next worker to the uncovered `(r,q)` pair. Use integer exponent changes rather than adaptive floating-point divisions. (3) Compute every power of two and cumulative work exactly. Estimate the unknown useful horizon by the first budget crossing a fixed validation-loss target, and estimate the useful learning-rate exponent by the best validation loss among workers. Record gradient norms, update norms, loss variance, divergence events, and validation loss to test whether the ladder is adapting to stochastic noise rather than merely benefiting from extra trials. (4) First cheap experiment: use a 4-layer MLP and a small CNN on MNIST or CIFAR-10, with p=4 workers, R=5 learning-rate exponents, and budgets from 256 to 8192 updates. Compare against SGD with one tuned learning rate, AdamW, and ordinary logarithmic random search under the same total update budget. The desired signal is lower median updates to reach 90% accuracy, fewer divergent runs at high initial learning rates, and performance close to the oracle learning rate without any smoothness or variance estimate.

## Disclaimer

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