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

Fast, Parallel, Query-Efficient Binary Classification

Ishani Karmarkar, Liam O'Carroll, Aaron Sidford

We study the fundamental classification problem of computing a separating hyperplane for a binary-labeled dataset of size n with normalized d-dimensional features. Letting Φ∈ℝ^n × d denote the feature matrix and γ the margin of the maximum-margin separating hyperplane, we present a randomized algorithm that solves this problem in Õ(γ^-2/3 nnz(Φ) + γ^-2(ω+1)/3)-sequential running time (work), Õ(γ^-2/3)-parallel (computational) depth, and accesses Φ only through Õ(γ^-2/3)-matrix-vector queries (matvecs). We also present a second, faster randomized algorithm with a Õ(γ^-2/3 nnz(Φ) + γ^-2)-sequential running time that uses Õ(γ^-2/3)-matvecs to Φ, but achieves only Õ(γ^-4/3)-parallel depth. Both algorithms match the near-optimal deterministic matvec complexity recently established by Kornowski and Shamir [2025], Karmarkar et al. [2026] and achieve improved sequential runtime and parallel depth, albeit at the expense of using randomness.

COLT 2026

Can SGD Select Good Fishermen? Local Convergence under Self-Selection Biases (Extended Abstract)

Alkis Kalavasis, Anay Mehrotra, Felix Zhou

We revisit the problem of estimating k linear regressors in d dimensions from samples affected by self-selection bias under the maximum selection rule. Our main result is an algorithm with sample complexity O(d)·poly(k,1/ε) and running time poly(d,k,1/ε)+(klog k)^O(k) for recovering the regressors up to joint squared error ε^2. The key ingredient is the first local-convergence algorithm for the maximum self-selection model. Our approach reduces self-selection to estimation from coarse observations, where the learner observes only the cell of a partition containing the latent sample. The self-selection reduction induces a structured non-convex partition. We prove that this partition preserves enough information locally and that the resulting negative log-likelihood is locally convex around the true parameters. These two geometric properties allow projected stochastic gradient descent, initialized from an existing warm start, to obtain the stated end-to-end guarantee.

COLT 2026

Ripple Mechanisms for Discrete and Private Statistics

Matthew Joseph, Alex Kulesza, Yuyan Wang, Alexander Yu

We study ripple mechanisms for pure differentially private computation of discrete statistics. For each of three natural statistics – sum, count, and vote – we construct an efficient instance of the ripple mechanism and show that it is often more accurate than the previous state of the art. We also prove that ripple mechanisms are, in some settings, optimal among all discrete pure differentially private additive noise mechanisms.

COLT 2026

Avoiding exp(k^*) Scaling for Thompson Sampling in Combinatorial Semi-Bandits: From Multiple Seeds to a Single Seed

Tianyuan Jin, Heyang Zhao, Vincent Y. F. Tan, Quanquan Gu

The Combinatorial Multi-Armed Bandit (CMAB) framework extends classical multi-armed bandit theory to complex decision-making settings where agents select super arms to maximize a collective reward. While Thompson Sampling (TS) is widely favored for its robust empirical performance in these settings, its theoretical guarantees have historically suffered from a significant bottleneck: standard Combinatorial Thompson Sampling () incurs a regret bound with an exponential dependence on the size k^* of the optimal super-arm. This exponential term arises because standard independent posterior sampling fails to coordinate optimism across the base arms of the optimal super arm, causing the probability of exploration to vanish as k^* increases. Although recent advances have achieved polynomial regret for linear rewards, designing an efficient TS algorithm for general, non-linear CMABs remains an open challenge. In this paper, we resolve this open question by proposing Combinatorial Thompson Sampling with a Single Seed (). Unlike standard approaches that sample base arms independently, employs a comonotonic coupling strategy: it generates parameters for all base arms using a single shared random seed via the inverse CDF transform. This mechanism synchronizes sampling fluctuations across arms, ensuring concerted optimism and preventing the exploration probability from decaying exponentially. We prove that achieves a regret bound of O( m kk^*B^2/Δ_min(log(T,m,Δ_max/Δ_min))) for general reward functions satisfying monotonicity and bounded smoothness, where m is the number of total base arms, k is the largest super arm size, and k^* is size of the optimal arm. To the best of our knowledge, this is the first polynomial regret bound for Thompson Sampling in general CMAB settings. Empirical evaluations confirm that significantly outperforms standard independent TS, particularly in regimes with large super arms.

