In this work, we develop first-order (Hessian-free) and zeroth-order (derivative-free) implementations of the Cubically Regularized Newton Method for solving general non-convex optimization problems. For that, we employ finite difference approximations of the derivatives. We use a special adaptive search procedure in our algorithms, which simultaneously fits both the regularization constant and the parameters of the finite difference approximations. It makes our schemes free from the need to know the actual Lipschitz constants. Additionally, we equip our algorithms with the lazy Hessian update that reuses a previously computed Hessian approximation matrix for several iterations. Specifically, we prove the global complexity bound of <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2842_Article_IEq1.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="90" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}( n^{1/2} \epsilon ^{-3/2})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>1</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> function and gradient evaluations for our new Hessian-free method, and a bound of <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2842_Article_IEq2.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="90" /> </InlineMediaObject> <EquationSource Format="TEX">$\mathcal {O}( n^{3/2} \epsilon ^{-3/2} )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mrow> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <msup> <mi>ϵ</mi> <mrow> <mo>-</mo> <mn>3</mn> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> function evaluations for the derivative-free method, where n is the dimension of the problem and <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2842_Article_IEq3.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> is the desired accuracy for the gradient norm. These complexity bounds significantly improve the previously known ones in terms of the joint dependence on n and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10915_2025_2842_Article_IEq4.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation>, for the first-order and zeroth-order non-convex optimization.

First and Zeroth-Order Implementations of the Regularized Newton Method with Lazy Approximated Hessians

期刊论文
出版模式：

开放获取
发表日期：

2025年3月12日

查看全文

Nikita Doikov,
Geovani Nunes Grapiglia

摘要

In this work, we develop first-order (Hessian-free) and zeroth-order (derivative-free) implementations of the Cubically Regularized Newton Method for solving general non-convex optimization problems. For that, we employ finite difference approximations of the derivatives. We use a special adaptive search procedure in our algorithms, which simultaneously fits both the regularization constant and the parameters of the finite difference approximations. It makes our schemes free from the need to know the actual Lipschitz constants. Additionally, we equip our algorithms with the lazy Hessian update that reuses a previously computed Hessian approximation matrix for several iterations. Specifically, we prove the global complexity bound of $\mathcal {O}( n^{1/2} \epsilon ^{-3/2})$ $O (n^{1 / 2} ϵ^{- 3 / 2})$ function and gradient evaluations for our new Hessian-free method, and a bound of $\mathcal {O}( n^{3/2} \epsilon ^{-3/2} )$ $O (n^{3 / 2} ϵ^{- 3 / 2})$ function evaluations for the derivative-free method, where n is the dimension of the problem and $\epsilon $ $ϵ$ is the desired accuracy for the gradient norm. These complexity bounds significantly improve the previously known ones in terms of the joint dependence on n and $\epsilon $ $ϵ$ , for the first-order and zeroth-order non-convex optimization.