Research map / Learning theory and algorithms / Sample complexity
Order Optimal One-Shot Distributed Learning
Arsalan Sharifnassab, Saber Salehkaleybar, S. Jamaloddin Golestani
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MRE-C-log to communicate empirical minimizers and multiresolution gradient information | One-shot distributed convex optimization · General convex optimization | expected estimation error: O\big( m^{-{1}/{\max(d,2)}} n^{-1/2} \big) | Improved |
| Use MRE-C-log instead of AVGM | Ridge regression, d=2 and n=1 · Ridge regression | average parameter error | Improved |
| Use MRE-C-log instead of AVGM | Logistic regression, d=2 and n=1 · Logistic regression | average parameter error | Improved |
| Increase the number of machines while keeping n=1 and use MRE-C-log | Ridge regression and logistic regression · Ridge regression and logistic regression | average parameter error | Improved |
| Use a one-bit randomized estimator | One-dimensional distributed optimization · One-dimensional, one-bit communication | root mean squared error: O\left(\frac{1}{\sqrt{n}}+\frac{1}{\sqrt{m}}\right) | Improved |
| Use the naive derivative-grid estimator | One-dimensional optimization with n=1 · One-dimensional, n=1 | expected absolute estimation error: O\big((\log(m)/\sqrt[3]{m})^k\big) | Improved |
Closest papers by meaning
- One-Shot Federated Learning: Theoretical Limits and Algorithms to Achieve Them (JMLR 2021 · similarity 0.93)
- New Bounds For Distributed Mean Estimation and Variance Reduction (ICLR 2021 · similarity 0.87)
- Distributed Mean Estimation with Limited Communication (ICML 2017 · similarity 0.87)
- Efficient Distributed Learning with Sparsity (ICML 2017 · similarity 0.86)
- EControl: Fast Distributed Optimization with Compression and Error Control (ICLR 2024 · similarity 0.86)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.84)
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.
