Research map / Federated learning and privacy / Communication-efficient FL
Decomposable Submodular Maximization in Federated Setting
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 Federated Continuous Greedy (FedCG and a practical variant) for maximizing sums of private monotone submodular client functions under matroid constraints, with client subsampling and local steps, plus a discrete federated greedy for facility location and max coverage.
Problem
Maximizing a decomposable monotone submodular function F = sum_i p_i f_i under a matroid constraint when component functions are private to clients and too numerous to centralize, with limits on communication rounds and bits.
Approach
Adapts continuous greedy to federated settings: clients compute local matroid-polytope linear maximizers (bases) and the server averages them; analyzes heterogeneity via a bounded gradient-dissimilarity assumption, samples K clients per round, and allows tau local steps between aggregations, retaining (1-1/e) approximation up to additive error. A discrete variant uses randomized-response sparsific
Key results
- Full-participation FedCG achieves (1-1/e)OPT minus an additive term rD/T + r^2 m_F/(2T) under bounded gradient-dissimilarity assumption.
- Client sampling with K clients gives a high-probability bound with an additional 6rD/sqrt(TK delta) error term.
- Discrete federated greedy achieves (1-1/e-eps)OPT for cardinality constraints with expected per-round participation independent of N (as stated in the text).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Sample K clients per round instead of using full participation | FedCG · Monotone submodular maximization under matroid constraints | additive approximation error: \frac{6rD}{\sqrt{TK\delta}} | Hurt |
| Use τ local steps between communication rounds instead of communicating every step | FedCG+ · Monotone submodular maximization under matroid constraints | additive approximation error: \frac{rD\tau}{T}; \frac{2r^{1.5}Q\tau}{T}; \frac{\sqrt{\tau}(6Dr+2r^{1.5}Q)}{\sqrt{TK\delta}} | Hurt |
| Estimate gradients by sampling m subsets | FedCG+ · Monotone submodular maximization under matroid constraints | additive approximation error: 2\sigma r(1+\frac{\sqrt{\tau}}{\sqrt{KT \delta}}) | Hurt |
Limitations
- Guarantees carry additive error terms from heterogeneity, local steps and client sampling, and rely on a bounded gradient-dissimilarity assumption.
- Only single-server secure aggregation privacy is considered; no differential privacy guarantees.
- No experiments reported in the provided text; results are purely theoretical.
Experimental setup
Metrics: approximation ratio additive error bound
Baselines: centralized continuous greedy Federated Frank-Wolfe Decentralized Continuous Greedy
Builds on: continuous greedy federated averaging federated frank-wolfe decomposable submodular sparsification
Closest papers by meaning
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.87)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.87)
- Pursuing Overall Welfare in Federated Learning through Sequential Decision Making (ICML 2024 · similarity 0.87)
- Communication-Efficient Federated Non-Linear Bandit Optimization (ICLR 2024 · similarity 0.87)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.87)
- Federated Optimization with Doubly Regularized Drift Correction (ICML 2024 · 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.