ASTRA improves TDA by more accurately approximating iHVP.
problem Improving insights into training data attribution.
method ASTRA uses EKFAC-preconditioner on Neumann series iterations to accurately approximate iHVP.
result Improving iHVP approximation significantly improves TDA performance.
Enhances influence functions for deep models without costly Hessian inversion.
problem Challenges in computing Hessian matrix inverse for deep models.
method Substitutes Hessian inverse with identity matrix and extends applications.
result TracIn method performs well in measuring model utility and fairness.
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…
NHGD solves bilevel optimization problems with reduced computational time.
problem Solving bilevel optimization problems with high computational cost.
method Exploits statistical structure of inner optimization to use empirical Fisher matrix as Hessian surrogate, enabling parallel optimization and approximation.
result NHGD achieves error bounds and sample complexity guarantees matching state-of-the-art methods, with significantly reduced computational time.
WoodFisher improves neural network compression efficiency and accuracy.
problem Efficiently estimating inverse Hessian for neural network optimization.
method WoodFisher: a method to compute a faithful and efficient estimate of the inverse Hessian.
result WoodFisher significantly outperforms state-of-the-art methods for pruning neural networks.
EiGLasso speeds up sparse Kronecker-sum covariance estimation.
problem Sparse Kronecker-sum inverse covariance estimation challenges in scalability and parameter identification.
method Newton's method combined with eigendecomposition of sample and feature graphs, approximating Hessian for speed.
result Two to three orders-of-magnitude speed-up on simulated and real-world data.
Proposes a new method for optimizing large-scale models using Nyström approximation of the Hessian.
problem Optimizing non-convex functions like deep learning models using second-order methods.
method Nyström-approximated curvature for stochastic optimization of large-scale empirical risk minimization.
result The proposed method achieves performance competitive with state-of-the-art first-order and stochastic quasi-Newton methods.
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…
New method uses Gaussian ODE filtering to approximate likelihoods for fast ODE inverse problems.
problem Intractable forward models in likelihood-free inference, especially for ODEs.
method Gaussian ODE filtering to construct local Gaussian likelihood approximations.
result New solvers outperform standard likelihood-free approaches on benchmark systems.
Paper develops efficient methods for estimating Hessian inverses in stochastic optimization.
problem Estimating the inverse Hessian for convex function minimization.
method Robbins-Monro procedure for recursive estimation of the inverse Hessian.
result Develops universal stochastic Newton methods with improved efficiency.
New criterion for solving inverse Hessian equations, including J-equation.
problem Existence of solutions to inverse Hessian equations, including J-equation.
method Stability of pairs in the sense of Paul, formulated in terms of GIT criterion.
result New numerical criterion for existence of solutions to inverse Hessian equations.
New ACV method speeds up CV in high dimensions with approximate low-rank data.
problem Accurate model assessment in high-dimensional, large data settings with expensive algorithms.
method Developed a new ACV algorithm that uses low-rank approximations of the Hessian matrix.
result The new method is fast and accurate in the presence of approximate low-rank data.
A new method tackles bilevel optimization using Lanczos process for efficient hyper-gradient computation.
problem Efficiently solving large-scale bilevel optimization problems with gradient-based methods.
method Constructing low-dimensional approximate Krylov subspaces with the Lanczos process to approximate the Hessian inverse vector product.
result Demonstrates a O(ε−1) convergence rate and efficiency in synthetic and deep learning tasks. Solving a bilevel optimization problem is at the core of several machine learning problems such as hyperparameter tuning, data denoising, meta- and few-shot learning, and training-data poisoning. Different from simultaneous or multi-objective optimization, the steepest descent direction for minimizing the upper-level c…
New method achieves superlinear convergence rate with limited memory.
problem Achieving superlinear convergence rate in quasi-Newton methods with limited memory.
method Limited-memory Greedy BFGS (LG-BFGS) method with displacement aggregation and basis vector selection.
result Explicit non-asymptotic superlinear convergence rate demonstrated.
A parallel optimization method for convex functions using Hessian sketching and debiasing.
problem Massively parallel optimization of convex functions with limited communication.
method Newton method with Hessian sketching and debiasing by workers, server averages descent directions.
result Approximation of Newton step with low-complexity adaptive sketching scheme.
Paper proposes HCDC to improve hyperparameter search efficiency.
problem Poor generalizability of dataset condensation across different hyperparameters.
method HCDC algorithm that matches hyperparameter gradients for synthetic validation dataset.
result HCDC effectively maintains validation-performance rankings of models.
FedNew improves federated learning efficiency and privacy.
problem Low communication efficiency and privacy issues in Newton-type methods for federated learning.
method Introduces a two-level framework using ADMM for inverse Hessian-gradient approximation and Newton's method for global model updates, reducing communication overhead.
result FedNew achieves superior communication efficiency and privacy compared to existing methods.
Recently, Stochastic Gradient Markov Chain Monte Carlo (SG-MCMC) methods have been proposed for scaling up Monte Carlo computations to large data problems. Whilst these approaches have proven useful in many applications, vanilla SG-MCMC might suffer from poor mixing rates when random variables exhibit strong couplings …
RES, a regularized stochastic version of the Broyden-Fletcher-Goldfarb-Shanno (BFGS) quasi-Newton method is proposed to solve convex optimization problems with stochastic objectives. The use of stochastic gradient descent algorithms is widespread, but the number of iterations required to approximate optimal arguments c…
We present two sampled quasi-Newton methods (sampled LBFGS and sampled LSR1) for solving empirical risk minimization problems that arise in machine learning. Contrary to the classical variants of these methods that sequentially build Hessian or inverse Hessian approximations as the optimization progresses, our proposed…
In distributed optimization and distributed numerical linear algebra, we often encounter an inversion bias: if we want to compute a quantity that depends on the inverse of a sum of distributed matrices, then the sum of the inverses does not equal the inverse of the sum. An example of this occurs in distributed Newton's…
We consider large scale empirical risk minimization (ERM) problems, where both the problem dimension and variable size is large. In these cases, most second order methods are infeasible due to the high cost in both computing the Hessian over all samples and computing its inverse in high dimensions. In this paper, we pr…
Paper introduces STSL, a second-order Tweedie sampler for efficient posterior sampling in inverse problems.
problem Computational challenges in sampling from posterior distributions using latent diffusion models.
method Introduces STSL, a novel second-order Tweedie sampler with tractable reverse process.
result STSL achieves 4X and 8X reduction in neural function evaluations compared to state-of-the-art solvers.
Proves solvability of general inverse σ_k equations with constant coefficients.
problem Solvability of general inverse σ_k equations with constant coefficients.
method Proves existence of unique solution if a C-subsolution exists.
result Confirms analytical conjecture for deformed Hermitian--Yang--Mills equation.
Establishes statistical and computational bounds for influence diagnostics.
problem Identifying influential datapoints or subsets in machine learning models.
method Finite-sample statistical bounds and computational complexity for influence functions and approximate maximum influence perturbations.
result Established statistical and computational guarantees for influence diagnostics.
New techniques extend certified unlearning to deep neural networks.
problem Applying certified unlearning to deep neural networks (DNNs) is challenging due to their nonconvex nature.
method Developed simple techniques and an efficient computation method for nonconvex objectives, considering nonconvergence training and sequential unlearning.
result Demonstrated the efficacy of the method on real-world datasets, showing advantages of certified unlearning in DNNs.
Better Hessian approximations improve influence function attributions in deep learning.
problem Influence functions are difficult to compute due to ill-conditioned Hessians, leading to poor data attribution performance.
method Investigated the impact of Hessian approximation quality on influence-function attributions in a controlled setting.
result Better Hessian approximations consistently yield better influence score quality.
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…
In this paper, we consider the inverse hessian quotient curvature flow with star-shaped initial hypersurface in anti-de Sitter-Schwarzschild manifold. We prove that the solution exists for all time, and the second fundamental form converges to identity exponentially fast.
We derive a priori estimates for solutions of a general class of fully non-linear equations on compact Hermitian manifolds. Our method is based on ideas that have been used for different specific equations, such as the complex Monge-Ampère, Hessian and inverse Hessian equations. As an application we solve a class of He…
Develops first and second-order pseudo-mirror descent methods for nonnegative function estimation.
problem Nonnegative function estimation in settings like MLE and trajectory optimization.
method First and second-order pseudo-mirror descent with pseudo-gradients and projections.
result Establishes tradeoffs and non-asymptotic bounds on model complexity.
CWGD measures gradient diversity weighted by curvature, improving SGD convergence.
problem Gradient noise in high-curvature directions is underestimated by standard methods.
method CWGD weights gradient diversity by the inverse square root of the Hessian.
result CWGD-Cosine reduces optimization error by up to 20% compared to standard cosine annealing.
The paper studies efficient Hessian fitting methods for stochastic optimization.
problem Efficient Hessian fitting for stochastic optimization.
method Preconditioned Stochastic Gradient Descent (PSGD) method and Lie groups.
result Hessian fitting problem is strongly convex in certain Lie groups.
Study on curvature flow in Minkowski space for cocompact hypersurfaces.
problem Investigating curvature flow in Minkowski space for cocompact hypersurfaces.
method Investigation of the cocompact inverse \(σ_k\) curvature flow in Minkowski space.
result Longtime existence and convergence of the curvature flow established.
Survey of SDR methods for high-dimensional regression and embedding.
problem Reducing dimensionality in high-dimensional data.
method Involves both statistical and machine learning approaches, covering inverse and forward regression methods.
result Supervised Kernel Dimension Reduction is equivalent to supervised PCA.
New method speeds up Bayesian inverse problem solving with neural operators.
problem Solving infinite-dimensional Bayesian inverse problems with high computational cost.
method Delayed-acceptance geometric MCMC driven by derivative-informed neural operator surrogates.
result Significant speedup in generating posterior samples (3-9 times faster).
Study inverse boundary value problem for Monge-Ampère equation on convex domains.
problem Determine a positive source function from the Dirichlet-to-Neumann map for Monge-Ampère equation.
method Recover Hessian as Riemannian metric, prove DN map uniqueness, develop asymptotic expansions, solve nonlocal ∂-equation. result DN map uniquely determines positive source function in convex Euclidean plane domains.
A new optimisation method efficiently scales Hessian-vector products for neural networks.
problem Challenges in applying second-order quasi-Newton methods due to large Hessian and non-convexity.
method Proposes an optimisation algorithm that asymptotically uses the exact inverse Hessian with modified eigenvalues.
result Demonstrates scalability and comparable performance to other optimisation methods in neural networks.
We propose an algorithm for inexpensive gradient-based hyperparameter optimization that combines the implicit function theorem (IFT) with efficient inverse Hessian approximations. We present results about the relationship between the IFT and differentiating through optimization, motivating our algorithm. We use the pro…
Paper proposes a new method for efficient second-order neural network training.
problem Infeasibility of Hessian calculation and noisy second-order information in deep learning.
method Adopting complex-step directional derivative (CSFD) for accurate Hessian computation and designing an effective Newton Krylov procedure.
result Our method outperforms existing methods and often converges one-order faster.
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 propose a fast second-order method that can be used as a drop-in replacement for current deep learning solvers. Compared to stochastic gradient descent (SGD), it only requires two additional forward-mode automatic differentiation operations per iteration, which has a computational cost comparable to two standard for…
We analyze the Hessian spectra of large models up to 100B parameters.
problem Accurate Hessian spectra of large foundation models are difficult to obtain.
method We use shard-local finite-difference Hessian vector products and stochastic Lanczos quadrature.
result We produce the first large-scale spectral density estimates of foundation models.
The Delta method is a classical procedure for quantifying epistemic uncertainty in statistical models, but its direct application to deep neural networks is prevented by the large number of parameters P. We propose a low cost variant of the Delta method applicable to L2-regularized deep neural networks based on th…
Apollo improves nonconvex stochastic optimization efficiency.
problem Nonconvex stochastic optimization challenges.
method Adaptive parameter-wise diagonal quasi-Newton method approximating Hessian.
result Significant improvements in convergence speed and generalization over SGD and Adam.
We provide a numerically robust and fast method capable of exploiting the local geometry when solving large-scale stochastic optimisation problems. Our key innovation is an auxiliary variable construction coupled with an inverse Hessian approximation computed using a receding history of iterates and gradients. It is th…
The paper solves a conjecture about spacelike hypersurfaces in de Sitter space.
problem Proving an Alexandrov-Fenchel inequality for closed 2-convex spacelike hypersurfaces in de Sitter space.
method Investigating the locally constrained inverse curvature flow to establish the inequality.
result Established an Alexandrov-Fenchel inequality for closed 2-convex spacelike hypersurfaces in de Sitter space.