Research map / Optimization / Nonconvex and smooth optimization
Freya PAGE: First Optimal Time Complexity for Large-Scale Nonconvex Finite-Sum Optimization with Heterogeneous Asynchronous Computations
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 Freya PAGE, an asynchronous variance-reduced (PAGE-based) method for nonconvex finite-sum optimization with heterogeneous worker speeds, with new gradient-collection subroutines, achieving optimal time complexity in the large-scale regime (sqrt(m) >= n) plus a matching lower bound.
Problem
Nonconvex finite-sum optimization in distributed settings where workers have arbitrarily heterogeneous and time-varying processing times; prior methods (Asynchronous SGD, Rennala SGD, SPIDER/PAGE with equal data allocation) have suboptimal time complexity or depend on the slowest worker.
Approach
Combine PAGE's probabilistic full-gradient/minibatch-difference updates with new asynchronous subroutines (ComputeGradient, ComputeBatchDifference) that assign data indices uniformly at random to whichever worker is free, so the method adapts to unknown and changing worker speeds without using {tau_i}; the resulting time complexity is governed by an equilibrium time t*(S) and is shown to be optima
Key results
- Freya PAGE achieves time complexity min_j((sum_{i<=j} 1/tau_i)^{-1}(m+j)) + (delta^0/eps) min_j((sum 1/tau_i)^{-1}(sqrt(m)+j)), matching a proven lower bound when sqrt(m) >= n.
- On MNIST logistic regression, Freya PAGE reaches 92.66% mean test accuracy vs 92.60% for Asynchronous SGD, 92.37% for Rennala SGD, and 92.31% for Soviet PAGE, with the lowest accuracy variance (1.01e-07).
- Simulated nonconvex quadratic experiments with n=1000 and n=10000 workers show Freya PAGE converging fastest among compared methods.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Freya PAGE instead of Asynchronous SGD | MNIST logistic regression · MNIST test set, final 100K seconds | accuracy: 92.60 -> 92.66 | Helped |
| Use Freya PAGE instead of Rennala SGD | MNIST logistic regression · MNIST test set, final 100K seconds | accuracy: 92.37 -> 92.66 | Helped |
| Use Freya PAGE instead of Soviet PAGE | MNIST logistic regression · MNIST test set, final 100K seconds | accuracy: 92.31 -> 92.66 | Helped |
| Use Freya PAGE instead of Asynchronous SGD | MNIST logistic regression · MNIST test set, final 100K seconds | variance of accuracy: 5.85e-07 -> 1.01e-07 | Helped |
| Use Freya PAGE instead of Rennala SGD | MNIST logistic regression · MNIST test set, final 100K seconds | variance of accuracy: 3.12e-06 -> 1.01e-07 | Helped |
| Use Freya PAGE instead of Soviet PAGE | MNIST logistic regression · MNIST test set, final 100K seconds | variance of accuracy: 1.62e-07 -> 1.01e-07 | Helped |
| Use Freya PAGE instead of Soviet PAGE | Nonconvex quadratic optimization · Synthetic quadratic tasks, n=1000 and n=10000 | function suboptimality | Helped |
| Use Freya PAGE instead of Rennala SGD | Nonconvex quadratic optimization · Synthetic quadratic tasks, n=1000 and n=10000 | function suboptimality | Helped |
| Use Freya PAGE instead of Asynchronous SGD | Nonconvex quadratic optimization · Synthetic quadratic tasks, n=1000 and n=10000 | function suboptimality | Helped |
| Use Freya PAGE instead of Rennala SGD or Asynchronous SGD | MNIST logistic regression · MNIST | accuracy | No clear effect |
Surprising findings
- Optimal parameters S and p can be chosen independently of the worker speeds {tau_i} in the large-scale regime, so the method is adaptive without knowing them.
Limitations
- Optimality holds only in the large-scale regime sqrt(m) >= n; the lower bound and optimal parameters differ otherwise.
- Analysis assumes m >= n log n to avoid a logarithmic term; ComputeGradient has an extra min{m,n} log min{m,n} term otherwise.
- Experiments use simulated worker times rather than real distributed hardware.
Experimental setup
Datasets: MNIST
Benchmarks: MNIST
Metrics: function suboptimality vs elapsed time test accuracy variance of accuracy
Baselines: Asynchronous SGD Rennala SGD Soviet PAGE SYNTHESIS Hero PAGE
Builds on: PAGE SPIDER Rennala SGD Asynchronous SGD
Closest papers by meaning
- On the Optimal Time Complexities in Decentralized Stochastic Asynchronous Optimization (NeurIPS 2024 · similarity 0.90)
- Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics (ICLR 2025 · similarity 0.89)
- An Accelerated Decentralized Stochastic Proximal Algorithm for Finite Sums (NeurIPS 2019 · similarity 0.89)
- Do We Need Asynchronous SGD? On the Near-Optimality of Synchronous Methods (NeurIPS 2026 · similarity 0.88)
- Shadowheart SGD: Distributed Asynchronous SGD with Optimal Time Complexity Under Arbitrary Computation and Communication Heterogeneity (NeurIPS 2024 · similarity 0.87)
- An Online Optimization Perspective on First-Order and Zero-Order Decentralized Nonsmooth Nonconvex Stochastic Optimization (ICML 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.