Second-Order Optimization

Follow this topic Ask about this topic

Second-order optimization studies how curvature can guide updates, often reaching good solutions in fewer steps than gradient-only methods, especially on ill-conditioned problems. Methods include Newton and cubic-regularized steps, Gauss–Newton, quasi-Newton methods such as BFGS, and structured preconditioners such as K-FAC and Shampoo. For neural networks and large models, researchers use Hessian-vector products, low-rank sketches, Kronecker factors, and matrix-function approximations to reduce memory and computation, with evaluations ranging from convex benchmarks and PINNs to language-model pretraining. A central tension is how to obtain reliable curvature cheaply: stale or inaccurate estimates can destabilize training, while exact curvature and its synchronization can be too costly at scale.

Latest papers

92 papers12 papers in the last four weeks, up 20% on the four weeks before. 0.1% of all new papers.

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration
Oct 11, 2023Zeyang Li, Chuxiong Hu, Yunan Wang +4Markov Decision Processes Reinforcement Learning
Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, United States · Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China · College of Artificial Intelligence and the School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China
Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods
Feb 23, 2023El Mahdi Chayti, Martin Jaggi, Nikita DoikovSecond-Order Optimization Stochastic Optimization Convergence
Machine Learning and Optimization Laboratory (MLO), EPFL

Oct 11, 2023J/K move · Enter open · S save

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

Zeyang Li, Chuxiong Hu, Yunan Wang, Guojian Zhan+3

Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, United States · Department of Mechanical Engineering, Tsinghua University, Beijing 100084, China · College of Artificial Intelligence and the School of Vehicle and Mobility, Tsinghua University, Beijing 100084, China

Markov Decision Processes Reinforcement Learning Policy Optimization Policy Iteration Second-Order Optimization Regularized RL

Open paper AskPDF arXiv

Regularization is a cornerstone of modern reinforcement learning. Regularized policy iteration (RPI) provides a fundamental scheme for solving regularized Markov decision processes (RMDPs), and the widely used soft actor-critic algorithm arises as a special case when the regularizer is Shannon entropy. Despite its empirical success, the theoretical underpinnings of RPI remain unclear. In this paper, we address this gap by proving that RPI is formally equivalent to the standard Newton-Raphson method applied to the Bellman equation smoothed by strongly convex regularizers. This equivalence enables a unified convergence analysis of existing methods and supports the development of accelerated algorithms. We show that RPI enjoys local quadratic convergence; notably, for Shannon entropy, the guarantee is dimension-free. We further study RPI with inexact policy evaluation, establishing its equivalence to an inexact Newton method in which each Newton step is solved via truncated iterations, and derive an asymptotic linear convergence rate of

γ^{M}

, where

M

denotes the number of operator steps used in policy evaluation. Finally, motivated by higher-order Newton schemes, we propose a new algorithm for RMDPs that achieves third-order local convergence. Numerical experiments corroborate our theory and demonstrate the practical advantages of the proposed algorithm. Overall, our results advance the theoretical understanding of regularization in reinforcement learning and suggest new directions for efficient algorithm design.

Latest papers

Bridging the Gap between Newton-Raphson Method and Regularized Policy Iteration

Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods