Breaking Precision Walls in First-, Second-, and Zeroth-Order Optimizers: One Constant, Set in Advance
In the authors' words
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 .
Appeared: Tuesday, November 10. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 23 pages, 6 figures, 9 tables