ALT 2026 Papers

This paper explores the suspicious alignment phenomenon in stochastic gradient descent (SGD) under ill-conditioned optimization, where the Hessian spectrum splits into dominant and bulk subspaces. This phenomenon describes the behavior of gradient alignment in SGD updates. Specifically, during the initial phase of SGD updates, the alignment between the gradient and the dominant subspace tends to decrease. Subsequently, it enters a rising phase and eventually stabilizes in a high-alignment phase. The alignment is considered “suspicious” because, paradoxically, the projected gradient update along this highly-aligned dominant subspace proves ineffective at reducing the loss. The focus of this work is to give a fine-grained analysis in a high-dimensional quadratic setup about how step size selection produces this phenomenon. Our primary contribution can be summarized as follows: We propose a step-size condition theory revealing that in low-alignment regimes, an adaptive critical step size η_t^∗ separates alignment-decreasing (η_t < η_t^∗) from alignment-increasing (η_t > η_t^∗) regimes, whereas in high-alignment regimes, the alignment is self-correcting and decreases regardless of the step size. We further show that under sufficient ill-conditioning, a step size interval exists where the loss in the bulk subspace decreases while the loss in the dominant subspace increases, which explains a recent empirical observation that projecting gradient updates to the dominant subspace is ineffective. Finally, based on this adaptive step-size theory, we prove that for a constant step size and large initialization, SGD exhibits this distinct two-phase behavior: an initial alignment-decreasing phase, followed by stabilization at high alignment.

We characterize conditions under which collections of distributions on {0,1}^ℕ admit uniform estimation of their mean. Prior work from Vapnik and Chervonenkis (1971) has focused on uniform convergence using the empirical mean estimator, leading to the principle known as P- Glivenko-Cantelli. We extend this framework by moving beyond the empirical mean estimator and introducing Uniform Mean Estimability, also called UME-learnability, which captures when a collection permits uniform mean estimation by any arbitrary estimator. We work on the space created by the mean vectors of the collection of distributions. For each distribution, the mean vector records the expected value in each coordinate. We show that separability of the mean vectors is a sufficient condition for UME-learnability. However, we show that separability of the mean vectors is not necessary for UME-learnability by constructing a collection of distributions whose mean vectors are non-separable yet UME-learnable using techniques fundamentally different from those used in our separability-based analysis. Finally, we establish that countable unions of UME-learnable collections are also UME-learnable, solving the conjecture posed in Cohen et al. (2025).

In online learning, a learner receives data in rounds 1 ≤ t ≤ T and, at each round, predicts a label that is then compared to the true label, resulting in a loss. The total loss over T rounds, when compared to the loss of the best expert from a class of experts, is called the regret. We study the *fixed-design* minimax regret for the best predictor and the worst label sequence, when the feature sequence is given in advance. This paper focuses on *logarithmic loss* over a class of experts ℋ_𝐰 parameterized by a d-dimensional weight vector 𝐰, which can be unbounded and may increase with T. For bounded weights, it is known that the minimax regret can grow no faster than (d/2)log(TR^2/d); hence, the leading coefficient in front of log T can grow without control as R increases. However, in this paper, we demonstrate a phase transition showing that, for R ≥ T and large (but constant) d, the minimax regret asymptotically equals (d ± 1)log T + O(loglog T) for a logistic-like expert class, which can be generalized to a broader family of experts. We prove our findings by introducing the so-called *splittable label sequences* that partition the weight space into T^d-1 regions (of equal sign for the scalar product of weights and features), coupled with tools from analytic combinatorics (e.g., Mellin transforms and the saddle-point method) and discrete geometry.

We study the common continual learning setup where an overparameterized model is sequentially fitted to a set of jointly realizable tasks. We analyze forgetting, defined as the loss on previously seen tasks, after k iterations. For continual linear models, we prove that fitting a task is equivalent to a single stochastic gradient descent (SGD) step on a modified objective. We develop novel last-iterate SGD upper bounds in the realizable least squares setup and leverage them to derive new results for continual learning. Focusing on random orderings over T tasks, we establish universal forgetting rates, whereas existing rates depend on problem dimensionality or complexity and become prohibitive in highly overparameterized regimes. In continual regression with replacement, we improve the best existing rate from 𝒪((d-r̅)/k) to 𝒪(min(1/√(k), √(d-r̅)/k, √(Tr̅)/k)), where d is the dimensionality and r̅ the average task rank. Furthermore, we establish the first rate for random task orderings without replacement. The resulting rate of 𝒪(min(1/√(T), (d-r̅)/T)) shows that randomization alone, without task repetition, prevents catastrophic forgetting in sufficiently long task sequences. Finally, we prove a matching 𝒪(1/√(k)) forgetting rate for continual linear classification on separable data. Our universal rates extend to broader methods, such as block Kaczmarz and POCS, illuminating their loss convergence under i.i.d. and single-pass orderings.

