4 papers
Stronger Memory-Query Tradeoffs for Convex Optimization: The Limitations of Subquadratic Memory
Michael Menart, Aleksandar Nikolov, Ohad Shamir
We prove two lower bounds for the first order oracle complexity of minimizing a -dimensional -Lipschitz convex function over the unit ball with bits of memory. We first s…
On the Gradient Complexity of Private Optimization with Private Oracles
Michael Menart, Aleksandar Nikolov
We study the running time, in terms of first order oracle queries, of differentially private empirical/population risk minimization of Lipschitz convex losses. We first consider th…
Private Rate-Constrained Optimization with Applications to Fair Learning
Mohammad Yaghini, Tudor Cebere, Michael Menart +2
Many problems in trustworthy ML can be expressed as constraints on prediction rates across subpopulations, including group fairness constraints (demographic parity, equalized odds,…
Private Algorithms for Stochastic Saddle Points and Variational Inequalities: Beyond Euclidean Geometry
Raef Bassily, Cristóbal Guzmán, Michael Menart
In this work, we conduct a systematic study of stochastic saddle point problems (SSP) and stochastic variational inequalities (SVI) under the constraint of -differential p…