COLT 2026 Papers

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.

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.

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.

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.

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.

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.

The study of tail behaviour of -induced processes has been attracting a lot of interest, due to offering strong guarantees with respect to individual runs of an algorithm. While many works provide high-probability guarantees, quantifying the error rate for a fixed probability threshold, there is a lack of work directly studying the probability of failure, i.e., quantifying the tail decay rate for a fixed error threshold. Moreover, existing results are of finite-time nature, limiting their ability to capture the true long-term tail decay which is more informative for modern learning models, typically trained for millions of iterations. Our work closes these gaps, by studying the long-term tail decay of -based methods through the lens of large deviations theory, establishing several strong results in the process. First, we provide an upper bound on the tails of the gradient norm-squared of the best iterate produced by (vanilla) , for non-convex costs and bounded noise, with long-term decay at rate e^-t/log(t). Next, we relax the noise assumption by considering clipped () under heavy-tailed noise with bounded moment of order p ∈ (1,2], showing an upper bound with long-term decay at rate e^-t^β_p/log(t), where β_p = 4(p-1)/3p-2 for p ∈ (1,2) and e^-t/log^2(t) for p = 2. Finally, we provide lower bounds on the tail decay, at rate e^-t, showing that our rates for both and are tight, up to poly-logarithmic factors. Notably, our results demonstrate an order of magnitude faster long-term tail decay compared to existing work based on finite-time bounds, which show rates e^-√(t) and e^-t^β_p/2, p ∈ (1,2], for and , respectively. As such, we uncover regimes where the tails decay much faster than previously known, providing stronger long-term guarantees for individual runs.

We address the problem of training conversion prediction models in advertising domains under privacy constraints, where direct links between ad clicks and conversions are unavailable. Motivated by privacy-preserving browser APIs and the deprecation of third-party cookies, we study a setting where the learner observes a sequence of clicks and a sequence of conversions, but can only link a conversion to a set of candidate clicks (an attribution set) rather than a unique source. We formalize this as learning from attribution sets generated by an oblivious adversary equipped with a prior distribution over the candidates. Despite the lack of explicit labels, we construct an unbiased estimator of the population loss from these coarse signals via a novel approach. Leveraging this estimator, we show that Empirical Risk Minimization achieves generalization guarantees that scale with the informativeness of the prior and is also robust against estimation errors in the prior, despite complex dependencies among attribution sets. Simple empirical evaluations on standard datasets suggest our unbiased approach significantly outperforms common industry heuristics, particularly in regimes where attribution sets are large or overlapping.

We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine based on the sum-of-squares method that finds a low-dimensional separation-preserving projection of the input data. Our method provides a non-spherical analog of the classical dimension reduction based on singular value decomposition that, among several other applications, forms a key component of the celebrated spherical clustering algorithm of Vempala and Wang (2004). As applications, we obtain an algorithm to (1) cluster an arbitrary total-variation separated mixture of k centered (i.e., zero-mean) Gaussians with n≥poly(d) f(w_min^-1) samples and poly(n) time, and (2) cluster an arbitrary total-variation separated mixture of k Gaussians with identical but arbitrary unknown covariance with n ≥ d^O(log w_min^-1) f(w_min^-1) samples and n^O(log w_min^-1) time. Here, w_min is the minimum mixing weight of the input mixture, and f does not depend on the dimension d. Our algorithms naturally extend to tolerate a dimension-independent fraction of arbitrary outliers. Before this work, the techniques in the state-of-the-art non-spherical clustering algorithms needed d^O(k) f(w_min^-1) samples and time for clustering such mixtures. Our results may come as a surprise in the context of the d^Ω(k) statistical query and sum-of-squares lower bounds (Diakonikolas et al. (2017, 2024)) for clustering non-spherical Gaussian mixtures. While these results are usually thought to rule out d^o(k) cost algorithms for the problem, our results show that the lower bounds can, in fact, be circumvented for a remarkably general class of Gaussian mixtures.