COLT 2026

Adaptive Matrix Online Learning through Smoothing with Guarantees for Nonsmooth Nonconvex Optimization

Ruichen Jiang, Zakaria Mhammedi, Mehryar Mohri, Aryan Mokhtari

We study online linear optimization with matrix variables constrained by the operator norm, a setting where the geometry renders designing data-dependent and efficient adaptive algorithms challenging. The best-known adaptive regret bounds are achieved by Shampoo-like methods, but they require solving a costly quadratic projection subproblem. To address this, we extend the gradient-based prediction scheme to adaptive matrix online learning and cast algorithm design as constructing a family of smoothed potentials for the nuclear norm. We define a notion of admissibility for such smoothings and prove any admissible smoothing yields a regret bound matching the best-known guarantees of one-sided Shampoo. We instantiate this framework with two efficient methods that avoid quadratic projections. The first is an adaptive Follow-the-Perturbed-Leader (FTPL) method using Gaussian stochastic smoothing. The second is Follow-the-Augmented-Matrix-Leader (FAML), which uses a deterministic hyperbolic smoothing in an augmented matrix space. By analyzing the admissibility of these smoothings, we show both methods admit closed-form updates and match one-sided Shampoo’s regret up to a constant factor, while significantly reducing computational cost. Lastly, using the online-to-nonconvex conversion, we derive two matrix-based optimizers, Pion (from FTPL) and Leon (from FAML). We prove convergence guarantees for these methods in nonsmooth nonconvex settings, a guarantee that the popular Muon optimizer lacks.

COLT 2026

Low-Degree Method Fails to Predict Robust Subspace Recovery

He Jia, Aravindan Vijayaraghavan

The low-degree polynomial framework has been highly successful in predicting computational versus statistical gaps for high-dimensional problems in average-case analysis and machine learning. This success has led to the low-degree conjecture, which posits that this method captures the power and limitations of efficient algorithms for a wide class of high-dimensional statistical problems. We identify a natural and basic hypothesis testing problem in ℝ^n which is polynomial time solvable, but for which the low-degree polynomial method fails to predict its computational tractability even up to degree k=n^Ω(1). Moreover, the low-degree moments match exactly up to degree k=O(√(log n/loglog n)). Our problem is a special case of the well-studied robust subspace recovery problem. The lower bounds suggest that there is no polynomial time algorithm for this problem. In contrast, we give a simple and robust polynomial time algorithm that solves the problem (and noisy variants of it), leveraging anti-concentration properties of the distribution. Our results suggest that the low-degree method and low-degree moments fail to capture algorithms based on anti-concentration, challenging their universality as a predictor of computational barriers.

COLT 2026

Sharp analysis of linear ensemble sampling

David Janz, Arya Akhavan, Csaba Szepesvari

We analyse linear ensemble sampling (ES) with standard Gaussian perturbations in stochastic linear bandits. We show that for ensemble size m=Θ(dlog n), ES attains Õ(d^3/2√(n)) high-probability regret, closing the gap to the Thompson sampling benchmark while keeping computation comparable. The proof brings a new perspective on randomized exploration in linear bandits by reducing the analysis to a time-uniform exceedance problem for m independent Brownian motions. This continuous-time lens appears particularly natural here: it yields an exact representation of the relevant discrete-time processes, and we do not know another route to a sharp ES bound.

