cs.LGFeb 23, 2026

Generalized Random Direction Newton Algorithms for Stochastic Optimization

Authors: Soumen Pachal, Prashanth L. A., Shalabh Bhatnagar, Avinash Achar

Organizations: Indian Institute of Technology Madras · Indian Institute of Science, Bangalore · TCS Research, Chennai, India

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

We present a family of generalized Hessian estimators of the objective using random direction stochastic approximation (RDSA) by utilizing only noisy function measurements. The form of each estimator and the order of the bias depend on the number of function measurements. In particular, we demonstrate that estimators with more function measurements exhibit lower-order estimation bias. We show the asymptotic unbiasedness of the estimators. We also perform asymptotic and non-asymptotic convergence analyses for stochastic Newton methods that incorporate our generalized Hessian estimators. Finally, we perform numerical experiments to validate our theoretical findings.

Figures & tables

 θn=arg min⁡θ∈Rd{ρ~h(θ,θn−1,Gˉk,Hkˉ,αn)},\displaystyle\theta_{n}=\argmin_{\theta\in\mathbb{R}^{d}}\left\{\tilde{\rho}_{h}(\theta,\theta_{n-1},\bar{G}^{k},\bar{\mathcal{H}^{k}},\alpha_{n})\right\}, 
Algorithm 1 Cubic-regularized zeroth-order stochastic Newton algorithm (CRZON)
Table 1: Parameter error ( ±\pm standard deviation) for GSF and G2SF algorithms under the Rastrigin objective defined in ( 52 ) with budget 5,0005,000 and 10,00010,000 . GSF-5 corresponds to the five measurements GSF proposed in Pachal et al. (2025) , and G2SF-9 represents our nine measurements Hessian estimator.
Table 2: Parameter error ( ±\pm standard deviation) for our algorithm under the Rastrigin objective defined in ( 52 ) with three and nine measurement Hessian estimators G2SF-3 and G2SF-9, respectively, and with budget of 2,000 and 30,000.
Table 3: Parameter error ( ±\pm standard deviation) under the Rastrigin objective defined in ( 52 ) with three measurement G2RDSA (G2R-3) and nine measurement G2RDSA(G2R-9) Hessian estimators, with budget of 5,000 and 10,000.
Comparison with existing methods
Budget2SPSA Spall (2000)2RDSA Prashanth et al. (2016)G2R-9G2SF-9
5×1035\times 10^{3}0.58±0.150.58\pm 0.150.44±0.140.44\pm 0.140.29±0.11\bf{0.29\pm 0.11}0.22±0.06\bf{0.22\pm 0.06}
1×1041\times 10^{4}0.55±0.180.55\pm 0.180.45±0.140.45\pm 0.140.26±0.06\bf{0.26\pm 0.06}0.15±0.05\bf{0.15\pm 0.05}
Table 4: Parameter error ( ±\pm standard deviation) comparison with existing approaches for the Rastrigin objective defined in ( 52 ) for d=10d=10 and budget of 5,000 and 10,000.
More in this topic

Stochastic Optimization

Stochastic optimization studies how to find good decisions or model parameters when objectives, data, or feedback are random or noisy.

See all 209 papers

Explore similar work

CardsList

  1. Finite-time analysis of Multi-timescale Stochastic Optimization Algorithms

    Mar 31, 2026Kaustubh Kartikey, Shalabh BhatnagarStochastic OptimizationStochastic Optimization Convergence

  2. Refining Covariance Matrix Estimation in Stochastic Gradient Descent Through Bias Reduction

    Apr 23, 2026Ziyang Wei, Wanrong Zhu, Jingyang Lyu +1Covariance EstimationStochastic Gradient Descent

    Department of Statistics University of Chicago Chicago, IL 60637, USA · Department of Statistics University of California, Irvine Irvine, CA 92617, USA · Department of Statistics University of Wisconsin–Madison Madison, WI 53706, USA

  3. Revisiting Zeroth-Order Hessian Approximation: A Single-Step Policy Optimization Lens

    May 29, 2026Junbin Qiu, Zhaowei Hong, Renzhe Xu +1Zeroth-Order OptimizationSecond-Order Optimization

    Hong Kong University of Science and Technology (Guangzhou) · Shanghai University of Finance and Economics