IP Library › Granted Patent US 12,373,692
Granted Patent B2
US 12,373,692 · App. 18/453,837 · Granted Jul 29, 2025

Controlled adaptive optimization

Inventors: Sashank Jakkam Reddi (Jersey City, NJ); Sanjiv Kumar (Jericho, NY); Manzil Zaheer (Mountain View, CA); Satyen Chandrakant Kale (New York, NY)
Assignee: GOOGLE LLC
G06N3/08G06N3/045
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,373,692
App. No.
18/453,837
Granted
Jul 29, 2025
Kind
B2
Abstract

Generally, the present disclosure is directed to systems and methods that perform adaptive optimization with improved convergence properties. The adaptive optimization techniques described herein are useful in various optimization scenarios, including, for example, training a machine-learned model such as, for example, a neural network. In particular, according to one aspect of the present disclosure, a system implementing the adaptive optimization technique can, over a plurality of iterations, employ an adaptive effective learning rate while also ensuring that the effective learning rate is non-increasing.

Claims (52)

1. A computing system for utilization of a machine-learned model that is optimized via adaptive learning, the computing system comprising:

one or more processors;

an optimized machine-learned model comprising a plurality of optimized parameters, wherein the plurality of optimized parameters have been optimized over a plurality of iterations based at least in part on a gradient of a loss function and an effective learning rate, wherein the effective learning rate is based at least in part on a current learning rate control value that equals a recent learning rate control value minus an update value, wherein a magnitude of the update value is a function of the gradient of the loss function, wherein a polarity of the update value is a function of both the gradient of the loss function and the recent learning rate control value, and wherein, for at least one of the plurality of iterations, the polarity of the update value is positive such that the current learning rate control value is less than the most recent learning rate control value, whereby the current effective learning rate is greater than a most recent effective learning rate; and

one or more tangible, non-transitory computer readable media storing computer-readable instructions that when executed by the one or more processors cause the one or more processors to perform operations, the operations comprising:

obtaining input data for the optimized machine-learned model; and

processing the input data using the optimized machine-learned model to obtain optimized output data.

2. The computing system of claim 1 , wherein the operations further comprise:

performing one or more actions based at least in part on the optimized output data.

3. The computing system of claim 1 , wherein the operations further comprise:

evaluating the loss function, wherein the loss function is configured to evaluate a difference between the optimized output data and a ground truth label associated with the input data.

4. The computing system of claim 3 , wherein the operations further comprise:

determining a second learning rate control value based at least in part on the gradient of the loss function, wherein the second learning rate control value equals the current learning rate control value minus a second update value, wherein a magnitude of the second update value is a function of the gradient of the loss function, and wherein a polarity of the second update value is a function of both the gradient of the loss function and the current learning rate control value;

determining a second effective learning rate based at least in part on the second learning rate control value; and

determining an updated set of values for the plurality of optimized parameters of the optimized machine-learned model based at least in part on the loss function and according to the second effective learning rate.

5. The computing system of claim 4 , wherein the polarity of the second update value is positive such that the second learning rate control value is less than the current learning rate control value, whereby the second effective learning rate is greater than the effective learning rate.

6. The computing system of claim 4 , wherein the second update value is equal to a square of the gradient of the loss function multiplied by a sign function applied to the current learning rate control value minus the square of the gradient of the loss function and multiplied by a scaling coefficient that is equal to one minus an update scaling parameter.

7. The computing system of claim 1 , wherein the optimized output data comprises an output for a task, and wherein the task comprises:

an image analysis task;

a predictive task; or

a classification task.

8. The computing system of claim 7 , wherein:

the task comprises the image analysis task;

the input data comprises image data that depicts one or more objects; and

the optimized output data comprises a descriptive annotation of at least one of the one or more objects.

9. The computing system of claim 7 , wherein:

the task comprises a classification task;

the input data comprises data descriptive of an entity; and

the optimized output data comprises a classification of the entity.

10. The computing system of claim 7 , wherein:

the task comprises a prediction task;

