LeT Workshop Learning Theory Workshop

Asynchronous pipeline parallelism can accelerate distributed model training, but suffers from instability caused by inconsistent gradient computations. We identify a fundamental source of this inconsistency: error signals are coupled to forward-time features, not just parameter states. This means that parameters may evolve as long as they preserve forward-equivalence. Leveraging this insight, we introduce FRESCO, which frames asynchronous updates as a constrained optimization problem: it finds the minimal update modification that acts trivially on the activation subspace. Thus, it serves as a principled generalization beyond the usual synchronous--asynchronous dichotomy: subspace-level protection preserves gradient validity without synchronization stalls, unconstrained-asynchrony instability, or memory overhead that works against pipeline scaling. We demonstrate that FRESCO consistently outperforms representative asynchronous baselines in LLM pre-training, with the gains most pronounced under deep pipelines and high inconsistency levels. Moving beyond the current limitations, FRESCO establishes a new foundation for high-utilization pipeline parallel training, providing a scalable path for large-model development on diverse, resource-constrained systems.

How do we initialize the neural network weights? Classic ideas have focused on stabilizing the activation distributions of the networks, so that one can train deeper nets without exploding or vanishing gradients. In this talk, we study how the initialization scale can affect the efficiency of model training. In particular, we describe modern theories on how the weight scale shapes the training speed and the generalization capabilities of the model, and recent breakthroughs in characterizing the optimal speed-generalization tradeoff point.

The Edge of Stability (EoS) is widely observed in neural network training for minimization, where gradient methods continue to make progress while operating near their stability thresholds. Yet an analogous phenomenon has not been clearly identified in minimax optimization. In this talk, I will formulate minimax EoS using possibly complex Jacobian eigenvalues and show that it arises in two-player zero-sum games trained with Extragradient (EG) and Optimistic Gradient Descent Ascent (OGDA). Interestingly, when the dominant eigenvalues lie near the real axis, OGDA continues to exhibit EoS whereas EG becomes unstable. I will also describe how the self-stabilization mechanism from minimization extends to explain these EoS behaviors.

We study steepest descent for linear multiclass classification with softmax cross-entropy on nonseparable data. Unlike binary nonseparable logistic regression, where the data split into separable and nonseparable examples, a multiclass example induces multiple pairwise margin constraints that may differ in separability. We therefore introduce a norm-dependent parameter-space decomposition: one component remains constant throughout the descent, an escaping component that maximizes the margin in the separable subspace, and a bounded component that converges to a finite optimum in the nonseparable subspace. We derive convergence rates of the risk to its infimum and of the normalized margin of the escaping component to the norm-dependent optimum. We also characterize directional convergence. When the norm is strictly convex, the max-margin direction is unique and the escaping component converges to it directionally. Without strict convexity, we find that this can fail: we construct a linear classification problem and an optimization norm for which the normalized escaping component has multiple distinct max-margin accumulation points, even with separable training data.

Denoising diffusion models require several coupled design choices: what the network predicts, how timesteps are sampled during training, and how much capacity the architecture provides. Three recent empirical findings shed light on how to make these choices: (i) clean data prediction can have higher generation quality than standard noise or velocity prediction; (ii) sampling timesteps from a logit-normal distribution can outperform uniform sampling; and (iii) generation quality can peak at an intermediate model capacity. However, a theoretical understanding of these observations and of how the three choices interact remains limited. In this paper, we show that theoretical counterparts of all three observations already arise in a tractable linear model with Gaussian data and a time-gated predictor. Specifically, our spectral analysis reveals how the three choices jointly determine spectral components of the data are represented by the model and, in turn, the generated distribution. This analysis further shows that optimal design choices vary with the spectral structure of the data. We provide empirical support for our theoretical findings on synthetic and real data.