We consider the problem of minimizing different notions of swap regret in online optimization. These forms of regret are tightly connected to correlated equilibrium concepts in games, and have been more recently shown to guarantee non-manipulability against strategic adversaries. The only computationally efficient algorithm for minimizing linear swap regret over a general convex set in ℝ^d was developed recently by Daskalakis, Farina, Fishelson, Pipis, and Schneider (STOC ’25). However, it incurs a highly suboptimal regret bound of Ω(d^4 √(T)) and also relies on computationally intensive calls to the ellipsoid algorithm at each iteration. In this paper, we develop a significantly simpler, computationally efficient algorithm that guarantees O(d √(T)) linear swap regret for a general convex set that has been preconditioned via the John ellipsoid. Our algorithm leverages the powerful response-based approachability framework of Bernstein and Shimkin (JMLR ’15)—previously overlooked in the line of work on swap regret minimization—and simultaneously minimizes profile swap regret, which was recently shown to guarantee non-manipulability. Moreover, we establish a matching information-theoretic lower bound: any learner must incur in expectation Ω(d √(T)) linear swap regret for large enough T, even when the set is centrally symmetric. This also shows that the classic algorithm of Gordon, Greenwald, and Marks (ICML ’08) is existentially optimal for minimizing linear swap regret, although it is computationally inefficient. Finally, we extend our approach to minimize regret with respect to the set of swap deviations with polynomial dimension, unifying and strengthening recent results in equilibrium computation and online learning.

We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix 𝐀 given access to matrix-vector product (matvec) queries of the form 𝐱↦𝐀𝐱 and 𝐱↦𝐀^𝐱. This problem is of central importance in scientific computing and machine learning, with applications to structured matrix compression, preconditioning, and as a theoretical model for operator learning. Prior work focuses on obtaining query complexity upper and lower bounds for learning specific structured matrix families that commonly arise in applications. We initiate the study of the problem in greater generality, aiming to understand the query complexity of learning approximations from general matrix families. Our main result focuses on finding a near-optimal approximation to 𝐀 from any finite-sized family of matrices, ℱ. Standard results from matrix sketching show that O(log|ℱ|) matvec queries suffice in this setting. This bound can also be achieved, and is optimal, for vector-matrix-vector queries of the form 𝐱,𝐲↦𝐱^𝐀𝐲, which have been widely studied in work on rank-1 matrix sensing. Surprisingly, we show that it is possible to obtain a nearly quadratic improvement in matvec complexity, to Õ(√(log|ℱ|)) and we prove that this bound is tight up to log-log factors. Via covering number arguments, our result extends to well-studied infinite families. For example, we show that a near-optimal approximation from any linear matrix family of dimension q can be learned with Õ(√(q)) matvec queries, improving on an O(q) bound achievable via sketching techniques.

Independence testing is a fundamental problem in statistical inference: given samples from a joint distribution p over multiple random variables, the goal is to determine whether p is a product distribution or is ϵ-far from all product distributions in total variation distance. In the non-parametric finite-sample regime, this task is notoriously expensive, as the minimax sample complexity scales polynomially with the support size. In this work, we move beyond these worst-case limitations by leveraging the framework of augmented distribution testing. We design independence testers that incorporate auxiliary, but potentially untrustworthy, predictive information. Our framework ensures that the tester remains robust, maintaining worst-case validity regardless of the prediction’s quality, while significantly improving sample efficiency when the prediction is accurate. Our main contributions include: (i) a bivariate independence tester for discrete distributions that adaptively reduces sample complexity based on the prediction error; (ii) a generalization to the high-dimensional multivariate setting for testing the independence of d random variables; and (iii) matching minimax lower bounds demonstrating that our testers achieve optimal sample complexity.

Recent work on “quiet planting” in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted k-SAT, where O(n^k/2) clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for k-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC’22). From a technical standpoint, we generalize the concept of (r-1)-wise uniformness in clause distributions, proving hardness holds if the marginal distribution over negation patterns is (r-1)-wise uniform, and reveal a connection to binary linear codes, demonstrating how a [k, t, r] code can guide the planting of up to 2^t - 1 solutions on k variables with (r-1)-wise uniform negation distributions.

We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number κ. For this fundamental problem, significant gaps remain in our understanding of the trade-offs among sample complexity, condition number, runtime, and prediction error for efficient algorithms. Our first result is a near-linear-time algorithm that uses O(d/ε^4) samples, where d is the dimension and ε is the corruption rate, and achieves prediction error O(√(εκ)) under the condition εκ≲ 1, improving over all prior works. We complement this result with a Statistical Query (SQ) lower bound showing that efficient SQ algorithms achieving error o(√(εκ)) when εκ≲ 1 require queries that take Ω(d^2) samples to simulate. Finally, we prove a low-degree polynomial lower bound that gives fine-grained evidence that, without assumptions such as εκ≲ 1, efficient algorithms may require Ω̃(mindε^2κ^2, ε^2d^2) samples to significantly outperform the trivial estimator that always guesses 0.

Hypothesis selection asks for a distribution close to an unknown P, given samples from P and access to n candidate hypotheses. We study the computational complexity of achieving statistically optimal sample complexity and approximation constants.