Lower Bound for Randomized First Order Convex Optimization

Abstract

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.

8 pages

References in corpus (1)

• Tight Complexity Bounds for Optimizing Composite Objectives

Cited by in corpus (11)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Tight Complexity Bounds for Optimizing Composite Objectives
• Calibration for the (Computationally-Identifiable) Masses
• Can We Find Near-Approximately-Stationary Points of Nonsmooth Nonconvex Functions?
• Acceleration with a Ball Optimization Oracle
• Oracle Complexity in Nonsmooth Nonconvex Optimization
• The gradient complexity of linear regression
• High-Order Oracle Complexity of Smooth and Strongly Convex Optimization
• The Minimax Complexity of Distributed Optimization
• Open Problem: The Oracle Complexity of Convex Optimization with Limited Memory
• Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales