MicroAdam (Sparse-Gradient Adaptive Optimization with Quantized Error Feedback)

At each step t, MicroAdam dequantizes the 4-bit error-feedback state into the gradient accumulator a_t = g_t + Q^{-1}(e_t, delta_t, Delta_t), extracts the Top-k largest-magnitude entries (I_t, V_t) = T_k(|a_t|) (with k = d/100 and block-relative int16 indices within blocks B_d < 2^{15} - 1), zeros those entries in a_t, quantizes the residual error e_{t+1} = Q(a_t, delta_{t+1}, Delta_{t+1}) to b = 4 bits, writes (I_t, V_t) into row t mod m of circular buffer G, and dynamically computes m_hat_t = AdamStats(beta_1, G) and v_hat_t = AdamStats(beta_2, G^2) via unrolled decay z[I_i] <- z[I_i] + beta^r V_i.

Storing the 4-bit error feedback buffer (0.5d bytes) and the circular window G of m sparse gradients with int16 indices and bfloat16 values (4mk bytes) yields total optimizer-state memory M_{mu A}(m) = 0.5d + 4mk bytes, which for k = d/100 is strictly smaller than 8-bit AdamW's 2d bytes whenever m < m_max = 37.5, requiring 0.9d bytes (5.65 GB vs 12.55 GB for 8-bit AdamW and 50.21 GB for FP32 AdamW) on LLaMA-2 7B at m = 10.

Under a q-contractive gradient compressor C (q = sqrt(1 - k/d)) and an unbiased omega-bounded error quantizer Q (Lemma 1: omega = (sqrt(d - 2) / (2^b - 1)) * (Delta - delta) / sqrt(Delta^2 + delta^2)) satisfying q_omega = (1 + omega) * q < 1, Lemma 3 bounds the error buffer by ||e_t||^2 <= 4 * q_omega^2 * G^2 / (1 - q_omega^2)^2, Theorem 1 proves O(1/sqrt(T) + d/T) non-convex gradient stationarity matching AMSGrad, and Theorem 2 proves O(log(T)/T) convergence under the Polyak-Lojasiewicz condition.

Applied to full fine-tuning of BERT-Base/Large and OPT-1.3B on GLUE/MNLI, LLaMA-2 7B/13B on GSM-8k and Open-Platypus, and from-scratch pre-training of ResNet-18/50 on ImageNet, MicroAdam matches or exceeds uncompressed AdamW and 8-bit AdamW accuracy (including 77.37% vs 72.05% for AdamW on ResNet-50 due to sparse-update implicit regularization) while enabling LLaMA-2 7B full fine-tuning on a single 40 GB GPU.

With window size m = 10 and density k = d/100, the per-step parameter update u_t has at least 90% sparsity, which is insufficient for from-scratch pre-training of large language models whose self-attention projection matrices require dense updates to learn global token correlations.