AI Paper Atlas

Research map / Optimization / Nonconvex and smooth optimization

Optimal Time Complexities of Parallel Stochastic Optimization Methods Under a Fixed Computation Model

Alexander Tyurin, Peter Richtárik

NeurIPS 2023 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity · 2 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Use Rennala SGD (ignore stale gradients, batch size S=max(sigma^2/eps,1)) instead of Asynchronous SGDParallel nonconvex SGD under fixed computation model · Homogeneous nonconvex, time complexitytime complexity to eps-stationary pointImproved
Use Rennala SGD instead of Minibatch SGDParallel nonconvex SGD · Homogeneous nonconvex, time complexitytime complexity to eps-stationary pointImproved
Let workers start asynchronously instead of synchronized startOptimal parallel methods · Homogeneous nonconvex, time complexitytime complexityImproved
Use Asynchronous SGD instead of Minibatch SGDParallel nonconvex SGD · Fixed computation modeltime complexityImproved
Use Malenia SGD (per-worker estimators) instead of Minibatch SGDHeterogeneous nonconvex parallel SGD · Heterogeneous nonconvex, time complexitytime complexityImproved
Ignore workers with delays beyond the optimal m* (done automatically by Rennala SGD)Rennala SGD · Homogeneous nonconvextime complexityImproved
Use the new time-based lower bound instead of the Woodworth et al. graph-oracle boundConvex fixed computation model lower bound · Convex homogeneous caselower bound tightnessImproved
Add Nesterov-style acceleration to Rennala SGD in the smooth convex caseRennala SGD · Convex smooth casetime complexityImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy