Private Convex Optimization in General Norms

Abstract: We propose a new framework for differentially private optimization of convex functions which are Lipschitz in an arbitrary norm

| c d o t |

. Our algorithms are based on a regularized exponential mechanism which samples from the density

p r o p t o e x p (- k (F + m u r))

where

F

is the empirical loss and

r

is a regularizer which is strongly convex with respect to

| c d o t |

, generalizing a recent work of [Gopi, Lee, Liu '22] to non-Euclidean settings. We show that this mechanism satisfies Gaussian differential privacy and solves both DP-ERM (empirical risk minimization) and DP-SCO (stochastic convex optimization) by using localization tools from convex geometry. Our framework is the first to apply to private convex optimization in general normed spaces and directly recovers non-private SCO rates achieved by mirror descent as the privacy parameter

e p s i l o n o i n f t y

. As applications, for Lipschitz optimization in

e l l_{p}

norms for all

p i n (1, 2)

, we obtain the first optimal privacy-utility tradeoffs; for

p = 1

, we improve tradeoffs obtained by the recent works [Asi, Feldman, Koren, Talwar '21, Bassily, Guzman, Nandi '21] by at least a logarithmic factor. Our

e l l_{p}

norm and Schatten-

p

norm optimization frameworks are complemented with polynomial-time samplers whose query complexity we explicitly bound.

Cited in

(1)

Faster high-accuracy log-concave sampling via algorithmic warm starts

This page was built for publication: Private Convex Optimization in General Norms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6405261)