AI Theory

A novel inventory reserving algorithm achieves near-optimal performance for bandit problems with knapsacks in piecewise-stationary settings, offering a competitive ratio of O(log(nmax/min)).

Spectral distances on k-nearest neighbor graphs enable robust topological analysis of high-dimensional noisy data using persistent homology, overcoming limitations of Euclidean distance.

In n-player games, a satisficing path always exists leading from any initial strategy profile to a Nash equilibrium by allowing unsatisfied players to explore suboptimal strategies.

This paper introduces a novel technique to bound prediction risks in new domains using causal diagrams, enabling reliable AI performance guarantees.

Learning optimal interventions in causal bandits with unknown causal graphs is now efficient; this paper identifies the minimal causal knowledge needed and offers a two-stage algorithm with sublinear …

Partially observing neural circuits during experiments can create misleading models, even if single neuron activity matches; researchers need better validation methods.

First parameterized approximation schemes for fair-range k-median & k-means in Euclidean spaces are presented, offering faster (1+ε)-approximation algorithms.

SGD’s dynamics are precisely characterized by the interplay of noise and symmetry in loss functions, leading to unique, initialization-independent fixed points.

New PAC-Bayes oracle bound extends Cramér-Chernoff to unbounded losses, enabling exact parameter optimization and richer assumptions for tighter generalization bounds.

OxonFair: a new open-source toolkit for enforcing fairness in binary classification, supporting NLP, Computer Vision, and tabular data, optimizing any fairness metric, and minimizing performance degra…

Ridgeless regression, surprisingly, generalizes well even with noisy data if dimension scales sub-polynomially with sample size.

This research introduces a novel framework that overcomes the brittleness of Pareto-optimal learning-augmented algorithms by enforcing smoothness in performance using user-specified profiles and devel…

Outlier-robust distributionally robust optimization achieved via a novel Unbalanced Optimal Transport (UOT) distance, improving efficiency and accuracy.

OT4P: a novel temperature-controlled differentiable transformation efficiently relaxes permutation matrices onto the orthogonal group for gradient-based optimization.

One-shot label-only attack (OSLO) achieves high membership inference accuracy with only one query, surpassing existing methods by a large margin.

Causal discovery algorithm CaPS efficiently handles mixed linear and nonlinear relationships in observational data, outperforming existing methods on synthetic and real-world datasets.

This paper introduces computationally efficient algorithms for differentially private learning by leveraging public data, overcoming previous computational limitations and enabling broader practical a…

Two novel algorithms, Local-Greedy and Greedy-Grid, optimize coalition gain in online auctions with limited observations, achieving constant regret and problem-independent guarantees while respecting …

Optimization can learn optimal Johnson-Lindenstrauss embeddings, avoiding the limitations of randomized methods and achieving comparable theoretical guarantees.

Design provably convergent optimization algorithms swiftly using electric circuit analogies; a novel methodology automating discretization for diverse algorithms.