Stochastic Diagonal Estimation Based on Matrix Quadratic Form Oracles

Haishan Ye, Xiangyu Chang · 2025

Read Stochastic Diagonal Estimation Based on Matrix Quadratic Form Oracles by Haishan Ye, Xiangyu Chang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15360.txt.

Introduction

Haishan Ye and Xiangyu Chang estimate the diagonal of a hidden matrix in a paper from two thousand twenty-five. Some matrices can only be probed through quadratic forms: feed in a vector, get one number back. Recovering every diagonal entry from such probes is the task.

Their method draws random Gaussian probe vectors and averages the oracle's answers in a clever way. They bound how many probes each entry, and the whole diagonal, needs for a set accuracy. Experiments on matrices of varied type and size confirm the method works and that the bounds are tight. The result gives a simple, provable tool for a job that arises in optimization and uncertainty studies.

Catalog record

CREATORHaishan Ye, Xiangyu Chang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE70 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-15360

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Stochastic Diagonal Estimation Based on Matrix Quadratic Form Oracles Haishan Ye, Xiangyu Chang Abstract We study the problem of estimating the diagonal of an implicitly given matrix 𝑨 \bm{A} . For such a matrix we have access to an oracle that allows us to evaluate the matrix quadratic form 𝒖 ⊤ ​ 𝑨 ​ 𝒖 \bm{u}^{\top}\bm{A}\bm{u} . Based on this query oracle, we propose a stochastic diagonal estimation method with random variable 𝒖 \bm{u} drawn from the standard Gaussian distribution. We provide the element-wise and norm-wise sample complexities of the proposed method. Our numerical experiments on different types and dimensions matrices demonstrate the effectiveness of our method and validate the tightness of theoretical results. 1 Introduction Estimating the diagonal entries of a matrix is important in many areas of science and engineering. Originally, the diagonal estimation is used in electronic structure calculations ( Bekas et al., 2007 ; Goedecker & Teter, 1995 ; Goedecker, 1999 ) . Because the diagonal preconditioners can accelerate the convergence of iterative optimization algorithms ( Wathen, 2015 ) , the diagonal estimator is applied in accelerating training machine learning models ( Yao et al., 2021 ; Liu et al., 2023 ) . The diagonal estimation is also used in network science ( Constantine & Diaz, 2017 ; Kucherenko & Iooss, 2015 ) . Because of its importance, the diagonal estimation has attracted much research attention in the past years ( Hallman et al., 2023 ; Baston & Nakatsukasa, 2022 ; Bekas et al., 2007 ; Epperly et al., 2024 ) . These diagonal estimation algorithms construct the following matrix \widehat{\bm{A}}=\frac{1}{N}\sum_{i=1}^{N}\bm{A}\bm{w}_{i}\bm{w}_{i}^{\top}, (1.1) where \bm{A}\in\mathbb{R}^{d\times d} and \bm{w}_{i}\in\mathbb{R}^{d} are independent random vectors, and use the diagonal entries of \widehat{\bm{A}} as the diagonal estimation of \bm{A} . Thus, this kind of diagonal estimation is mainly based on the matrix-vector product. In this paper, we will study stochastic diagonal estimation by only accessing the quadratic form of a matrix \bm{u}^{\top}\bm{A}\bm{u} and we will construct the following estimation: \bm{g}=\frac{1}{2N}\sum_{j=1}^{N}\left[\bm{u}^{(j)}\right]^{\top}\bm{A}\bm{u}^{(j)}\cdot\Big([\bm{u}^{(j)}]^{2}-\bm{1}_{d}\Big), (1.2) where \bm{u}^{(j)} ’s are independent standard Gaussian vectors, \mathbf{1}_{d} is a d dimensional all one vector, and [\bm{u}]^{2} denotes the element-wise square. Compared with the diagonal estimation based on Eq. ( 1.1 ) which needs the matrix-vector product, Eq. ( 1.2 ) can only access the quadratic form of a matrix \bm{u}^{\top}\bm{A}\bm{u} . Our study is motivated by the zeroth-order optimization for high-dimensional problems. Recently, post-training large language models with first-order algorithms suffers from the giant memory costs. Thus the memory-efficient zeroth-order algorithms attract much research attention because they only need forward passes and achieve the memory efficiency ( Malladi et al., 2023 ; Zhao et al., 2025 ; Zhang et al., 2024 ; Dery et al., 2024 ; Chen et al., 2025 ) . Similar to the first-order algorithms, one can also use the Hessian diagonal as the preconditioner to accelerate the convergence of zeroth-order algorithms ( Zhao et al., 2025 ) . Because zeroth-order algorithms can only access function values, the diagonal estimation in Eq. ( 1.1 ) which requires Hessian-vector product can not be used to estimate the Hessian diagonals. Instead, our estimation in Eq. ( 1.2 ) only needs the quadratic form \bm{u}^{\top}\bm{A}\bm{u} with \bm{A} being the Hessian \nabla^{2}f(\bm{x}) which can be approximately computed by three function value queries as follows: \bm{u}^{\top}\bm{A}\bm{u}\approx\frac{f(\bm{x}+\alpha\bm{u})+f(\bm{x}-\alpha\bm{u})-2f(\bm{x})}{\alpha^{2}}, (1.3) where 0<\alpha is a constant of a small value. Please refer to Proposition 1 to get a detailed description. 1.1 Literature Review To our knowledge, Monte Carlo diagonal estimators based on matrix-vector product were first studied by Bekas et al., 2007 . This kind of diagonal estimation is further explored in ( Hallman et al., 2023 ; Baston & Nakatsukasa, 2022 ; Epperly et al., 2024 ) . In contrast, our work studies the diagonal estimation which only accesses the quadratic form of a matrix instead of accessing the matrix-vector product. Another important research topic closely related to our study is the Hessian approximation by zeroth-order oracles and several works have been proposed ( Ye, 2023 ; Lyu & Tsang, 2021 ; Lattimore & György, 2023 ) . More Hessian matrix estimation methods by function values can be found in Chapter 6 of Prashanth et al., 2025 . Our diagonal estimation is a special case of the Hessian approximation when matrix \bm{A} is the Hessian. However, the sample complexities of Hessian approximation are rarely analyzed ( Lyu & Tsang, 2021 ; Lattimore & György, 2023 ; Prashanth et al., 2025 ) . Though Ye, 2023 provides a sample complexity of Hessian approximation, the result of Ye, 2023 can not derive the sample complexities in this work and our work achieves much tighter sample complexities. 1.2 Contributions The novel features of our contributions are the following: 1. We propose a stochastic diagonal estimation method that only queries matrix quadratic form oracles. Our method does not require the matrix to be symmetric nor positive (semi)-definite. 2. We provide the sample complexity analysis of our method to achieve the target precision. Our element-wise bound (Theorem 1 ) shows that the sample complexity mainly depends on the square of the trace and the square of the “Frobenius” norm of \bm{A}+\bm{A}^{\top} . Thus, to achieve the same relative error, diagonal entries with small absolute values require large sample sizes. Our numerical experiments (Section 4 ) confirms this in different types and different dimension matrices. 3. We provide the sample complexity of norm-wise bound (Theorem 2 ) and show that it linearly depends the dimension d . The trace of the matrix and off-diagonal entries of \bm{A}+\bm{A}^{\top} mainly determine the sample complexity. 4. Our numerical studies show the effectiveness of our algorithm and validate the tightness of our theoretical result about the sample complexities. 1.3 Notation and Preliminaries Notation In this paper, given a d\times d matrix \bm{A} , we use \bm{A}_{i,j} with integers 1\leq i,j\leq d to denote the entry of \bm{A} in the i -th row and j -th column. Furthermore, we will follow the Matlab convention and we define \mathrm{diag}(\bm{A})=[\bm{A}_{1,1},\dots,\bm{A}_{d,d}]^{\top} . We use \bm{A}_{i,:} and \bm{A}_{:,j} to denote the i -th row and j -th column of \bm{A} . We also define the trace of matrix \mathrm{tr}(\bm{A})=\sum_{i=1}^{d}\bm{A}_{i,i} and the “Frobenius” norm \left\|\bm{A}\right\|=\sqrt{\mathrm{tr}(\bm{A}^{\top}\bm{A})} . We denote by \mathbb{P}\{E\} the probability of an event E and by \mathbb{E}[Z] the expectation of a random variable Z , which can be a scalar-, vector-, or matrix-valued. Zeroth-order Optimization In the zeroth-order optimization, one can only access the function value f(\bm{x}) instead of the gradient \nabla f(\bm{x}) . Next, we will give a proposition that describes the relation between zeroth-order optimization and matrix quadratic form. Proposition 1 . Let function f(\bm{x}) be of twice continuous with \bm{x}\in\mathbb{R}^{d} and its Hessian be \gamma -Lipschitz continuous. Given a random Gaussian vector \bm{u}\in\mathbb{R}^{d} , then it holds that \bm{u}^{\top}\nabla^{2}f(\bm{x})\bm{u}=\frac{f(\bm{x}+\alpha\bm{u})+f(\bm{x}-\alpha\bm{u})-2f(\bm{x})}{\alpha^{2}}-\frac{\Delta(\bm{x},\alpha\bm{u})+\Delta(\bm{x},-\alpha\bm{u})}{\alpha^{2}}, where 0<\alpha is a constant of a small value and \Delta(\bm{x},\alpha\bm{u}) is defined as \displaystyle\Delta(\bm{x},\alpha\bm{u})=f(\bm{x}+\alpha\bm{u})-\Big(f(\bm{x})+\alpha\nabla^{\top}f(\bm{x})\bm{u}+\frac{\alpha^{2}}{2}\bm{u}^{\top}\nabla^{2}f(\bm{x})\bm{u}\Big). Furthermore, with a probability 1-\delta with 0<\delta<1 , it holds that \displaystyle\left|\frac{\Delta(\bm{x},\alpha\bm{u})+\Delta(\bm{x},-\alpha\bm{u})}{\alpha^{2}}\right|\leq\frac{\alpha\left(2d+3\log\frac{1}{\delta}\right)^{3}}{3}. Proposition 1 shows that given a function f(\bm{x}) , one can obtain the quadratic form of the Hessian by three function values but with some small perturbation. 2 Stochastic Diagonal Estimation Based on Quadratic Form Oracles 2.1 Algorithm Description Our stochastic diagonal estimation method lies on the following

Read the complete text