AI conference papers

AI conference paper library

Search papers from 30+ top conferences, including NeurIPS, ICLR, ICML, CVPR, ACL and AAAI. Filter by keyword, then open any paper for its abstract, authors and links.

COLT 2026

Learning Periodic Strategies in Blocking Bandits Is as Hard as Bandits with Switching Costs

Nicolo Cesa-Bianchi, Junya Honda, Yuko Kuroki, Atsushi Miyauchi, Lukas Zierahn

In blocking K-armed bandits, playing an arm renders it unavailable for a fixed number of future rounds. While this model is relatively well understood in the stochastic regime, much less is known when rewards are generated adversarially. Via a novel reduction, we first show that computing the total reward of the best dynamic policy is NP-hard, even when the blocking time d > 1 is identical across arms. We therefore turn to tractable comparators and study the class of d-periodic policies, proving that the optimal periodic policy is efficiently computable and always obtains at least a 1/K fraction of the dynamic optimum. We also show that this 1/K factor is information-theoretically tight: no algorithm can achieve sublinear α-regret with respect to the offline optimal dynamic policy for any α > 1/K. Our main result shows that T^2/3 is the minimax rate for the regret (against periodic policies) for adversarial blocking bandits with identical blocking times, and that this rate is achievable by an efficient algorithm. Our main technical contribution is the lower bound, which establishes that blocking bandits are at least as hard as bandits with switching costs. The matching upper bound instead follows from a reduction to combinatorial semi-bandits over bipartite matchings. Finally, we show that √(T) regret rates are efficiently achievable in the full information setting, and more generally via α-regret with α = 1/2.

COLT 2026

Phase Transition for Stochastic Block Model with more than √(n) Communities

Alexandra Carpentier, Christophe Giraud, Nicolas Verzelen

Predictions from statistical physics postulate that recovery of the communities in the Stochastic Block Model (SBM) with a fixed number K of communities is possible in polynomial time above, and only above, the Kesten-Stigum (KS) threshold. This conjecture has given rise to a rich literature, proving that non-trivial community recovery is indeed possible in SBM above the KS threshold. Failure of low-degree polynomials (LDP) below the KS threshold was also proven, as long as K≪√(n), where n is the number of nodes in the observed graph. When K≥√(n), Chin et al. (2025) recently proved that, in a sparse regime, community recovery in polynomial time is possible below the KS threshold by counting non-backtracking paths. This breakthrough led them to postulate a new threshold for the many-communities regime K≥√(n). In this work, we provide evidence supporting their conjecture: 1- We prove that, for any graph density, LDP fail to recover communities below the threshold postulated by Chin et al. (2025) ; 2- We prove that community recovery is possible in polynomial time above the postulated threshold, not only in the sparse regime considered in Chin et al. (2025), but also in moderately sparse regimes, by counting occurrences of some specific motifs inspired by the LDP analysis. In particular, counting self-avoiding paths of length log(n)—which is closely related to spectral algorithms based on the Non-Backtracking operator—is optimal only in the sparse regime. More complex motifs based on the blow-up of a cycle must be considered in denser regimes.

COLT 2026

Universal priors: solving empirical Bayes via Bayesian inference and pretraining

Nick Cannella, Anzo Teh, Yanjun Han, Yury Polyanskiy

We theoretically justify the recent empirical finding of Teh et al. (2025) that a transformer pretrained on synthetically generated data achieves strong performance on empirical Bayes (EB) problems. We take an indirect approach to this question: rather than analyzing the model architecture or training dynamics, we ask why a pretrained Bayes estimator, trained under a prespecified training distribution, can adapt to arbitrary test distributions. Focusing on Poisson EB problems, we identify the existence of universal priors such that training under these priors yields a near-optimal regret bound of O(1/n) uniformly over all test distributions. Our analysis leverages the classical phenomenon of posterior contraction in Bayesian statistics, showing that the pretrained Bayes estimator adapts to unknown test distributions precisely through posterior contraction. This perspective also explains the phenomenon of length generalization, in which the test sequence length exceeds the training length, as the model performs Bayesian inference using a fractional posterior.

COLT 2026

Active Learning on Adversarially Corrupted Graphs

Marco Bressan, Nicolo Cesa-Bianchi, Tommaso d’Orsi, Emmanuel Esposito, Silvio Lattanzi

Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of corrupted vertices inside a graph G^*. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and G^*, and its power is then measured by the size of the neighborhood of the corrupted vertices in G^*. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the vertex expansion of G^*, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.