COLT 2026

On the Importance of Randomization in Discriminative Feature Feedback

Valentio Iverson, Tosca Lechner, Sivan Sabato

Discriminative Feature Feedback (DFF) (Dasgupta et al., 2018) is an interactive learning protocol in which a learner attempts to predict labels based on online feedback about previous correct labels, as well as discriminative features. Recent work (Bar Oz et al., 2025) studied DFF learning with general teacher classes and defined a dimension that characterizes the optimal mistake bound for deterministic algorithms in the realizable setting. In this work, we show that in sharp contrast to Online Learning, in DFF there can be an unbounded ratio between the optimal mistake bound of deterministic algorithms and that of randomized algorithms, even in the realizable setting. We further show that in this case, also non-realizable learning can have a mistake bound that does not depend on the dimension at all. This result relies on a new algorithmic technique that allows introducing new candidate hypotheses incrementally and could be of independent interest. We further show that in DFF, there can be a significant difference between the obtainable mistake bounds against an oblivious adversary and against an adaptive adversary, again in contrast to Online Learning. Our work shows that once richer feedback than labels is allowed, the landscape of randomized versus deterministic algorithms becomes significantly more involved, and raises new questions on characterizing the optimal mistake bound under differing randomization regimes.

COLT 2026

Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret

Shinji Ito, Haipeng Luo, Arnab Maiti, Taira Tsuchiya, Yue Wu

Learning to play zero-sum games is a fundamental problem in game theory and machine learning. While significant progress has been made in minimizing external regret in the self-play settings or with full-information feedback, real-world applications often force learners to play against unknown, arbitrary opponents and restrict learners to bandit feedback where only the reward of the realized action is observable. In such challenging settings, it is well-known that Ω(√(T)) external regret is unavoidable (where T is the number of rounds). To overcome this barrier, we investigate adversarial learning in zero-sum games under bandit feedback, aiming to minimize the deficit against the maximin pure strategy — a metric we term Pure-Strategy Maximin Regret. We analyze this problem under two bandit feedback models: uninformed (only the realized reward is revealed) and informed (both the reward and the opponent’s action are revealed). For uninformed bandit learning of normal-form games, we show that the Tsallis-INF algorithm achieves 𝒪(c log T) instance-dependent regret with a game-dependent parameter c. Crucially, we prove an information-theoretic lower bound showing that the dependence on c is necessary. To overcome this hardness, we turn to the informed setting and introduce Maximin-UCB, which obtains another regret bound of the form 𝒪(c’ log T) for a different game-dependent parameter c’ that could potentially be much smaller than c. Finally, we generalize both results to bilinear games over an arbitrary, large action set, proposing Tsallis-FTRL-SPM and Maximin-LinUCB for the uninformed and informed settings respectively and establishing similar game-dependent logarithmic regret bounds.

COLT 2026

On Randomized Algorithms in Online Strategic Classification

Chase Hutton, Adam Melrod, Han Shao

Online strategic classification studies settings in which agents strategically modify their features to obtain favorable predictions. For example, given a classifier that determines loan approval based on credit scores, applicants may open or close credit cards and bank accounts to obtain a positive prediction. The learning goal is to achieve low mistake or regret bounds despite such strategic behavior. While randomized algorithms have the potential to offer advantages to the learner in strategic settings, they have been largely underexplored. In the realizable setting, no lower bound is known for randomized algorithms, and existing lower bound constructions for deterministic learners can be circumvented by randomization. In the agnostic setting, the best known regret upper bound is O(T^3/4log^1/4(T|ℋ|)) due to Ahmadi et al. (2023), which is far from the standard online learning rate of O(√(Tlog|ℋ|)). In this work, we provide refined upper and lower bounds for online strategic classification in both the realizable and agnostic settings; our bounds depend on the Littlestone dimension Ldim(ℋ) of the hypothesis class ℋ and the maximum degree Δ of the manipulation graph. In the realizable setting, using a new construction, we prove a lower bound that, for T > Ldim(ℋ) Δ^2, extends the existing deterministic lower bound of Ω(Ldim(ℋ) Δ) to all algorithms. This is the first lower bound that applies to randomized algorithms, resolving an open question of Ahmadi et al. (2023). We also give the first randomized algorithm that improves on the known deterministic upper bound of O(Ldim(ℋ)·ΔlogΔ), achieving O(√(T·Ldim(ℋ)logΔ)) expected mistakes, in the regime T < Ldim(ℋ) Δ^2logΔ. In the agnostic setting, we give an improper randomized algorithm with expected regret O(√(Tlog|ℋ|)) against adaptive adversaries, improving upon the previous O(T^3/4log^1/4(T|ℋ|)) bound and matching the standard online learning rate. We also prove that this optimal rate requires improper learning.

