From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD

• URL: http://arxiv.org/abs/2510.21020v1
• Date: Thu, 23 Oct 2025 22:03:53 GMT
• Title: From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD
• Authors: Konstantinos Christopher Tsiolis, Alireza Mousavi-Hosseini, Murat A. Erdogdu,
• Abstract summary: 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.
• Score: 24.623693376876602
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To understand feature learning dynamics in neural networks, recent theoretical works have focused on gradient-based learning of Gaussian single-index models, where the label is a nonlinear function of a latent one-dimensional projection of the input. While the sample complexity of online SGD is determined by the information exponent of the link function, recent works improved this by performing multiple gradient steps on the same sample with different learning rates -- yielding a non-correlational update rule -- and instead are limited by the (potentially much smaller) generative exponent. However, this picture is only valid when these learning rates are sufficiently large. In this paper, we characterize the relationship between learning rate(s) and sample complexity for a broad class of gradient-based algorithms that encapsulates both correlational and non-correlational updates. 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. Our framework covers prior analyses of one-pass SGD and SGD with batch reuse, while also introducing a new layer-wise training algorithm that leverages a two-timescales approach (via different learning rates for each layer) to go beyond correlational queries without reusing samples or modifying the loss from squared error. Our theoretical study demonstrates that the choice of learning rate is as important as the design of the algorithm in achieving statistical and computational efficiency.

Related papers

• Interactive Learning of Single-Index Models via Stochastic Gradient Descent [15.788049354466715]
  gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization.<n>Recent theoretical advances have provided a deep understanding of how SGD enables feature learning in high-dimensional nonlinear models.
  arXiv  Detail & Related papers  (2026-02-19T22:22:45Z)
• Decentralized Nonconvex Composite Federated Learning with Gradient Tracking and Momentum [78.27945336558987]
  Decentralized server (DFL) eliminates reliance on client-client architecture.<n>Non-smooth regularization is often incorporated into machine learning tasks.<n>We propose a novel novel DNCFL algorithm to solve these problems.
  arXiv  Detail & Related papers  (2025-04-17T08:32:25Z)
• NTKCPL: Active Learning on Top of Self-Supervised Model by Estimating True Coverage [3.4806267677524896]
  We propose a novel active learning strategy, neural tangent kernel clustering-pseudo-labels (NTKCPL) It estimates empirical risk based on pseudo-labels and the model prediction with NTK approximation. We validate our method on five datasets, empirically demonstrating that it outperforms the baseline methods in most cases.
  arXiv  Detail & Related papers  (2023-06-07T01:43:47Z)
• Faster Adaptive Federated Learning [84.38913517122619]
  Federated learning has attracted increasing attention with the emergence of distributed data. In this paper, we propose an efficient adaptive algorithm (i.e., FAFED) based on momentum-based variance reduced technique in cross-silo FL.
  arXiv  Detail & Related papers  (2022-12-02T05:07:50Z)
• Pairwise Learning via Stagewise Training in Proximal Setting [0.0]
  We combine adaptive sample size and importance sampling techniques for pairwise learning, with convergence guarantees for nonsmooth convex pairwise loss functions. We demonstrate that sampling opposite instances at each reduces the variance of the gradient, hence accelerating convergence.
  arXiv  Detail & Related papers  (2022-08-08T11:51:01Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Cooperative Deep $Q$-learning Framework for Environments Providing Image Feedback [5.607676459156789]
  We address two key challenges in deep reinforcement learning setting, sample inefficiency and slow learning, with a dual NN-driven learning approach. In particular, we develop a temporal difference (TD) error-driven learning approach, where we introduce a set of linear transformations of the TD error to directly update the parameters of each layer in the deep NN. We show that the proposed methods enables faster learning and convergence and requires reduced buffer size.
  arXiv  Detail & Related papers  (2021-10-28T17:12:41Z)
• Cogradient Descent for Dependable Learning [64.02052988844301]
  We propose a dependable learning based on Cogradient Descent (CoGD) algorithm to address the bilinear optimization problem. CoGD is introduced to solve bilinear problems when one variable is with sparsity constraint. It can also be used to decompose the association of features and weights, which further generalizes our method to better train convolutional neural networks (CNNs)
  arXiv  Detail & Related papers  (2021-06-20T04:28:20Z)
• Exploring Complementary Strengths of Invariant and Equivariant Representations for Few-Shot Learning [96.75889543560497]
  In many real-world problems, collecting a large number of labeled samples is infeasible. Few-shot learning is the dominant approach to address this issue, where the objective is to quickly adapt to novel categories in presence of a limited number of samples. We propose a novel training mechanism that simultaneously enforces equivariance and invariance to a general set of geometric transformations.
  arXiv  Detail & Related papers  (2021-03-01T21:14:33Z)
• Fast Reinforcement Learning with Incremental Gaussian Mixture Models [0.0]
  An online and incremental algorithm capable of learning from a single pass through data, called Incremental Gaussian Mixture Network (IGMN), was employed as a sample-efficient function approximator for the joint state and Q-values space. Results are analyzed to explain the properties of the obtained algorithm, and it is observed that the use of the IGMN function approximator brings some important advantages to reinforcement learning in relation to conventional neural networks trained by gradient descent methods.
  arXiv  Detail & Related papers  (2020-11-02T03:18:15Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

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.