← All AI/ML open problems

Learning dynamics & scaling · Optimization & optimizers / Open question

How Many Bits Does Reused Data Need?

Reusing examples changes gradient correlations, so an optimal low-precision schedule for fresh samples may be wrong for repeated epochs. Efficiency payoff: Choose width, passes and forward/backward precision jointly when data collection is limited and training compute is fixed.

OpenEditorially scopedSpecified modelCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

Draw one dataset of nn Gaussian examples x∼N(0,Σ)x\sim N(0,\Sigma), y=x⊤θ∗+ξy=x^\top\theta_*+\xi, with λj(Σ)≍j−a\lambda_j(\Sigma)\asymp j^{-a} and λj(Σ)Eθ∗,j2≍j−b\lambda_j(\Sigma)\mathbb E\theta_{*,j}^2\asymp j^{-b}, 1<b<a1<b<a. Fix a Gaussian sketch S∈RM×dS\in\mathbb R^{M\times d}, d=⌈cM⌉d=\lceil cM\rceil, c>1c>1. Starting at zero, train vv for EE independently reshuffled epochs by vt+1=vt−ηtQpb,t(Sxit)(Qpf,t(Sxit)⊤vt−yit)v_{t+1}=v_t-\eta_t Q_{p_{b,t}}(Sx_{i_t})(Q_{p_{f,t}}(Sx_{i_t})^\top v_t-y_{i_t}). Determine sharp final/averaged excess-risk laws in n,E,M,pf,pbn,E,M,p_f,p_b and their compute-optimal allocations.

Assumptions and scope

  • The sketch has independent N(0,1/M) entries; teacher coordinates are independent centered Gaussian with the displayed energy law, and label noise is independent N(0,sigma^2), sigma>0. Teacher, sketch and original samples are independent. Each epoch visits the same n pairs once in a new uniform permutation.
  • Q_p is unbiased independent coordinatewise rounding to adjacent signed binary numbers with p mantissa bits and unbounded integer exponent, fixing grid points. Use fresh independent rounding for forward/backward copies and visits; all other arithmetic and test-time prediction are exact.
  • Risk is one half E[||S^T v-theta_*||_Sigma^2], averaged over teacher, data, sketch, reshuffling and rounding. Analyze v_T and T^(-1)sum_{t=1}^T v_t, T=nE. Schedules are fixed before observing data. Charge n sketch evaluations, dataset/feature storage and T precision-dependent updates under an explicit bit-operation proxy; no full-format GPU claim is implied.

What would settle it?

Matching-order upper/lower risk bounds in a nontrivial finite-data multi-pass regime, recovering exact-arithmetic and single-pass baselines, then an allocation law under a stated arithmetic-cost proxy. Identify any new rounding-induced floor or stability constraint.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Wang and Mahoney explicitly leave data reuse for future theory while testing it empirically; their fresh-data laws already cover precision schedules and averaging. Lin et al. provide exact-arithmetic multi-pass scaling. Random reshuffling fixes one concrete specialization of the published direction. This is an editorial reformulation of a published open problem. The preliminary review through 2026-11-20 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Wang and Mahoney — Where, When, and How Many Bits? Scaling Laws for SGD with Stochastic Rounding ↗problem statement · source checked 2026-11-20

    HTML Sections 2–6 checked: fresh Gaussian random-feature data, independent forward/backward rounding and exact remaining arithmetic. Finite-dataset reuse is explicitly future work. Precision counts mantissa bits with unbounded exponent, not a complete hardware format.

  2. Lin, Wu and Bartlett — Improved Scaling Laws in Linear Regression via Data Reuse ↗partial theory · source checked 2026-11-20

    Primary abstract checked: sharp multi-pass SGD risk in sketched power-law linear models. This supplies an exact-arithmetic reuse baseline, not a joint rounding/reuse law.

  3. Paquette et al. — 4+3 Phases of Compute-Optimal Neural Scaling Laws ↗partial theory · source checked 2026-11-19

    Abstract checked: proven compute-optimal exponents for a solvable linear power-law model trained by one-pass SGD.