COLT 2026

Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction

Lunjia Hu, Kevin Tian, Chutong Yang

Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses ℒ against a family of comparator predictors 𝒞. We initiate the study of omniprediction in a multiclass setting, where the comparator family 𝒞 may be infinite. Our main result is an extension of the recent binary omniprediction algorithm of Okoroafor et al. (2025) to the multiclass setting, with sample complexity (in statistical settings) or regret horizon (in online settings) ≈ε^-(k+1), for ε-omniprediction in a k-class prediction problem. En route to proving this result, we design a framework of potential broader interest for solving Blackwell approachability problems where multiple sets must simultaneously be approached via coupled actions.

COLT 2026

Recovery of Planted Subgraphs

Wasim Huleihel

Understanding the fundamental limits of recovering planted subgraphs in random graphs is a central challenge in high-dimensional statistics and theoretical computer science. While existing work has largely focused on special subgraph families such as cliques, bicliques, or dense blocks, the exact recovery of a general planted subgraph in Erdős–Rényi random graphs remains poorly understood. In this paper, we study the exact recovery of an arbitrary planted subgraph Γ = Γ_n embedded in a dense Erdős–Rényi random graph 𝒢(n,q_n), where edges within Γ are present independently with probability p_n > q_n. Our main results identify sharp conditions under which exact recovery is possible with high probability, and we establish matching lower bounds showing the necessity of these conditions. The resulting statistical threshold is characterized by a new graph-theoretic quantity, which we term the minimal maximum subgraph density. This quantity is defined as the maximum subgraph density of the smallest induced balanced subgraph of Γ. We then turn to the problem of recovery under polynomial-time constraints. We propose a computationally efficient recovery algorithm that applies to arbitrary planted subgraphs and analyze its performance in terms of certain spectral properties of the adjacency matrix. In addition, we derive computational lower bounds for recovery using the low-degree polynomial framework, establishing regimes where recovery is statistically possible but computationally hard. Finally, we consider several extensions of our setting, including recovery in semi-random models and weaker notions of recovery.

COLT 2026

Almost Linear Convergence under Minimal Score Assumptions: Quantized Transition Diffusion

Xunpeng Huang, Yingyu Lin, Lijing Kuang, Hanze Dong, Difan Zou, Yian Ma, Tong Zhang

Continuous diffusion models have demonstrated remarkable generative performance across diverse domains but are often constrained by the computational cost of simulating reverse Ornstein–Uhlenbeck processes via SDE/ODE solvers. Existing theoretical results typically establish query complexities that scale polynomially with both the dimension d and the error tolerance ϵ (e.g., 𝒪̃(d/ϵ)). This mirrors the limitations of unadjusted Langevin algorithm, where standard first-order score solvers lack access to zeroth-order density information, precluding natural error-correction mechanisms and thus preventing the fast ln(1/ϵ) convergence attainable by Metropolis-adjusted methods. In this paper, we develop an improved generative modeling method by introducing Quantized Transition Diffusion (QTD), a framework that reformulates continuous diffusion into a discrete generation problem through spatial quantization and the parameterization of zeroth-order information (e.g., density ratios). To sample from this discrete target, we propose a truncated uniformization algorithm that simulates the underlying continuous-time Markov chain of the discrete diffusion process without discretization error, while eliminating the restrictive bounded-score assumption required by prior uniformization-based approaches. Consequently, QTD attains ϵ-accuracy in total variation distance with a query complexity of 𝒪(d ln^2(d/ϵ)), yielding a notable improvement in ϵ-dependence compared to existing continuous diffusion samplers. Crucially, our analysis capitalizes on a novel proof technique based on the infinitesimal chain rule of KL divergence, providing a fresh perspective on unifying continuous and discrete diffusion paradigms.