COLT 2026

Learning Conditional Averages

Marco Bressan, Nataly Brukhim, Nicolo Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, Maximilian Thiessen

We introduce the problem of learning conditional averages in the PAC framework. The learner receives a sample labeled by an unknown target concept from a known concept class, as in standard PAC learning. However, instead of learning the target concept itself, the goal is to predict, for each instance, the average label over its neighborhood—an arbitrary subset of points that contains the instance. In the degenerate case where all neighborhoods are singletons, the problem reduces exactly to classic PAC learning. More generally, it extends PAC learning to a setting that captures learning tasks arising in several domains, including explainability, fairness, and recommendation systems. Our main contribution is a complete characterization of when conditional averages are learnable, together with sample complexity bounds that are tight up to logarithmic factors. The characterization hinges on the joint finiteness of two novel combinatorial parameters, which depend on both the concept class and the neighborhood system, and are closely related to the independence number of the associated neighborhood graph.

COLT 2026

Learning from Equivalence Queries, Revisited

Mark Braverman, Roi Livni, Yishay Mansour, Shay Moran, Kobbi Nissim

Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deploying a model, observing user interactions, and updating the model intermittently based on feedback. This mode of learning contrasts with common supervised learning frameworks, which focus on loss or regret minimization over a shared sequence of prediction tasks. Motivated by this deployment-driven learning cycle, we revisit the classical model of learning from equivalence queries, introduced by Angluin, which provides a simple abstraction of such interactions: a learner repeatedly proposes hypotheses and, whenever the deployed hypothesis is inadequate, receives a counterexample tailored to that hypothesis. Under fully adversarial counterexample generation, however, this model exhibits overly pessimistic worst-case behavior. Moreover, most existing work on learning from equivalence queries considers the full-information setting, where the learner observes not only a counterexample but also its correct label. This is an assumption that does not always align with natural interactive settings. To address these considerations, we restrict the environment to generate counterexamples in a less adversarial manner by introducing a broad class of counterexample generators, which we call symmetric. Informally, such symmetric counterexample generators select counterexamples based only on the symmetric difference between the hypothesis and the target, and encompass natural feedback mechanisms such as random counterexamples, as well as generators that select counterexamples minimizing a prescribed complexity measure over the instance space. Within this framework, we study learning from equivalence queries under both full-information and bandit feedback. We establish tight bounds on the number of learning rounds in both settings and outline directions for future research. Our techniques rely on a game-theoretic perspective on symmetric adversaries and combine adaptive weighting algorithms with minimax arguments.

COLT 2026

Tight list replicability bounds via a novel sphere covering theorem

Ari Blondal, Hamed Hatami, Pooya Hatami, Chavdar Lalov, Sivan Tretiak

In recent years, list replicability has emerged as a framework for formalizing reproducibility in learning theory. A central question is how the required list size relates to the accuracy parameter and natural complexity measures of the hypothesis class. To achieve sharp bounds on list replicability, we prove a novel topological sphere covering theorem, derived from the Borsuk-Ulam theorem. Specifically, if the d-sphere is covered by open sets, each of which lies in an open hemisphere, then d+1 of these sets must have a common intersection. Using this result, we obtain a sharp bound on the relationship between list size and accuracy for VC classes. We also show that for large-margin half-spaces, provided the margin is not too large, the optimal list size equals the ambient dimension. However, when the margin is taken to be very large, we devise a replicable algorithm achieving the minimal list size of ⌈ d/2 ⌉ + 1.

COLT 2026

Partition Function Estimation under Bounded f-Divergence

Adam Block, Abhishek Shetty

We study the statistical complexity of estimating partition functions given sample access to a proposal distribution and an unnormalized density ratio for a target distribution. While partition function estimation is a classical problem, existing guarantees typically rely on structural assumptions about the domain or model geometry. We instead provide a general, information-theoretic characterization that depends only on the relationship between the proposal and target distributions. Our analysis introduces the integrated coverage profile, a functional that quantifies how much target mass lies in regions where the density ratio is large. We show that integrated coverage tightly characterizes the sample complexity of multiplicative partition function estimation and provide matching lower bounds. We further express these bounds in terms of f-divergences, yielding sharp phase transitions depending on the growth rate of f and recovering classical results as a special case while extending to heavy-tailed regimes. Matching lower bounds establish tightness in all regimes. As applications, we derive improved finite-sample guarantees for importance sampling and self-normalized importance sampling, and we show a strict separation between the complexity of approximate sampling and counting under the same divergence constraints. Our results unify and generalize prior analyses of importance sampling, rejection sampling, and heavy-tailed mean estimation, providing a minimal-assumption theory of partition function estimation. Along the way we introduce new technical tools including new connections between coverage and f-divergences as well as a generalization of the classical Paley-Zygmund inequality.

