Research map / Optimization / Implicit bias and generalization

The Benefits of Temporal Correlations: SGD Efficiently Learns k-Juntas from Random Walks

NeurIPS 2026 · Optimization › Implicit bias and generalization · approach: Low-rank and single-index recovery

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that SGD on a two-layer ReLU net with a temporal-difference loss learns Boolean k-juntas from lazy random-walk samples with near-linear (in d) sample complexity, while large-batch noisy SGD with standard pointwise losses cannot exploit this.

Problem

Gradient-based methods need d^{Omega(k)} time to learn k-juntas/parities from i.i.d. uniform samples; the paper asks whether temporal correlations from a random walk on the hypercube make these sparse problems efficiently learnable by gradient methods.

Approach

Use a temporal-difference loss on consecutive random-walk samples so that finite-difference label increments reveal support coordinates via second-moment (anisotropy) effects; a layerwise SGD (first layer on TD loss, then second layer on square loss with regularization) then solves a regression on the recovered support.

Key results

• Theorem: for fixed k, two-layer ReLU net trained with layerwise SGD on TD loss learns k-juntas from lazy random walk with T = O~(d) samples (linear in d).
• Noisy large-batch SGD with pointwise convex losses: for parities with batch B=d^c, any method needs T >= Omega(d^{min{k,c-1}/4 - 1/2}) to beat random guessing; superlinear when min{k,c-1}>6.
• 5-parity with d=50: TD loss on random-walk data reaches high test accuracy while i.i.d. baselines fail; square loss on random-walk data also learns the parity at batch size 1.

Surprising findings

• At batch size 1, the plain square loss on random-walk data learns the parity and can outperform the TD loss, outside the regime covered by the lower bound.
• Relevant Fourier-Walsh coefficients of the 7-junta emerge at roughly the same time, unlike the usual lower-to-higher order learning under i.i.d. sampling.

Limitations

• Lower bound for pointwise losses only covers large-batch noisy SGD, not small-batch SGD.
• Analysis restricted to single-bit-flip lazy random walks and exponential dependence on k.

Experimental setup

Datasets: synthetic lazy random walk on hypercube, d=50

Benchmarks: synthetic 5-parity d=50 synthetic 7-junta d=50

Metrics: test accuracy test loss Fourier-Walsh coefficients

Baselines: square loss SGD on i.i.d. uniform data TD loss on i.i.d. uniform data square loss on random-walk data

Builds on: Arpe and Mossel random walk junta learning Markov chain SGD analysis quantitative CLT for Markov chains Positive distribution shift

Closest papers by meaning

• Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent (NeurIPS 2024 · similarity 0.85)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries (NeurIPS 2024 · similarity 0.84)
• Online Learning and Information Exponents: The Importance of Batch size & Time/Complexity Tradeoffs (ICML 2024 · similarity 0.84)
• Statistical Guarantees for High-Dimensional Stochastic Gradient Descent (NeurIPS 2025 · similarity 0.84)
• On Sparse Canonical Correlation Analysis (NeurIPS 2024 · similarity 0.84)
• Complexity Matters: Feature Learning in the Presence of Spurious Correlations (ICML 2024 · similarity 0.83)