Generalization of Zeroth-Order Method for Quotients of Quadratic Functions
Jonas Bresch [email protected] · 2026
Read Generalization of Zeroth-Order Method for Quotients of Quadratic Functions by Jonas Bresch [email protected] (2026) 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-2604-26913.txt.
Introduction
Bresch studies computation of the generalized operator norm and maximizing a Rayleigh quotient, using only forward runs of two linear operators. His method samples search directions evenly from the unit sphere, avoiding tangent-space sampling and access to the metric matrix. Each line search reduces to a 2 by 2 eigenvalue problem on Gram matrices, whose maximizing step has a closed form usually. He proves objective values converge almost surely to the largest eigenvalue, with iterates closing on the leading eigenspace. Tests on Gaussian operators show good convergence barely tied to size.
Catalog record
| CREATOR | Jonas Bresch [email protected] |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83934 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26913
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalization of Zeroth-Order Method for Quotients of Quadratic Functions Jonas Bresch [email protected] Abstract Optimization of quadratic functions and the quotient of those are relevant in subspace and iterative optimization methods. In this paper, the calculation of the generalized operator norm and extremal generalized Rayleigh quotient is considered. In contrast to recent works an unconstrained sampling approach on the entire sphere for the random search direction in each iteration is proposed. Furthermore, the link to zeroth-order methods for Riemannian first- and second-order optimization methods is provided in the sense that the Riemannian gradient and Hessian are estimated by the specific surrogates. Even though the tangent space is not used in this construction the optimal step size problem can be computed in a closed form. The subproblems of this and recent works are illuminated in the context of sub-generalized Rayleigh quotient problems on specific Gram matrices. Together the achieved theory allows to construct an accelerated algorithm which shows state-of-the-art behavior and outperforms recent works. Keywords. operator norm \cdot Rayleigh quotient \cdot Riemannian optimization \cdot zeroth-order \cdot first-order \cdot second-order \cdot unbiased estimator \cdot Riemannian manifold \cdot generalized sphere MSC. 65F35 \cdot 15A60 \cdot 68W20 1 Introduction The computation of extremal spectral quantities of linear operators under restricted access models remains a fundamental challenge in applied mathematics, scientific computing, and data analysis. Quantities such as the operator norm, generalized Rayleigh quotients, numerical radius, and pseudospectral measures govern stability, transient amplification, and admissible step sizes in optimization and inverse problems [ 45 , 44 , 46 , 42 , 11 , 6 ] . In particular, for non-normal operators, eigenvalues alone fail to capture transient growth phenomena, making Rayleigh-type extremal formulations and pseudospectral diagnostics indispensable [ 47 , 14 ] . A central object in this context is the generalized Rayleigh quotient, which generalizes the operator norm and appears in a variety of applications. In statistics and machine learning, it underlies linear discriminant analysis (LDA) and signal-to-noise ratio (SNR) optimization, where between-class and within-class covariance matrices define operators A and B [ 16 , 39 ] . In signal processing, related formulations arise in beamforming and detection theory [ 48 ] . In inverse problems and PDE-constrained optimization, generalized Rayleigh quotients govern stability constants and convergence rates when weighted norms or preconditioners are involved [ 13 , 32 ] . Despite their importance, computing these quantities becomes highly nontrivial when only black-box access to the operators is available. Adjoint-free and matrix-free constraints. In many modern applications, linear maps A:\mathbb{R}^{d}\to\mathbb{R}^{m} and B:\mathbb{R}^{d}\to\mathbb{R}^{\ell} are accessible only through forward evaluations. This setting arises, for example, in large-scale PDE solvers, time-stepping schemes, tomographic forward models, and legacy simulation codes [ 4 , 43 , 19 , 31 ] . In such scenarios, forming matrices, computing adjoints, or inverting operators is infeasible. Moreover, discretized adjoints may be inconsistent with the forward operator, leading to unreliable results in classical adjoint-based schemes [ 46 , 21 , 15 , 33 , 34 ] . These constraints rule out standard methods such as power-schemes, Lanczos procedures, and Krylov subspace methods, which rely on repeated adjoint applications or dense linear algebra [ 24 , 25 , 36 , 23 ] . Relying on inexact adjoints [ 12 , § 1] for reducing numerical complexity [ 19 , § 2.9] in the computations [ 46 , § 28 & 48, p. 446] introduces the so-called adjoint mismatch as detailedly studied in [ 7 , § 1.1] . This has motivated the development of zeroth-order and derivative-free methods, which use only function evaluations and random perturbations [ 10 , 28 , 3 ] . Recent approaches combine random search, sketching, and consensus-based dynamics to approximate spectral quantities in a matrix-free fashion [ 20 , 41 ] . However, existing methods and novel, substantially improved algorithms [ 7 , 9 , 8 ] for the operator norm, generalized Rayleigh quotient, and the adjoint mismatch, often rely on tangent-space sampling on manifolds, require access to adjoint operators or metric information, or employ heuristic curvature approximations. Unconstrained sampling and zeroth-order quasi-Newton methods. This work introduces a fundamentally different approach based on sampling on the entire unit sphere. Therefore, it can be seen as an unconstrained sampling approach compared to [ 7 , 9 , 8 ] . Instead of drawing search directions from tangent spaces of a Riemannian manifold, we sample directions globally on the unit sphere, which removes the need for conditional sampling or metric-dependent constructions. This seemingly simple modification has significant algorithmic consequences: it decouples the sampling step from the operators, simplifies implementation, and enables unbiased zeroth-order estimators for both gradient and curvature information. Building on this sampling strategy, we develop a zeroth-order optimization framework for generalized Rayleigh quotient maximization that operates entirely with forward evaluations. The first component is a stochastic gradient estimator derived from random directional evaluations. The second and main novelty is a zeroth-order quasi-Newton method in which the curvature model is given by an unbiased estimator of the Riemannian Hessian . This distinguishes the approach from classical quasi-Newton methods, which rely on secant conditions or deterministic approximations [ 18 , 2 ] . Here, curvature information is obtained directly from randomized function evaluations, yielding a principled second-order method in a fully derivative-free setting. Relevance. The improved methods [ 7 , 9 , 8 ] already blend random search [ 28 , 3 ] , sketching [ 30 ] , slicing [ 37 , 38 ] , projection [ 28 , 5 ] , and consensus-style [ 41 ] updates to balance implementability for legacy and black-box codes with provable approximation behavior and empirical robustness in non-normal and ill-conditioned settings. The proposed generalization and extension for zeroth-order and derivative-free, as well as curvature-based methods provide a viable path to reliable operator norms \|A\| , extremal Rayleigh quotient \mathcal{R}(A,B) , where d=m=\ell , and generalized operator norm \|A/B\| diagnostics, and may also contribute to pseudospectral analysis. 2 Preliminaries In this section, we introduce the considered problem of the generalized operator norm, link it to the extremal generalized Rayleigh quotient, and introduce tools for zeroth-, first-, and second-order Riemannian optimization techniques. 2.1 Optimization Problem The optimization problem \|A/B\|\coloneqq\max_{v\in\mathbb{R}^{d}\setminus\{0\}}\;\frac{\|Av\|}{\|Bv\|} (1) for two rectangular matrices A\in\mathbb{R}^{m\times d} and B\in\mathbb{R}^{\ell\times d} , which is considered in this paper, is a generalization of the operator norm \|A\|\coloneqq\|A/I_{d}\|=\max_{v\in\mathbb{R}^{d}\setminus\{0\}}\nicefrac{{\|Av\|}}{{\|v\|}} where B=I_{d} is chosen. Here, we have to guarantee that B^{\tT}B\succ 0 , so that ( 1 ) is well defined. Hence, \ell\geq d is a necessary assumption on the dimension of the space of the domain and range of B . The sufficient condition on B is equivalently given by \det(B^{\tT}B)\neq 0 , \rank(B)=d , or \ker(B)=\{0\} , whenever \ell\geq d . Considering the (generalized) spheres given by \mathbb{S}_{D}^{d-1}\coloneqq\{v\in\mathbb{R}^{d}\mid\|v\|_{D}\coloneqq\sqrt{\left\langle{v},{Dv}\right\rangle}=1\},\quad\text{where}\quad D\succ 0, and we write for the unit sphere, i.e. for D=I_{d} , \mathbb{S}^{d-1}\coloneqq\mathbb{S}_{I_{d}}^{d-1} , yields \|A/B\|^{2}=\max_{v\in\mathbb{R}^{d}\setminus\{0\}}\;\frac{\left\langle{v},{A^{\tT}Av}\right\rangle}{\left\langle{v},{B^{\tT}Bv}\right\rangle}=\max_{v\in\mathbb{S}^{d-1}}\;\frac{\left\langle{v},{A^{\tT}Av}\right\rangle}{\left\langle{v},{B^{\tT}Bv}\right\rangle}=\max_{v\in\mathbb{S}_{B^{\tT}B}^{d-1}}\;\left\langle{v},{A^{\tT}Av}\right\rangle. (2) The latter is due to the scale invariance of the considered (squared) objective f(v)\coloneqq\frac{\left\langle{v},{A^{\tT}Av}\right\rangle}{\left\langle{v},{B^{\tT}Bv}\right\rangle}=\frac{\|Av\|^{2}}{\|Bv\|^{2}} (3) from ( 1 ), respectively ( 2 ). The function in ( 3 ) is also known as the generalized Rayleigh quotient of (A^{\tT}A,B^{\tT}B) . Furthermore, ( 1 ) is a generalization of the extremal generalized Rayleigh quotient computation \mathcal{R}(C,D)\coloneqq\max_{v\in\mathbb{R}^{d}\setminus\{0\}}\frac{\left\langle{v},{Cv}\right\rangle}{\left\langle{v},{Dv}\right\rangle}=\max_{v\in\mathbb{S}_{D}^{d-1}}\left\langle{v},{Cv}\right\rangle , where C\in\mathbb{R}^{d\times d} is an arbitrary, quadratic matrix