COLT 2026

Characterizing Online and Private Learnability under Distributional Constraints via Generalized Smoothness

Moise Blanchard, Abhishek Shetty, Alexander Rakhlin

Understanding minimal assumptions that enable learning and generalization is perhaps the central question of learning theory. Several celebrated results in statistical learning theory, such as the VC theorem and Littlestone’s characterization of online learnability, establish conditions on the hypothesis class that allow for learning under independent data and adversarial data, respectively. Building upon recent work bridging these extremes, we study sequential decision making under distributional adversaries that can adaptively choose data-generating distributions from a fixed family 𝒰 and ask when such problems are learnable with sample complexity that behaves like the favorable independent case. We provide a near complete characterization of families 𝒰 that admit learnability in terms of a notion known as generalized smoothness, i.e., a distribution family admits VC-dimension-dependent regret bounds for every finite-VC hypothesis class if and only if it is generalized smooth. Further, we give universal algorithms that achieve low regret under any generalized smooth adversary without explicit knowledge of 𝒰. Finally, when 𝒰 is known, we provide refined bounds in terms of a combinatorial parameter, the fragmentation number, that captures how many disjoint regions can carry nontrivial mass under 𝒰. These results provide a nearly complete understanding of learnability under distributional adversaries. In addition, building upon the surprising connection between online learning and differential privacy, we show that the generalized smoothness also characterizes private learnability under distributional constraints.

COLT 2026

Actively Learning Halfspaces without Synthetic Data

Hadley Black, Kasper Green Larsen, Arya Mazumdar, Barna Saha, Geelon So

In the classic point location problem, one is given an arbitrary dataset X in d-dimensional Euclidean space R^d of n points with query access to an unknown halfspace f: R^d -> 0,1, and the goal is to learn the label of every point in X. This problem is extremely well-studied and a nearly-optimal Õ(d log n) query algorithm is known due to Hopkins-Kane-Lovett-Mahajan (FOCS 2020). However, their algorithm is granted the power to query arbitrary points outside of X (point synthesis), and in fact without this power there is an Ω(n) query lower bound due to Dasgupta (NeurIPS 2004). Nonetheless, query access to arbitrary synthesized data points is unrealistic in many contexts. Our objective in this work is to design efficient algorithms for learning halfspaces without point synthesis. To circumvent the Ω(n) lower bound, we consider learning halfspaces whose normal vectors come from a known set of size D, and show tight bounds Θ(D + log n). As a corollary, we obtain an optimal O(d + log n) query deterministic learner for the fundamental class of decision stumps (depth-one decision trees, or axis-aligned halfspaces), closing a previous gap of O(d log n) vs. Ω(d + log n) left open in the active learning literature. In fact, our algorithm solves the more general problem of learning a Boolean function f over n elements which is monotone under at least one of D provided orderings of these elements. Our technical insight is to exploit the structure in these orderings to essentially perform a binary search in parallel rather than considering each ordering sequentially, and we believe our approach may be of broader interest. Furthermore, we use our exact learning algorithm to obtain nearly optimal algorithms for PAC-learning. We show that O(min(D + log(1/ϵ), 1/ϵ) * log D) queries suffice to learn f within error ϵ, even in a setting when f can be adversarially corrupted on a cϵ-fraction of points, for a sufficiently small constant c. This bound is optimal up to a log D factor, including in the realizable setting.

COLT 2026

Adaptive Weighted Averaging

Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, Manish Purohit

We study the problem of selecting the largest among n unknown values x_1,…,x_n given only a single unbiased estimate y_i for each x_i. We design strategies that are simultaneously admissible (not uniformly dominated by any other strategy) and also never worse than a given baseline such as uniform random selection. We provide an application to stochastic optimization, where we obtain online-to-batch conversion bounds with a desirable “no-compromise” guarantee: they are never worse than standard random iterate selection, and yet can be significantly better in benign settings.

COLT 2026

Omniprediction with Long-Term Constraints

Yahav Bechavod, Jiuyao Lu, Aaron Roth

