Deep Frank-Wolfe For Neural Network Optimization

Abstract

Learning a deep neural network requires solving a challenging optimization problem: it is a high-dimensional, non-convex and non-smooth minimization problem with a large number of terms. The current practice in neural network optimization is to rely on the stochastic gradient descent (SGD) algorithm or its adaptive variants. However, SGD requires a hand-designed schedule for the learning rate. In addition, its adaptive variants tend to produce solutions that generalize less well on unseen data than SGD with a hand-designed schedule. We present an optimization method that offers empirically the best of both worlds: our algorithm yields good generalization performance while requiring only one hyper-parameter. Our approach is based on a composite proximal framework, which exploits the compositional nature of deep neural networks and can leverage powerful convex optimization algorithms by design. Specifically, we employ the Frank-Wolfe (FW) algorithm for SVM, which computes an optimal step-size in closed-form at each time-step. We further show that the descent direction is given by a simple backward pass in the network, yielding the same computational cost per iteration as SGD. We present experiments on the CIFAR and SNLI data sets, where we demonstrate the significant superiority of our method over Adam, Adagrad, as well as the recently proposed BPGrad and AMSGrad. Furthermore, we compare our algorithm to SGD with a hand-designed learning rate schedule, and show that it provides similar generalization while converging faster. The code is publicly available at https://github.com/oval-group/dfw.

arXiv commentPublished as a conference paper at ICLR 2019, last version fixing an inaccuracy (details in appendix A.5, Proposition 2)

References in corpus (15)

• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• A Closer Look at Memorization in Deep Networks
• No More Pesky Learning Rates
• Path-SGD: Path-Normalized Optimization in Deep Neural Networks
• Training Neural Networks Without Gradients: A Scalable ADMM Approach
• Learned Optimizers that Scale and Generalize
• Smooth Loss Functions for Deep Top-k Classification
• Natural Neural Networks
• WNGrad: Learn the Learning Rate in Gradient Descent
• Reliably Learning the ReLU in Polynomial Time
• Practical Gauss-Newton Optimisation for Deep Learning
• Trusting SVM for Piecewise Linear CNNs
• Faster Convergence & Generalization in DNNs

Cited by in corpus (13)

• Semantic-Aware Scene Recognition
• HardCoRe-NAS: Hard Constrained diffeRentiable Neural Architecture Search
• A Second look at Exponential and Cosine Step Sizes: Simplicity, Adaptivity, and Performance
• Quantized Frank-Wolfe: Faster Optimization, Lower Communication, and Projection Free
• Learning Rates as a Function of Batch Size: A Random Matrix Theory Approach to Neural Network Training
• Training Neural Networks for and by Interpolation
• Safe Screening for the Generalized Conditional Gradient Method
• Flatness is a False Friend
• Dual Averaging is Surprisingly Effective for Deep Learning Optimization
• Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings
• Scalable Projection-Free Optimization
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
• Training Deep Neural Networks via Branch-and-Bound