mlsanityData to 7 Oct 2026

Federated Empirical Risk Minimization via Second-Order Method

arXiv 2305.17482 ↗First posted 27 May 2023cs.LG cs.DCcited by 9

Not on the map. Why?

Abstract (arXiv)

Many convex optimization problems with important applications in machine learning are formulated as empirical risk minimization (ERM). There are several examples: linear and logistic regression, LASSO, kernel regression, quantile regression, p-norm regression, support vector machines (SVM), and mean-field variational inference. To improve data privacy, federated learning is proposed in machine learning as a framework for training deep learning models on the network edge without sharing data between participating nodes. In this work, we present an interior point method (IPM) to solve a general ERM problem under the federated learning setting. We show that the communication complexity of each iteration of our IPM is tildeO(d3/2), where d is the dimension (i.e., number of features) of the dataset.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 71 of its 117 references that are in the map. First posted on arXiv 27 May 2023.

Builds on

71 of 117 references.

References · 71

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
  4. 2020The Future of Digital Health with Federated Learningcited by 625
  5. 2021FedBN: Federated Learning on Non-IID Features via Local Batch Normalizationcited by 565
  6. 2017Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Trainingcited by 471
  7. 2020FetchSGD: Communication-Efficient Federated Learning with Sketchingcited by 178
  8. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 131
  9. 2020Multi-site fMRI Analysis Using Privacy-preserving Federated Learning and Domain Adaptation: ABIDE Resultscited by 122
  10. 2023Fast Attention Requires Bounded Entriescited by 102
  11. 2018Solving Linear Programs in the Current Matrix Multiplication Timecited by 100
  12. 2020InstaHide: Instance-hiding Schemes for Private Distributed Learningcited by 90
38 more
  1. 2019Communication-efficient distributed SGD with Sketchingcited by 81
  2. 2016CoCoA: A General Framework for Communication-Efficient Distributed Optimizationcited by 69
  3. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  4. 2020Training (Overparametrized) Neural Networks in Near-Linear Timecited by 58
  5. 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
  6. 2019Solving Empirical Risk Minimization in the Current Matrix Multiplication Timecited by 53
  7. 2020A Faster Interior Point Method for Semidefinite Programmingcited by 53
  8. 2023Attention Scheme Inspired Softmax Regressioncited by 49
  9. 2017Relative Error Tensor Low Rank Approximationcited by 45
  10. 2020Faster Dynamic Matrix Inverse for Faster LPscited by 44
  11. 2023Solving Regularized Exp, Cosh and Sinh Regression Problemscited by 44
  12. 2019Federated Transfer Reinforcement Learning for Autonomous Drivingcited by 43
  13. 2016AIDE: Fast and Communication Efficient Distributed Optimizationcited by 42
  14. 2019A Deterministic Linear Program Solver in Current Matrix Multiplication Timecited by 42
  15. 2023The Closeness of In-Context Learning and Weight Shifting for Softmax Regressioncited by 41
  16. 2023Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimensioncited by 37
  17. 2022A Faster Small Treewidth SDP Solvercited by 36
  18. 2023An Iterative Algorithm for Rescaled Hyperbolic Functions Regressioncited by 35
  19. 2021Solving SDP Faster: A Robust IPM Framework and Efficient Implementationcited by 33
  20. 2020TextHide: Tackling Data Privacy in Language Understanding Taskscited by 32
  21. 2021Does Preprocessing Help Training Over-parameterized Neural Networks?cited by 32
  22. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  23. 2014Communication-Efficient Distributed Dual Coordinate Ascentcited by 30
  24. 2014Optimal CUR Matrix Decompositionscited by 29
  25. 2020A Nearly-Linear Time Algorithm for Linear Programs with Small Treewidth: A Multiscale Representation of Robust Central Pathcited by 29
  26. 2022Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessingcited by 29
  27. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  28. 2015Optimal Principal Component Analysis in Distributed and Streaming Modelscited by 24
  29. 2013Distributed Coordinate Descent Method for Learning with Big Datacited by 23
  30. 2018BourGAN: Generative Networks with Metric Embeddingscited by 22
  31. 2022Training Overparametrized Neural Networks in Sublinear Timecited by 22
  32. 2022A Sublinear Adversarial Training Algorithmcited by 22
  33. 2022Discrepancy Minimization in Input-Sparsity Timecited by 22
  34. 2015Adding vs. Averaging in Distributed Primal-Dual Optimizationcited by 19
  35. 2018Subspace Embedding and Linear Regression with Orlicz Normcited by 19
  36. 2015On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variantscited by 18
  37. 2022Federated Adversarial Learning: A Framework with Convergence Analysiscited by 17
  38. 2021LocalNewton: Reducing Communication Bottleneck for Distributed Learningcited by 15

50 most cited of 71 All 71 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 4; 2025: 4.

9 papers.

  1. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  2. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  3. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  4. 2025High-Order Matching for One-Step Shortcut Diffusion Modelscited by 15
  5. 2024How to Inverting the Leverage Score Distribution?cited by 5
  6. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  7. 2024Inverting the Leverage Score Gradient: An Efficient Approximate Newton Methodcited by 3
  8. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  9. 2025Which Coauthor Should I Nominate in My 99 ICLR Submissions? A Mathematical Analysis of the ICLR 2026 Reciprocal Reviewer Nomination Policycited by 0