arXiv research

Better Hessian approximations improve influence function attributions in deep learning.

We consider variants of trust-region and cubic regularization methods for non-convex optimization, in which the Hessian matrix is approximated. Under mild conditions on the inexact Hessian, and using approximate solution of the corresponding sub-problems, we provide iteration complexity to achieve $ε$-approximate seco…

Proposes a new method for optimizing large-scale models using Nyström approximation of the Hessian.

Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent are easily scaled for very large problems but may involve fine-tuning many hyper-parameters. Quasi-Newton approaches based on the lim…

We analyze the Hessian spectra of large models up to 100B parameters.

Apollo improves nonconvex stochastic optimization efficiency.

Approximate Newton methods are a standard optimization tool which aim to maintain the benefits of Newton's method, such as a fast rate of convergence, whilst alleviating its drawbacks, such as computationally expensive calculation or estimation of the inverse Hessian. In this work we investigate approximate Newton meth…

In this work we develop Curvature Propagation (CP), a general technique for efficiently computing unbiased approximations of the Hessian of any function that is computed using a computational graph. At the cost of roughly two gradient evaluations, CP can give a rank-1 approximation of the whole Hessian, and can be repe…

The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear ra…

New Hessian-free method improves bilevel optimization for meta-learning.

The most fruitful approach to studying low energy soliton dynamics in field theories of Bogomol'nyi type is the geodesic approximation of Manton. In the case of vortices and monopoles, Stuart has obtained rigorous estimates of the errors in this approximation, and hence proved that it is valid in the low speed regime. …

ASTRA improves TDA by more accurately approximating iHVP.

Improved neural network ensembles using Stein Variational Newton updates.

Subsampled Newton methods approximate Hessian matrices through subsampling techniques, alleviating the cost of forming Hessian matrices but using sufficient curvature information. However, previous results require $Ω(d)$ samples to approximate Hessians, where $d$ is the dimension of data points, making it less practica…

We consdier in dimension four weakly convergent sequences of approximate biharmonic maos into sphere with bi-tension fields bounded in $L^p$ for some $p>1$. We prove an energy identity that accounts for the loss of Hessian energies by the sum of Hessian energies over finitely many nontrivial biharmonic maps on $\mathbb…

Zeroth-order optimization is an important research topic in machine learning. In recent years, it has become a key tool in black-box adversarial attack to neural network based image classifiers. However, existing zeroth-order optimization algorithms rarely extract second-order information of the model function. In this…

We apply state-of-the-art tools in modern high-dimensional numerical linear algebra to approximate efficiently the spectrum of the Hessian of modern deepnets, with tens of millions of parameters, trained on real data. Our results corroborate previous findings, based on small-scale networks, that the Hessian exhibits "s…

HA-SME models SGD dynamics with Hessian info for better escaping behaviors.

Enhances influence functions for deep models without costly Hessian inversion.

Learning RBMs using standard algorithms such as CD(k) involves gradient descent on the negative log-likelihood. One of the terms in the gradient, which involves expectation w.r.t. the model distribution, is intractable and is obtained through an MCMC estimate. In this work we show that the Hessian of the log-likelihood…

Shampoo optimizes preconditioners for faster convergence in machine learning.

Improved robustness in optimization methods using second-order information.

We consider in dimension four weakly convergent sequences of approximate biharmonic maps to a Riemannian manifold with bi-tension fields bounded in $L^p$ for $p>\frac43$. We prove an energy identity that accounts for the loss of hessian energies by the sum of hessian energies over finitely many nontrivial biharmonic ma…

We propose a modular extension of backpropagation for the computation of block-diagonal approximations to various curvature matrices of the training objective (in particular, the Hessian, generalized Gauss-Newton, and positive-curvature Hessian). The approach reduces the otherwise tedious manual derivation of these mat…

NHGD solves bilevel optimization problems with reduced computational time.

A parallel optimization method for convex functions using Hessian sketching and debiasing.

Let $(X,ω)$ be a compact Kähler manifold of dimension $n$ and fix $m\in \mathbb{N}$ such that $1\leq m \leq n$. We prove that any $(ω,m)$-sh function can be approximated from above by smooth $(ω,m)$-sh functions. A potential theory for the complex Hessian equation is also developed which generalizes the classical pluri…

SNS accelerates Sinkhorn algorithm with sparse Newton iterations.

Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coo…

D2SRM solves complex PDEs using deep learning.

New algorithms estimate Hessians using random directions for faster stochastic optimization.

In supervised learning using kernel methods, we often encounter a large-scale finite-sum minimization over a reproducing kernel Hilbert space (RKHS). Large-scale finite-sum problems can be solved using efficient variants of Newton method, where the Hessian is approximated via sub-samples of data. In RKHS, however, the …

New methods optimize functions faster with less gradient accuracy needed.

Develops efficient quasi-Newton methods for training deep neural networks.

Second-order methods for neural network optimization have several advantages over methods based on first-order gradient descent, including better scaling to large mini-batch sizes and fewer updates needed for convergence. But they are rarely applied to deep learning in practice because of high computational cost and th…

Our goal is to improve variance reducing stochastic methods through better control variates. We first propose a modification of SVRG which uses the Hessian to track gradients over time, rather than to recondition, increasing the correlation of the control variates and leading to faster theoretical convergence close to …

New methods use Kronecker-factored approximations for faster deep learning optimization.

Paper tackles Hessian/Jacobian-free stochastic bilevel optimization with ${O}(ε^{-1.5})$ complexity.

A new spline method for manifold learning using Hessian-based curvature penalties.

Natural gradient descent is an optimization method traditionally motivated from the perspective of information geometry, and works well for many applications as an alternative to stochastic gradient descent. In this paper we critically analyze this method and its properties, and show how it can be viewed as a type of 2…

Stochastic Variance-Reduced Cubic regularization (SVRC) algorithms have received increasing attention due to its improved gradient/Hessian complexities (i.e., number of queries to stochastic gradient/Hessian oracles) to find local minima for nonconvex finite-sum optimization. However, it is unclear whether existing SVR…

Enhances SMC² with Hessian info for more efficient posterior approximation.

In this paper, we propose a second order optimization method to learn models where both the dimensionality of the parameter space and the number of training samples is high. In our method, we construct on each iteration a Krylov subspace formed by the gradient and an approximation to the Hessian matrix, and then use a …

We show that Newton's method converges globally at a linear rate for objective functions whose Hessians are stable. This class of problems includes many functions which are not strongly convex, such as logistic regression. Our linear convergence result is (i) affine-invariant, and holds even if an (ii) approximate Hess…

Improved continual learning for neural networks with BN layers using K-FAC extension.

Analyzes the structure and rank of neural network Hessians.

A new method for training diffusion models using likelihood matching.

WoodFisher improves neural network compression efficiency and accuracy.