In the context of learning hypergraphs with shortest-path queries (SP-queries), we present the first provably optimal online algorithm for learning a broad and natural class of hypertrees which we call orderly hypertrees. Our online algorithm can be transformed into a provably optimal offline algorithm. Orderly hypertrees can be positioned within the Fagin hierarchy of hypergraph acyclicity (studied in database theory), and strictly encompass the broadest class in this hierarchy that is learnable with subquadratic SP-query complexity. Our results also motivate the study of a new type of query, called dependency query (D-query), which is weaker than an SP-query. Positive and negative results on D-queries shed light on the structural properties of classes of hypertrees for which efficient learning requires the full information provided by SP-queries.

We study the benefits of sparsity in nonparametric contextual bandit problems, in which the set of candidate features is countably or uncountably infinite. Our contribution is two-fold. First, using a novel reduction to sequences of multi-armed bandit problems, we provide lower bounds on the minimax regret, which show that polynomial dependence on the number of actions is generally unavoidable in this setting. Second, we show that a variant of the Feel-Good Thompson Sampling algorithm enjoys regret bounds that match our lower bounds up to logarithmic factors of the horizon, and have logarithmic dependence on the effective number of candidate features. When we apply our results to kernelised and neural contextual bandits, we find that sparsity enables better regret bounds whenever the horizon is large enough relative to the sparsity and the number of actions.

The sample complexity of estimating or maximising an unknown function in a reproducing kernel Hilbert space is known to be linked to both the effective dimension and the information gain associated with the kernel. While the information gain has an attractive information-theoretic interpretation, the effective dimension typically results in better rates. We introduce a new quantity called the relative information gain, which measures the sensitivity of the information gain with respect to the observation noise. We show that the relative information gain smoothly interpolates between the effective dimension and the information gain, and that the relative information gain has the same growth rate as the effective dimension. In the second half of the paper, we prove a new PAC-Bayesian excess risk bound for Gaussian process regression. The relative information gain arises naturally from the complexity term in this PAC-Bayesian bound. We prove bounds on the relative information gain which depend on the spectral properties of the kernel. When these upper bounds are combined with our excess risk bound, we obtain minimax-optimal rates of convergence.

To address the needs of modeling uncertainty in sensitive machine learning applications, the setup of distributionally robust optimization (DRO) seeks good performance uniformly across a variety of tasks. The recent multi-distribution learning (MDL) framework <cit.> tackles this objective in a dynamic interaction with the environment, where the learner has sampling access to each target distribution. Drawing inspiration from the field of pure-exploration multi-armed bandits, we provide distribution-dependent guarantees in the MDL regime, that scale with suboptimality gaps and result in superior dependence on the sample size when compared to the existing distribution-independent analyses. We investigate two non-adaptive strategies, uniform and non-uniform exploration, and present non-asymptotic regret bounds using novel tools from empirical process theory. Furthermore, we devise an adaptive optimistic algorithm, LCB-DR, that showcases enhanced dependence on the gaps, mirroring the contrast between uniform and optimistic allocation in the multi-armed bandit literature. We also conduct a small synthetic experiment illustrating the comparative strengths of each strategy.

We consider the fundamental problem of estimating a discrete distribution on a domain of size K with high probability in Kullback-Leibler divergence. We provide upper and lower bounds on the minimax estimation rate, which show that the optimal rate is between (K + ln(K)ln(1/δ)) /n and (Klnln(K) + ln(K)ln(1/δ)) /n at error probability δ and sample size n, which pins down the rate up to the doubly logarithmic factor lnln K that multiplies K. Our upper bound uses techniques from online learning to construct a novel estimator via online-to-batch conversion. Perhaps surprisingly, the tail behavior of the minimax rate is worse than for the squared total variation and squared Hellinger distance, for which it is (K + ln(1/δ)) /n, i.e. without the ln K multiplying ln (1/δ). As a consequence, we cannot obtain a fully tight lower bound from the usual reduction to these smaller distances. Moreover, we show that this lower bound cannot be achieved by the standard lower bound approach based on a reduction to hypothesis testing, and instead we need to introduce a new reduction to what we call weak hypothesis testing. We investigate the source of the gap with other divergences further in refined results, which show that the total variation rate is achievable for Kullback-Leibler divergence after all (in fact by the maximum likelihood estimator) if we rule out outcome probabilities smaller than O(ln(K/δ) / n), which is a vanishing set as n increases for fixed K and δ. This explains why minimax Kullback-Leibler estimation is more difficult than asymptotic estimation.

