Built on

Problem Complexity and Method Efficiency in Optimization
AS Nemirovsky and DB Yudin · 1983
Earlier work this paper cites.

Similar

Tight complexity bounds for optimizing composite objectives
Original
Blake Woodworth and Nathan Srebro · 2016
Cited alongside, same era.

Then

Lower bounds for finding stationary points i
Original
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…

2017

Lower Bound for Randomized First Order Convex Optimization

Woodworth, Blake, Srebro, Nathan

Understand

We provide an explicit construction and direct proof for the lower bound on the number of first order oracle accesses required for a randomized algorithm to minimize a convex Lipschitz function.