Breaking Precision Walls in First-, Second-, and Zeroth-Order Optimizers: One Constant, Set in Advance
Organizations: A2O Labs
Abstract
Under power-law signal decay across directions, an optimizer can fit strong directions and miss weak ones while average loss hides it. A precision wall measures the steepest decay where the weakest direction recovers within 5% in a fixed budget. On low-rank matrix sensing and quadratics one constant sets the wall: once it dominates the denominator, Adam or grafted Shampoo is momentum descent at step , setting the wall; in Shampoo, matching grafting's constant to damping restores the wall after three hypotheses failed. In zeroth-order Adam, acts against from a mean-square spectral model; below error hits a noise floor. Set from true curvature or spectrum on new shapes, the rule raised the wall above the same-step default by a forecast amount: on two sensing shapes by (Adam) and (grafted Shampoo), and on two Hadamard-rotated quadratics by (zeroth-order Adam, longer budget), rising on all seeds; fixed-step momentum at that step reaches those walls. A cosine-scheduled default (small constant giving weak modes large steps) is higher on one sensing shape, matched on new seeds of the other, and lower with the rule's constant. A default step retuned per budget catches up on rotated quadratics and population logistic regression, fails at 1 query/step on two diagonal quadratics (catching up at 16), and exceeds the rule on digits logistic regression (full-batch and minibatches, where gradient noise sets the default walls). On logistic regression the rule did not raise the first-order wall: same-step default Adam was higher (its wall on 4 new shapes at the forecast stability limit), while in zeroth order on the population loss setting raised the wall by .
Figures & tables
| Walls | Number | Below | rms | Largest |
|---|---|---|---|---|
| Ungrafted Shampoo, | ||||
| Adam at , | ||||
| Grafted, ladder of | ||||
| Ungrafted, other step sizes | ||||
| Ungrafted, long budgets | ||||
| Ungrafted, measurement ratios |
| Reading | Forecast | Measured | Band |
|---|---|---|---|
| Change of the wall from to , minus at the larger step | ; on three problems | ||
| Walls within of the forecast, thresholds and | – | of | ; none beyond |
| Conditions with ; collapses with | ; | ; of | ; of |
| Gain at from scaling , against ; against the default setting | ; | ; | second ; both on three problems |
| Method | Problem | Forecast | Measured | Default | Lift |
|---|---|---|---|---|---|
| Adam | |||||
| Adam | |||||
| Zeroth-order Adam | lattice, | ||||
| Zeroth-order Adam | power law, |
| Axis | First order | Zeroth order |
|---|---|---|
| Seeds, shapes or spectra, budgets, thresholds | yes | yes |
| Longer budgets | no | yes |
| Step size, default constant | yes | yes |
| Step size, rule’s/bound’s constant | no | yes |
| Multiple of | – | yes |
| Constant without true curvature/spectrum; fix, or non-quadratic | yes; – | yes; no |
| Cell | ( ) | Model | gap | ( , model) |
|---|---|---|---|---|
| ( ) | ||||
| ( ) | ||||
| ( ) | ||||
| ( ) | ( ) |
| Study | Problem | Forecast | Rule | Default | Lift |
|---|---|---|---|---|---|
| Matrix sensing, , Adam ( , ) | / | / | / | / | / |
| Matrix sensing, cosine ( ) | / | / | / | / | / |
| Diagonal quadratic, , ZO Adam ( ) | / | / | / | / | / |
| Diagonal quadratic, , vs. ( ; ) | / | / | / | / | / ; / |
| Matrix sensing, , ZO Adam ( , ) | |||||
| Matrix sensing, , ZO Adam ( , vs. ) | – |
| Quantity | ||||
|---|---|---|---|---|
| / model ( / ) | / | / | / | / |
| default (forecast) | ( ) | ( ) | ( ) | ( ) |
| rule (forecast) | ( ) | ( ) | ( ) | ( ) |
| Rule def. (fc.) | ( ) | ( ) | ( ) | ( ) |
| default (forecast) | ( ) | ( ) | ( ) | ( ) |
| default (forecast) | ( ) | ( ) | ( ) | ( ) |
| Regime | Condition | Sections | Consequence for or |
|---|---|---|---|
| Fixed-step oscillation floor | Small default leaves strong modes above | 4 , 5 , 7 , 8 | (or ) keeps modes below , raising the wall as forecast. |
| Cosine time-integrated step | drops modes below late; small enlarges | 7 , 8 | Cosine default beats rule on , matches on ; rule’s halves , lowering the wall. |
| Full-batch stability-limit saturation | Default sits at or larger is stable | 9 | The -to- margin cannot lift same-step default on logistic regression; is higher on digits. |
| Minibatch and zeroth-order floors | Noise sets ; zeroth-order variance ( ) and cubic ( ) floors | 6 , 7 , 9 | Noise buries under and stalls ; in zeroth order removes the variance floor (leaving sensing’s floor), while retuned catches up on rotated quadratics, population logistic, and . |
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
| Study | Walls | Change tested |
|---|---|---|
| Shampoo to SOAP | Shampoo , Eigen-Adafactor , SOAP ; Adam on the unrotated problem | along the path |
| Truncating SOAP’s left matrix | Block size 16: ; 8: ; 4: ; 2: ; 1: | from size 16 to size 1 |
| Evolution Strategies | 4 pairs: ; 128 pairs under the schedule: ; 128 pairs at the 4-pair step size: | Measured over predicted gain: ; at fixed step size, |
Adaptive Gradient Methods
Adaptive Gradient Methods adjust updates using gradient history, curvature, or noise estimates to improve optimization across diverse problems.
See all 177 papers