AI Theory

This paper proves Nesterov’s Accelerated Gradient achieves faster convergence for rectangular matrix factorization and linear neural networks, using a novel unbalanced initialization.

ProTransformer robustifies transformers with a novel plug-and-play attention mechanism, significantly improving robustness across various tasks and domains without retraining.

This paper introduces proportionally fair non-centroid clustering, achieving fairness guarantees via novel algorithms and auditing methods, demonstrating significant improvements over traditional meth…

This paper reveals the surprising connection between individual and proportional fairness in clustering, showing that any approximation to one directly implies an approximation to the other, enabling …

This paper presents novel algorithms for online matching markets that prioritize fairness among dynamic agents, achieving asymptotic optimality in various scenarios and offering extensions to group-le…

Prod-family algorithms achieve optimal regret in adversarial multi-armed bandits, disproving prior suboptimality conjectures.

PrivCirNet accelerates private deep learning inference by cleverly transforming DNN weights into circulant matrices, converting matrix-vector multiplications into efficient 1D convolutions suitable fo…

Achieving near-optimal rates for differentially private stochastic convex optimization with heavy-tailed gradients is possible using simple reduction-based techniques.

New transformation boosts privacy in online learning!

This paper introduces new differentially private algorithms to compute the geometric median, achieving improved accuracy by scaling with the effective data diameter instead of a known radius.

This paper delivers a groundbreaking polynomial-time algorithm for optimally estimating edge density in random graphs while ensuring node privacy and robustness against data corruption.

This paper presents novel, privacy-preserving algorithms achieving near-optimal rates for solving stochastic saddle point problems and variational inequalities in non-Euclidean geometries.

Train high-quality generative models with strong differential privacy using a novel slicing mechanism that injects noise into random low-dimensional data projections, avoiding noisy gradients.

Researchers reveal ‘privacy backdoors,’ a new attack that exploits pre-trained models to leak user training data, highlighting critical vulnerabilities and prompting stricter model security measures.

This paper introduces a Bayesian approach to setting the privacy budget in differential privacy, enabling agencies to balance data utility and confidentiality by customizing risk profiles.

COBOL: a novel Bayesian Optimization algorithm leverages human expert advice via binary labels, achieving both fast convergence and robustness to noisy input, while guaranteeing minimal expert effort.

Position coupling, a novel method, enhances the length generalization ability of arithmetic Transformers by directly embedding task structures into positional encodings. This simple technique enables…

POSEIDON: a novel foundation model for PDEs achieves significant gains in accuracy and sample efficiency, generalizing well to unseen physics.

This paper introduces efficient algorithms that leverage social choice theory to aggregate multiple individual preferences, resulting in a desirable collective AI policy.

Learning-augmented mechanisms for fair allocation achieve constant-factor approximation with accurate predictions and near-optimal approximation even with inaccurate ones.