Can I read Lower Bounds for Finding Stationary Points I on EtoBox?

Lower Bounds for Finding Stationary Points I by Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron is a scholarly article available to read on EtoBox.

What is Lower Bounds for Finding Stationary Points I about?

We prove lower bounds on the complexity of finding $\epsilon$-stationary points (points $x$ such that $\|\nabla f(x)\| \le \epsilon$) of smooth, high-dimensional, and potentially non-convex functions $f$. We consider oracle-based complexity measures, where an algorithm is given access to the value and all derivatives of $f$ at a query point $x$. We show that for any (potentially randomized) algorithm $\mathsf{A}$, there exists a function $f$ with Lipschitz $p$th order derivatives such that $\mathsf{A}$ requires at least $\epsilon^{-(p+1)/p}$ queries to find an $\epsilon$-stationary point. Our lower bounds are sharp to within constants, and they show that gradient descent, cubic-regularized Newton's method, and generalized $p$th order regularization are worst-case optimal within their natural function classes.

Author

Carmon, Yair; Duchi, John C.; Hinder, Oliver; Sidford, Aaron

Published

2017

Language

EN