COLT 2026

Reconstructing Riemannian Metrics From Random Geometric Graphs

Han Huang, Pakawut Jiradilok, Elchanan Mossel

Random geometric graphs are random graph models defined on metric measure spaces. A random geometric graph is generated by first sampling points from a metric space and then connecting each pair of sampled points independently with a probability that depends on their distance. In recent work of Huang, Jiradilok, and Mossel, the authors study the problem of reconstructing an embedded manifold from a random geometric graph sampled from the manifold, where edge probabilities depend monotonically on the Euclidean distance between the embedded points. They show that, under mild regularity assumptions on the manifold, the sampling measure, and the connection probability function, it is possible to recover the pairwise Euclidean distances of the embedded sampled points up to a vanishing error as the number of vertices grows. In this work we consider a similar and arguably more natural problem where the metric is the Riemannian metric on the manifold. Again points are sampled from the manifold and a random graph is generated where the connection probability is monotone in the Riemannian distance. Perhaps surprisingly we obtain stronger results in this setup. Unlike the previous work that only considered dense graph we provide reconstruction algorithms from sparse graphs with average degree n^1/2polylog(n), where n denotes the number of vertices. Our algorithm is also a more efficient algorithm for distance reconstruction with improved error bounds. The local distance-estimation part runs in O(n^2polylog(n)) time, and the final all-pairs shortest-path step gives an overall running time of O(n^3). Our distance error also nearly matches the volumetric lower bounds for distance estimation.

COLT 2026

Wasserstein Policy Learning for Distributional Outcomes

Yiyan HUANG, Cheuk Hang LEUNG, Qi Wu, Zhiheng Zhang

Offline policy learning has received growing attention in causal inference. The primary objective is to learn a policy (individualized treatment rule) as a mapping from covariates to treatment that maximizes the empirical welfare defined as the mean of scalar-valued potential outcomes. In this paper, we study offline policy learning with distribution-valued outcomes, where each potential outcome is a probability measure on ℝ and the reward is defined through a utility functional applied to the Wasserstein barycenter of induced outcome distributions. We establish statistical guarantees for the policy learning framework based on both Inverse Probability Weighting (IPW) and Doubly Robust (DR) estimators. By handling the challenging uniform deviation over the product of the combinatorial policy class and the infinite-dimensional quantile domain, we prove that the finite-sample regret has leading dependence 𝒪(√(N-dim(Π)/N)). In the one-dimensional Wasserstein setting and under the stated regularity conditions, the leading regret rate is still governed by the policy-class complexity. Moreover, we provide a minimax lower bound establishing the sharpness of the leading dependence on N and N-dim(Π).

COLT 2026

Efficient Swap Multicalibration of Elicitable Properties

Lunjia Hu, Haipeng Luo, Spandan Senapati, Vatsal Sharan