the input data comprises sensor data from one or more sensors; and

the optimized output data comprises a decision.

11. A process for production of an optimized machine-learned model product trained using an adaptive learning algorithm with improved convergence properties and stored on one or more tangible, non-transitory computer readable media, wherein the process comprises the steps of:

(a) for a plurality of iterations:

determining a gradient of a loss function that evaluates a performance of a machine-learned model, wherein the machine-learned model comprises a plurality of parameters;

determining a current learning rate control value based on the gradient of the loss function, wherein the current learning rate control value equals a most recent learning rate control value minus an update value, wherein a magnitude of the update value is a function of the gradient of the loss function but not the most recent learning rate control value, and wherein a polarity of the update value is a function of both the gradient of the loss function and the most recent learning rate control value; and

determining an updated set of values for the plurality of parameters of the machine-learned model based at least in part on the gradient of the loss function and according to the current effective learning rate;

wherein, for at least one of the plurality of iterations, the polarity of the update value is positive such that the current learning rate control value is less than the most recent learning rate control value, whereby the current effective learning rate is greater than a most recent effective learning rate; and

(b) storing the optimized machine-learned model product on the one or more tangible, non-transitory computer readable media, wherein the optimized machine-learned model product comprises an optimized version of the machine-learned model.

12. The process according to claim 11 , wherein the update value is equal to a square of the gradient of the loss function multiplied by a sign function applied to the most recent learning rate control value minus the square of the gradient of the loss function and multiplied by a scaling coefficient that is equal to one minus an update scaling parameter.

13. The process according to claim 11 , wherein determining the current effective learning rate based at least in part on the current learning rate control value comprises dividing a current learning rate by a square root of the current learning rate control value plus an adaptivity control value.

14. The process according to claim 11 , wherein, for at least one of the plurality of iterations, the polarity of the update value is positive such that the current learning rate control value is less than the most recent learning rate control value, whereby the current effective learning rate is greater than a most recent effective learning rate.

15. A computer-implemented method for utilization of a machine-learned model that is optimized via adaptive learning, comprising:

obtaining, by a computing system comprising one or more computing devices, input data for an optimized machine-learned model, wherein the optimized machine-learned model comprises a plurality of optimized parameters, wherein the plurality of optimized parameters have been optimized over a plurality of iterations based at least in part on a gradient of a loss function and an effective learning rate, wherein the effective learning rate is based at least in part on a current learning rate control value that equals a recent learning rate control value minus an update value, wherein the update value is equal to a square of the gradient of the loss function multiplied by a sign function applied to the recent learning rate control value minus the square of the gradient of the loss function and multiplied by a scaling coefficient that is equal to one minus an update scaling parameter; and

processing, by the computing system, the input data using the optimized machine-learned model to obtain optimized output data.

16. The computer-implemented method of claim 15 , wherein the method further comprises:

performing, by the computing system, one or more actions based at least in part on the optimized output data.

17. The computer-implemented method of claim 15 , wherein the method further comprises:

evaluating, by the computing system, the loss function, wherein the loss function is configured to evaluate a difference between the optimized output data and a ground truth label associated with the input data.

18. The computer-implemented method of claim 15 , wherein the effective learning rate is inversely correlated to the current learning rate control value.

19. The computer-implemented method of claim 15 , wherein, for at least one of the plurality of iterations, a polarity of the update value is positive such that the current learning rate control value is less than the recent learning rate control value, whereby the effective learning rate is greater than the recent effective learning rate.