Mamba, a recently proposed linear-time sequence model, has attracted significant attention for its computational efficiency and strong empirical performance. However, a rigorous theoretical understanding of its underlying mechanisms remains limited. In this work, we provide a theoretical analysis of Mamba's in-context learning (ICL) capability by focusing on tasks defined by low-dimensional nonlinear target functions. Specifically, we study in-context learning of a single-index model, which depends on only a single relevant direction, referred to as a feature. We prove that Mamba, pretrained by gradient-based methods, can achieve efficient ICL via test-time feature learning, extracting the relevant direction directly from context examples. Consequently, we establish a test-time sample complexity that improves upon linear Transformers — analyzed to behave like kernel methods — and is comparable to nonlinear Transformers, which have been shown to surpass the Correlational Statistical Query (CSQ) lower bound and achieve near information-theoretically optimal rate in previous works. Our analysis reveals the crucial role of the nonlinear gating mechanism in Mamba for feature extraction, highlighting it as the fundamental driver behind Mamba's ability to achieve both computational efficiency and high performance.

Posterior sampling for reinforcement learning (PSRL) is one of the simplest and most effective exploration methods, but a basic question has remained open: does unmodified PSRL achieve minimax regret without structural assumptions on the prior? We answer yes. Exact vanilla PSRL is minimax optimal in leading-order Bayesian regret under arbitrary correlated priors. The difficulty is that a posterior-sampled transition model is coupled with its own continuation value. We overcome this with a common empirical transition reference that isolates the resulting value mismatch and a Bellman-based variance argument that controls it without an extra leading-order state-space factor. For finite-horizon, time-inhomogeneous tabular MDPs with unknown stochastic rewards, this yields the minimax Oe( √ SAH3K) regret rate under arbitrary joint priors over rewards and transitions. The same proof principle gives the minimax Oe(d √ H3K) rate for linear-mixture MDPs under arbitrary joint parameter priors.

Applying Thompson sampling (TS) to generalized linear bandits (GLBs) is computationally challenging because exact posterior updates are generally intractable. Existing GLB algorithms with strong regret guarantees typically rely on batch estimators built from accumulated data, while computationally efficient one-pass methods often require problem-dependent quantities, such as an upper bound on the context norm and a radius of a ball containing the true parameter, as explicit inputs to their implementation. We propose OnlineTS, an online TS algorithm for GLBs based on Bayesian one-pass online learning. Our method uses a Gaussian approximation induced by a local quadratic expansion of the log-likelihood, leading to a recursive posterior update that depends only on the current estimator and the current observation. We show that this Bayesian online one-pass estimator admits a high probability concentration bound in the bandit setting, which yields a frequentist regret bound of $\widetilde O(\sqrt{T})$ for OnlineTS over horizon $T$. Thus, OnlineTS combines strong statistical performance with computational efficiency without requiring such problem-dependent quantities as inputs to its implementation. Through numerical experiments, we demonstrate that OnlineTS achieves regret competitive with the existing GLB methods at substantially lower computational cost.

The Edge of Stability (EoS) phenomenon is widely observed in minimization, where gradient methods continue to decrease the loss even while remaining near their stability thresholds, a behavior associated with a self-stabilization mechanism. Yet an analogous phenomenon has not been clearly identified in minimax optimization. In this paper, we formulate EoS for minimax optimization, demonstrate that it indeed occurs, and characterize the self-stabilization mechanism underlying it. We first define EoS for minimax optimization in terms of possibly complex dominant Jacobian eigenvalues reaching the boundary of the stability region. Using two-player zero-sum games, we observe minimax EoS for both Extragradient (EG) and Optimistic Gradient Descent Ascent (OGDA). However, when the dominant eigenvalues lie near the real axis, OGDA still exhibits EoS whereas EG does not. Finally, we generalize the self-stabilization mechanism to minimax methods and show how it explains these behaviors.

Vector quantization is a fundamental primitive for scalable machine learning systems, enabling memory-efficient storage, fast retrieval, and compressed inference. Recent rotation-based quantizers such as EDEN, RabitQ, and TurboQuant have introduced strong guarantees and empirical performance, but the surrounding comparisons have been difficult to interpret because they rely on different distortion criteria, probability regimes, and implementation assumptions. As our first contribution, we provide a unified theoretical comparison of these methods and show that their relative advantages are criterion-dependent rather than absolute: EDEN and TurboQuant are favorable for MSE distortion, EDEN is also effective for expected inner-product distortion, and RabitQ provides strong high-probability control. This comparison further clarifies that EDEN provides particularly strong guarantees for expected distortion measures. As our second contribution, we introduce Block-Sphere Quantization (BlockQuant), a new rotation-based block quantization algorithm designed around the spherical geometry of randomly rotated vectors. Unlike coordinate-wise quantizers, BlockQuant quantizes blocks on the sphere, preserving the geometry of rotated embeddings more faithfully. We prove that this block-spherical design theoretically improves over the baselines considered in this paper for both reconstruction MSE and expected inner-product distortion. Our experiments on real embedding datasets and long-context LLM inference tasks show practical gains that are consistent with our theoretical improvements.

