Source-linked AI summary
Learning to Optimize
Ke Li, Jitendra Malik
TL;DR
The paper addresses the laborious, iterative design of optimization algorithms by representing algorithms as policies and learning them with reinforcement learning and guided policy search. The resulting autonomous optimizers converge faster and/or reach better optima than hand-engineered optimizers, within the studied setting.
Problem
Algorithm design is laborious and iterative, motivating automation of unconstrained continuous optimization algorithm design.
Method
The method represents optimization algorithms as policies, defines cost using the current objective value, and learns policies with guided policy search.
Results
The learned autonomous optimizer converges faster and/or reaches better optima than hand-engineered optimizers across studied objective-function classes.
Takeaways & Limitations
Autonomous optimizers may solve common classes of optimization problems more quickly and help accelerate innovation in science and engineering.
Takeaways & Limitations
The dynamics may be unknown and must therefore be estimated; the method focuses on the undiscounted setting with γ = 1.
Abstract
from arXiv · showhide
Algorithm design is a laborious process and often requires many iterations of ideation and validation. In this paper, we explore automating algorithm design and present a method to learn an optimization algorithm, which we believe to be the first method that can automatically discover a better algorithm. We approach this problem from a reinforcement learning perspective and represent any particular optimization algorithm as a policy. We learn an optimization algorithm using guided policy search and demonstrate that the resulting algorithm outperforms existing hand-engineered algorithms in terms of convergence speed and/or the final objective value.
1 Introduction
Algorithm design is laborious because it repeatedly requires ideation, analysis, comparison, and refinement. The paper formulates optimization-algorithm design as reinforcement-learning policy search and reports faster convergence and/or better optima than hand-engineered methods.
- Designers iteratively devise algorithms, test them on examples, compare existing methods, diagnose shortcomings, and refine their designs.
- The paper targets unconstrained continuous optimization, whose widely used methods—including gradient descent, momentum, conjugate gradient, and L-BFGS—are hand-engineered.
- Optimization algorithms are represented as policies, with rewards favoring quick convergence and guided policy search used to learn the policy.
- The learned autonomous optimizer converges faster and/or finds better optima than existing hand-engineered optimization algorithms.
2 Related Work
Related work includes learning from prior tasks, program induction, and hyperparameter search. The paper distinguishes its approach as an attempt to learn a better algorithm automatically.
- Meta-learning uses knowledge from related tasks to train faster, whereas this method can accelerate the training procedure itself without auxiliary-task training.
- Programming by demonstration learns programs from examples of inputs and outputs using explicit or implicit program representations.
- Hyperparameter optimization searches over optimization-algorithm instantiations through Bayesian optimization, random search, or gradient-based optimization.
- The authors characterize their method as the first attempt, to their knowledge, to learn a better algorithm automatically.
3 Method
The method casts optimization as reinforcement-learning policy search: states summarize optimization history, actions are step vectors, and costs reward rapid objective reduction. Guided policy search trains a neural policy on objective-function executions.
- 3 Method: Reinforcement learning selects actions from observed states to minimize cumulative cost, typically formalized as a Markov decision process.
- 3 Method: Policy search approximately finds a parameterized policy that minimizes expected cumulative cost because exact optimization is generally intractable.
- 3 Method: Guided policy search alternates between target trajectory distributions and supervised policy learning using local approximations and trust-region-constrained optimization.
- 3 Method: The policy maps objective values and gradients along the trajectory to the next step vector and is trained with guided policy search.
- 3 Method: An optimization algorithm becomes an MDP policy whose state contains current and past objective information, action is a step vector, and transitions follow location updates.
- 3 Method: The cost at each state equals the current objective value, encouraging the policy to reach the minimum quickly.
- 3 Method: Training and evaluation use randomly generated objective functions drawn from the same distribution.
- 3.3 Discussion: Autonomous optimizers jointly predict step direction and size, dynamically adjusting step size without user-tuned hyperparameters.
4 Experiments
The experiments evaluate learned optimizers on convex logistic regression, non-convex robust regression, and neural-network objectives against hand-engineered methods. The autonomous optimizer generally converges faster and often reaches better optima, with especially strong gains on challenging non-convex problems.
- Experimental setup: The study learns autonomous optimizers for logistic regression, robust linear regression with the Geman-McClure estimator, and two-layer neural-network classification objectives.The logistic-regression objective is convex, whereas the robust-regression objective is non-convex; the neural-network error surface has multiple local optima.
- Logistic Regression: The autonomous optimizer outperforms gradient descent, momentum, and conjugate gradient at almost every logistic-regression iteration, while L-BFGS reaches slightly better optima.It converges faster early, generalizes beyond the training trajectory length of 40, and eventually matches L-BFGS on shown test objectives.
- Robust Linear Regression: 120 objective functions train the robust-regression optimizer, which surpasses all hand-engineered methods after roughly 30 iterations despite momentum’s stronger initial progress.Conjugate gradient and L-BFGS diverge quickly, and the authors suggest non-convexity could explain L-BFGS’s poor performance.
- Robust Linear Regression: On robust-regression test objectives, the autonomous optimizer converges fastest, reaches a better optimum, and largely avoids oscillations affecting gradient descent and momentum.These results are reported for two test-set objective functions shown in Figures 2b and 2c.
- Neural Net Classifier: For neural-network classification, the autonomous optimizer significantly outperforms other methods, reaches better optima, and is less prone to local-optimum trapping and oscillations.The sustained performance gap over momentum is larger than in previous experiments, while non-convexity often causes conjugate gradient and L-BFGS to diverge.
5 Conclusion
The paper learns optimization algorithms by casting them as policies in a reinforcement-learning problem and using guided policy search. Across convex and non-convex objectives, the resulting autonomous optimizers converge faster and/or reach better optima than hand-engineered optimizers.
- Guided policy search learns optimization algorithms by representing each algorithm as a policy and seeking an optimal policy.
- The authors train autonomous optimizers for different classes of convex and non-convex objective functions.
- Autonomous optimizers converge faster and/or reach better optima than hand-engineered optimizers.
- The proposed optimizers are intended to solve common optimization problems more quickly and help accelerate innovation in science and engineering.