Nearly Optimal Private LASSO

By Kunal Talwar, Abhradeep Thakurta, Li Zhang. 2015

163 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

Tight Lower Bounds for Locally Differentially Private Selection (2018, background): “ot locally differentially private) algorithm M:(Bd 1) n!Bd 1 such that for any distribution Pover [1]d, P X1;:::;X n˘P;M E x˘P x; PM(X1;:::;X n) 99 100 : In fact, Talwar, Thakurta, and Zhang [TTZ15] showed an algorithm that achieves a similar guarantee (although with slightly weaker parameters) ”
Tight Lower Bounds for Differentially Private Selection (2017, background): “We remark that previous fingerprinting-based lower bounds in differential privacy [16], [27], [28], [17], [18], [3] essentially correspond to setting β = O(1) in Theorem 3.”
Measuring Forgetting of Memorized Training Examples (2022, background): “There is a large amount of theoretical work on differential privacy which designs algorithms specific to convex models, which do not apply to non-convex settings [12, 71, 34, 79].”
Is Interaction Necessary for Distributed Private Learning? (2017, background): “Variants of this result has appeared in [7, 43].”
Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data (2018, methodology): “At first glance, it seems straightforward by integrating the Report-Noisy-Max for privacy protection (Talwar, Thakurta, and Zhang 2015) with the existing distributed FW design.”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, background): “…studied extensively for over a decade (see, e.g., (Chaudhuri and Monteleoni, 2008; Chaudhuri et al., 2011; Jain et al., 2012; Kifer et al., 2012; Smith and Thakurta, 2013; Bassily et al., 2014; Ullman, 2015; Jain and Thakurta, 2014; Talwar et al., 2015; Bassily et al., 2019; Feldman et al., 2020)).”
Evaluating Differentially Private Machine Learning in Practice (2019, background): “There has also been considerable progress in generalizing privacy-preserving machine learning to more complex scenarios such as learning in high-dimensional settings [33, 34, 65], learning without strong convexity assumptions [66], or relaxing the assumptions on data and objective functions [63, 69,”
Differentially Private Empirical Risk Minimization Revisited: Faster and More General (2018, background): “[29] Gradient Perturbation O( (G 2 3 C log (2)(n)) (n ) 2 3 ) O( (n ) 2 3”
Unlocking High-Accuracy Differentially Private Image Classification through Scale (2022, background): “…analysis of the privacy-utility oﬀered by these algorithms, and by now there are large classes of problems for which algorithms achieving (nearly) optimal privacy-utility trade-oﬀs are known (Asi et al., 2021; Bassily et al., 2014; Feldman et al., 2020; Song et al., 2021; Talwar et al., 2015).”
When Relaxations Go Bad: "Differentially-Private" Machine Learning (2019, unknown): “…has also been a considerable progress in generalizing privacy-preserving machine learning to more complex scenarios such as learning in high dimensional settings [34,35,65], learning without strong convexity assumptions [66], or relaxing the assumptions on data and objective functions [63, 70, 79].”
Privacy-preserving Prediction (2018, background): “This setting captures many important learning problems and has also been extensively investigated in the privacy literature (see (Chaudhuri et al., 2011; Kifer et al., 2012; Bassily et al., 2014; Talwar et al., 2015; Wang et al., 2017) and references therein).”
Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget (2018, methodology): “, they also have shown that their lower bounds on expected the excess risk is optimal, ignoring multiplicative log factor for both lipschitz convex and strongly convex functions. Later, Talwar et al. [20] improved those lower bounds on the utility for LASSO problem. In [21], gradient perturbation me”
Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, methodology): “Note (Talwar et al., 2015) assume data is in L∞ ball, while both (Kasiviswanathan & Jin, 2016) and ours assume data is in L2 ball.”
Empirical Risk Minimization in Non-interactive Local Differential Privacy Revisited (2018, background): “There is a long list of works on differentially private ERM in the last decade which attack the problem from different perspectives, such as (Wang et al., 2017a; Bassily et al., 2014; Kifer et al., 2012; Chaudhuri et al., 2011; Talwar et al., 2015).”
Differentially Private Federated Learning: An Information-Theoretic Perspective (2021, background): “Following the de facto standard of differential privacy (DP) in large-scale model fitting (Bassily et al., 2014; 2019; Chaudhuri & Mishra, 2006; Chaudhuri & Monteleoni, 2009; Chaudhuri et al., 2011; Duchi et al., 2013; Jain & Thakurta, 2014; Jain et al., 2012; Smith et al., 2017; Song et al., 2013; ”
Differentially Private Matrix Completion, Revisited (2017, background): “Also note that a prior work [42] also proposed a diﬀerentially private Frank-Wolfe (FW) algorithm for high dimensional regression but it was for a completely diﬀerent problem in a diﬀerent setting where the segregation of computation into global and local components was not required.”