The Precision Complexity of Dithered Adam

Low-precision Adam can reduce the memory used by optimizer states. We study the cumulative precision needed to reach a target accuracy when write widths can change over time and respond to observed numerical errors. We first consider bias-corrected Adam on the scalar quadratic objective, with fresh uniform additive dither in the parameter, gradient, and two moment writes. We also extend the complexity bounds to scalar strongly convex smooth objectives and higher-dimensional separable objectives. A causal policy chooses each width using the revealed history, and we measure cost by the sum of all widths used during the run. Under an explicit step-size condition, we establish matching lower and upper bounds of order $T+{\log }^2(1/ϵ)$ on the expected cumulative precision required to achieve $\mathbb{E}[x_T^2]\le ϵ$. These bounds hold for every sufficiently small $ϵ$ and every deterministic horizon $T$ above a threshold of order $\log (1/ϵ)$. The lower bound applies to all causal policies using the full error history, while a deterministic schedule attains the upper bound by keeping second-moment precision fixed and raising the other three widths near the end of the run. For the same target accuracy and horizon, keeping all four write widths fixed throughout the run gives a minimum cost of $\Theta (T\log (1/ϵ))$. Thus, for $T\ge {\log }^2(1/ϵ)$, temporal precision allocation saves a factor of order $\log (1/ϵ)$. If the deterministic horizon can also be chosen, a stronger step-size condition gives an optimal cost of $\Theta ({\log }^2(1/ϵ))$. Without this additional condition, suitable parameters and initialization can permit finite-time cancellation, reducing the cost to $\Theta (\log (1/ϵ))$.