5 papers · 1 filter
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…