Learning effective pricing strategies is crucial in digital marketplaces, especially when buyers’ valuations are unknown and must be inferred through interaction. We study the online contextual pricing problem, where a seller observes a stream of context–valuation pairs and dynamically sets prices. Moreover, departing from traditional online learning frameworks, we consider a strategic setting in which buyers may misreport valuations to influence future prices—a challenge known as strategic overfitting (Amin et al., 2013). We introduce a strategy-robust notion of regret for multi-buyer online environments, capturing worst-case strategic behavior in the spirit of the Price of Anarchy. Our first contribution is a polynomial-time approximation scheme (PTAS) for learning linear pricing policies in adversarial, adaptive environments, enabled by a novel online sketching technique. Building on this result, we propose our main construction: the Sparse Update Mechanism (SUM), a simple yet effective sequential mechanism that ensures robustness to all Nash equilibria among buyers. Moreover, our construction yields a black-box reduction from online expert algorithms to strategy-robust learners.

We provide a general framework to improve trade-offs between the number of _full batch_ and _sample_ queries used to solve structured optimization problems. Our results apply to a broad class of randomized optimization algorithms that iteratively solve sub-problems to high accuracy. We show that such algorithms can be modified to _reuse the randomness_ used to query the input across sub-problems. Consequently, we improve the trade-off between the number of gradient (full batch) and individual function (sample) queries for finite sum minimization, the number of matrix-vector multiplies (full batch) and random row (sample) queries for top-eigenvector computation, and the number of matrix-vector multiplies with the transition matrix (full batch) and generative model (sample) queries for optimizing Markov Decision Processes. To facilitate our analysis we introduce the notion of _pseudo-independent algorithms_, a generalization of pseudo-deterministic algorithms (Gat and Goldwasser 2011) that quantifies how independent the output of a randomized algorithm is from a randomness source.

We study language generation in the limit – introduced by Kleinberg and Mullainathan – building on classical works of Gold and Angluin. Kleinberg’s and Mullainathan’s main result is an algorithm for generating from any countable language collection in the limit. While their algorithm eventually generates unseen strings from the target language K, it sacrifices coverage or breadth, i.e., its ability to generate a rich set of strings. Recent work introduces different notions of breadth and explores when generation with breadth is possible, leaving a full characterization of these notions open. Our first set of results settles this by characterizing generation for existing notions of breadth and their natural combinations. Interestingly, our lower bounds are very flexible and extend to many performance metrics beyond breadth – for instance, showing that, in general, it is impossible to train generators that achieve a higher perplexity or lower hallucination rate for K compared to other languages. Next, we study language generation with breadth with stable generators – which eventually stop changing after seeing an arbitrary but finite number of strings – and prove unconditional lower bounds for stable generators – strengthening the results of Kalavasis, Mehrotra, and Velegkas – and surprisingly demonstrating that generation with many existing notions of breadth becomes equally hard, when stability is required. This gives a separation for generation with approximate breadth, between stable and unstable generators, highlighting the rich interplay between breadth, stability, and consistency in language generation.

We study generalization in an overparameterized continual linear regression setting, where a model is trained with L2 (isotropic) regularization across a sequence of tasks. We derive a closed-form expression for the expected generalization loss in the high-dimensional regime that holds for arbitrary linear teachers. We demonstrate that isotropic regularization mitigates label noise under both single-teacher and multiple i.i.d. teacher settings, whereas prior work accommodating multiple teachers either did not employ regularization or used memory-demanding methods. Furthermore, we prove that the optimal fixed regularization strength scales nearly linearly with the number of tasks T, specifically as T/ln T. To our knowledge, this is the first such result in theoretical continual learning. Finally, we validate our theoretical findings through experiments on linear regression and neural networks, illustrating how this scaling law affects generalization and offering a practical recipe for the design of continual learning systems.

