(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings

By Abhradeep Thakurta, Adam D. Smith. 2013

171 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “[17], Smith and Thakurta [44] study online optimization, Jain and Thakurta [26] study an interactive model tailored to high-dimensional kernel learning.”
Towards Practical Differentially Private Convex Optimization (2019, neutral): “Many recent works [30], [31], [32] examine the setting of online learning, whereas highdimensional kernel learning is considered in [33]; these settings are quite different from ours, and the results are incomparable.”
Analyze gauss: optimal bounds for privacy-preserving principal component analysis (2014, background): “The key ingredient is the exploitation of the intuition that differential privacy ensures robustness [14, 39], which in turn guarantees low regret.”
Efficient Use of Differentially Private Binary Trees (2015, methodology): “They are central to the algorithm of Dwork et al (2010) for releasing private streaming data, and used in numerous adaptations of this problem, such as Chan et al (2012), Cao et al (2013), and Thakurta and Smith (2013).”
Nearly Optimal Private LASSO (2015, background): “Similar dependence is also present in the online version of the problem [18, 26].”
Private Empirical Risk Minimization, Revisited (2014, background): “Jain and Thakurta [23] gave dimension-independent expected excess risk bounds for the special case of “generalized linear models” with a strongly convex regularizer, assuming that C = Rp (that is, unconstrained optimization).”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “[17][30] and [2] investigated regret bound in online settings.”
Online Learning via the Differential Privacy Lens (2017, unknown): “We emphasize that our aim is not to design low-regret algorithms that satisfy the privacy condition– there is already substantial existing work along these lines [4, 21, 39, 40].”