We propose a contextual cascading bandit model in which the click probability at each position depends on both the displayed item and the topics of previously shown items. This captures how previously displayed topics affect later click probabilities, allowing different topic orders to induce different user responses. Unlike standard cascading bandits, the optimal cascade is no longer determined only by the selected set of items, since the ordering itself affects the expected reward. To address the resulting planning challenge, we reformulate cascade construction as a Markov decision process whose state summarizes the previously selected topics. Based on this formulation, we develop an optimism-based algorithm and prove a regret upper bound that decreases with the cascade length K, a phenomenon that had not been established even in order-insensitive contextual cascading bandits. We further provide a local regret lower bound showing that this decreasing dependence on K is intrinsic, and validate our theory through experiments with topic-order-dependent click probabilities.

Recent analyses of multi-pathway Deep Linear Networks use Gradient Flow to predict a "winner-takes-all" specialization in which path symmetry breaks and each feature concentrates in a single pathway. In this work, we show that discrete Gradient Descent (GD) with a large step size tells a different story. We prove that single-path solutions are sharp minima, whereas distributing signals across pathways reduces sharpness by a factor that decreases with both the number of pathways and depth. Consequently, while early training reproduces the depth-driven symmetry breaking predicted by GF, oscillations at the Edge of Stability subsequently override this tendency and drive the network into a re-balancing phase, where signals redistribute across pathways. Together, these results clarify how depth shapes pathway competition and explain why large-step GD favors shared representations rather than persistent single-pathway dominance.

Mckean-Vlasov equations model various measure-evolving situations arising from various fields. In the field of machine learning, SGD dynamics of two-layer neural networks and forward passes of certain mean-field transformers are Mckean-Vlasov equations with specific interaction and potential kernels. In this presentation we classify the asymptoptic convergence rates of Mckean-Vlasov equations using Adams-Simon conditions. In the case of mean-field transformers with constant-times-identity parameters, the convergence rates are described explicitly by the parameters. This answers the recent question by Mun--Rosenzweig(2026).

Ensemble sampling is a practically attractive approach to randomized exploration, but existing theoretical guarantees for linear bandits require ensembles much larger than what its practical motivation would suggest. In particular, the sharpest existing analysis achieves an ensemble complexity of order d log T, leaving a log T gap from the intrinsic order-d ensemble-size barrier. We aim to narrow this gap by proposing an ensemble sampling algorithm that refreshes the ensemble only when the regularized Gram matrix changes substantially. This mechanism localizes the perturbation analysis to epochs with controlled Gram-matrix drift and reduces the sufficient ensemble size to order d log d + d log log T, while preserving the state-of-the-art regret for ensemble sampling with arbitrary bounded arm sets. We further show that, when the arm set is finite of cardinality K, the proposed algorithm achieves the sharper regret bound of order d√(T log K). To the best of our knowledge, this is the first ensemble-sampling guarantee that simultaneously recovers both canonical regret scalings known for randomized linear bandit algorithms. The algorithm also admits an anytime implementation without resetting past data, and experiments show that it remains competitive with baselines while using substantially smaller ensembles.

