SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws
Abstract
We study the training dynamics of multiclass logistic regression on high-dimensional Gaussian mixture models with a large number of classes and establish precise scaling laws governing the cross-entropy risk under gradient-based optimization. We show that learning proceeds sequentially across classes, from most to least frequent. When the class priors follow a power law distribution, the risk dynamics decompose into three phases: an initial plateau until the first class is learned, a power-law decay regime during which sequential learning occurs, and a final convergence regime. We then analyze how model capacity interacts with optimization under a fixed compute budget. When the effective dimension is restricted via projection onto leading principal components, the risk decomposes into a capacity term (a power law in the retained dimension) and an optimization term (a power law in training time). Optimizing this tradeoff yields a compute-optimal scaling law for logistic regression, with explicit prescriptions for model size and training time as functions of compute. These results extend theoretical scaling laws from linear regression to multiclass classification, while connecting to empirical scaling laws observed in large-scale neural networks.
Related
- Gradient descent reaches arbitrary accuracy in a fixed number of large steps on multiclass logistic regression
- Using Bayesian Sequential Logistic Regression to Model the Organ Transplant Selection Process
- Large Stepsizes Federated Learning on Logistic Regression with Linearly Separable Data: The Case of Heterogeneous Devices
- Minimax-optimal Scaling Laws in Ridge Regression via Transfer Learning
- Data generation for the logistic regression model under controlled conditions
BibTeX
@misc{tsiolis2026multiclass,
title = {{SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws}},
author = {Konstantinos Christopher Tsiolis and Denny Wu and Christos Thrampoulidis and Murat A. Erdogdu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07868},
eprint = {2609.07868},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07868},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws
AU - Konstantinos Christopher Tsiolis
AU - Denny Wu
AU - Christos Thrampoulidis
AU - Murat A. Erdogdu
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07868
UR - https://arxiv.org/abs/2609.07868
AB - We study the training dynamics of multiclass logistic regression on high-dimensional Gaussian mixture models with a large number of classes and establish precise scaling laws governing the cross-entropy risk under gradient-based optimization. We show that learning proceeds sequentially across classes, from most to least frequent. When the class priors follow a power law distribution, the risk dynamics decompose into three phases: an initial plateau until the first class is learned, a power-law decay regime during which sequential learning occurs, and a final convergence regime. We then analyze how model capacity interacts with optimization under a fixed compute budget. When the effective dimension is restricted via projection onto leading principal components, the risk decomposes into a capacity term (a power law in the retained dimension) and an optimization term (a power law in training time). Optimizing this tradeoff yields a compute-optimal scaling law for logistic regression, with explicit prescriptions for model size and training time as functions of compute. These results extend theoretical scaling laws from linear regression to multiclass classification, while connecting to empirical scaling laws observed in large-scale neural networks.
ER -