We introduce and study the problem of online omniprediction with long-term constraints. At each round, a forecaster is tasked with generating predictions for an underlying (adaptively, adversarially chosen) state that are broadcast to a collection of downstream agents, who must each choose an action. Each of the downstream agents has both a utility function mapping actions and state to utilities, and a vector-valued constraint function mapping actions and states to vector-valued costs. The utility and constraint functions can arbitrarily differ across downstream agents. Their goal is to choose actions that guarantee themselves no regret while simultaneously guaranteeing that they do not cumulatively violate the constraints across time. We show how to make a single set of predictions so that each of the downstream agents can guarantee this by acting as a simple function of the predictions, guaranteeing each of them Õ(|𝒜|√(T)) regret and O(|𝒜|) cumulative constraint violation for a finite action space 𝒜. We also show how to extend our guarantees to arbitrary intersecting contextually defined subsequences, guaranteeing each agent both regret and constraint violation bounds not just marginally, but simultaneously on each subsequence, against a benchmark set of actions simultaneously tailored to each subsequence.

COLT 2026

Algorithmic Thinking Theory

Mohammadhossein Bateni, Vincent Cohen-Addad, Yuzhou Gu, Silvio Lattanzi, Simon Meierhans, Christopher Mohri

Large language models (LLMs) have proven to be highly effective for solving complex reasoning tasks. Surprisingly, their capabilities can often be improved by iterating on previously generated solutions. In this context, a reasoning plan for generating and combining a set of solutions can be thought of as an algorithm for reasoning using a probabilistic oracle. We introduce a theoretical framework for analyzing such reasoning algorithms. This framework formalizes the principles underlying popular techniques for iterative improvement and answer aggregation, providing a foundation for designing a new generation of more powerful reasoning methods. Unlike approaches for understanding models that rely on architectural specifics, our model is grounded in experimental evidence. As a result, it offers a general perspective that may extend to a wide range of current and future reasoning oracles.

COLT 2026

Limitations of SGD for Multi-Index Models Beyond Statistical Queries

Daniel Barzilai, Ohad Shamir

Understanding the limitations of gradient methods, and stochastic gradient descent (SGD) in particular, is a central challenge in learning theory. To that end, a commonly used tool is the Statistical Queries (SQ) framework, which studies performance limits of algorithms based on noisy interaction with the data. However, it is known that the formal connection between the SQ framework and SGD is tenuous: Existing results typically rely on adversarial or specially-structured gradient noise that does not reflect the noise in standard SGD, and (as we point out here) can sometimes lead to incorrect predictions. Moreover, many analyses of SGD for challenging problems rely on non-trivial algorithmic modifications, such as restricting the SGD trajectory to the sphere or using very small learning rates. To address these shortcomings, we develop a new, non-SQ framework to study the limitations of standard vanilla SGD, for single-index and multi-index models (namely, when the target function depends on a low-dimensional projection of the inputs). Our results apply to a broad class of settings and architectures, including (potentially deep) neural networks.

COLT 2026

Cloning is as Hard as Learning for Stabilizer States

Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan

The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for n-qubit stabilizer states, we show that the optimal sample complexity of cloning is Θ(n). Thus, also for this structured class of states, cloning is as hard as learning. To prove this result, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.

COLT 2026

Variational Tail Bounds for Norms of Random Vectors and Matrices

Sohail Bahmani

We propose a variational tail bound for norms of random vectors and matrices under moment assumptions on their one-dimensional marginals. A simplified version of the bound that parametrizes the “aggregating distribution” using a certain pushforward of the Gaussian distribution is also provided. We apply the proposed method to reproduce some of the well-known bounds on norms of Gaussian random vectors, and also obtain dimension-free tail bounds for the Euclidean norm of random vectors with arbitrary moment profiles. Furthermore, we reproduce a dimension-free concentration inequality for sum of independent and identically distributed positive semidefinite matrices with sub-exponential marginals, and obtain a concentration inequality for the sample covariance matrix of sub-exponential random vectors. We also obtain a tail bound for the operator norm of a random matrix series whose random coefficients may have arbitrary moment profiles. Furthermore, we use coupling to formulate an abstraction of the proposed approach that applies more broadly. As a corollary, we derive a PAC-Bayesian-style bound in terms of a certain combination of the KL and Rényi divergences between the prior and posterior distributions.

COLT 2026

A Complexity Measure for Active Learning in Multi-group Mean Estimation

Abdellah Aznag, Rachel Cummings, Adam N. Elmachtoub

