← Back to papers
2016 COLT COLT 2016

Gradient Descent Only Converges to Minimizers

Abstract

We show that gradient descent converges to a local minimizer, almost surely with random initial- ization. This is proved by applying the Stable Manifold Theorem from dynamical systems theory.

🧭 Keyword Pioneer — local minimizer
🐣 Hot Topic Early Bird — dynamical system
🐝 Cross-Pollinator — Artificial Intelligence, Computer Science, Computer Vision, Data Science & Analytics, Deep Learning, Healthcare & Medicine, Interdisciplinary, Knowledge & Reasoning, Machine Learning, Mathematics & Optimization, Natural Language Processing, Reinforcement Learning, Robotics, Security & Privacy, Speech & Audio

Authors

Jason D. Lee , Max Simchowitz , Michael I. Jordan , Benjamin Recht

Topics

Machine Learning > Optimization & Theory > Optimization Machine Learning > Optimization & Theory > Theory

Keywords

gradient descent dynamical system random initialization local minimizer stable manifold
Download PDF

Related papers

Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies 2016
Open Problem: Best Arm Identification: Almost Instance-Wise Optimality and the Gap Entropy Conjecture 2016
Open Problem: Kernel methods on manifolds and metric spaces. What is the probability of a positive definite geodesic exponential kernel? 2016
Learning and Testing Junta Distributions 2016
Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes 2016