Research map / Learning theory and algorithms / Matrix and tensor methods
Privacy Amplification by Iteration for ADMM with (Strongly) Convex Objective Functions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Analyzes privacy amplification by iteration for a gradient-variant noisy ADMM with convex and strongly convex objectives, using a customized norm and two-step Markov operators to obtain zCDP amplification proportional to 1/T (exponential for strongly convex).
Problem
Privacy amplification by iteration for ADMM where each iteration uses one user's private function via a single gradient access, with noise masking only the primal variable and the dual variable unmasked.
Approach
Adapts the Balle et al. coupling framework to gradient ADMM by introducing a customized norm under which one ADMM iteration is non-expansive (contractive for strongly convex), and treats two consecutive noisy ADMM iterations as one Markov operator to obtain finite zCDP bounds.
Key results
- Privacy amplification by iteration for gradient ADMM: zCDP divergence after 2T+1 noisy iterations bounded by C/T times local privacy term, with C = max{2, 3/(βη)}(1+βη||A||^2).
- For strongly convex objectives, the amplification factor becomes exponential in the number of iterations (L^T/T for some 0<L<1).
- Empirical Lasso experiments show that strong convexity and noise variance affect convergence rates, as predicted by theory.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| increase the number of noisy ADMM iterations | gradient ADMM · Final output after T iterations | zCDP divergence: proportional to 1/T | Helped |
| use strongly convex objective functions | gradient ADMM · Final output after T iterations | zCDP divergence: L^T/T | Helped |
Surprising findings
- A single ADMM iteration under the usual norm can be strictly expanding, so a customized norm is needed for non-expansiveness.
Limitations
- Assumes subsequent users generate randomness honestly and do not collude with the adversary.
- Constant C has dependence O(1/(βη)) on parameters; the analysis fixes a fixed deterministic sequence of functions without subsampling or shuffling.
Experimental setup
Benchmarks: general Lasso problem
Metrics: convergence rate
Baselines: Cyffers et al. proximal ADMM
Builds on: Balle et al. 2019 privacy amplification by iteration coupling framework Cyffers et al. 2023 proximal ADMM privacy amplification Feldman et al. 2018 privacy amplification by iteration
Closest papers by meaning
- Shifted Interpolation for Differential Privacy (ICML 2024 · similarity 0.90)
- Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.88)
- Privacy amplification by random allocation (NeurIPS 2025 · similarity 0.88)
- Convergent Privacy Loss of Noisy-SGD without Convexity and Smoothness (ICLR 2025 · similarity 0.87)
- Rényi Pufferfish Privacy: General Additive Noise Mechanisms and Privacy Amplification by Iteration via Shift Reduction Lemmas (ICML 2024 · similarity 0.87)
- Faster Algorithms for User-Level Private Stochastic Convex Optimization (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.