More training data can improve generalization, but does it always help a model learn faster? We investigate this question through controlled Transformer experiments on elementary cellular automata: binary sequences updated by a local rule mapping each cell and its two neighbors to its next value. We identify an intermediate-difficulty regime in which larger datasets delay both training-set fitting and generalization, measured in optimizer updates at a fixed batch size rather than epochs. Comparisons with easy and hard rules highlight a key distinction: the availability of lower-order predictive signals, which enable better-than-chance prediction from partial local inputs. Under the uniform population distribution, the intermediate rule provides neither output bias nor single-input predictive information. Sampling fluctuations nevertheless introduce these signals into smaller datasets, but the signals weaken as datasets grow. Biasing training inputs to introduce such signals accelerates generalization on unchanged, uniformly sampled validation inputs. We separately probe example-specific fitting by appending a fixed random bit string to each training target. Fitting these strings takes more updates as datasets grow, and the model can generalize on the cellular-automaton task before accurately reproducing them. Together, these observations suggest that weaker empirical signals and more example-specific associations may both contribute to the slowdown. We also observe similar slowdowns in dynamic programming and scratchpad multiplication. Our findings distinguish data sufficiency from learning speed: adding examples can delay algorithmic learning even when smaller datasets already support generalization.

We study linear contextual bandits under \emph{rare parameter updates}: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many ``strictly batched'' methods additionally restrict \emph{within-interval context adaptivity}, meaning that the action rule inside an interval cannot depend on the \emph{sequence} of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only $\Ocal(\log\log T)$ parameter updates. Our first algorithm \texttt{BLCE-G} attains minimax-optimal regret (up to polylogarithmic factors in $T$) \emph{simultaneously} in both the small-$K$ and large-$K$ regimes under a static schedule. Our second algorithm \texttt{BLCE} removes the near G-optimal design step---a dominant computational bottleneck in prior strictly batched static-grid methods---yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield minimax-optimal algorithms for linear contextual bandits and a near-optimal generalized-linear extension under $\Ocal(\log\log T)$ parameter updates, while remaining computationally efficient in practice.

Statistical physics has offered valuable perspectives on machine learning (ML) through frameworks such as spin-glass theory and stochastic dynamics. An important challenge is to translate these perspectives into practical methods that not only explain the learning dynamics of deep neural networks (DNNs) but also improve their performance on imperfect datasets. In this work, we take a statistical physics approach to learning from datasets corrupted by label noise. We analyze the dynamics of stochastic gradient descent (SGD) and identify a latent gradient bias induced by corrupted labels that impairs the generalization of DNNs. To address this problem, we incorporate stochastic resetting into SGD. Through theoretical analysis and empirical evaluation, we demonstrate that stochastic resetting mitigates the adverse effects of this bias, leading to improved generalization performance. Our findings provide insights into the learning dynamics of DNNs, highlighting the potential to both analyze and enhance ML methods through the lens of statistical physics.

We study \emph{bilinear matching bandits}, an online sequential decision problem in which at each round a learner assigns $M$ users to $N$ items via an injective matching $\pi:[M]\hookrightarrow[N]$ and observes semi-bandit feedback with bilinear mean reward $\mathbf{x}i^\top \mathbf{\Theta}^\star \mathbf{y}{\pi(i)}$, where the parameter $\mathbf{\Theta}^\star \in \mathbb{R}^{d_1 \times d_2}$ is unknown. We propose \textsc{HybridRRD}, a hybrid algorithm that combines high-width elimination with a row-wise regularized design sampler over the fractional matching polytope. Without assuming $\mathbf{\Theta}^\star$ is low-rank, \textsc{HybridRRD} achieves a high-probability regret bound of $\widetilde{O} (d_2 \sqrt{d_1MT} + Md_1 d_2)$, suppressing problem-scale constants. This improves the leading dimension dependence from $d_1d_2$ to $d_2\sqrt{d_1}$ over the standard Kronecker-linearized contextual combinatorial semi-bandit baseline. We further prove a minimax lower bound of $\Omega(d_2 \sqrt{d_1 M T})$ in a large-item regime, matching the leading regret term up to logarithmic factors. Numerical experiments show that \textsc{HybridRRD} performs favorably against Kronecker-linearized baselines.

In the past years, theory has done much to explain why large language models work. It has clarified scaling laws and hyperparameter transfer, the low-rank structure behind LoRA, the statistics of preference learning, the dynamics of critic-free RL methods such as GRPO, and the expressive limits of Transformers and state-space models. All of these results share one unit of analysis: a single model trained on a single objective. Today’s LLM systems have outgrown that picture, combining many models, noisy signals, and tight cost budgets. This talk explores the questions theory should ask next, now that the object of study is a system of models. I will close with an open discussion on the future of theoretical research. Now that AI can produce research-level proofs, proving is no longer the bottleneck. What is scarce instead is the ability to find important problems grounded in real systems, and the intuition to steer AI toward their answers.