Multicalibration (Hébert-Johnson et al., 2018) is an algorithmic fairness perspective which demands that the predictions of a predictor are correct conditional on themselves and membership in a collection of potentially overlapping subgroups of a population. The work of Noarov and Roth (2023) established a surprising connection between multicalibration for an arbitrary property Γ (e.g., mean or median) and property elicitation: a property Γ can be multicalibrated if and only if it is elicitable, where elicitability is the notion that the true property value of a distribution can be obtained by solving a regression problem over the distribution. In the adversarial (online) setting, Noarov and Roth (2023) proposed an inefficient algorithm that achieves 𝒪̃(√(T)) ℓ_2-multicalibration error for a hypothesis class of group membership functions and an elicitable property Γ, after T rounds of interaction between a forecaster and adversary. In this paper, we generalize multicalibration for an elicitable property Γ from group membership functions to arbitrary bounded hypothesis classes and introduce a stronger notion—swap multicalibration, following Gopalan et al. (2023b). Subsequently, we propose an oracle-efficient algorithm which when given access to an online agnostic learner, achieves 𝒪̃(T^1/r+1) ℓ_r-swap multicalibration error with high probability (r ≥ 2) for a hypothesis class with bounded sequential Rademacher complexity and an elicitable property Γ. For the special case of r = 2, this implies an oracle-efficient algorithm that achieves 𝒪̃(T^1/3) ℓ_2-swap multicalibration error, which significantly improves on the previously established bounds for the problem (Noarov and Roth, 2023; Ghuge et al., 2025; Luo et al., 2025a), and completely resolves an open question raised in Garg et al. (2024) on the possibility of an oracle-efficient algorithm that achieves 𝒪̃(√(T)) ℓ_2-mean multicalibration error by answering it in a strongly affirmative sense.

COLT 2026

Near-optimal Swap Regret Minimization for Convex Losses

Lunjia Hu, Jon Schneider, Yifan Wu

We give a randomized online algorithm that guarantees near-optimal O(√(T)) expected swap regret against any sequence of T adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of O(T^2/3) and answers an open question from prior work. In addition, our algorithm is efficient: it runs in polynomial time. A key technical idea we develop to obtain this result is to discretize the unit interval into bins at multiple scales of granularity and simultaneously use all scales to make randomized predictions, which we call multi-scale binning and may be of independent interest. A direct corollary of our result is an efficient online algorithm for minimizing the calibration error for general elicitable properties. This result does not require the Lipschitzness assumption of the identification function needed in prior work, making it applicable to median calibration, for which we achieve the first O(√(T)) calibration error guarantee.

COLT 2026

Recovery thresholds for hidden weighted sparse graphs (extended abstract)

Zhe Hou, Jingcheng Liu

Recovering structural information from noisy high-dimensional data is a fundamental task in statistical inference. We investigate the information-theoretic recovery thresholds for a graph hidden in a randomly weighted complete graph. Specifically, an unknown graph H^* ∈ℋ_n is chosen uniformly at random, and hidden in a complete graph of n vertices through edge weights: for an edge e ∈ H^*, its weight is distributed independently according to 𝒫_n; otherwise the edge weight is distributed independently according to 𝒬_n. The goal is to recover the hidden edge set from these noisy observations. Our primary focus on almost exact recovery, where all but a vanishing fraction of the edges of H^* must be identified. By choosing 𝒫 = Bern(1), 𝒬 = Bern(q), this model captures the well-studied planted Erdős-Rényi recovery setting, and other weighted formulations such as Gaussian and Exponential distributions. Assuming a local Lipschitzness of the Rényi divergence between distributions 𝒫_n and 𝒬_n, and a mild density condition for the graphs ℋ_n, we give a unified characterization of the information-theoretic limit for recovering almost all of H (also known as almost exact recovery). Our characterization uses the KL divergence D_KL(𝒫_n𝒬_n) as the signal-to-noise metric. We show that there is a critical threshold D_c governed by the logarithm of the first moment threshold of ℋ_n in the Erdős-Rényi random graph model G(n,p). For any constant η, if D_KL≥ (1+η)D_c, the maximum likelihood estimator (MLE) achieves almost exact recovery; conversely if D_KL≤ (1-η)D_c, almost exact recovery is information-theoretically impossible. Our MLE analysis is based on an extension of (Jian Ding, Yihong Wu, Jiaming Xu, Dana Yang, 2020); While our lower bound involves deriving a distance-based Fano-type inequality based on Sibson’s α-mutual information, and it also extends to the task of partial recovery, in which only a constant λ-fraction of the hidden graph is required to be recovered. As a result, if D_KL≤ (λ-η)D_c, we also proved that the recovery of any λ-fraction must fail with high probability. Another interesting phenomenon exhibited by some of these models is the “All-or-Nothing” (AoN), where one can either recover almost all of the hidden graph or essentially nothing at all. For several natural distributional families, including certain Gaussian, Bernoulli and Exponential regimes, we establish an All-or-Nothing (AoN) threshold phenomenon at the exponential scale. For Gaussians, we obtained an AoN by lifting the sharp almost exact recovery threshold through the I-MMSE relation; For the others, we combine a second-moment argument inspired by planted subgraph recovery (Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn, Nike Sun, Ilias Zadik, 2023) with the second-order Rényi divergence. We also provide distributional examples where AoN is not universal at this level of generality, and our partial recovery lower bound is already the best possible.