20. The computer-implemented method of claim 15 , wherein, over the plurality of iterations, the update scaling parameter is held constant or increased.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 23, 2023
From: JAKKAM REDDI, SASHANK; KUMAR, SANJIV; ZAHEER, MANZIL; KALE, SATYEN CHANDRAKANT
To: GOOGLE LLC
Reel/Frame 064682/0652 →
Continuity (4)
Continuation 17014139 · Sep 8, 2020
Continuation 16657356 · Oct 18, 2019
Provisional Application 62775016 · Dec 4, 2018
Related Publication 20230394310A1 · Dec 7, 2023
References Cited (89)
US 9723144B1 · Gao · 2017 [cited by examiner]
US 10860920B2 · Gendron-Bellemare · 2020 [cited by examiner]
US 10984308B2 · Li · 2021 [cited by examiner]
US 20170161640A1 · Shamir · 2017 [cited by examiner]
US 20180075347A1 · Alistarh · 2018 [cited by examiner]
US 20180107926A1 · Choi · 2018 [cited by examiner]
US 20180144242A1 · Simard · 2018 [cited by examiner]
US 20200012936A1 · Lee · 2020 [cited by examiner]
Agarwal et al., “Finding Approximate Local Minima for Nonconvex Optimization in Linear Time”, arXiv:1611.01146v2, Nov. 4, 2016, 27 pages. [cited by applicant]
Allen-Zhu et al., “Variance Reduction for Faster Non-Convex Optimization”, International Conference on Machine Learning, Jun. 19-24, 2016, New York City, New York, United States, 9 pages. [cited by applicant]
Ba et al., “Layer Normalization”, arXiv: 1607.06450v1, Jul. 21, 2016, 14 pages. [cited by applicant]
Basu et al., “Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations”, arXiv:1906.02367v2. Nov. 2, 2019, 50 pages. [cited by applicant]
Bernstein et al., “SignSGD: Compressed Optimisation for Non-Convex Problems”, arXiv:1802.04434v3. Aug. 7, 2018, 25 pages. [cited by applicant]
Bonawitz et al., “Towards Federated Learning at Scale: System Design”, Conference on Systems and Machine Learning (SysML), Mar. 31-Apr. 2, 2019, Stanford, CA, 15 pages. [cited by applicant]
Brownlee, “Gentle Introduction to the Adam Optimization Algorithm for Deep Leaming”, Machine Learning Mastery, Jul. 3, 2017. [cited by applicant]
Caldas et al., “Leaf: A Benchmark for Federated Settings”, arXiv:1812.01097v1, Dec. 3, 2018, 6 pages. [cited by applicant]
Carmon et al., “Accelerated Methods for Non-Convex Optimization”, arXiv:1611.00756v2, Feb. 2, 2017, 24 pages. [cited by applicant]
Charles et al., “On the Outsized Importance of Learning Rates in Local Update Methods”, arXiv:2007.00878v1, Jul. 2, 2020, 69 pages. [cited by applicant]
Chiu et al., “Named Entity Recognition with Bidirectional LSTM-CNNs”, arXiv:1511.08308v5, Jul. 19, 2016, 14 pages. [cited by applicant]
Clark, “Semi-Supervised Learning for NLP”, Stanford University, Lecture 17, 77 pages. [cited by applicant]
Cohen et al., “Emnist: an extension of Minist to Handwritten Letter”, arXiv:1702.05373v2, Mar. 1, 2017, 10 pages. [cited by applicant]
Defazio et al. “On the Ineffectiveness of Variance Reduced Optimization for Deep Learning”, arXiv:1812.04529v1, Dec. 11, 2018, 10 pages. [cited by applicant]
Defazio et al., “Saga: A Fast Incremental Gradient Method with Support for Non-Strongly Convex Composite Objectives”, Conference on Neural Information Processing Systems, Dec. 8-13, 2014, Montreal, Canada, 9 pages. [cited by applicant]
Duchi et al., “Adaptive Subgradient Methods for Online Learning and Stochastic Optimization”, Journal of Machine Learning Research, vol. 12, Jul. 2011, pp. 2121-2159. [cited by applicant]
Ghadimi et al., “Mini-Batch Stochastic Approximation Methods for Nonconvex Stochastic Composite Optimization”, arXiv:1308.6594v2, Sep. 5, 2013, 33 pages. [cited by applicant]
Ghadimi et al., “Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming”, arXiv:1309.5549v1, Sep. 22, 2013, 25 pages. [cited by applicant]
Goyal et al., “Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour”, arXiv: 1706.02677v1, Jun. 8, 2017, 12 pages. [cited by applicant]
Hazan et al., “Beyond Convexity: Stochastic Quasi-Convex Optimization”, arXiv:1507.02030v3, Oct. 28, 2015, 23 pages. [cited by applicant]
He et al., “Deep Residual Learning for Image Recognition”, Conference on Computer Vision and Pattern Recognition, Jun. 26-Jul. 1, 2016, Las Vegas, Nevada, United States, 9 pages. [cited by applicant]
Hinton et al., “Reducing the Dimensionality of Data with Neural Networks”, Science, vol. 313, Jul. 28, 2006, pp. 504-507. [cited by applicant]
Hsieh et al., “The Non-IID Data Quagmire of Decentralized Machine Learning”, arXiv:1910.00189v1, Oct. 2, 2019, 18 pages. [cited by applicant]
Hsu et al., “Measuring the Effects of Non-Identical Data Distribution for Federated Visual Classification”, arXiv:1909.06335v1, Sep. 13, 2019, 5 pages. [cited by applicant]
Huang et al., “Densely Connected Convolutional Networks”, arXiv:1608.06993v5, Jan. 28, 2018, 9 pages. [cited by applicant]
Ingerman et al., “Introducing TensorFlow Federated”, Mar. 6, 2019, https://medium.com/tensorflow/introducing-tensorflow-federated-a4147aa20041, Retrieved on May 24, 2021, 5 pages. [cited by applicant]
Jin et al., “How to Escape Saddle Points Efficiently”, arXiv:1703.00887v1, Mar. 2, 2017, 35 pages. [cited by applicant]
Johnson et al., “Accelerating Stochastic Gradient Descent using Predictive Variance Reduction”, Conference on Neural Information Processing Systems, Dec. 5-10, 2013, Lake Tahoe, Nevada, United States, 9 pages. [cited by applicant]
Kairouz et al., “Advances and Open Problems in Federated Learning”, arXiv:1912.04977v1, Dec. 10, 2019, 105 pages. [cited by applicant]
Karimireddy et al., “Scaffold: Stochastic Controlled Averaging for On-Device Federated Learning”, arXiv:1910.06378v1, Oct. 14, 2019, 30 pages. [cited by applicant]
Keskar et al., “Improving Generalization Performance by Switching from Adam to SGD”, arXiv:1712.07628v1, Dec. 20, 2017. [cited by applicant]
Khaled et al., “First Analysis of Local GD on Heterogeneous Data”, arXiv:1909.04715v2, Mar. 18, 2020, 11 pages. [cited by applicant]
Kingma et al. “Adam: A Method for Stochastic Optimization”, 2015, 15 pages. [cited by applicant]
Krizhevsky et al., “Learning Multiple Layers of Features from Tiny Images”, Technical Report, Citeseer, Apr. 8, 2009, 60 pages. [cited by applicant]
Li et al., “Federated Learning: Challenges, Methods, and Future Directions”, arXiv:1908.07873v1, Aug. 21, 2019, 21 pages. [cited by applicant]
Li et al., “On the Convergence of FedAvg on Non-IID Data”, arXiv:1907.02189v2, Oct. 8, 2019, 26 pages. [cited by applicant]
Li et al., “On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes”, arXiv: 1805.08114v2, May 31, 2018, 13 pages. [cited by applicant]
Li et al., “Pachinko Allocation: DAG-Structured Mixture Models of Topic Correlations”, International Conference on Machine Learning, Jun. 25-29, 2006, Pittsburgh, Pennsylvania, United States, 9 pages. [cited by applicant]
Li et al., “Stochastic Variance Reduced Optimization for Nonconvex Sparse Learning”, Jun. 19-24, 2016, New York City, New York, United States, 9 pages. [cited by applicant]
Luo et al., “Adaptive Gradient Methods with Dynamic Bound of Learning Rate”, International Conference on Learning Representations, May 6-9, 2019, New Orleans, Louisiana, United States, 21 pages. [cited by applicant]
Luong et al., “Stanford Neural Machine Translation Systems for Spoken Language Domain”, International Workshop on Spoken Language Translation, Dec. 3-4, 2015, Da Nang, Vietnam, 4 pages. [cited by applicant]
Ma et al., “End-To-End Sequence Labeling via Bi-directional LSTM-CNNs-CRF”, arXiv:1603.01354v5, May 29, 2016, 12 pages. [cited by applicant]
Martens et al., “Deep learning via Hessian-free optimization”, Conference on Learning Theory, Jun. 27-29, 2010, Haifa, Israel, 8 pages. [cited by applicant]
Martens et al., “Optimizing Neural Networks with Kronecker-factored Approximate Curvature”; arXiv:1503.05671v7, Jun. 8, 2020, 58 pages. [cited by applicant]
McMahan et al., “Adaptive Bound Optimization for Online Convex Optimization”, Conference on Learning Theory, Jun. 27-29, 2010, Haifa, Israel, 15 pages,. [cited by applicant]
McMahan et al., “Communication-Efficient Learning of Deep Networks from Decentralized Data”, International Conference on Artificial Intelligence and Statistics (AISTATS), Apr. 20-22, 2017, Ft. Lauderdale, Florida, Unite… [cited by applicant]
Nesterov, “Introductory Lectures on Convex Optimization: A Basic Course”, Applied Optimization, vol. 87, Kluwer Academic Publishers, Massachusetts, 2004, 253 pages. [cited by applicant]
Reddi et al., “A Generic Approach for Escaping Saddle points”, arXiv:1709.01434v1. Sep. 5, 2017, 18 pages. [cited by applicant]
Reddi et al., “Fast Incremental Method for Nonconvex Optimization”, arXi: 1603.06159v1, Mar. 19, 2016, 14 pages. [cited by applicant]
Reddi et al., “Fast Stochastic Methods for Nonsmooth Nonconvex Optimization”, arXiv:1605.06900v1, May 23, 2016, 24 pages. [cited by applicant]
Reddi et al., “On the Convergency of Adam and Beyond”, arXiv41 1904vl, Apr. 19, 2019, 23 pages. [cited by applicant]
Reddi et al., “Stochastic Variance Reduction for Nonconvex Optimization”, arXiv:1603.06160v2, Apr. 4, 2016, 26 pages. [cited by applicant]
Robbins et al., “A Stochastic Approximation Method”, The Annals of Mathematical Statistics, vol. 22, No. 3. Sep. 1951, pp. 400-407. [cited by applicant]
Sahu et al., “On the Convergence of Federated Optimization in Heterogeneous Networks”, arXiv: 1812.06127v1, Dec. 14, 2018, 12 pages. [cited by applicant]
Sennrich et al., “Neural Machine Translation of Rare Words with Subword Units”, arXiv:1508.07909v5, Jun. 10, 2016, 11 pages. [cited by applicant]
Stefan, “Neural Machine Translation system for English to Vietnamese”, https://github.com/stefan-it/nmt-en-vi, retrieved on May 27, 2021, 5 pages. [cited by applicant]
Stich et al., “The Error-Feedback Framework: Better Rates for SGD with Delayed Gradients and Compressed Communication”, arXiv:1909.05350v1, Sep. 11, 2019, 29 pages. [cited by applicant]
Stich, “Local SGD Converges Fast and Communicates Little”, International Conference on Learning Representations, May 6-9, 2019, New Orleans, Louisiana, United States, 17 pages. [cited by applicant]
Sutskever et al., “On the Importance of Initialization and Momentum in Deep Learning”, International Conference on Machine Learning, Jun. 16-23, 2013, Atlanta, Georgia, United States, 9 pages. [cited by applicant]
Szegedy et al., “Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning”, arXiv: 160207261v2, Aug. 23, 2016, 12 pages. [cited by applicant]
Tensorflow Federated Authors, “TensorFlow Federated Stack Overflow Dataset”, 2019, https://www.tensorflow.org/federated/apidocs/python/tff/simulation/datasets/stackoverflow/load_data, Retrieved on May 24, 2021, 3 pages. [cited by applicant]
Tieleman et al., “RmsProp: Divide the Gradient by a Running Average of its Recent Magnitude”, Coursera: Neural Networks for Machine Learning, vol. 4, Issue 2, Oct. 2012, pp. 26-31. [cited by applicant]
Tong et al., “Effective Federated Adaptive Gradient Methods with Non-IID Decentralized Data”, arXiv:2009.06557v2, Dec. 22, 2020, 42 pages. [cited by applicant]
Vaswani et al., “Attention is All you Need”, Conference on Neural Information Processing Systems, Dec. 4-9, 2017, Long Beach, California, United States, 11 pages. [cited by applicant]
Vinyals et al., “Krylov Subspace Descent for Deep Learning”, arXiv:1111.4259v1, Nov. 18, 2011, 11 pages. [cited by applicant]
Wang et al., “Adaptive Federated Learning in Resource Constrained Edge Computing Systems”, arXiv:1804.05271v3, Feb. 17, 2019, 20 pages. [cited by applicant]
Wang et al., “Cooperative SGD: A Unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithms”, arXiv:1808.07576v2, Oct. 19, 2018, 23 pages. [cited by applicant]
Wang et al., “Cross-Type Biomedical Named Entity Recognition with Deep Multi-Task Learning”, arXiv:1801.09851v4, Oct. 8, 2018, 7 pages. [cited by applicant]
Ward et al., “AdaGrad Stepsizes: Sharp Convergence over Nonconvex Landscapes, from any Initialization”, arXiv:1806.01811v5, Jun. 21, 2018, 17 pages. [cited by applicant]
Wu et al., “3D ShapeNets: A Deep Representation for Volumetric Shapes”, Conference on Computer Vision and Pattern Recognition, Jun. 7-12, 2015, Boston, Massachusetts, United States, 9 pages. [cited by applicant]
Wu et al., “Global Convergence of Adaptive Gradient Methods for an Over-parameterized Neural Network”, arXiv:1902.07111v2, Oct. 19, 2019, 27 pages. [cited by applicant]
Wu et al., “Group Normalization”, European Conference on Computer Vision, Sep. 8-14, 2018, Munich, Germany, 17 pages. [cited by applicant]
Xie et al., “Local AdaAlter: Communication-Efficient Stochastic Gradient Descent with Adaptive Learning Rates”, arXiv:1911.09030v1, Nov. 20, 2019, 18 pages. [cited by applicant]
Yu et al., “Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learning”, AAAI Conference on Artificial Intelligence, Jan. 27-Feb. 1, 2019, Honolulu, H… [cited by applicant]
Zaheer et al. “Adaptive Methods for Nonconvex Optimization”, Conference on Neural Information Processing Systems, 2018, 11 pages. [cited by applicant]
Zaheer et al., “Deep Sets”, arXiv:1703.06114v3, Apr. 14, 2018, 29 pages. [cited by applicant]
Zeiler, “Adadelta: An Adaptive Learning Rate Method”, arXiv:1212.5701v1, Dec. 22, 2012, 6 pages. [cited by applicant]
Zhang et al., “Lookahead Optimizer: k steps forward, 1 step back”, Conference on Neural Information Processing Systems, Dec. 8-14, 2019, Vancouver, Canada, 12 pages. [cited by applicant]
Zhang et al., “Why Adam Beats SGD for Attention Models”, arXiv:1912.03194v1. Dec. 6, 2019, 20 pages. [cited by applicant]
Zinkevich et al., “Parallelized Stochastic Gradient Descent”, Conference on Neural Information Processing Systems, Dec. 6-11, 2010, Vancouver, Canada, 9 pages. [cited by applicant]
McMahan et al., “Federated Learning of Deep Networks using Model Averaging”, arXiv:1602.05629v1, 11 pages, Feb. 17, 2016. [cited by applicant]