AI Theory

Deep learning optimization is revolutionized by a new function class, enabling convergence guarantees without over-parameterization and accommodating saddle points.

Generative image restoration models face a critical trade-off: higher perceptual quality often leads to increased hallucinations (unreliable predictions).

This paper enhances prophet inequalities by allowing lookback, improving competitive ratios and providing algorithms for diverse observation orders, thereby bridging theory and real-world online selec…

Recurrent Graph Neural Networks (GNNs) with real and floating-point numbers are precisely characterized by rule-based and infinitary modal logics, respectively, enabling a deeper understanding of thei…

This paper introduces robust Dikin walks for log-concave sampling, achieving faster mixing times and lower iteration costs than existing methods, particularly for high-dimensional settings.

This research unveils a fundamental interplay between local differential privacy (LDP) and robustness against data corruption and heavy-tailed rewards in multi-armed bandits, offering a tight characte…

Localized Adaptive Risk Control (L-ARC) improves fairness and reliability of online prediction by providing localized statistical risk guarantees, surpassing existing methods in high-stakes applicatio…

Unlocking Causal Structures: New algorithms identify latent causal relationships from interventions, even when multiple variables are affected simultaneously.

Causal bandits with unknown graphs and soft interventions are solved by establishing novel upper and lower regret bounds, plus a computationally efficient algorithm.

Under-parameterized linear regression models can surprisingly exhibit double descent, contradicting traditional bias-variance assumptions.

This paper introduces learning-augmented priority queues, using predictions to boost efficiency and optimality, achieving significant performance gains over traditional methods.

Leveraging predictions, this paper presents a novel algorithm for dynamic submodular maximization achieving significantly faster update times (O(poly(log n, log w, log k)) amortized) compared to exist…

This paper shows how noisy predictions about optimal solutions can improve approximation algorithms for NP-hard problems like MAX-CUT, exceeding classical hardness bounds.

This paper introduces a novel framework for learning-augmented algorithms that improves performance by integrating the learning process into the algorithm itself, rather than treating the predictor as…

PFSUM, a novel learning-augmented algorithm, leverages short-term predictions to achieve superior performance in solving the Bahncard problem, outperforming existing methods with improved consistency …

Tighter losses than Fenchel-Young losses are presented, refining Fenchel-Young inequalities using the Fitzpatrick function to improve model accuracy while preserving prediction link functions.

Unlocking complex models’ secrets: New algorithm identifies input interactions using the Möbius Transform, boosting interpretability with surprising speed and accuracy.

Researchers developed Value Classification Model (VCM), a neural solver that swiftly solves quadratic unconstrained binary optimization (QUBO) problems by directly generating solutions using a classif…

Economists learn to resolve externalities efficiently even when players lack perfect information, maximizing social welfare by leveraging bargaining and online learning.

Proactive Infeasibility Prevention (PIP) framework significantly improves neural methods for solving complex Vehicle Routing Problems by proactively preventing infeasible solutions and enhancing const…