View publication

Stochastic convex optimization over an 1ℓ_1-bounded domain is ubiquitous in machine learning applications such as LASSO but remains poorly understood when learning with differential privacy. We show that, up to logarithmic factors the optimal excess population loss of any (ε,δ)(\varepsilon, \delta)-differentially private optimizer is log(d)/n  +\sqrt{\log(d)/n}\; + d/εn.\sqrt{d}/\varepsilon n. The upper bound is based on a new algorithm that combines the iterative localization approach of FeldmanKoTa20 with a new analysis of private regularized mirror descent. It applies to pℓ_p bounded domains for p[1,2]p\in [1,2] and queries at most n3/2n^{3/2} gradients improving over the best previously known algorithm for the 2\ell_2 case which needs n2n^2 gradients. Further, we show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by log(d)/n  +\sqrt{\log(d)/n}\; + (log(d)/εn)2/3.(\log(d)/\varepsilon n)^{2/3}. This bound is achieved by a new variance-reduced version of the Frank-Wolfe algorithm that requires just a single pass over the data. We also show that the lower bound in this case is the minimum of the two rates mentioned above.

Related readings and updates.

Private Online Prediction from Experts: Separations and Faster Rates

*= Equal Contributors Online prediction from experts is a fundamental problem in machine learning and several works have studied this problem under privacy constraints. We propose and analyze new algorithms for this problem that improve over the regret bounds of the best existing algorithms for non-adaptive adversaries. For approximate differential privacy, our algorithms achieve regret bounds of O(Tlog⁡d+log⁡d/ε)O(\sqrt{T \log d} + \log…
See paper details

Near-Optimal Algorithms for Private Online Optimization in the Realizable Regime

*=Equal Contributors We consider online learning problems in the realizable setting, where there is a zero-loss solution, and propose new Differentially Private (DP) algorithms that obtain near-optimal regret bounds. For the problem of online prediction from experts, we design new algorithms that obtain near-optimal regret O(ε−1log⁡1.5d)O \big( \varepsilon^{-1} \log^{1.5}{d} \big)O(ε−1log1.5d) where ddd is the number of experts. This…
See paper details