6 citations · 10 across the 10 of their papers we have counts for
10 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 pri…
Public-data Assisted Private Stochastic Optimization: Power and Limitations
Enayat Ullah, Michael Menart, Raef Bassily +2
We study the limits and capability of public-data assisted differentially private (PA-DP) algorithms. Specifically, we focus on the problem of stochastic convex optimization (SCO)…
Differentially Private Non-Convex Optimization under the KL Condition with Optimal Rates
Michael Menart, Enayat Ullah, Raman Arora +2
We study private empirical risk minimization (ERM) problem for losses satisfying the -Kurdyka-Łojasiewicz (KL) condition. The Polyak-Łojasiewicz (PL) condition is a special…
Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gap
Raef Bassily, Cristóbal Guzmán, Michael Menart
We show that convex-concave Lipschitz stochastic saddle point problems (also known as stochastic minimax optimization) can be solved under the constraint of -differential pr…
Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
Raman Arora, Raef Bassily, Tomás González +3
We study the problem of approximating stationary points of Lipschitz and smooth functions under -differential privacy (DP) in both the finite-sum and stochastic se…
Differentially Private Generalized Linear Models Revisited
Raman Arora, Raef Bassily, Cristóbal Guzmán +2
We study the problem of -differentially private learning of linear predictors with convex losses. We provide results for two subclasses of loss functions. The first case is…
Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
Raef Bassily, Cristóbal Guzmán, Michael Menart
We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs…