Research map / Optimization / Distributed and compressed
A Doubly Recursive Stochastic Compositional Gradient Descent Method for Federated Multi-Level Compositional Optimization
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.
Proposes Fed-DR-SCGD, a federated algorithm for multi-level compositional optimization that communicates recursively computed Jacobian-vector products with variance reduction, achieving level-independent and linear-speedup convergence under heterogeneous data.
Problem
Federated stochastic multi-level compositional optimization under heterogeneous data, where existing federated methods handle only two levels and fail to achieve linear speedup in the number of workers, and communicating full Jacobians is too costly.
Approach
Instead of communicating Jacobian matrices, communicate a recursively computed Jacobian-vector product estimator (variance-reduced across levels) together with inner-level function estimators, which removes the heterogeneity bias term and yields linear speedup with level-independent rate.
Key results
- Fed-DR-SCGD achieves O(1/(N^{2/3}T^{2/3})) nonconvex convergence rate, indicating linear speedup in workers under heterogeneity, versus an additive heterogeneity term for LocalSCGDM that does not vanish.
- In portfolio optimization experiments, Fed-DR-SCGD is more communication-efficient than NLASG, SCSC and SMVR across three datasets with communication period p=4 and p=12.
- With 8 vs 16 workers on Operating Profitability, the 16-worker run reaches lower loss in less wall-clock time, confirming speedup.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a recursively computed Jacobian-vector product estimator instead of communicating Jacobian matrices | Fed-DR-SCGD · Risk-Averse Portfolio Optimization: Operating Profitability, Investment, and Book-to-Market | communication efficiency | Helped |
| Use variance-reduced gradient estimation | Fed-DR-SCGD and SMVR · Risk-Averse Portfolio Optimization: Operating Profitability, Investment, and Book-to-Market | convergence speed | Helped |
| Increase the number of workers from 8 to 16 | Fed-DR-SCGD · Operating Profitability | runtime | Helped |
| Apply LocalSCGDM in the heterogeneous setting | LocalSCGDM · Federated two-level compositional optimization | average squared gradient norm convergence rate: O(\frac{1}{\sqrt{T}}) + O(\delta^2) | Hurt |
Surprising findings
- Communicating the Jacobian matrix itself, the natural fix for heterogeneity, is impractical due to its size, motivating the Jacobian-vector product estimator.
Limitations
- Experiments are limited to a single risk-averse portfolio optimization task with a three-level formulation.
- Assumes bounded stochastic gradients and Lipschitz conditions (Assumptions 3.1-3.3), with projection operators needed to enforce bounds.
Experimental setup
Datasets: Book-to-Market Operating Profitability Investment
Benchmarks: Risk-averse portfolio optimization (Operating Profitability, Investment, Book-to-Market)
Metrics: log loss vs epochs log loss vs communication cost (MB) loss vs wall-clock time
Baselines: NLASG SCSC SMVR LocalSCGDM
Builds on: LocalSCGDM SMVR NLASG SCSC
Closest papers by meaning
- A Federated Stochastic Multi-level Compositional Minimax Algorithm for Deep AUC Maximization (ICML 2024 · similarity 0.88)
- How Does Black-Box Impact the Learning Guarantee of Stochastic Compositional Optimization? (NeurIPS 2024 · similarity 0.87)
- Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms (ICML 2024 · similarity 0.86)
- A Near-Optimal Single-Loop Stochastic Algorithm for Convex Finite-Sum Coupled Compositional Optimization (ICML 2025 · similarity 0.86)
- Faster Stochastic Variance Reduction Methods for Compositional MiniMax Optimization (AAAI 2024 · similarity 0.85)
- Projection-Free Variance Reduction Methods for Stochastic Constrained Multi-Level Compositional Optimization (ICML 2024 · similarity 0.85)
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.