AI Theory

This paper reveals significant privacy gaps in shuffling-based DP-SGD, proposes a scalable Poisson subsampling method, and demonstrates its superior utility for private model training.

Researchers achieve a breakthrough in privacy-preserving machine learning by developing sample-efficient algorithms for learning Gaussian Mixture Models, significantly reducing the data needed while m…

Reconstructing geometry from minimal Euclidean distance samples: A novel algorithm achieves state-of-the-art data efficiency with theoretical guarantees.

Boost Bayesian Optimization’s efficiency by leveraging known invariances in objective functions for faster, more effective solutions.

Efficiently learn causal graphs from limited interventions using a novel Bayesian algorithm that outperforms existing methods and requires fewer experiments.

This paper reveals how many buyer samples are needed to set near-optimal posted prices for a single item, resolving a fundamental problem in online markets and offering both theoretical and practical …

First finite-sample analysis of interventional causal representation learning shows that surprisingly few samples suffice for accurate graph and latent variable recovery.

Neural networks enhance algorithm selection in branch-and-cut, significantly reducing tree sizes and improving efficiency for mixed-integer optimization, as proven by rigorous theoretical bounds and e…

This paper presents a computationally efficient algorithm for robustly learning Gaussian single-index models under adversarial label noise, achieving near-optimal sample complexity.

This paper characterizes the fundamental tradeoff between trusting and distrusting learned type beliefs in games, establishing upper and lower bounds for optimal strategies in both normal-form and sto…

A novel safe & sparse Newton method (SSNS) for entropic-regularized optimal transport boasts strict error control, avoids singularity, needs no hyperparameter tuning, and offers rigorous convergence a…

S-SOS: A new algorithm solves complex, parameterized polynomial problems with provable convergence, enabling efficient solutions for high-dimensional applications like sensor network localization.

Rule-Based Rewards (RBRs) enhance LLM safety by using AI feedback and a few-shot prompt-based approach, achieving higher safety-behavior accuracy with less human annotation than existing methods.

ROPINN: Revolutionizing Physics-Informed Neural Networks with Region Optimization

New algorithms achieve near-optimal error rates for sparse linear regression, even under adversarial data corruption and heavy-tailed noise distributions.

R-NeuralUCB: A robust neural contextual bandit algorithm uses a context-aware gradient descent training to defend against adversarial reward corruptions, achieving better performance with theoretical …

Outlier-robust mixture learning gets order-optimal error guarantees, even when outliers massively outnumber small groups, via a novel meta-algorithm leveraging mixture structure.

RUNG: a novel GNN architecture boasting superior robustness against adaptive attacks by employing an unbiased aggregation technique.

ZO-GDEGA: A unified algorithm achieves faster, more robust zeroth-order minimax optimization with lower complexity and weaker conditions, solving stochastic nonconvex-concave problems.

This paper proposes a lightweight and scalable k-mer based model for metagenomic binning, achieving comparable performance to computationally expensive genome foundation models while significantly imp…