Research map / Optimization / Nonconvex and smooth optimization
Decentralized Sum-of-Nonconvex 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.
Analyzes PMGT-SVRG for decentralized sum-of-nonconvex composite optimization and proposes PMGT-KatyushaX, an accelerated variance-reduced decentralized method whose complexities scale with the square root of the condition number.
Problem
Decentralized stochastic minimization of a strongly convex composite objective that is an average of smooth but nonconvex component functions across m agents, where prior methods either need full gradients or have suboptimal rates for this setting.
Approach
Extends KatyushaX-style acceleration (linear coupling with a mirror-descent step) on top of SVRG, and adds gradient tracking and multi-consensus (FastMix) mixing, so the decentralized method's SFO and communication complexities depend on the square root of the condition number rather than linearly.
Key results
- PMGT-SVRG analysis gives SFO complexity O((n + sqrt(n) kappa) log(1/eps)) for decentralized sum-of-nonconvex problems, linear in condition number.
- PMGT-KatyushaX achieves SFO complexity O((n + n^{3/4} sqrt(kappa)) log(1/eps)) and communication complexity tilde-O((sqrt(n) + n^{1/4} sqrt(kappa))/sqrt(1-lambda_2(W)) log(1/eps)).
- In experiments on synthetic and Covtype data for PCA subproblems, PMGT-KatyushaX needs the fewest gradient evaluations; on Covtype with r=2 it requires more communication rounds than NIDS/PG-EXTRA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PMGT-KatyushaX instead of PMGT-SVRG | Decentralized sum-of-nonconvex composite optimization · Sum-of-nonconvex composite | SFO complexity dependence on condition number: PMGT-SVRG: \mathcal{O}\left((n+ \sqrt{n} \kappa)\log\frac{1}{\epsilon}\right); PMGT-KatyushaX: \mathcal{O}\left((n + n^{ | Helped |
| Use PMGT-KatyushaX instead of PMGT-SVRG | Decentralized sum-of-nonconvex composite optimization · Sum-of-nonconvex composite | Communication complexity dependence on condition number: PMGT-SVRG: \tilde{\mathcal{O}}\left( \frac{ \sqrt{n} + {\kappa}}{\sqrt{1 - \lambda_2(W)}} \log \frac{1}{\epsilon} \right | Helped |
| Use PMGT-KatyushaX rather than PMGT-SVRG, PGEXTRA, or NIDS | Decentralized PCA shift-and-invert optimization · Synthetic dataset, r=2 and r=300 | Gradient evaluations | Helped |
| Use PMGT-KatyushaX rather than NIDS | Decentralized PCA shift-and-invert optimization · Synthetic dataset, r=2 and r=300 | Communication rounds | Helped |
| Use PMGT-KatyushaX rather than NIDS or PGEXTRA | Decentralized PCA shift-and-invert optimization · Covtype, r=2 | Gradient evaluations | Helped |
| Use PMGT-KatyushaX rather than NIDS or PGEXTRA | Decentralized PCA shift-and-invert optimization · Covtype, r=2 | Communication rounds | Hurt |
| Use PMGT-KatyushaX rather than other baselines | Decentralized PCA shift-and-invert optimization · Covtype, r=300 | Gradient evaluations | Helped |
| Use PMGT-KatyushaX rather than other baselines | Decentralized PCA shift-and-invert optimization · Covtype, r=300 | Communication rounds | Helped |
Surprising findings
- On the synthetic dataset PMGT-KatyushaX even required fewer communication rounds than NIDS, despite its communication bound depending on sqrt(n).
- On Covtype with small eigengap ratio r=2, PMGT-KatyushaX used more communication rounds than NIDS and PG-EXTRA.
Limitations
- Communication complexity still contains a sqrt(n) factor that the authors consider unsatisfying.
- Empirical evaluation limited to PCA shift-and-invert subproblem on one synthetic and one real dataset.
- Theory assumes strong convexity of the global objective.
Experimental setup
Datasets: Covtype (LIBSVM) synthetic Bernoulli matrix 60000x50
Benchmarks: Covtype synthetic Bernoulli PCA shift-and-invert subproblem
Metrics: suboptimality F(y)-F(x*) vs gradient evaluations suboptimality vs communication rounds suboptimality vs weighted cost
Baselines: PMGT-SVRG PG-EXTRA NIDS
Builds on: PMGT-SVRG KatyushaX SVRG gradient tracking FastMix
Closest papers by meaning
- Efficient Decentralized Stochastic Gradient Descent Method for Nonconvex Finite-Sum Optimization Problems (AAAI 2022 · similarity 0.92)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.89)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 2024 · similarity 0.89)
- Decentralized Gradient-Free Methods for Stochastic Non-smooth Non-convex Optimization (AAAI 2024 · similarity 0.88)
- Faster Adaptive Decentralized Learning Algorithms (ICML 2024 · similarity 0.88)
- Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization (AAAI 2024 · similarity 0.87)
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.