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

Konstantinos Christopher Tsiolis, Alireza Mousavi-Hosseini, Murat A. Erdogdu · 2025

Read From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD by Konstantinos Christopher Tsiolis, Alireza Mousavi-Hosseini, Murat A. Erdogdu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-21020.txt.

Introduction

Konstantinos Christopher Tsiolis leads two co-authors on phase transitions in stochastic gradient learning of single index models, where labels depend on a nonlinear function of one hidden direction. Sample complexity is classically set by the information exponent of that link function.

Repeated gradient steps on one sample with varied learning rates were known to beat that limit down to a smaller generative exponent, but only within a learning rate window. Outside the window the picture changes, and learning rate itself induces phase transitions between regimes. Mapping those transitions clarifies when clever step schedules help and when they cannot rescue a hard target function.

Catalog record

CREATORKonstantinos Christopher Tsiolis, Alireza Mousavi-Hosseini, Murat A. Erdogdu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE87 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-21020

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

From Information to Generative Exponent: Learning Rate Induces Phase Transitions in SGD Konstantinos Christopher Tsiolis, Alireza Mousavi-Hosseini, Murat A. Erdogdu 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. 1 Introduction A key aspect of deep learning theory is to understand how neural networks can adapt to underlying data structure and achieve desirable statistical and computational complexity through their optimization dynamics. Towards this goal, several works have focused on learning target functions that depend on low-dimensional projections of data, such as single- and multi-index models. The complexity of learning these models depends on assumptions on the data distribution and on the optimization algorithm. For Gaussian data and online (also called one-pass) SGD on the squared loss, the number of training samples/iterations needed to learn a single-index model depends on a property of the target function known as the information exponent BAGJ 21 . Moreover, through computational lower bounds, the information exponent governs the complexity of any Correlational Statistical Query (CSQ) algorithm for learning single- and multi-index models DNGL 23 ; VE 24 . Such an algorithm interacts with data only through queries of the form yh(x) that lie within a fixed tolerance of their expectation Kea 98 ; Rey 20 . Though SGD can only heuristically be cast as CSQ, this formalism has served as a useful proxy to inform attempts to break this “curse of information exponent”. One such attempt is to consider variants of SGD that apply consecutive gradient updates — with distinct learning rates — on the same batch ( DTA+ 24 ; LOSW 24 ; ADK+24b ) . This simulates more general non-correlational queries h(x,y) and thus bears a connection to the broader class of Statistical Query (SQ) algorithms. Here, the complexity may be controlled by another property of the target function, namely the generative exponent DPVLB 24 , which is at most as large as the information exponent, and can be significantly smaller. JMS 24 further demonstrated that batch reuse is not strictly necessary and other online algorithms can also break the curse of information exponent by instead choosing alternative loss functions, while leaving open the study of other components of the training algorithm. A puzzling observation around reusing batches is that the sample complexity of full-batch gradient flow on the squared loss, through the best known upper bounds, still depends on the information exponent BBSS 22 ; MHWSE 23 . This is in contrast with the intuition that reusing samples is sufficient for breaking out of CSQ, since full-batch gradient flow reuses the entire dataset at every “iteration”. This observation suggests that the role of the learning rate, while ignored in the current literature, is also crucial in determining the query class and the resulting sample complexity of SGD. 1.1 Our Contributions In this paper we aim to answer the following question: Can we characterize the regimes of complexity emerging from the choice of learning rate? We give a precise answer to the above question for a class of online iterative algorithms when learning single-index models. Specifically, we make the following contributions: • In Section 3 , we introduce our general framework and provide a careful learning-rate-dependent analysis of the sample complexity of learning single-index models, resulting in bounds that explicitly demonstrate phase transitions induced by the choice of learning rate hyperparameters. • We show that our framework is expressive enough to capture both vanilla online SGD (Section 4.1 ) and algorithms with non-correlational update rules such as SGD with batch reuse (Section 4.2 ). For the latter, our analysis interpolates between the complexity n=\Theta(d^{(p_{*}-1)\lor 1}) and the online SGD complexity n=\Theta(d^{(p-1)\lor 1}) as the learning rates decrease, where p and p_{*} are the information and generative exponents respectively, n is the number of training samples, and d is in the input dimension. Specifically, we prove phase transitions in the complexity as a function of the learning rate for the first update on each batch. • In Section 4.3 , we show that even when considering squared loss, batch reuse is not the only approach that goes beyond CSQ limitations. In particular, we introduce a new layer-wise training algorithm that uses a different scaling of learning rate for the first and second layers of the network, thus using a two-timescales dynamics. We demonstrate that the performance of this algorithm also depends critically on the learning rate of the second layer. When the latter is sufficiently large, the algorithm can recover the target with almost linear sample complexity when the square of the link function has information exponent 1 or 2. Additionally, this analysis can be extended to a sparsely-connected network with D layers, with the same conclusion holding (under further assumptions) when the D th power of the link function has information exponent 1 or 2. Figure 1 : Combinations of learning rate \eta and sample size n which achieve alignment \langle\bm{w},\bm{\theta}_{*}\rangle\geq 0.5 for a network ( 2.2 ) with N=1 trained by alternating SGD (Algorithm 2 ) in the setting \sigma_{*}=\sigma=\mathsf{He}_{3} and d=50 . The rest of the paper is organized as follows. We provide background on Gaussian single-index models in Section 2 . In Section 3 , we introduce a generic framework to study online gradient-based algorithms and provide our main result. We instantiate this framework for SGD with batch-reuse and the layer-wise two-timescales algorithm in Section 4 . We sketch the proof of our main result in Section 5 , and we conclude in Section 6 . Notation. For k\in\mathbb{N} , we use [k] to denote the set \{1,\dots,k\} . All asymptotic notation is with respect to the input dimension d . We use \tilde{O}(\cdot) and \tilde{\Theta}(\cdot) to denote O(\cdot) and \Theta(\cdot) up to polylogarithmic factors, respectively. Similarly, the relations \lesssim and \gtrsim denote bounds up to polylogarithmic factors. We write a\asymp b when a\lesssim b and a\gtrsim b . An event is said to occur with high probability

Read the complete text