The duality structure gradient descent algorithm: analysis and\n applications to neural networks

2017/08/01 by Thomas R. Flynn, Flynn, Thomas · 2 citations
Computer Science · #Advanced Neural Network Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and ELM #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1708.00523

openalex publication_date 2017/08/01 · openalex created_date 2022/09/02 · openalex updated_date 2026/07/28

Abstract

The training of machine learning models is typically carried out using some\nform of gradient descent, often with great success. However, non-asymptotic\nanalyses of first-order optimization algorithms typically employ a gradient\nsmoothness assumption (formally, Lipschitz continuity of the gradient) that is\ntoo strong to be applicable in the case of deep neural networks. To address\nthis, we propose an algorithm named duality structure gradient descent (DSGD)\nthat is amenable to non-asymptotic performance analysis, under mild assumptions\non the training set and network architecture. The algorithm can be viewed as a\nform of layer-wise coordinate descent, where at each iteration the algorithm\nchooses one layer of the network to update. The decision of what layer to\nupdate is done in a greedy fashion, based on a rigorous lower bound on the\nimprovement of the objective function for each choice of layer. In the\nanalysis, we bound the time required to reach approximate stationary points, in\nboth the deterministic and stochastic settings. The convergence is measured in\nterms of a parameter-dependent family of norms that is derived from the network\narchitecture and designed to confirm a smoothness-like property on the gradient\nof the training loss function. We empirically demonstrate the behavior of DSGD\nin several neural network training scenarios.\n

Citations

• Natural Gradient Works Efficiently in Learning
• ImageNet classification with deep convolutional neural networks
• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• A Convergence Theory for Deep Learning via Over-Parameterization
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes
• Learning Multiple Layers of Features from Tiny Images

Cited by

• Training Transformers with Enforced Lipschitz Constants
• AuON: A Linear-time Alternative to Semi-Orthogonal Momentum Updates

Related

• On the convergence of gradient descent for two layer neural networks
• Gradient Descent Finds Global Minima for Generalizable Deep Neural Networks of Practical Sizes
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Gradient Descent as a Perceptron Algorithm: Understanding Dynamics and Implicit Acceleration
• Towards Guided Descent: Optimization Algorithms for Training Neural Networks At Scale