AI Paper Atlas

Research map / Optimization / Nonconvex and smooth optimization

Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimization

Blake E Woodworth, Jialei Wang, Adam Smith, Brendan McMahan, Nati Srebro

NeurIPS 2018 · Optimization › Nonconvex and smooth optimization · approach: Stochastic convex optimization complexity · 51 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 A-MB-SGD on the layer graph with gradient queriesLayer(T,M) optimization · layer(T,M)expected suboptimalityImproved
Allow prox queries for sufficiently smooth objectivesLayer(T,M) optimization · layer(T,M)optimal complexityNo clear effect
Use prox queries to compute gradients of the Moreau envelope, then apply accelerated mini-batch SGDLayer(T,M) optimization on non-smooth or insufficiently smooth objectives · layer(T,M)expected suboptimalityImproved
Use delayed SGD updates instead of a wait-and-collect scheduleDelayed update optimization · delay(T,τ)expected suboptimality: O\left( \frac{H}{T/\tau^2} + \frac{L}{\sqrt{T}} \right)Hurt
Batch τ gradients at one point and wait for their results before updatingDelayed update optimization · delay(T,τ)expected suboptimalityImproved
Use mini-batch SGD over all KM queries per round rather than exploiting local sequential computationIntermittent communication optimization · intermittent(T,K,M)optimization term in expected suboptimality: H/T^2 vs. H/(T^2K^2)Hurt
Use only one chain for sequential SGDIntermittent communication optimization · intermittent(T,K,M)expected suboptimality: O\parens{\frac{L}{\sqrt{T K}}}Improved
Use active queries and SVRG instead of pure stochastic queriesIntermittent communication optimization · intermittent(T,K,M)expected suboptimality: O\parens{\parens{ \frac{H}{T K} + \frac{L}{\sqrt{T K M} }}\log\parens{ \frac{T K M}{ L}}}Improved

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