In online learning, a best-of-both-worlds (BOBW) policy provides strong performance guarantees in both stochastic and adversarial environments. While much of the existing literature has established such guarantees within the follow-the-regularized-leader framework, Follow-the-Perturbed-Leader (FTPL) offers a conceptually simple and often computationally attractive alternative based on randomized decision rules.

In this talk, I will review our recent progress on establishing BOBW guarantees for FTPL across several online learning problems, with particular emphasis on multi-armed bandits and structured feedback settings. I will discuss the main ideas behind these results, including adaptive learning rates, surrogate probabilities, perturbation-based stability analysis, and efficient loss estimation. Rather than focusing on a single result, the talk will discuss broader insights gained from this line of work, including how simple randomized decision rules can achieve strong theoretical guarantees while maintaining computational efficiency.

Bellman residual minimization (BRM) is a classical approach to reinforcement learning that directly seeks a value function satisfying the Bellman equation. Despite its conceptual simplicity and attractive fixed-point interpretation, BRM has historically faced major computational and statistical difficulties, including the double-sampling problem and challenging nonconvex optimization. Recent dual formulations provide a new perspective on these obstacles, transforming BRM into tractable minimax problems amenable to stochastic gradient methods.

In this talk, I will briefly review the history, strengths, and limitations of BRM and discuss how this dual perspective enables a modern treatment of the framework. I will then present our recent results along three directions: Off-GLADIUS, which establishes global convergence guarantees for gradient-based BRM in offline reinforcement learning; Stability and Generalization for Bellman Residuals, which provides fast statistical guarantees through algorithmic stability; and Stoc-TBRM, which extends the BRM perspective to stochastic trajectory-level learning. Together, these results suggest that BRM, despite being a classical framework, can provide a scalable and theoretically principled foundation for modern offline reinforcement learning.

Many multi-armed bandit and reinforcement learning algorithms rely on full optimism, using confidence bonuses large enough to upper-bound unknown values with high probability. This talk presents quasi-optimism, a new exploration principle that allows a controlled degree of underestimation while retaining provably optimal regret guarantees. We first introduce this principle in tabular reinforcement learning, where a simple inverse-count bonus achieves minimax-optimal regret without empirical variance estimation. We then discuss its extension to distribution-dependent and instance-dependent regret guarantees in bandits and reinforcement learning. Finally, we extend quasi-optimism to linear contextual bandits using a quadratic–linear bonus. Despite not being pointwise optimistic, the resulting algorithm simultaneously achieves minimax-optimal and tight margin-dependent regret guarantees while substantially reducing unnecessary exploration in empirical evaluations. Together, these results suggest that quasi-optimism is both theoretically optimal and practically effective.

At the heart of modern machine learning lies a fundamental challenge: how can an intelligent system not just learn from data but also decide which data to collect for learning? This is the essence of interactive machine learning (IML) -- a paradigm that encompasses reinforcement learning, contextual bandits, and active learning. Recently, the offline version of IML has gained popularity because the traditional online version often cannot be run due to real-world constraints. In this talk, I will show two recent advances in offline IML problems. First, I will discuss the contextual bandit problem that has applications in recommendation systems. I will show how an improved confidence bound for [0,∞)-valued random variable translates into a superior learning algorithm, both in theory and practice. Second, I will show that the LLM alignment problem is an instance of offline IML and that existing training objectives for it lack theoretical justification, leaving us wondering if they are the right ones to use. As such, I will present a novel theoretical framework for alignment from which three different alignment algorithms are derived along with theoretical guarantees, which is a strong form of justification. Surprisingly, two of them are very similar to existing algorithms called Direct Policy Optimization (DPO) and reinforcement learning from human feedback (RLHF), respectively. Together with our theoretical guarantees, our work can be seen as providing theoretical justifications to DPO and RLHF, with minor corrections. Furthermore, our theory confirms the existing empirical finding that RLHF performs better than DPO. I will conclude with empirical results and exciting future research directions.