We study a max-risk objective for active learning in d-armed bandits: a learner adaptively allocates a budget of T samples across d groups to minimize the worst-case per-group uncertainty index max_k∈[d]σ_k^2/n_k. We develop a local minimax framework and prove the first general lower bound for this objective, valid for any finite-variance hypothesis class ℋ. The bound separates difficulty into three orthogonal factors: a budget term, a heteroscedasticity index measuring how unevenly the uncertainty is spread across arms, and a model-dependent curvature functional, the Variance Local Curvature (VLC), which captures how much information a local change of variance creates inside ℋ. For smooth classes, the VLC is a reparametrization of a variance–Fisher information, with closed-form values for common families. Benchmarking against the strongest available upper bound shows near-optimality up to logarithmic factors in broad regimes, and pinpoints a systematic gap in highly heterogeneous instances. Our proof introduces two key ingredients: a loss-induced ℓ_1 geometry on the decision space, and a representation-based instance generator that reduces hard-instance construction to an explicit random matrix calculation.

COLT 2026

Margin in Abstract Spaces

Yair Ashlagi, Roi Livni, Shay Moran, Tom Waknine

Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structure underlies this phenomenon. We begin with a simple margin-based problem in arbitrary metric spaces: concepts are defined by a center point and classify points according to whether their distance lies below r or above R. We show that whenever R>3r, this class is learnable in any metric space. Thus, sufficiently large margins make learnability rely only on the triangle inequality, without any linear or analytic structure being necessary. Our first main result extends this phenomenon to concepts defined by bounded linear combinations of distance functions, and reveals a sharp threshold: there exists a universal constant such that whenever the margin is larger than this constant, the class is learnable in every metric space, while below it there exist metric spaces where it is not learnable at all. We then ask whether margin-based learnability can always be explained via an embedding into a linear space – that is, reduced to linear classification in some Banach space through a kernel-type construction. We answer this negatively by demonstrating a margin learnable class that cannot be embedded into any Banach space in which linear classification with margins is learnable.

COLT 2026

Strongly Polynomial Time Complexity of Policy Iteration for L_∞ Robust MDPs

Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady, Mehrdad Karrabi, Alipasha Montaseri, Carlo Pagano

Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilities and optimizing against the worst-case realization of that uncertainty. In particular, (s, a)-rectangular RMDPs with L_∞ uncertainty sets form a fundamental and expressive model: they subsume classical MDPs and turn-based stochastic games. We consider this model with discounted payoffs. The existence of polynomial and strongly-polynomial time algorithms is a fundamental problem for these optimization models. For MDPs, linear programming yields polynomial-time algorithms for any arbitrary discount factor, and the seminal work of Ye established strongly-polynomial time for a fixed discount factor. The generalization of such results to RMDPs has remained an important open problem. In this work, we show that a robust policy iteration algorithm runs in strongly-polynomial time for (s, a)-rectangular L_∞ RMDPs with a constant (fixed) discount factor, resolving an important algorithmic question.

COLT 2026

Learning depth-3 circuits via quantum agnostic boosting

Srinivasan Arunachalam, Arkopal Dutt, Alexandru Gheorghiu, Michael De Oliveira

We initiate the study of quantum agnostic learning of phase states with respect to a function class C ⊆c:0,1^n→0,1: given copies of an unknown n-qubit state |ψ⟩ which has fidelity with a phase state |ϕ_c⟩=1/√(2^n)∑_x∈0,1^n(-1)^c(x)|x⟩ for some c∈ C, output |ϕ⟩ which has fidelity |⟨ϕ | ψ ⟩|^2 ≥-ε. To this end, we give agnostic learning protocols for the following classes: 1. Size-t decision trees which runs in time (n,t,1/ε). This also implies k-juntas can be agnostically learned in time (n,2^k,1/ε). 2. s-term DNF formulas in time (n,(s/ε)^loglog (s/ε) ·log(1/ε)). Our main technical contribution is a quantum agnostic boosting protocol which converts a “weak” agnostic learner, which outputs a parity state |ϕ⟩ such that |⟨ϕ|ψ⟩|^2≥/(n), into a “strong” learner which outputs a superposition of parity states |ϕ’⟩ such that |⟨ϕ’|ψ⟩|^2≥ - ε. Using quantum agnostic boosting, we give a n^O(log(n/ε)·loglog n)-time algorithm for ε-learning (n)-sized depth-3 circuits (consisting of , , gates) in the uniform model given quantum examples. Classically, obtaining an algorithm with a similar complexity has been an open question in the model and our work answers this given quantum examples.

Keep browsing

More papers from top AI conferences

30+ top conferences, by conference, year, and topic.