Research map / Optimization / Nonconvex and smooth optimization
On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition
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.
Proves IFO and decentralized lower bounds for finite-sum smooth optimization under the PL condition and proposes DRONE, a decentralized recursive-gradient method that nearly matches them.
Problem
Finite-sum minimization under the Polyak–Łojasiewicz condition with mean-squared smooth components, both centralized (IFO complexity) and decentralized over a network (communication, time, and local oracle complexity); the optimality of existing methods was open.
Approach
Constructs zero-chain hard instances adapted to the PL condition (via orthogonal splitting and scaling lemmas) to derive matching lower bounds, and proposes DRONE, combining a local recursive (SARAH/PAGE-style) gradient estimator with gradient tracking and Chebyshev acceleration to nearly match these bounds.
Key results
- Lower bound Omega(n + kappa*sqrt(n) log(1/epsilon)) on IFO calls for PL finite-sum problems, nearly matching SPIDER/PAGE-type upper bounds.
- Decentralized lower bounds Omega(kappa/sqrt(gamma) log(1/epsilon)) communication rounds and Omega((kappa + tau*kappa/sqrt(gamma)) log(1/epsilon)) time cost.
- DRONE achieves communication O~(kappa/sqrt(gamma) log(1/epsilon)), time O~(kappa(1+tau/sqrt(gamma)) log(1/epsilon)) and LFO O((n+kappa sqrt(n)) log(1/epsilon)) in expectation.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use recursive local gradient estimation in place of the full local-gradient computation pattern in DGD-GT | Decentralized optimization with DRONE · Decentralized PL optimization | LFO complexity: $\fO\big(\kappa n\log(1/\epsilon)\big)$; $\fO\big((n+\kappa\sqrt{n}\,)\log(1/\epsilon)\big)$ | Helped |
| Use DRONE rather than DGD-GT | Decentralized optimization · Decentralized PL optimization | Communication complexity: $\tilde\fO\left({\kappa}/{\sqrt{\gamma}}\log(1/\epsilon)\right)$ | No clear effect |
| Use DRONE rather than DGD-GT | Decentralized optimization · Decentralized PL optimization | Time complexity: $\tilde\fO\left(\kappa (1+\tau/\sqrt{\gamma}\,)\log(1/\epsilon)\right)$ | No clear effect |
| Use DRONE rather than the cited PAGE parameter choices | DRONE · Decentralized PL optimization with $n=\Omega(\kappa^2)$ | Communication complexity: $\tilde\fO\big(\kappa/\sqrt{\gamma}\log(1/\epsilon)\big)$; $\tilde\fO\big((\kappa+\sqrt{n}\,)\log(1/\epsilon)/\sqrt{\gam | Helped |
| Use a client-server framework instead of decentralized communication | CGD · Hard instance, DrivFace, and RCV1 experiments | Communication rounds | Helped |
| Use DRONE rather than CGD | Decentralized and client-server optimization · Hard instance, DrivFace, and RCV1 experiments | LFO calls | Helped |
Surprising findings
- CGD in a client-server setting needs far fewer communication rounds than DGD-GT and DRONE on a linear graph, which the authors attribute to consensus error in decentralized methods.
Limitations
- Upper bounds hold only in expectation.
- Lower bounds are up to logarithmic factors and rely on specific hard instances.
- Experiments use a linear graph with n=32 and a small spectral gap (about 0.0024).
Experimental setup
Datasets: DrivFace RCV1
Benchmarks: DrivFace RCV1
Metrics: LFO calls communication rounds running time objective gap
Baselines: GD SVRG PAGE DGD-GT CGD
Builds on: PAGE SPIDER DGD-GT Chebyshev acceleration
Closest papers by meaning
- Faster Stochastic Algorithms for Minimax Optimization under Polyak-{\L}ojasiewicz Condition (NeurIPS 2022 · similarity 0.89)
- Optimal Algorithms for Non-Smooth Distributed Optimization in Networks (NeurIPS 2018 · similarity 0.89)
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks (NeurIPS 2024 · similarity 0.88)
- Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks (NeurIPS 2021 · similarity 0.88)
- Decentralized Convex Finite-Sum Optimization with Better Dependence on Condition Numbers (ICML 2024 · similarity 0.87)
- 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.