Browsing by Author "Raef Bassily"

Now showing 1 - 5 of 5
  • Thumbnail Image
    Item
    Differentially Private Generalized Linear Models Revisited
    (2022) Raman Arora; Raef Bassily; Guzman Paredes, Cristobal Andres; Michael Menart; Enayat Ullah
  • Thumbnail Image
    Item
    Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings
    (2021) Raef Bassily; Guzman Paredes, Cristobal Andres; Michael Menart
    We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. Our algorithm for the $\ell_1$ setting has nearly-optimal excess population risk $\tilde{O}\big(\sqrt{\frac{\log{d}}{n\varepsilon}}\big)$, and circumvents the dimension dependent lower bound of \cite{Asi:2021} for general non-smooth convex losses. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. For the $\ell_1$-case with smooth losses and polyhedral constraint, we provide the first nearly dimension independent rate, $\tilde O\big(\frac{\log^{2/3}{d}}{{(n\varepsilon)^{1/3}}}\big)$ in linear time. For the constrained $\ell_2$-case with smooth losses, we obtain a linear-time algorithm with rate $\tilde O\big(\frac{1}{n^{1/3}}+\frac{d^{1/5}}{(n\varepsilon)^{2/5}}\big)$. Finally, for the $\ell_2$-case we provide the first method for {\em non-smooth weakly convex} stochastic optimization with rate $\tilde O\big(\frac{1}{n^{1/4}}+\frac{d^{1/6}}{(n\varepsilon)^{1/3}}\big)$ which matches the best existing non-private algorithm when $d= O(\sqrt{n})$. We also extend all our results above for the non-convex $\ell_2$ setting to the $\ell_p$ setting, where $1 < p \leq 2$, with only polylogarithmic (in the dimension) overhead in the rates.
  • Thumbnail Image
    Item
    Faster Rates of Convergence to Stationary Points in Differentially Private Optimization
    (2023) Raman Arora; Raef Bassily; Guzman Paredes, Cristobal Andres; Tomás González; Michael Menart; Enayat Ullah
  • Thumbnail Image
    Item
    Non-Euclidean Differentially Private Stochastic Convex Optimization
    (2021) Raef Bassily; Guzman Paredes, Cristobal Andres; Anupama Nandi
  • Thumbnail Image
    Item
    Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses
    (2020) Raef Bassily; Vitaly Feldman; Guzman Paredes, Cristobal Andres; Kunal Talwar
    Uniform stability is a notion of algorithmic stability that bounds the worst case change in the model output by the algorithm when a single data point in the dataset is replaced. An influential work of Hardt et al. [2016] provides strong upper bounds on the uniform stability of the stochastic gradient descent (SGD) algorithm on sufficiently smooth convex losses. These results led to important progress in understanding of the generalization properties of SGD and several applications to differentially private convex optimization for smooth losses.Our work is the first to address uniform stability of SGD on nonsmooth convex losses. Specifically, we provide sharp upper and lower bounds for several forms of SGD and full-batch GD on arbitrary Lipschitz nonsmooth convex losses. Our lower bounds show that, in the nonsmooth case, (S)GD can be inherently less stable than in the smooth case. On the other hand, our upper bounds show that (S)GD is sufficiently stable for deriving new and useful bounds on generalization error. Most notably, we obtain the first dimension-independent generalization bounds for multi-pass SGD in the nonsmooth case. In addition, our bound allow us to derive a new algorithm for differentially private nonsmooth stochastic convex optimization with optimal excess population risk. Our algorithm is simpler and more efficient than the best known algorithm for the nonsmooth case, due to Feldman et al. [2020].