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

• URL: http://arxiv.org/abs/2605.10237v1
• Date: Mon, 11 May 2026 09:11:20 GMT
• Title: The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently
• Abstract summary: temporal correlations in the data can make certain sparse learning problems efficiently learnable by gradient-based methods.<n>We show that for large-batch gradient methods using standard convex pointwise losses, temporal correlations do not provide the same advantage.
• Score: 17.896041616302657
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Path-dependent Discrete Amortized Inference [7.20046890493201]
  We consider the problem of sampling compositional and discrete objects from a given unnormalized posterior distribution.<n>We show that the Markovian assumption can both hamper signal propagation during training and catastrophically reduce the learned sampler's expressivity.<n>We propose lifting the MDP with a learnable latent dynamical system that allows the underlying policy to depend on the entire past trajectory.
  arXiv  Detail & Related papers  (2026-08-09T11:35:05Z)
• InvarDiff: Cross-Scale Invariance Caching for Accelerated Diffusion Models [2.6735992385049663]
  InvarDiff is a training-free acceleration method that exploits the relative temporal invariance across timestep-scale and layer-scale.<n> Experiments show that InvarDiff achieves $2$-$3times$ end-to-end speed-ups with minimal impact on standard quality metrics.
  arXiv  Detail & Related papers  (2025-11-29T02:34:23Z)
• From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD [24.623693376876602]
  In this paper, we characterize the relationship between learning rate(s) and sample complexity for a broad class of gradient-based algorithms.<n>We demonstrate that, in certain cases, there is a phase transition from an "information exponent regime" with small learning rate to a "generative exponent regime" with large learning rate.
  arXiv  Detail & Related papers  (2025-10-23T22:03:53Z)
• Learning Time-Series Representations by Hierarchical Uniformity-Tolerance Latent Balancing [31.568247637126035]
  TimeHUT is a novel method for learning time-series representations by hierarchical-tolerance balancing of contrastive representations.<n>Our method uses two distinct losses to learn strong representations with the aim of striking an effective balance between uniformity and tolerance in the embedding space.
  arXiv  Detail & Related papers  (2025-10-02T04:30:13Z)
• LSCD: Lomb-Scargle Conditioned Diffusion for Time series Imputation [55.800319453296886]
  Time series with missing or irregularly sampled data are a persistent challenge in machine learning.<n>We introduce a different Lombiable--Scargle layer that enables a reliable computation of the power spectrum of irregularly sampled data.
  arXiv  Detail & Related papers  (2025-06-20T14:48:42Z)
• A theoretical framework for self-supervised contrastive learning for continuous dependent data [79.62732169706054]
  Self-supervised learning (SSL) has emerged as a powerful approach to learning representations, particularly in the field of computer vision.<n>We propose a novel theoretical framework for contrastive SSL tailored to emphsemantic independence between samples.<n>Specifically, we outperform TS2Vec on the standard UEA and UCR benchmarks, with accuracy improvements of $4.17$% and $2.08$%, respectively.
  arXiv  Detail & Related papers  (2025-06-11T14:23:47Z)
• Noisy Correspondence Learning with Self-Reinforcing Errors Mitigation [63.180725016463974]
  Cross-modal retrieval relies on well-matched large-scale datasets that are laborious in practice. We introduce a novel noisy correspondence learning framework, namely textbfSelf-textbfReinforcing textbfErrors textbfMitigation (SREM)
  arXiv  Detail & Related papers  (2023-12-27T09:03:43Z)
• Diffeomorphic Transformations for Time Series Analysis: An Efficient Approach to Nonlinear Warping [0.0]
  The proliferation and ubiquity of temporal data across many disciplines has sparked interest for similarity, classification and clustering methods. Traditional distance measures such as the Euclidean are not well-suited due to the time-dependent nature of the data. This thesis proposes novel elastic alignment methods that use parametric & diffeomorphic warping transformations.
  arXiv  Detail & Related papers  (2023-09-25T10:51:47Z)
• Gradient-Based Feature Learning under Structured Data [57.76552698981579]
  In the anisotropic setting, the commonly used spherical gradient dynamics may fail to recover the true direction. We show that appropriate weight normalization that is reminiscent of batch normalization can alleviate this issue. In particular, under the spiked model with a suitably large spike, the sample complexity of gradient-based training can be made independent of the information exponent.
  arXiv  Detail & Related papers  (2023-09-07T16:55:50Z)
• Adaptive Sketches for Robust Regression with Importance Sampling [64.75899469557272]
  We introduce data structures for solving robust regression through gradient descent (SGD) Our algorithm effectively runs $T$ steps of SGD with importance sampling while using sublinear space and just making a single pass over the data.
  arXiv  Detail & Related papers  (2022-07-16T03:09:30Z)
• Learning from time-dependent streaming data with online stochastic algorithms [7.283533791778357]
  This paper addresses optimization in a streaming setting with time-dependent and biased estimates. We analyze several first-order methods, including Gradient Descent (SGD), mini-batch SGD, and time-varying mini-batch SGD, along with their Polyak-Ruppert averages.
  arXiv  Detail & Related papers  (2022-05-25T07:53:51Z)
• Contrastive learning of strong-mixing continuous-time stochastic processes [53.82893653745542]
  Contrastive learning is a family of self-supervised methods where a model is trained to solve a classification task constructed from unlabeled data. We show that a properly constructed contrastive learning task can be used to estimate the transition kernel for small-to-mid-range intervals in the diffusion case.
  arXiv  Detail & Related papers  (2021-03-03T23:06:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.