Stochastic Optimization for Nonconvex Problem With Inexact Hessian Matrix, Gradient, and Function.

Area of Science:

• Optimization Theory
• Numerical Analysis
• Computational Mathematics

Background:

• Trust Region (TR) and Adaptive Regularization using Cubics (ARC) methods are effective for nonconvex optimization, utilizing function value, gradient, and Hessian.
• Stochastic approximations reduce computational cost but pose challenges for theoretical convergence rate guarantees.

Purpose of the Study:

• To explore a family of stochastic TR (STR) and stochastic ARC (SARC) methods.
• To enable inexact computations of Hessian matrix, gradient, and function values simultaneously.
• To reduce propagation overhead per iteration compared to traditional TR and ARC methods.

Main Methods:

• Development of stochastic Trust Region (STR) and stochastic Adaptive Regularization using Cubics (SARC) algorithms.
• Theoretical analysis of iteration complexity for achieving -approximate second-order optimality.
• Application of random sampling technology for finite-sum minimization problems to meet inexactness conditions.

Main Results:

• STR and SARC algorithms require significantly less propagation overhead per iteration.
• The iteration complexity for achieving -approximate second-order optimality is proven to be of the same order as exact computation methods.
• Numerical experiments confirm that these algorithms achieve similar or better results with reduced computational overhead.

Conclusions:

• Stochastic TR and SARC methods provide an efficient approach to nonconvex optimization with reduced computational cost.
• These methods maintain theoretical convergence rates for second-order optimality under mild inexactness conditions.
• The findings are supported by numerical experiments on nonconvex problems, demonstrating practical advantages over existing second-order methods.