COLT 2026

Uniform Laws of Large Numbers in Product Spaces

Ron Holzman, Shay Moran, Alexander Shlimovich

Uniform laws of large numbers form a cornerstone of Vapnik–Chervonenkis theory, where they are characterized by the finiteness of the VC dimension. In this work, we study uniform convergence phenomena in cartesian product spaces, under assumptions on the underlying distribution that are compatible with the product structure. Specifically, we assume that the distribution is absolutely continuous with respect to the product of its marginals, a condition that captures many natural settings, including product distributions, sparse mixtures of product distributions, distributions with low mutual information, and more. We show that, under this assumption, a uniform law of large numbers holds for a family of events if and only if the linear VC dimension of the family is finite. The linear VC dimension is defined as the maximum size of a shattered set that lies on an axis-parallel line, namely, a set of vectors that agree on all but at most one coordinate. This dimension is always at most the classical VC dimension, yet it can be arbitrarily smaller. For instance, the family of convex sets in ℝ^d has linear VC dimension 2, while its VC dimension is infinite already for d ≥ 2. Our proofs rely on an estimator that departs substantially from the standard empirical mean estimator and exhibits a more intricate structure. We show that such deviations from the standard empirical mean estimator are unavoidable in this setting. Throughout the paper, we propose several open questions, with a particular focus on quantitative sample complexity bounds.

COLT 2026

A Perfectly Truthful Calibration Measure

Jason Hartline, Lunjia Hu, Yifan Wu

Calibration requires that predictions are conditionally unbiased and, therefore, reliably interpretable as probabilities. A calibration measure quantifies how far a predictor is from perfect calibration. A calibration measure is truthful if it is minimized in expectation when a predictor outputs the ground-truth probabilities. Predicting the true probabilities guarantees perfect calibration, but in reality, when calibration is evaluated on a random sample, all known calibration measures incentivize predictors to lie in order to appear more calibrated. This lack of truthfulness motivated approximately truthful calibration measures in the sequential prediction setting, but no perfectly truthful calibration measure was known to exist even in the more basic batch setting. We design a simple, perfectly and strictly truthful, sound, and complete calibration measure in the batch setting: Averaged Two-Bin Calibration Error (ATB). ATB is quadratically related to two existing calibration measures: the smooth calibration error and the lower distance to calibration. The simplicity of our definition of ATB makes it efficient and straightforward to compute, allowing us to give the first linear-time calibration testing algorithm. We also introduce a general recipe for constructing truthful measures based on the variance additivity of independent random variables, which proves the truthfulness of ATB as a special case and allows us to construct other truthful calibration measures, such as quantile-binned ℓ_2 Expected Calibration Error (ECE).

Keep browsing

More papers from top AI conferences

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