232 citations · 453 across the 44 of their papers we have counts for
49 papers
Valid Stopping in Adaptive Generator-Verifier Loops
Mahmoud Hegazy, Michael I. Jordan, Aymeric Dieuleveut
Numerous agentic workflows are based on a generator-verifier loop: a generator proposes candidates, a cheap verifier scores them, and the workflow terminates when a proposal is ver…
Finding Simple Proofs for First-Order Optimization
Daniel Berg Thomsen, Manu Upadhyaya, Baptiste Goujaud +2
Progress in mathematics often requires more than a certificate of truth: it requires proof structures that are transparent, checkable, and reusable. Automated systems can increasin…
Self-Organized Conformal Prediction: Reducing Regional Coverage Gaps with Unsupervised Group Discovery
Louis Berthier, Ahmed Shokry, Maxime Moreaud +2
Conformal prediction guarantees marginal coverage, but a pooled calibration quantile can hide systematic undercoverage across heterogeneous regions of the feature space. We introdu…
A Tight Theory of Error Feedback Algorithms in Distributed Optimization
Daniel Berg Thomsen, Adrien Taylor, Aymeric Dieuleveut
Communication costs are a major bottleneck in distributed learning and first-order optimization. A common approach to alleviate this issue is to compress the gradient information e…
An optimal first-order method for smooth and strongly convex composite optimization and its stationary limit
Manu Upadhyaya, Daniel Berg Thomsen, Aymeric Dieuleveut +1
We introduce Prox-ITEM, an optimal proximal gradient method for minimizing , where is smooth and strongly convex, and is convex, proper, and lower semicontinuous. In t…
From Inexact Gradients to Byzantine Robustness: Acceleration and Optimization under Similarity
Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx
Standard federated learning algorithms are vulnerable to adversarial nodes, a.k.a. Byzantine failures. To solve this issue, robust distributed learning algorithms have been develop…
Tight Analysis of Decentralized SGD: A Markov Chain Perspective
Lucas Versini, Paul Mangold, Aymeric Dieuleveut
We propose a novel analysis of the Decentralized Stochastic Gradient Descent (DSGD) algorithm with constant step size, interpreting the iterates of the algorithm as a Markov chain.…
Scalable Utility-Aware Multiclass Calibration
Mahmoud Hegazy, Michael I. Jordan, Aymeric Dieuleveut
Ensuring that classifiers are well-calibrated, i.e., their predictions align with observed frequencies, is a minimal and fundamental requirement for classifiers to be viewed as tru…
Federated Majorize-Minimization: Beyond Parameter Aggregation
Aymeric Dieuleveut, Gersende Fort, Mahmoud Hegazy +1
This paper proposes a unified approach for designing stochastic optimization algorithms that robustly scale to the federated learning setting. Our work studies a class of Majorize-…
Valid Selection among Conformal Sets
Mahmoud Hegazy, Liviu Aolaritei, Michael I. Jordan +1
Conformal prediction offers a distribution-free framework for constructing prediction sets with coverage guarantees. In practice, multiple valid conformal prediction sets may be av…
Tight analyses of first-order methods with error feedback
Daniel Berg Thomsen, Adrien Taylor, Aymeric Dieuleveut
Communication between agents often constitutes a major computational bottleneck in distributed learning. One of the most common mitigation strategies is to compress the information…
Scaffold with Stochastic Gradients: New Analysis with Linear Speed-Up
Paul Mangold, Alain Durmus, Aymeric Dieuleveut +1
This paper proposes a novel analysis for the Scaffold algorithm, a popular method for dealing with data heterogeneity in federated learning. While its convergence in deterministic…
Open Problem: Two Riddles in Heavy-Ball Dynamics
Baptiste Goujaud, Adrien Taylor, Aymeric Dieuleveut
This short paper presents two open problems on the widely used Polyak's Heavy-Ball algorithm. The first problem is the method's ability to exactly \textit{accelerate} in dimension…
Humanity's Last Exam
Long Phan, Alice Gatti, Ziwen Han +1168
Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achi…
Refined Analysis of Federated Averaging and Federated Richardson-Romberg
Paul Mangold, Alain Durmus, Aymeric Dieuleveut +2
In this paper, we present a novel analysis of \FedAvg with constant step size, relying on the Markov property of the underlying process. We demonstrate that the global iterates of…
Unified Breakdown Analysis for Byzantine Robust Gossip
Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx
In decentralized machine learning, different devices communicate in a peer-to-peer manner to collaboratively learn from each other's data. Such approaches are vulnerable to misbeha…
Predictive Uncertainty Quantification with Missing Covariates
Margaux Zaffran, Julie Josse, Yaniv Romano +1
Predictive uncertainty quantification is crucial in decision-making problems. We investigate how to adequately quantify predictive uncertainty with missing covariates. A bottleneck…
Byzantine-Robust Gossip: Insights from a Dual Approach
Renaud Gaucher, Aymeric Dieuleveut, Hadrien Hendrikx
Distributed learning has many computational benefits but is vulnerable to attacks from a subset of devices transmitting incorrect information. This paper investigates Byzantine-res…
Random features models: a way to study the success of naive imputation
Alexis Ayme, Claire Boyer, Aymeric Dieuleveut +1
Constant (naive) imputation is still widely used in practice as this is a first easy-to-use technique to deal with missing data. Yet, this simple method could be expected to induce…
Sliced-Wasserstein Estimation with Spherical Harmonics as Control Variates
Rémi Leluc, Aymeric Dieuleveut, François Portier +2
The Sliced-Wasserstein (SW) distance between probability measures is defined as the average of the Wasserstein distances resulting for the associated one-dimensional projections. A…
Compression with Exact Error Distribution for Federated Learning
Mahmoud Hegazy, Rémi Leluc, Cheuk Ting Li +1
Compression schemes have been extensively used in Federated Learning (FL) to reduce the communication cost of distributed learning. While most approaches rely on a bounded variance…
On Fundamental Proof Structures in First-Order Optimization
Baptiste Goujaud, Aymeric Dieuleveut, Adrien Taylor
First-order optimization methods have attracted a lot of attention due to their practical success in many applications, including in machine learning. Obtaining convergence guarant…
Proving Linear Mode Connectivity of Neural Networks via Optimal Transport
Damien Ferbach, Baptiste Goujaud, Gauthier Gidel +1
The energy landscape of high-dimensional non-convex optimization problems is crucial to understanding the effectiveness of modern deep neural network architectures. Recent works ha…
Compressed and distributed least-squares regression: convergence rates with applications to Federated Learning
Constantin Philippenko, Aymeric Dieuleveut
In this paper, we investigate the impact of compression on stochastic gradient algorithms for machine learning, a technique widely used in distributed and federated learning. We un…