利用随机游走中的时间相关性，梯度方法能高效学习布尔k-掩码问题。
The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently
- 用带时序差分损失的两层ReLU网络，捕捉数据的时间相关性。
- 对任意固定k，样本复杂度几乎随维度线性增长。
- 适合研究带依赖数据的高效学习机制，尤其是小批量优化场景。
我们研究了数据中时间相关性如何使某些稀疏学习问题被基于梯度的方法高效求解。聚焦于布尔k-掩码（Boolean k-juntas）这一经典稀疏学习问题，该问题在独立均匀采样下对梯度方法构成挑战。当样本由超立方体上的懒惰随机游走生成时，时间依赖性可被两层ReLU网络结合时序差分损失（temporal-difference loss）有效利用，该损失比较连续样本间的增量目标与预测值。对于任意固定k，样本复杂度本质上是环境维度d的线性函数。相反，使用标准凸点式损失的大批次梯度方法无法获得相同优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。