AI Theory

Extrapolated FTRL ensures Nash equilibrium convergence in harmonic games, defying standard no-regret learning limitations.

This paper solves the open problem of achieving no-regret learning in online multi-agent Nash social welfare maximization.

No free lunch for adversarial optimization: This paper proves that no single algorithm universally outperforms others when finding Nash Equilibrium, introducing black-box complexity analysis to estab…

Passive data collection in complex social systems invalidates standard AI model validation; new methods are needed.

Nimbus achieves 2.7-4.7x speedup in BERT base inference using novel two-party computation techniques for efficient matrix multiplication and non-linear layer approximation.

Neural Pfaffians revolutionize many-electron Schrödinger equation solutions by using fully learnable neural wave functions based on Pfaffians, achieving unprecedented accuracy and generalizability acr…

Neural Persistence Dynamics learns collective behavior from topological features, accurately predicting parameters of governing equations without tracking individual entities.

Accelerate molecular simulations using neural network reparametrization! This flexible method adjusts system complexity, enhances optimization, and maintains continuous access to fine-grained modes, o…

SGD can train neural networks to learn low-dimensional polynomials near the information-theoretic limit, surpassing previous correlational statistical query lower bounds.

Neural networks revolutionize hardware model checking by generating formal proof certificates, outperforming state-of-the-art techniques in speed and scalability.

Neural networks efficiently solve robust routing problems with uncertain travel times, minimizing worst-case deviations from optimal routes under the min-max regret criterion.

Deep neural collapse, previously believed optimal, is shown suboptimal in multi-class, multi-layer networks due to a low-rank bias, yielding even lower-rank solutions.

NEUR2BILO: a neural network-based heuristic solves mixed-integer bilevel optimization problems extremely fast, achieving high-quality solutions for diverse applications.

AGNES, a novel accelerated gradient descent algorithm, achieves accelerated convergence even with very noisy gradients, significantly improving training efficiency for machine learning models.

This paper presents a new auditing method for DP-SGD that provides substantially tighter black-box privacy analyses than previous methods, yielding significantly closer empirical estimates to theoreti…

Lanczos-FA, a simple algorithm for approximating matrix functions, surprisingly outperforms newer methods; this paper proves its near-optimality for rational functions, explaining its practical succes…

This research establishes the first minimax optimal algorithm for submodular maximization with bandit feedback, achieving a regret bound matching the lower bound.

This paper presents OFU-MNL+, a constant-time algorithm achieving nearly minimax optimal regret for contextual multinomial logistic bandits, closing the gap between existing upper and lower bounds.

Clipped SGD achieves near-optimal sub-Gaussian rates for high-dimensional heavy-tailed statistical estimation in streaming settings, improving upon existing state-of-the-art results.

Sparse navigable graphs enable efficient nearest neighbor search, but their construction and limits in high dimensions remain unclear. This paper presents an efficient method to construct navigable gr…