




















Abstract: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. In this setting, the temporal dependencies can be exploited by a two-layer ReLU network trained using stylized-SGD with a temporal-difference loss, which compares target and predicted increments across consecutive samples. For every fixed k, the resulting sample complexity is essentially linear in the ambient dimension d. By contrast, we show that for large-batch gradient methods using standard convex pointwise losses, temporal correlations do not provide the same advantage.
| Comments: | 10 pages main body, 3 figures |
| Subjects: | Machine Learning (cs.LG) |
| Cite as: | arXiv:2605.10237 [cs.LG] |
| (or arXiv:2605.10237v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2605.10237 arXiv-issued DOI via DataCite (pending registration) |
From: Elisabetta Cornacchia [view email]
[v1]
Mon, 11 May 2026 09:11:20 UTC (458 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。