AI RESEARCH
The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently
arXiv CS.LG
•
ArXi:2605.10237v1 Announce Type: new We study how temporal correlations in the data can make certain sparse learning problems efficiently learnable by gradient-based methods. Our focus is on Boolean k-juntas, a canonical sparse learning problem known to pose barriers for gradient-based methods under independent uniform samples. We show that this picture changes when the samples are generated by a lazy random walk on the hypercube.