Efficiently solves Elastic Net in high dimensions with Newton method.
problem Feature selection in high-dimensional data with non-negligible collinearity.
method Semi-smooth Newton Augmented Lagrangian Method.
result Significantly reduces computational cost compared to competitors.
This paper approximates scattered data using samplet coordinates with sparsity constraints.
problem Scattered data approximation with sparsity constraints.
method Samplet basis pursuit with ℓ1-regularization, multiresolution techniques, and semi-smooth Newton method. result The proposed method provides faster convergence and better signal sparsity compared to existing methods.
Improved sampling algorithm with state-of-the-art complexity bounds.
problem Efficient sampling from various probability distributions.
method Proximal sampler with inexact restricted Gaussian oracle.
result State-of-the-art complexity bounds in almost all settings.
This paper analyzes the convergence of Federated Average under relaxed assumptions.
problem Lack of theoretical analysis for Federated Average under assumptions beyond smoothness.
method Relaxing assumptions of strong smoothness to semi-smoothness and semi-Lipschitz properties, and introducing a bound on the gradient.
result Provides a theoretical convergence study on Federated Learning under new assumptions.
A new multi-task learning estimator improves Gaussian graphical regression model fitting.
problem High error rate in fitting Gaussian graphical regression models due to separate node-wise lasso regressions.
method Proposes a multi-task learning estimator with cross-task group sparsity and within-task element-wise sparsity penalties, solved via an efficient augmented Lagrangian algorithm.
result Error rate improvement over separate node-wise lasso estimates, demonstrated through simulations and application to gene co-expression network study.
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.
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.
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…
We describe stochastic Newton and stochastic quasi-Newton approaches to efficiently solve large linear least-squares problems where the very large data sets present a significant computational burden (e.g., the size may exceed computer memory or data are collected in real-time). In our proposed framework, stochasticity…
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.
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.
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.
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.
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 present two new remarkably simple stochastic second-order methods for minimizing the average of a very large number of sufficiently smooth and strongly convex functions. The first is a stochastic variant of Newton's method (SN), and the second is a stochastic variant of cubically regularized Newton's method (SCN). W…
The second order method as Newton Step is a suitable technique in Online Learning to guarantee regret bound. The large data is a challenge in Newton method to store second order matrices as hessian. In this paper, we have proposed an modified online Newton step that store first and second order matrices of dimension m …
SVRN accelerates Newton methods by reducing variance and improving performance.
problem Improving the efficiency of Newton methods for large-scale optimization problems.
method Stochastic Variance-Reduced Newton (SVRN) algorithm that accelerates Subsampled Newton and Iterative Hessian Sketch algorithms.
result SVRN accelerates Newton methods by reducing the number of passes over the data, achieving a significant improvement in performance.
New quasi-Newton method guarantees global superlinear convergence.
problem Global convergence and superlinear convergence of quasi-Newton methods.
method Hybrid proximal extragradient method with online learning for Hessian approximation.
result First globally convergent quasi-Newton method with explicit superlinear convergence rate.
Deep learning involves a difficult non-convex optimization problem, which is often solved by stochastic gradient (SG) methods. While SG is usually effective, it may not be robust in some situations. Recently, Newton methods have been investigated as an alternative optimization technique, but nearly all existing studies…
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…
A new quasi-Newton method uses cubic regularization to avoid saddle points in deep learning.
problem Avoiding saddle points and poor local minima in deep learning models.
method Limited-memory symmetric rank-one quasi-Newton approach with adaptive regularized cubics.
result The method effectively avoids saddle points and converges to better local minima.
Four decades after their invention, quasi-Newton methods are still state of the art in unconstrained numerical optimization. Although not usually interpreted thus, these are learning algorithms that fit a local quadratic approximation to the objective function. We show that many, including the most popular, quasi-Newto…
Proposes a Quasi-Newton trust region method for policy optimization in reinforcement learning.
problem Lack of stepsize selection criterion and slow convergence in gradient descent for policy optimization.
method Uses a trust region method with Quasi-Newton approximation for the Hessian.
result Demonstrates improved performance and efficiency in continuous control tasks.
Improved root-finding method for smooth functions.
problem Finding roots of smooth functions efficiently and reliably.
method A new improvement over Newton's method for doubly differentiable functions.
result Faster and more reliable convergence compared to Newton's method.
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.
ISAAC Newton uses input-based curvature for efficient training.
problem Efficient training in small-batch stochastic regimes.
method ISAAC Newton conditions gradients using selected second-order information based on input.
result Effective training even in small-batch stochastic regimes, competitive to first-order and second-order methods.
Recently algorithms incorporating second order curvature information have become popular in training neural networks. The Nesterov's Accelerated Quasi-Newton (NAQ) method has shown to effectively accelerate the BFGS quasi-Newton method by incorporating the momentum term and Nesterov's accelerated gradient vector. A sto…
A new Bayesian filtering method speeds up stochastic Newton optimization.
problem Minimizing log-convex functions using stochastic methods.
method Contextualizes the problem as Bayesian inference, applying Bayesian filtering to update estimates.
result Establishes conditions for diminishing effect of older observations, akin to momentum.
A new method for faster optimization on statistical manifolds.
problem Slow convergence of first-order methods in manifold optimization.
method Dual Riemannian Newton method on manifolds with dual connections.
result Local quadratic convergence of the dual Riemannian Newton method.
A new method solves distributed optimization problems over networks.
problem Solving optimization problems over networks with local cost functions and limited communication.
method Distributed semismooth Newton based augmented Lagrangian method.
result The method efficiently solves distributed optimization problems over networks.
The Gauss-Newton method is analyzed for neural networks using Riemannian optimization techniques.
problem Training neural networks with smooth activations and convergence rates.
method Riemannian optimization perspective, analyzing the Gauss-Newton method in both underparameterized and overparameterized regimes.
result Geometric convergence rates independent of conditioning and eigenvalues, demonstrating accelerated convergence.
Paper proposes a new method to efficiently incorporate curvature information in stochastic optimization.
problem Minimizing nonconvex functions with limited curvature information.
method Structured stochastic quasi-Newton method using partial Hessian information.
result Global convergence to stationary point and local superlinear convergence rate established.
Recent studies incorporate Nesterov's accelerated gradient method for the acceleration of gradient based training. The Nesterov's Accelerated Quasi-Newton (NAQ) method has shown to drastically improve the convergence speed compared to the conventional quasi-Newton method. This paper implements NAQ for non-convex optimi…
For distributed computing environment, we consider the empirical risk minimization problem and propose a distributed and communication-efficient Newton-type optimization method. At every iteration, each worker locally finds an Approximate NewTon (ANT) direction, which is sent to the main driver. The main driver, then, …
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.
In [19], a general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed and a sublinear global convergence rate has been established. In this paper, we analyze the convergence properties of this method, both in the exact and inexact setting, in the case when the obje…
In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via…
Develops a new screening method called Newton screening for faster and more accurate sparse learning.
problem Sparse learning problems with large-scale optimization.
method Newton screening method with built-in working set and dual variable updates.
result Newton screening achieves one-step local convergence and sharp estimation error bound.
New algorithm improves convergence of gradient boosting trees.
problem Global convergence of Newton boosting in tabular machine learning.
method Introduces Gradient Regularized Newton Descent for GBDTs, proving linear convergence for smooth, strongly convex losses and O(k21) rate for general convex losses. result Achieves globally convergent second-order GBDT algorithm with rate matching first-order boosting.
We consider stochastic zero-order optimization problems, which arise in settings from simulation optimization to reinforcement learning. We propose an adaptive sampling quasi-Newton method where we estimate the gradients of a stochastic function using finite differences within a common random number framework. We emplo…
Improved neural network ensembles using Stein Variational Newton updates.
problem Lack of efficient second-order information in current ensemble methods.
method Proposes a novel approximate Bayesian inference method integrating Stein Variational Newton updates with scalable Hessian approximations.
result Significantly faster convergence and more accurate posterior distribution approximations.
A new method for machine learning updates reduces complexity and improves robustness.
problem Stochastic gradient updates are inefficient and sensitive to feature scaling.
method Incremental Gauss-Newton Descent (IGND) reduces the need for matrix operations and improves robustness.
result IGND improves robustness to sensitivity scaling and can be competitive with common stochastic optimizers.
A general class of Newton algorithms on Graßmann and Lagrange-Graßmann manifolds is introduced, that depends on an arbitrary pair of local coordinates. Local quadratic convergence of the algorithm is shown under a suitable condition on the choice of coordinate systems. Our result extends and unifies previous convergenc…
Newton's method converges faster than gradient descent in overparameterized neural networks.
problem Training neural networks efficiently in the overparameterized limit.
method Developed a convergence analysis for the regularized Newton method in this context.
result The NN training dynamics converge to the solution of a deterministic limit equation involving a Newton neural tangent kernel (NNTK).
Deep learning involves a difficult non-convex optimization problem with a large number of weights between any two adjacent layers of a deep structure. To handle large data sets or complicated networks, distributed training is needed, but the calculation of function, gradient, and Hessian is expensive. In particular, th…
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.
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…