Notes on Worst-case Inefficiency of Gradient Descent Even in R^2
Gradient descent is a popular algorithm in optimization, and its performance in convex settings is mostly well understood. In non-convex settings, it has been shown that gradient descent is able to escape saddle points asymptotically and converge to local minimizers [Lee et. al. 2016]. Recent studies also show a perturbed version of gradient descent is enough to escape saddle points efficiently [Jin et. al. 2015, Ge et. al. 2017]. In this paper we show a negative result: gradient descent may take exponential time to escape saddle points, with non-pathological two dimensional functions. While our focus is theoretical, we also conduct experiments verifying our theoretical result. Through our analysis we demonstrate that stochasticity is essential to escape saddle points efficiently.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Understanding Schedule-Free Methods in Nonconvex Optimization: Rate Guarantees and Escaping Saddles
Schedule-Free methods have attracted growing interest for alleviating the burden of designing and tuning a learning rate scheduler, while matching and sometimes even outperforming optimizers with tuned schedulers. Despit…
How Does the ReLU Activation Affect the Implicit Bias of Gradient Descent on High-dimensional Neural Network Regression?
Overparameterized ML models, including neural networks, typically induce underdetermined training objectives with multiple global minima. The implicit bias refers to the limiting global minimum that is attained by a comm…
Globally Optimal Gradient Descent for a ConvNet with Gaussian Inputs
Deep learning models are often successfully trained using gradient descent, despite the worst case hardness of the underlying non-convex optimization problem. The key question is then under what conditions can one prove …
Efficient Projection Algorithms onto the Weighted l1 Ball
Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted $\ell_1$ ball has been shown effective in sparse system identification and features selection. In this…
BIG-bench Machine Learningfeature selectionGreen Hacks: Generating Sustainability-Targeting Attacks For Cyber-Physical Systems
Sustainability-targeting attacks (STA) or "Green Hacks" are a growing threat to cyber-physical system (CPS)-based infrastructure, as its performance objectives are increasingly linked to sustainability goals. These attac…