Given a list X∼𝒩(0,I_n) of numbers, the random number partitioning problem (NPP) seeks a partition σ∈ -1,1^n with a small H(σ)=1/√(n)|⟨σ,X⟩|. The NPP has been extensively studied in computer science, probability and combinatorics; it is also closely linked to covariate balancing and randomized controlled trials. We introduce a planted version of the random NPP: fix a σ* and generate X∼𝒩(0,I_n) conditional on H(σ^*)≤ 3^-n. The random and planted models are statistically distinguishable, since in the former case min_σH(σ)=Θ(√(n)2^-n) w.h.p. We first analyze the values of H(σ). We show that, perhaps surprisingly, planting does not yield partitions with objective values substantially smaller than 2^-n: we have min_σ±σ* H(σ) = Θ(2^-n) w.h.p. Moreover, we precisely characterize the minimal H(σ) achievable at any fixed distance from σ^*. Turning to the algorithmic problem, we ask whether one can efficiently find a partition σ with small H(σ). We prove that planted NPP exhibits the multi Overlap Gap Property (m-OGP) at scales 2^-Θ(n). Building on this barrier, we show that stable algorithms satisfying a natural anti-concentration property cannot find partitions with H(σ)=2^-Θ(n). This is the first instance where the m-OGP rules out stable algorithms in a planted setting. Our results demonstrate that the multi OGP framework, previously developed for unplanted models, extends naturally to planted ones when the goal is to recover low-objective solutions. They further point to a statistical–computational gap: although the random and planted NPP are statistically distinguishable, we conjecture that no polynomial-time algorithm can distinguish them with nontrivial advantage. Our results demonstrate that planted NPP harbors intriguing features and it is a particularly promising model for probing algorithmic barriers in planted problems.

We study context-conditioned reliability in Dawid–Skene (DS) models and propose a DS-compatible parameterization in which a log-linear correction to confusion logits is softmax-renormalized over reported labels, yielding valid, interpretable confusion matrices conditioned on covariates. We derive a KL-proximal (mirror-descent) update for confusion matrices that warm-starts at DS and provably yields monotone ascent of a standard EM surrogate. Under diagonal-dominance at warm start and mild covariate excitation, we prove identifiability up to permutation; for the correction head we give a finite-sample generalization bound of order O(√(dlog(dK)/n)) via Rademacher complexity. The formulation drops into vanilla EM, preserves DS interpretability, and supports physics-inspired priors (e.g., monotonicity) without breaking guarantees. Empirical validation on multi-agent label fusion confirms monotone convergence and calibration improvements with minimal overhead.

We present differentially private (DP) algorithms for bilevel optimization, a problem class that received significant attention lately in various machine learning applications. These are the first algorithms for such problems under standard DP constraints, and are also the first to avoid Hessian computations which are prohibitive in large-scale settings. Under the well-studied setting in which the upper-level is not necessarily convex and the lower-level problem is strongly-convex, our proposed gradient-based (ϵ,δ)-DP algorithm returns a point with hypergradient norm at most 𝒪((√(d_up)/ϵ n)^1/2+(√(d_low)/ϵ n)^1/3) where n is the dataset size, and d_up/d_low are the upper/lower level dimensions. Our analysis covers constrained and unconstrained problems alike, accounts for mini-batch gradients, and applies to both empirical and population losses. As an application, we specialize our analysis to derive a simple private rule for tuning a regularization hyperparameter.

We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into the dataset. These added points are constrained to be monotone corruptions, in that they get labeled according to the ground-truth target function. Perhaps surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can be made to achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. On the other hand, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.

We introduce a new replicable boosting algorithm which significantly improves the sample complexity compared to previous algorithms. First, we create an improved version of the replicable boosting algorithm introduced by Impagliazzo et al. (2022). We then use this algorithm with a constant accuracy parameter and run another layer of boosting on top to achieve the desired accuracy. This outer layer of boosting is inspired by the classical AdaBoost algorithm while capping the weights for a smoother distribution over the data which we show ensures replicability.

Learning probability distributions is one of the most basic statistical learning tasks. While for many learning tasks learnability of a class can be characterized by a combinatorial dimension (like the VC-dimension for binary classification prediction), no such characterization is known for classes of probability distributions. A leap toward resolving this long-standing problem was made recently by Lechner and Ben-David who showed that there can be no scale invariant characterization of PAC style learnability of such classes. The question of scale sensitive characterization remained open. In this paper we fully resolve the question by showing that there can be no scale sensitive combinatorial characterization of PAC style learnability of classes of probability distributions.