# DRSOM: A Dimension Reduced Second-Order Method

arXiv: https://arxiv.org/abs/2208.00208 · HTML: https://mlsanity.com/paper/2208.00208/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 53 references that are in the map.
- First posted on arXiv 30 Jul 2022.

## Builds on (most cited first, 17 of 17)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- ["Convex Until Proven Guilty": Dimension-Free Acceleration of Gradient Descent on Non-Convex Functions](https://mlsanity.com/paper/1705.02766/) (2017)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [iPiano: Inertial Proximal Algorithm for Non-Convex Optimization](https://mlsanity.com/paper/1404.4805/) (2014)
- [Accelerated Methods for Non-Convex Optimization](https://mlsanity.com/paper/1611.00756/) (2016)
- [Worst-Case Complexity of an SQP Method for Nonlinear Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2112.14799/) (2021)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [Non-ergodic Convergence Analysis of Heavy-Ball Algorithms](https://mlsanity.com/paper/1811.01777/) (2018)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Heavy-ball Algorithms Always Escape Saddle Points](https://mlsanity.com/paper/1907.09697/) (2019)
- [Convergence rates for the Heavy-Ball continuous dynamics for non-convex optimization, under Polyak-L ojasiewicz condition](https://mlsanity.com/paper/2107.10123/) (2021)
- [NG+ : A Multi-Step Matrix-Product Natural Gradient Method for Deep Learning](https://mlsanity.com/paper/2106.07454/) (2021)

## Abstract (arXiv)

In this paper, we propose a Dimension-Reduced Second-Order Method (DRSOM) for convex and nonconvex (unconstrained) optimization. Under a trust-region-like framework, our method preserves the convergence of the second-order method while using only curvature information in a few directions. Consequently, the computational overhead of our method remains comparable to the first-order such as the gradient descent method. Theoretically, we show that the method has a local quadratic convergence and a global convergence rate of O(ε-3/2) to satisfy the first-order and second-order conditions if the subspace satisfies a commonly adopted approximated Hessian assumption. We further show that this assumption can be removed if we perform a corrector step using a Krylov-like method periodically at the end stage of the algorithm. The applicability and performance of DRSOM are exhibited by various computational experiments, including L2 - Lp minimization, CUTEst problems, and sensor network localization.