Lune

ICLR2025Top-tier venue

Exploiting Hidden Symmetry to Improve Objective Perturbation for DP Linear Learners with a Nonsmooth L1-Norm

Du Chen, Geoffrey A. Chua

Abstract

Objective Perturbation (OP) is a classic approach to differentially private (DP) convex optimization with smooth loss functions but is less understood for nonsmooth cases. In this work, we study how to apply OP to DP linear learners under loss functions with a hidden or implicit ℓ 1 -norm structure, such as max0, x as a motivating example. We propose to first smooth out the implicit ℓ 1 -norm by convolution, and then invoke standard OP. Convolution has many advantages that distinguish itself from Moreau Envelope, such as approximating from above and a higher degree of hyperparameters. These advantages, in conjunction with the symmetry of ℓ 1 -norm, result in tighter pointwise approximation, which further facilitates tighter analysis of generalization risks by using pointwise bounds. Under mild assumptions on groundtruth distributions, the proposed OP-based algorithm is found to be rate-optimal, and can achieve the excess generalization risk

. Experiments demonstrate the competitive performance of the proposed method to Noisy-SGD.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Towards Practical Differentially Private Convex Optimization cites Deep Learning with Differential Privacy
  • Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settings cites Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry
  • Hyperparameter Tuning with Renyi Differential Privacy cites Deep Learning with Differential Privacy
  • Private Stochastic Convex Optimization: Optimal Rates in L1 Geometry cites Deep Learning with Differential Privacy
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on14

  1. Deep Learning with Differential PrivacyMartín Abadi, Andy Chu, Ian J. Goodfellow, H. Brendan McMahan et al.CCS 2016 · 7,620 citations
  2. Towards Practical Differentially Private Convex OptimizationRoger Iyengar, Joseph P. Near, Dawn Song, Om Thakkar et al.S&P 2019 · 201 citations
  3. Hyperparameter Tuning with Renyi Differential PrivacyNicolas Papernot, Thomas SteinkeICLR 2022 · 157 citations
  4. Private Stochastic Convex Optimization: Optimal Rates in L1 GeometryHilal Asi, Vitaly Feldman, Tomer Koren, Kunal TalwarICML 2021 · 106 citations
  5. Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex SettingsRaef Bassily, Cristóbal Guzmán, Michael MenartNeurIPS 2021 · 68 citations

Related papers

  1. Differentially Private Stochastic Convex Optimization under a Quantile Loss FunctionDu Chen, Geoffrey A. ChuaICML 2023 · 1 citation
  2. Oracle Efficient Private Non-Convex OptimizationSeth Neel, Aaron Roth, Giuseppe Vietri, Zhiwei Steven WuICML 2020 · 9 citations
  3. Bring Your Own Algorithm for Optimal Differentially Private Stochastic Minimax OptimizationLiang Zhang, Kiran Koshy Thekumparampil, Sewoong Oh, Niao HeNeurIPS 2022 · 25 citations
  4. Improving the Privacy and Practicality of Objective Perturbation for Differentially Private Linear LearnersRachel Redberg, Antti Koskela, Yu-Xiang WangNeurIPS 2023 · 14 citations
  5. Private Convex Optimization in General NormsSivakanth Gopi, Yin Tat Lee, Daogao Liu, Ruoqi Shen et al.SODA 2023 · 3 citations
Dusk over the sea between two cliffs drawn in fine vertical lines