4 papers
The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
El Mehdi Saad, Victor Thuot, Nicolas Verzelen
We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with…
New Lower Bounds for Stochastic Non-Convex Optimization through Divergence Decomposition
El Mehdi Saad, Wei-Cheng Lee, Francesco Orabona
We study fundamental limits of first-order stochastic optimization in a range of nonconvex settings, including L-smooth functions satisfying Quasar-Convexity (QC), Quadratic Growth…
Dual Averaging Converges for Nonconvex Smooth Stochastic Optimization
Tuo Liu, El Mehdi Saad, Wojciech KotÅowski +1
Dual averaging and gradient descent with their stochastic variants stand as the two canonical recipe books for first-order optimization: Every modern variant can be viewed as a des…
ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning
Artavazd Maranjyan, El Mehdi Saad, Peter Richtárik +1
Asynchronous methods are fundamental for parallelizing computations in distributed machine learning. They aim to accelerate training by fully utilizing all available resources. How…