AI Theory

This paper introduces the Strategic Littlestone Dimension, a novel complexity measure for online strategic classification, proving instance-optimal mistake bounds in the realizable setting and improve…

Strategic agents gaming recommender systems is solved by a novel mechanism that incentivizes truthful behavior while minimizing regret, offering a solution to a key challenge in online learning.

Stochastic zeroth-order optimization of strongly convex functions with Lipschitz Hessian achieves optimal sample complexity, as proven by matching upper and lower bounds with a novel two-stage algorit…

New streaming algorithms for instrumental variable regression achieve fast convergence rates, solving the problem efficiently without matrix inversions or mini-batches, enabling real-time causal analy…

Stochastic Optimal Control Matching (SOCM) significantly reduces errors in stochastic optimal control by learning a matching vector field using a novel iterative diffusion optimization technique.

A novel algorithm significantly improves stochastic optimal control by accurately modeling sensorimotor noise, achieving substantially lower costs than current state-of-the-art solutions, particularly…

Stochastic Newton Proximal Extragradient (SNPE) achieves faster global and local convergence rates for strongly convex functions, improving upon existing stochastic Newton methods by requiring signifi…

Stochastic extragradient with flip-flop shuffling & anchoring achieves provably faster convergence in minimax optimization.

Stochastic Concept Bottleneck Models (SCBMs) revolutionize interpretable ML by efficiently modeling concept dependencies, drastically improving intervention effectiveness and enabling CLIP-based conce…

Stochastic Amortization accelerates feature and data attribution by training amortized models using noisy, yet unbiased, labels, achieving order-of-magnitude speedups over existing methods.

Stepwise Alignment for Constrained Policy Optimization (SACPO) efficiently aligns LLMs with human values, prioritizing both helpfulness and harmlessness via a novel stepwise approach.

Density estimation algorithms face inherent trade-offs: reducing sample needs often increases query time. This paper proves these trade-offs are fundamental, showing limits to how much improvement is…

Researchers can now reliably benchmark classifiers using multiple quality metrics via the GSD-front, a new information-efficient technique that accounts for statistical uncertainty and deviations from…

Quantum Approximate Optimization Algorithm (QAOA) achieves weak recovery in spiked tensor models matching classical methods, but with potential constant factor advantages for certain parameters.

Regularized Kernel Kullback-Leibler divergence solves the original KKL’s disjoint support limitation, enabling comparison of any probability distributions with a closed-form solution and efficient gra…

Deep ReLU networks trained with large, constant learning rates avoid overfitting in univariate regression due to minima stability, generalizing well even with noisy labels.

Sharper ASGD generalization bounds achieved by leveraging on-average model stability, even without Lipschitz and smoothness assumptions; validated with diverse machine learning models.

This paper provides novel theoretical guarantees for adversarial training of shallow neural networks, improving generalization bounds via early stopping and Moreau’s envelope smoothing.

Spectral graph pruning simultaneously mitigates over-squashing and over-smoothing in GNNs via edge deletion, improving generalization.

Revolutionizing inverse problem solving, this paper introduces diffusion optimal control, a novel framework converting signal recovery into a discrete optimal control problem, surpassing limitations o…