Beyond Convexity: Stochastic Quasi-Convex Optimization

Abstract

Stochastic convex optimization is a basic and well studied primitive in machine learning. It is well known that convex and Lipschitz functions can be minimized efficiently using Stochastic Gradient Descent (SGD). The Normalized Gradient Descent (NGD) algorithm, is an adaptation of Gradient Descent, which updates according to the direction of the gradients, rather than the gradients themselves. In this paper we analyze a stochastic version of NGD and prove its convergence to a global minimum for a wider class of functions: we require the functions to be quasi-convex and locally-Lipschitz. Quasi-convexity broadens the con- cept of unimodality to multidimensions and allows for certain types of saddle points, which are a known hurdle for first-order optimization methods such as gradient descent. Locally-Lipschitz functions are only required to be Lipschitz in a small region around the optimum. This assumption circumvents gradient explosion, which is another known hurdle for gradient descent variants. Interestingly, unlike the vanilla SGD algorithm, the stochastic normalized gradient descent algorithm provably requires a minimal minibatch size.

References in corpus (1)

• On the difficulty of training Recurrent Neural Networks

Cited by in corpus (20)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• Stochastic Variance Reduction for Nonconvex Optimization
• Online Batch Selection for Faster Training of Neural Networks
• Sampling Matters in Deep Embedding Learning
• The Power of Normalization: Faster Evasion of Saddle Points
• Robust Optimization for Non-Convex Objectives
• Variational quantum amplitude estimation
• Theoretical properties of the global optimizer of two layer neural network
• Porcupine Neural Networks: (Almost) All Local Optima are Global
• Distribution-Specific Hardness of Learning Neural Networks
• Universal gradient descent
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General
• Normalized Direction-preserving Adam
• Deep Q-Networks for Accelerating the Training of Deep Neural Networks
• DANTE: Deep AlterNations for Training nEural networks
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Normalized Gradient Descent for Variational Quantum Algorithms
• A Unified Framework for Training Neural Networks
• Analyzing and Improving the Optimization Landscape of Noise-Contrastive Estimation
• On the alpha-loss Landscape in the Logistic Model