Timezone: »
Poster
“Convex Until Proven Guilty”: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions
Yair Carmon · John Duchi · Oliver Hinder · Aaron Sidford
We develop and analyze a variant of Nesterov's accelerated gradient descent (AGD) for minimization of smooth non-convex functions. We prove that one of two cases occurs: either our AGD variant converges quickly, as if the function was convex, or we produce a certificate that the function is “guilty” of being non-convex. This non-convexity certificate allows us to exploit negative curvature and obtain deterministic, dimension-free acceleration of convergence for non-convex functions. For a function $f$ with Lipschitz continuous gradient and Hessian, we compute a point $x$ with $\|\nabla f(x)\| \le \epsilon$ in $O(\epsilon^{-7/4} \log(1/ \epsilon) )$ gradient and function evaluations. Assuming additionally that the third derivative is Lipschitz, we require only $O(\epsilon^{-5/3} \log(1/ \epsilon) )$ evaluations.
Author Information
Yair Carmon (Stanford University)
John Duchi (Stanford University)
Oliver Hinder (Stanford)
Aaron Sidford (Stanford)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Talk: “Convex Until Proven Guilty”: Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions »
Tue. Aug 8th 06:06 -- 06:24 AM Room Parkside 2
More from the Same Authors
-
2021 : Adapting to function difficulty and growth conditions in private optimization »
Hilal Asi · Daniel A Levy · John Duchi -
2023 : Differentially Private Heavy Hitters using Federated Analytics »
Karan Chadha · Junye Chen · John Duchi · Vitaly Feldman · Hanieh Hashemi · Omid Javidbakht · Audra McMillan · Kunal Talwar -
2023 Poster: Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling »
Adam Bouland · Yosheb Getachew · Yujia Jin · Aaron Sidford · Kevin Tian -
2022 Poster: Accelerated, Optimal and Parallel: Some results on model-based stochastic optimization »
Karan Chadha · Gary Cheng · John Duchi -
2022 Spotlight: Accelerated, Optimal and Parallel: Some results on model-based stochastic optimization »
Karan Chadha · Gary Cheng · John Duchi -
2022 Poster: Private optimization in the interpolation regime: faster rates and hardness results »
Hilal Asi · Karan Chadha · Gary Cheng · John Duchi -
2022 Poster: RECAPP: Crafting a More Efficient Catalyst for Convex Optimization »
Yair Carmon · Arun Jambulapati · Yujia Jin · Aaron Sidford -
2022 Spotlight: Private optimization in the interpolation regime: faster rates and hardness results »
Hilal Asi · Karan Chadha · Gary Cheng · John Duchi -
2022 Spotlight: RECAPP: Crafting a More Efficient Catalyst for Convex Optimization »
Yair Carmon · Arun Jambulapati · Yujia Jin · Aaron Sidford -
2021 Poster: Private Adaptive Gradient Methods for Convex Optimization »
Hilal Asi · John Duchi · Alireza Fallah · Omid Javidbakht · Kunal Talwar -
2021 Spotlight: Private Adaptive Gradient Methods for Convex Optimization »
Hilal Asi · John Duchi · Alireza Fallah · Omid Javidbakht · Kunal Talwar -
2021 Poster: Towards Tight Bounds on the Sample Complexity of Average-reward MDPs »
Yujia Jin · Aaron Sidford -
2021 Spotlight: Towards Tight Bounds on the Sample Complexity of Average-reward MDPs »
Yujia Jin · Aaron Sidford -
2020 Poster: Efficiently Solving MDPs with Stochastic Mirror Descent »
Yujia Jin · Aaron Sidford -
2020 Poster: Understanding and Mitigating the Tradeoff between Robustness and Accuracy »
Aditi Raghunathan · Sang Michael Xie · Fanny Yang · John Duchi · Percy Liang -
2020 Poster: FormulaZero: Distributionally Robust Online Adaptation via Offline Population Synthesis »
Aman Sinha · Matthew O'Kelly · Hongrui Zheng · Rahul Mangharam · John Duchi · Russ Tedrake -
2017 Poster: Adaptive Sampling Probabilities for Non-Smooth Optimization »
Hongseok Namkoong · Aman Sinha · Steven Yadlowsky · John Duchi -
2017 Talk: Adaptive Sampling Probabilities for Non-Smooth Optimization »
Hongseok Namkoong · Aman Sinha · Steven Yadlowsky · John Duchi