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).
Two new algorithms improve reinforcement learning by avoiding saddle points.
problem Control in reinforcement learning without model information.
method Cubic-regularized Policy Newton algorithms using likelihood ratio method.
result Convergence to a second-order stationary point with improved sample complexity.
The paper applies momentum to CR Newton's method for nonconvex optimization, improving convergence.
problem Improving convergence in nonconvex optimization problems.
method Applying momentum to cubic regularized Newton's method.
result CR with momentum achieves the best convergence rate to second-order stationary points.
A new distributed method for convex optimization over networks with fast convergence.
problem Large-scale convex optimization over networks with limited communication.
method Distributed cubic-regularized Newton method.
result Convergence rate of O ( k − 3 ) O(k^{{-}3}) O ( k − 3 ) for convex functions with Lipschitz gradient and Hessian. 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.
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.
New method solves optimization problems faster than existing methods.
problem Large-scale nonconvex optimization problems.
method ARC method using LQN matrices with exact CR subproblem solution.
result Exact solutions to CR subproblem found in matrix-free manner.
CR method improves convergence for nonconvex optimization under KL property.
problem Improving convergence rate for nonconvex optimization problems.
method Cubic-regularized Newton's method exploiting Kurdyka-Lojasiewicz (KL) property.
result Asymptotic convergence rates of various optimality measures are fully characterized.
Paper shows faster convergence to local-minimizers in over-parametrized models under interpolation-like conditions.
problem Escaping saddle-points in over-parametrized models.
method Stochastic and deterministic optimization algorithms under interpolation-like conditions.
result Oracle complexity of PSGD and SCRN algorithms to reach ε ε ε -local-minimizer matches or improves upon deterministic rates. This paper extends Newton's method to distributed learning, avoiding saddle points and handling Byzantine workers.
problem Avoiding saddle points in distributed non-convex optimization, especially in the presence of Byzantine workers.
method Extends cubic-regularized Newton method to distributed framework, addressing communication bottlenecks and Byzantine attacks.
result The method achieves improved iteration complexity compared to first-order methods, with a 25% improvement in experiments.
This paper proposes a stochastic variant of a classic algorithm---the cubic-regularized Newton method [Nesterov and Polyak 2006]. The proposed algorithm efficiently escapes saddle points and finds approximate local minima for general smooth, nonconvex functions in only O ~ ( ε − 3.5 ) \mathcal{\tilde{O}}(ε^{-3.5}) O ~ ( ε − 3.5 ) stochastic gradien…
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…
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.
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 new algorithm reduces Hessian computation for nonconvex optimization.
problem Finding local minimum in nonconvex optimization efficiently.
method Stochastic variance-reduced cubic regularization (Lite-SVRC) with constant batch size.
result Achieves lower Hessian sample complexity than existing methods.
We consider the minimization of non-convex functions that typically arise in machine learning. Specifically, we focus our attention on a variant of trust region methods known as cubic regularization. This approach is particularly attractive because it escapes strict saddle points and it provides stronger convergence gu…
Stochastic methods tackle inexact Hessian and gradient computations in large-scale non-convex optimization.
problem Efficiently solving non-convex optimization problems with inexact Hessian and gradient computations.
method Stochastic trust region and cubic regularization methods with inexact gradient, Hessian, and function values.
result Achieves ε-approximate second-order optimality with similar iteration complexity as exact computations.
The study analyzes the performance of statistical estimators under stability and computational efficiency.
problem Understanding the performance of statistical estimators in relation to stability and computational efficiency.
method Developed a framework to bound statistical accuracy based on the interplay between algorithm convergence rates and stability.
result Unstable algorithms can achieve the same statistical accuracy as stable ones in fewer steps.
Improved SVRC algorithm reduces complexity for nonconvex optimization.
problem Finding local minima for nonconvex finite-sum optimization with improved complexity.
method Stochastic Recursive Variance-Reduced Cubic regularization (SRVRC) using recursively updated semi-stochastic gradient and Hessian estimators.
result SRVRC achieves improved gradient and Hessian complexities to find ( ε , ε ) (ε, \sqrtε) ( ε , ε ) -approximate local minimum. Paper develops bandit algorithms for nonstationary nonconvex optimization.
problem Nonstationary online nonconvex optimization problems.
method Proposes and analyzes bandit algorithms for nonconvex functions with nonstationary regret.
result Develops bandit versions of Newton's method for nonstationary nonconvex optimization.
Cubic regularization (CR) is an optimization method with emerging popularity due to its capability to escape saddle points and converge to second-order stationary solutions for nonconvex optimization. However, CR encounters a high sample complexity issue for finite-sum problems with a large data size. %Various inexact …
Heavy Ball method speeds up finding global optima in non-convex problems.
problem Finding global optima in non-convex optimization problems.
method Heavy Ball momentum in non-convex optimization.
result Heavy Ball helps iterates enter a benign region faster, containing a global optimal point.
State-of-the-art methods in convex and non-convex optimization employ higher-order derivative information, either implicitly or explicitly. We explore the limitations of higher-order optimization and prove that even for convex optimization, a polynomial dependence on the approximation guarantee and higher-order smoothn…
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.
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…
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 tackles zeroth-order optimization for nonconvex problems with constraints, high-dimensions, and saddle-points.
problem Optimization of nonconvex functions with constraints and high-dimensionality, avoiding saddle-points.
method Proposes zeroth-order stochastic approximation algorithms, including conditional gradient and truncated gradient methods, and a zeroth-order cubic regularization Newton's method.
result Demonstrates algorithms achieving rates similar to standard stochastic gradient methods, with rates dependent on poly-logarithmic dimensionality.
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.
A new algorithm solves minimax problems without needing parameters.
problem Convex-concave minimax optimization problems in machine learning.
method Proposes a fully parameter-free LF-CR and FF-CR algorithms for solving these problems.
result The FF-CR algorithm achieves the best iteration complexity under gradient norm termination criterion.
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.
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.
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.
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.
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.
Efficient methods for training deep neural networks using subsampled Gauss-Newton and natural gradient.
problem Training deep neural networks with large datasets and variables.
method Subsampled Gauss-Newton and natural gradient methods with subsampled gradient estimates.
result Methods converge to a stationary point and are efficient to implement.
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…
Improved training of large-scale neural networks with reduced variance noise.
problem Training large-scale neural networks with high variance noise.
method Stochastic variance reduced Nesterov's Accelerated Quasi-Newton method (SVR-NAQ).
result Improved performance compared to conventional methods on benchmark problems.
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.
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…
This paper improves NAQ method for faster convergence on Tensorflow.
problem Non-convex optimization problems.
method Modified Nesterov's Accelerated Quasi-Newton (NAQ) method on Tensorflow.
result mNAQ converges better and faster than first and second order optimizers.
A new optimizer combines Newton and ADMM for faster classification.
problem Slower convergence of first-order methods in distributed learning.
method Integrates GPU-accelerated Newton solver with ADMM for multiclass classification.
result Significantly reduces the time to solution and generalization error.
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.
This paper proves subsampled Newton methods work for high-dimensional data.
problem The high cost of forming Hessian matrices in Newton methods for high-dimensional data.
method Subsampled Newton methods approximate Hessians using subsampling techniques, requiring only d m e f f γ d^γ_{
m eff} d m e f f γ samples. result Only d m e f f γ d^γ_{
m eff} d m e f f γ samples are needed, where d m e f f γ d^γ_{
m eff} d m e f f γ is much smaller than d d d for high-dimensional data.