AI Theory

Optimal multi-objective optimization achieved via hypervolume scalarization, offering sublinear regret bounds and outperforming existing methods.

This paper closes the performance gap in parallel boosting algorithms by presenting improved lower bounds and a novel algorithm matching these bounds, settling the parallel complexity of sample-optima…

This paper proves the minimax optimal U-calibration error is Θ(√KT) for online multiclass prediction, resolving an open problem and showing logarithmic error is achievable for specific loss functions.

This paper presents the first almost linear-time algorithm achieving the optimal accuracy parameter for hypothesis selection, solving a decades-long open problem.

This paper introduces a novel push-forward model for performative learning, proving the convexity of performative risk under new assumptions and linking performative learning to adversarial robustness…

Optimal algorithms for online convex optimization with adversarial constraints are developed, achieving O(√T) regret and Õ(√T) constraint violation—a breakthrough in the field.

Optimal algorithms for learning partitions are designed, achieving minimum query complexity even with up to l faulty oracle responses.

Leveraging predictions, this research presents novel algorithms for uniformity, identity, and closeness testing of discrete distributions, achieving information-theoretically optimal sample complexity…

Optimal ablation (OA) improves model interpretability by precisely measuring component importance, outperforming existing methods. OA-based importance shines in circuit discovery, factual recall, and …

Predictive coding networks learn faster than backpropagation by changing the loss landscape’s geometry, making saddles easier to escape and improving robustness to vanishing gradients.

First algorithm for online weighted paging that learns page weights from samples, achieving optimal O(log k) competitiveness and sublinear regret.

New algorithms conquer delayed feedback in online choice modeling, achieving optimal decision-making even with unknown customer preferences and delayed responses.

This paper introduces a novel information-theoretic framework, showing how to convert offline into online estimation algorithms efficiently, impacting interactive decision-making.

Algorithm RESET achieves optimal switching regret simultaneously across all segmentations, offering efficiency and parameter-free operation.

The 1-nearest neighbor rule achieves online consistency under surprisingly broad conditions: measurable label functions and mild assumptions on instance generation in doubling metric spaces.

Researchers achieve optimal regret bounds in online composite optimization under stochastic and adversarial settings using a novel optimistic composite mirror descent algorithm and a universal strateg…

MetaAd, a novel meta-algorithm, achieves provable competitive ratios for online budgeted matching with general bids, removing prior restrictive assumptions.

Researchers developed a novel online Bayesian persuasion algorithm that achieves sublinear regret without prior knowledge of the receiver or the state distribution, providing tight theoretical guarant…

One-layer transformers provably learn the one-nearest neighbor prediction rule, offering theoretical insights into their in-context learning capabilities.

One-Sample-Fits-All (OFA) framework efficiently approximates all probabilistic values simultaneously, achieving faster convergence rates than existing methods.