Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms

• URL: http://arxiv.org/abs/2401.10923v2
• Date: Thu, 4 Jul 2024 09:40:14 GMT
• Title: Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms
• Authors: Antoine Godichon-Baggioni, Wei Lu, Bruno Portier,
• Abstract summary: This paper addresses second-order optimization for estimating the minimizer of a convex function written as an expectation. A direct recursive estimation technique for the inverse Hessian matrix using a Robbins-Monro procedure is introduced. Above all, it allows to develop universal Newton methods and investigate the efficiency of the proposed approach.
• Score: 4.389938747401259
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper addresses second-order stochastic optimization for estimating the minimizer of a convex function written as an expectation. A direct recursive estimation technique for the inverse Hessian matrix using a Robbins-Monro procedure is introduced. This approach enables to drastically reduces computational complexity. Above all, it allows to develop universal stochastic Newton methods and investigate the asymptotic efficiency of the proposed approach. This work so expands the application scope of secondorder algorithms in stochastic optimization.

Related papers

• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• A Full Adagrad algorithm with O(Nd) operations [4.389938747401259]
  The study offers efficient and practical algorithms for large-scale applications. This innovative strategy significantly reduces the complexity and resource demands typically associated with full-matrix methods.
  arXiv  Detail & Related papers  (2024-05-03T08:02:08Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  Trust-region (TR) and adaptive regularization using cubics have proven to have some very appealing theoretical properties. We show that TR and ARC methods can simultaneously provide inexact computations of the Hessian, gradient, and function values.
  arXiv  Detail & Related papers  (2023-10-18T10:29:58Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Stochastic Mirror Descent for Large-Scale Sparse Recovery [13.500750042707407]
  We discuss an application of quadratic Approximation to statistical estimation of high-dimensional sparse parameters. We show that the proposed algorithm attains the optimal convergence of the estimation error under weak assumptions on the regressor distribution.
  arXiv  Detail & Related papers  (2022-10-23T23:23:23Z)
• Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation [11.345796608258434]
  We provide performance guarantees for a variant of simulation-based policy iteration for controlling Markov decision processes. We analyze two algorithms; the first algorithm involves a least squares approach where a new set of weights associated with feature vectors is obtained via at least squares at each iteration. The second algorithm involves a two-time-scale approximation algorithm taking several steps of gradient descent towards the least squares solution.
  arXiv  Detail & Related papers  (2022-10-13T20:16:19Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  We study optimization of areas under precision-recall curves (AUPRC), which is widely used for imbalanced tasks. We develop novel momentum methods with a better iteration of $O (1/epsilon4)$ for finding an $epsilon$stationary solution. We also design a novel family of adaptive methods with the same complexity of $O (1/epsilon4)$, which enjoy faster convergence in practice.
  arXiv  Detail & Related papers  (2021-07-02T16:21:52Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  We present a computable approximation type algorithm, namely the linearized proximal convex method of multipliers. Some preliminary numerical results demonstrate the performance of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-06-22T07:24:17Z)
• Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box Optimization Framework [100.36569795440889]
  This work is on the iteration of zero-th-order (ZO) optimization which does not require first-order information. We show that with a graceful design in coordinate importance sampling, the proposed ZO optimization method is efficient both in terms of complexity as well as as function query cost.
  arXiv  Detail & Related papers  (2020-12-21T17:29:58Z)
• Riemannian stochastic recursive momentum method for non-convex optimization [36.79189106909088]
  We propose atildeOepsilon$-approximate gradient evaluations evaluation method for $mathcalO gradient evaluations with one iteration. Proposed experiment demonstrate the superiority of the algorithm.
  arXiv  Detail & Related papers  (2020-08-11T07:05:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.