Novel Newton method for large-scale kernel methods using random features.
problem Efficiently solving large-scale finite-sum minimization problems in RKHS.
method Randomized feature-based Newton method for empirical risk minimization.
result Local superlinear and global linear convergence of the method.
Newton-LESS sparsifies Gaussian sketching for faster optimization.
problem Computing the Hessian matrix in optimization is computationally expensive.
method Uses a sparsified version of a dense Gaussian sketching matrix.
result Achieves nearly the same convergence rate as dense Gaussian embeddings without the computational cost.
Paper proposes an efficient online Newton method with Nesterov's acceleration for streaming data.
problem Efficient inference of online Newton methods with robustness to noise and ill-conditioning.
method Online Newton method with Hessian averaging and Nesterov's accelerated sketch-and-project solver.
result Global almost-sure convergence and asymptotic normality of the last iterate with non-asymptotic convergence guarantees.
New method solves constrained optimization problems efficiently.
problem Equality-constrained nonlinear, nonconvex optimization problems.
method Adaptive inexact Newton method with randomized iterative sketching.
result Global almost sure convergence and local linear/superlinear convergence.
Study on Newton-Sketch and Subsampled Newton methods for large-scale optimization.
problem Optimization of large-scale finite-sum problems with high-dimensional data.
method Hessian subsampling and randomized Hadamard transformations for dimensionality reduction in Newton's method.
result Advantages of conjugate gradient vs. stochastic gradient iterations revealed through experiments.
Corrects bias in random sampling matrices for improved ML methods.
problem Inversion bias in random sampling matrices hampers ML applications.
method Corrects inversion bias for various random sampling methods.
result Establishes local convergence rates for sub-sampled Newton methods.
New method uses adaptive sampling for optimization in uncertain conditions.
problem Optimizing functions with unknown gradients in uncertain environments.
method Adaptive sampling quasi-Newton method with finite differences and norm tests.
result Potential performance benefits of the proposed method demonstrated in preliminary experiments.
We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, wi…
Paper proposes an online covariance estimator for sketched Newton methods.
problem Estimating the limiting covariance matrix of sketched Newton methods.
method Proposes a fully online covariance matrix estimator from Newton iterates.
result Establishes the consistency and convergence rate of the proposed estimator.
Bayesian coresets improved with random sampling and quasi-Newton optimization.
problem Efficiently approximate Bayesian posterior distributions for computationally expensive inference.
method Randomly select a subset of data points, then optimize weights using quasi-Newton method.
result First algorithm with high-probability KL divergence bound on coreset quality.
SnapBoost uses random base hypothesis classes to improve gradient boosting performance.
problem Improving gradient boosting performance.
method Heterogeneous Newton Boosting Machine (HNBM) with variable base hypothesis classes.
result SnapBoost achieves better generalization loss than competing frameworks.
A new method solves nonsmooth nonconvex optimization problems with noisy gradients.
problem Solving nonsmooth nonconvex optimization problems with noisy gradient information.
method Globalized stochastic semismooth Newton method combining semismooth Newton steps and proximal gradient steps.
result The method converges globally to stationary points in expectation and locally r-superlinearly.
Random polynomial dynamical systems often have negative Lyapunov exponents.
problem Understanding the behavior of random polynomial dynamical systems.
method Investigation of i.i.d. random complex dynamical systems generated by probability measures.
result For a generic system, the Lyapunov exponent of almost every sequence of maps is negative for most initial values.
A new method for faster optimization in high dimensions.
problem Slow convergence in high-dimensional optimization problems.
method Subspace cubic regularized Newton method within Krylov subspace.
result Achieves a dimension-independent convergence rate of O(1/mk + 1/k^2).
New algorithms estimate Hessians using random directions for faster stochastic optimization.
problem Efficiently estimating Hessians for stochastic optimization.
method Generalized Hessian estimators using random directions and noisy function measurements.
result Asymptotically unbiased estimators with lower bias for more measurements.
New Q-Newton's method avoids saddle points and converges quadratically.
problem Optimizing functions with saddle points and ensuring convergence guarantees.
method Modified New Q-Newton's method with Backtracking line search.
result Theorem for Morse functions: quadratic convergence to local minima.
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.
A new method avoids saddle points in Newton's method.
problem Avoiding saddle points in optimization problems.
method New Q-Newton's method with specific update rule.
result The method guarantees convergence to a critical point that is not a saddle point.
Proposes a new method to solve large-scale CSC minimization problems.
problem Composite self-concordant minimization problems in machine learning.
method Randomized block proximal damped Newton (RBPDN) method.
result RBPDN method significantly reduces computational cost per iteration.
New method improves zeroth-order stochastic optimization with adaptive sampling.
problem Optimization problems without gradient information.
method Adaptive sampling quasi-Newton method using finite differences.
result Significant improvement in performance with adaptive sample sizes.
Improved sampling for complex distributions using quasi-Newton proposals.
problem Sampling from complex, high-dimensional target distributions efficiently.
method Extended pseudo-marginal Metropolis-Hastings with quasi-Newton proposals.
result Quasi-Newton proposals outperform standard random-walk and Hessian-based proposals.
Develops precise expressions for random projections for better machine learning tasks.
problem Improving the accuracy of dimensionality reduction in machine learning tasks.
method Exploits recent developments in spectral analysis of random matrices to derive accurate expressions for random projection matrices.
result Provides precise expressions that reflect the practical performance of sketching methods, including Gaussian and Rademacher sketches.
Determinantal averaging corrects inversion bias in distributed Newton's method.
problem Inverting a sum of distributed matrices is biased; local averages are incorrect.
method Reweighting local estimates of the Newton's step proportionally to the determinant of the local Hessian estimate, then averaging them.
result Determinantal averaging provides the first known asymptotically consistent distributed Newton step.
Stochastic Newton and quasi-Newton methods solve large linear least-squares problems efficiently.
problem Efficiently solve large linear least-squares problems with limited computational resources.
method Introduce stochasticity in Newton and quasi-Newton approaches to handle large datasets.
result Stochastic Newton iterates may not converge to the least-squares solution.
Two new sampling methods improve machine learning optimization.
problem Efficiently solving machine learning empirical risk minimization problems.
method Randomly sampled quasi-Newton methods for optimization.
result Sampled methods outperform classical variants in machine learning tasks.
New algorithms reduce Newton method complexity by non-uniformly sampling Hessians.
problem Finding minimizers of convex functions with high-rank Hessians.
method Randomized Newton-type algorithms with non-uniform sub-sampling.
result Non-uniform sampling of Hessians at most O(d log d) terms achieves linear-quadratic convergence.
A new method for optimization in probability space using Newton's flows.
problem Optimization in probability space with information metrics.
method Information Newton's flows, including Fisher-Rao and Wasserstein-2 metrics, with Newton's Langevin dynamics and variational methods.
result Effective numerical implementation and convergence results for the proposed method.
This paper introduces online algorithms to estimate robust geometric median in large data streams.
problem Detecting outliers in large data sets using robust statistical measures.
method Online stochastic Newton methods for estimating the geometric median.
result Rates of convergence for online estimation of the geometric median.
Newton's method solves variational problems on manifolds.
problem Solving variational equations on manifolds.
method Newton's method with affine covariant damping strategy.
result Numerical results for variational problems demonstrated.
Simple stochastic Newton and cubic Newton methods with fast convergence.
problem Minimizing large numbers of smooth and strongly convex functions.
method Stochastic Newton and cubic Newton methods with simple local linear-quadratic rates.
result Local linear-quadratic convergence results with fast adaptation to problem's curvature.
Newton methods improve CNN optimization, showing competitive accuracy.
problem Optimizing CNNs for deep learning applications.
method Detailed investigation and implementation of Newton methods for CNNs.
result Newton methods for CNNs achieve competitive test accuracy.
We generalize Newton-type methods for minimizing smooth functions to handle a sum of two convex functions: a smooth function and a nonsmooth function with a simple proximal mapping. We show that the resulting proximal Newton-type methods inherit the desirable convergence behavior of Newton-type methods for minimizing s…
Modified Newton step for online learning reduces matrix size for large datasets.
problem Handling large multi-class datasets efficiently in online learning.
method Element-wise multiplication to reduce matrix size of second order matrices.
result Proposed method achieves similar mistake rates to popular methods but with faster computations.
New method improves MCMC for large data problems with better mixing rates.
problem Poor mixing rates in vanilla SG-MCMC for strong couplings and scale differences.
method Uses Quasi-Newton optimization ideas to approximate Hessian and scale linearly.
result Asymptotically unbiased and consistent with posterior expectations, achieving fast convergence rates.
New optimization methods reduce computational complexity for large-scale problems.
problem Optimizing large sums of functions with high-dimensional parameters.
method Sub-sampling Hessian and gradient, using random matrix concentration and RandNLA.
result Locally Q-linear and Q-superlinear convergence rates for sub-sampled Newton methods.
A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for these l…
The paper analyzes Newton-like and inexact Newton methods for stochastic optimization problems.
problem Optimization of stochastic problems with approximated gradients and Hessians.
method Newton-like methods using subsampled gradients and Hessians, and inexact Newton methods using conjugate gradient for Hessian approximation.
result Inexact Newton methods can achieve similar convergence rates to exact methods, with lower computational cost.
The paper develops methods for unconstrained optimization on Riemannian manifolds.
problem Optimization on Riemannian manifolds with general functions.
method Developed explicit versions of gradient descent and Newton's method for Riemannian optimization.
result The algorithms either converge to a local minimum or diverge to infinity, depending on the function and manifold properties.
Unified approach to Bayesian inference with guarantees on covariance matrices.
problem Approximate Bayesian inference with PSD guarantees.
method Bayes-Newton methods extending Newton's method for optimisation.
result Novel algorithms with PSD covariance matrices.
Newton's method tackles nonlinear mappings into vector bundles with connections and retractions.
problem Finding zeros of mappings from a manifold into a vector bundle.
method Local convergence using differentiability concepts, Banach space Riemannian distance, and affine covariant damping strategy.
result Illustrated application to generalized non-symmetric eigenvalue problems.
GIANT optimizes distributed computing by improving Newton method efficiency.
problem Efficiently solving empirical risk minimization problems in distributed environments.
method GIANT combines local ANT directions to form a GIANT direction, averaging communications and computations.
result GIANT achieves faster convergence compared to first-order and existing Newton-type methods.
This research compares gradient and Newton boosting methods in classification and regression.
problem The distinction between gradient descent and Newton updates in boosting algorithms is not well understood.
method Presented a unified framework for gradient and Newton boosting, and compared them with tree base learners.
result Newton boosting outperforms gradient and hybrid boosting in predictive accuracy on most datasets.
A new optimization method improves deep learning accuracy without hyper-parameter tuning.
problem Computational demands and convergence behavior in deep learning training.
method Stochastic quasi-Gauss-Newton (SQGN) optimization method combining stochastic quasi-Newton, Gauss-Newton, and variance reduction.
result SQGN provides excellent accuracy without hyper-parameter experimentation, improving convergence and computational performance.
Pathfinder uses quasi-Newton optimization for variational inference.
problem Approximating complex posterior distributions efficiently.
method Pathfinder combines quasi-Newton optimization with variational methods to approximate log densities.
result Pathfinder produces draws with lower KL divergence than ADVI and comparable to HMC, requiring fewer evaluations.
This thesis disentangles Gauss-Newton and variational approximations in Bayesian deep learning.
problem Understanding the interplay between the Gauss-Newton method and variational approximations in Bayesian deep learning.
method Analysis of the Gauss-Newton method and Laplace/Gaussian variational approximations for neural networks.
result The combination of the Gauss-Newton method with approximate inference can be cast as inference in a linear or Gaussian process model.
We consider the class of optimization problems arising from computationally intensive L1-regularized M-estimators, where the function or gradient values are very expensive to compute. A particular instance of interest is the L1-regularized MLE for learning Conditional Random Fields (CRFs), which are a popular class of …
Newton's method converges linearly for stable Hessians, even with approximations.
problem Finding global linear convergence for functions without strong convexity or Lipschitz gradients.
method Global linear convergence of Newton's method for stable Hessians, using approximate Hessians and subproblems.
result Global linear convergence rate for a broad class of functions, superior to first-order methods.
Improved quasi-Newton method for convex optimization with linear and accelerated convergence.
problem Efficiently solving composite optimization problems with strong convexity.
method Proximal quasi-Newton algorithm with accelerated variant.
result Acceleration may not improve convergence in quasi-Newton setting.