Research map / Federated learning and privacy / Differential privacy
Private Heterogeneous Federated Learning Without a Trusted Server Revisited: Error-Optimal and Communication-Efficient Algorithms for Convex Losses
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.
Gives ISRL-DP federated learning algorithms for convex losses under heterogeneous silo data that attain the optimal excess risk, with improved communication and gradient complexity via localized accelerated MB-SGD and subgradient/smoothing variants.
Problem
Private federated learning without a trusted server under inter-silo record-level DP with heterogeneous (non-i.i.d.) silo data: achieving optimal convex excess risk with fewer communication rounds and fewer (sub)gradient computations.
Approach
Combines iterative localization with multi-stage ISRL-DP accelerated MB-SGD, solving a sequence of regularized ERM subproblems whose stability/generalization holds without i.i.d. data; nonsmooth losses are handled via Nesterov or convolutional smoothing or a direct ISRL-DP minibatch subgradient method.
Key results
- Smooth-loss algorithm attains the optimal ISRL-DP excess risk LD/sqrt(N)(1/sqrt(n)+sqrt(d log(1/delta))/(eps n)) under heterogeneous data, with communication complexity Õ(N^{1/4} n^{1/4}) in the M=N, d=Θ(n), eps=Θ(1) regime versus Õ(Nn) for the prior i.i.d. algorithm.
- Nonsmooth subgradient-based algorithm achieves communication Õ(min(nN, Nε²n²/d)) and subgradient complexity Õ(Nn + N²min(n,n²/d) + N^{3/2}min(n^{3/2},n²/√d)) at optimal excess risk.
- On heterogeneous MNIST logistic regression with N=25 silos, localized ISRL-DP MB-SGD outperforms one-pass ISRL-DP MB-SGD across privacy levels in both reliable and unreliable (M=18) communication settings.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply localized ISRL-DP MB-SGD instead of one-pass ISRL-DP MB-SGD | binary logistic regression on heterogeneous MNIST · MNIST test split, reliable and unreliable communication | test error | Helped |
| use localized ISRL-DP Accelerated MB-SGD for heterogeneous rather than only i.i.d. silo data | ISRL-DP federated learning with smooth convex losses · heterogeneous silo data | excess risk | Helped |
| use Nesterov smoothing rather than the prior state-of-the-art approach | ISRL-DP federated learning with nonsmooth losses · heterogeneous silo data | communication complexity | Helped |
| use convolutional smoothing rather than Nesterov smoothing | ISRL-DP federated learning with nonsmooth losses · heterogeneous silo data | gradient complexity | Helped |
| use convolutional smoothing rather than Nesterov smoothing | ISRL-DP federated learning with nonsmooth losses · heterogeneous silo data | communication complexity | Hurt |
Surprising findings
- Acceleration may impede stability of iterates, so the optimal bound is obtained indirectly via stability of regularized ERM rather than stability of the accelerated iterates.
Limitations
- The communication lower bound is non-private and only for zero-respecting algorithms; the paper does not prove a rigorous ISRL-DP communication lower bound, so optimality is not established.
- Gradient complexity does not match the best known in all regimes; achieving both optimal communication and gradient complexity simultaneously is open.
- Experiments are small-scale (MNIST, PCA to 50 dims, logistic regression) and use vanilla MB-SGD instead of the accelerated variant.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST (binary odd/even logistic regression)
Metrics: test error excess risk (theoretical)
Baselines: One-pass ISRL-DP MB-SGD LR'23 Algorithm 1 (non-i.i.d.) LR'23 Algorithm 2 (i.i.d.)
Builds on: ISRL-DP Accelerated MB-SGD localization AC-SA Nesterov smoothing
Closest papers by meaning
- Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learning (ICML 2024 · similarity 0.90)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.87)
- Privacy-Preserving Federated Convex Optimization: Balancing Partial-Participation and Efficiency via Noise Cancellation (ICML 2025 · similarity 0.87)
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.87)
- Towards the Robustness of Differentially Private Federated Learning (AAAI 2024 · similarity 0.86)
- Clients Collaborate: Flexible Differentially Private Federated Learning with Guaranteed Improvement of Utility-Privacy Trade-off (ICML 2025 · similarity 0.86)
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.