CS Paper Radar

Optimization over covariance matrices with a parameterized metric

Yibang Li, Bamdev Mishra, Pratik Jawanpuria, Cyrus Mostajeran

cs.LG math.OC ·submitted 2026-09-15 12:22 UTC · v1
theory

Abstract

The choice of Riemannian metric can strongly influence the convergence of gradient-based optimization over covariance matrices. Euclidean, Bures-Wasserstein and affine-invariant metrics are common choices, but their relative effectiveness depends on the objective. We introduce a two-parameter family defined by $X^{p}LX^{q}+X^{q}LX^{p}=U$, solved for $L$ at each tangent vector $U$, that contains all three as exact members, at $(0,0)$, $(1,0)$ and $(1,1)$, and extends past them. We treat the choice of member as a particular way of preconditioning for a given problem. To this end, we analyze the conditioning of the Riemannian Hessian at the solution. We show that it obeys a lower bound that depends on $(p,q)$ only through the exponent $r=p+q$. When the Euclidean Hessian is a pure power that mixes no eigendirections, the member $p=q=r/2$ attains that bound, and a closed-form criterion identifies the other members that do. We discuss ways to tune $r$ for a given problem. Experiments on real covariance data confirm the predicted conditioning and the benefit of tuning $r$. A task covariance example shows a further gain from tuning the shape.

Closest papers

Nearest neighbours by meaning across the whole index.

Riemannian ascent--descent for nonconvex nonconcave minimax landscapes: convergence to basin saddle points and applications to distributionally robust optimization

cs.LG math.OCstat.ML ·2026-09-12 ·Rishabh Dixit, Pranav Upadrashta, Alex Cloninger
hot direction similarity 0.59
Abstract

We study a class of distributionally robust optimization (DRO) problems for the statistical risk problem, formulated as minimax problems over the product of a Euclidean space and a Riemannian manifold. Because the resulting minimax landscape is nonconvex nonconcave in general, no globally convergent first order method is known to be available. We instead introduce the notion of a \emph{basin saddle point}, a Nash equilibrium defined locally on the Cartesian product of a $δ$ basin around a connected component of the local minima critical set and a geodesic ball on the measure manifold. We develop an abstract convergence framework for a Riemannian gradient ascent multistep descent iteration to a basin saddle point under a local Łojasiewicz type growth condition, with exponent $β\in (1,2]$, in the $δ$ basin around connected components of the local minima critical sets. Under Lipschitz regularity of critical sets we establish linear convergence for $β= 2$ and polynomial convergence for $β\in (1,2)$ to a basin saddle point, with explicit dependence on the sectional curvature of the manifold. We then instantiate this framework for the statistical risk DRO problem over Gaussian measures, where the ambiguity set is naturally modeled as the product of Euclidean space and the Bures Wasserstein manifold of covariance matrices, which we relax to a penalized DRO formulation. We derive nonasymptotic Hessian estimates for the resulting Lagrangian, establish existence and local uniqueness of its maximizer, and prove that an alternating Riemannian gradient scheme converges to a basin saddle point of the penalized DRO problem, recovering the linear and polynomial rates of the abstract theory with all constants explicit in terms of data dimension, loss moments, and the reference covariance.

0.42

Curvature-Independent Regret Bounds for Distributed Online Optimization on Hadamard Manifolds

cs.LG math.OCstat.ML ·2026-09-12 ·Zhanyuan Cai, Emre Sahinoglu, Shahin Shahrampour
theoryhot direction similarity 0.59
Abstract · 6 pages, 2 figures

This work addresses decentralized online Riemannian optimization on Hadamard manifolds. Prior work under geodesic convexity (g-convexity) may require curvature information in the optimization analysis, typically through a finite lower bound on the sectional curvature. Curvature may also enter the step size or contraction factor of tangent-space Riemannian consensus schemes. In this work, we relax the curvature dependence for a narrower class of horospherical convex (h-convex) functions. We study Distributed Riemannian Online Gradient Descent (D-ROGD), which combines local Riemannian h-subgradient updates with an implicit Fréchet-mean consensus. For h-convex and strongly h-convex local objectives, we establish $O(\sqrt{T})$ and $O(\log T)$ static regret, respectively, matching the corresponding Euclidean rates with respect to $T$, with network dependence governed solely by the spectral gap. To our knowledge, these are the first curvature-independent regret guarantees for decentralized online optimization on Hadamard manifolds. Experiments on hyperbolic embeddings corroborate the predicted rates, with no observable degradation due to curvature.

0.35

Projected Riemannian Gradient Descent for the Bures-Wasserstein Barycenter: Dimension-Independent Linear Convergence at Unit Step Size

cs.LG math.OCquant-ph ·2026-09-03 ·A. Afham
similarity 0.58
Abstract · 33 Pages, 3 figures. Comments welcome!

The computation of the Bures-Wasserstein (BW) barycenter of an ensemble of positive definite matrices arises throughout machine learning, optimal transport, and quantum information. Riemannian gradient descent (RGD) at unit step size -- the fixed-point iteration used in practice -- converges rapidly, yet existing analyses present a dichotomy: unit-step guarantees carry worst-case exponential dependence on the dimension, while dimension-independent guarantees require small step sizes that forfeit the empirical speed. We resolve this dichotomy, not by improving the guarantees for unit-step RGD, but by proposing a Projected RGD algorithm that achieves dimension-independent linear convergence at unit step size. The achieved rate, $(1 - κ^{-3/2})$, where $κ$ is the condition number of the ensemble, also polynomially improves on the best small-step guarantee ($κ^{3/2}$ versus $κ^{5/2}$ iteration complexity). The crux is a novel Projection Lemma: clipping the eigenvalues of a positive matrix to an interval $[α, β]$ is the closed-form, non-expansive (1-Lipschitz) BW-metric projection onto the set $\{S : αI \leq S \leq βI\}$ -- a statement which, unlike its known one-sided counterpart, does not follow from convexity. The projection is moreover free: it reuses an eigendecomposition the next iteration must perform in any case, so the projected and unprojected iterations cost the same per step. The same analysis covers the invariant matrix projection problem of Brahmachari et al. (2025), whose fixed-point algorithm we identify as unit-step RGD on a totally geodesic submanifold, thereby extending the dimension-independent guarantee to that setting verbatim.

0.20

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.57
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

A Lifted Hessian-Riemannian Gradient Flow for LQR Synthesis under Passivity Constraints

eess.SY math.OC ·2026-11-16 ·Armin Gießler, Sören Hohmann
theory similarity 0.57
Abstract

The static state-feedback gain that renders a linear system passive at an external port and minimizes a linear quadratic regulator (LQR) cost cannot be computed by convex optimization, since the passivity certificate and the LQR cost are coupled bilinearly through the common gain. A previous indirect approach restricts the gain to a convex inner approximation of the passivity region, which is conservative and whose construction scales exponentially with the number of gain entries. This paper proposes a direct approach. The set of strictly passivating gains is the image of a convex lifted set of inverse storage matrices and transformed gains. We describe this set by a strict linear matrix inequality and an affine equality for every feedthrough matrix with positive semidefinite symmetric part, including feedthrough matrices with a singular symmetric part, and minimize the LQR cost over it by a gradient flow whose metric is the Hessian of a logarithmic barrier. For multi-input systems, this Hessian is singular along gain changes that preserve the storage function, and we complete the metric along these directions by the metric of the gain space. We prove that the flow exists for all times, that every gain along the flow is strictly passivating with an explicit storage function, and that the cost decreases monotonically while the gains remain in a compact set of stabilizing gains. Numerical examples show that the flow attains a lower cost than the indirect approach, that the completion is required for multi-input systems, and that the flow can converge to a local minimizer on nonconvex passivity regions.

0.28

On the Geometry of Radar Waveform Design with Constraints

eess.SP ·2026-10-12 ·Hazel Brenner, Katelyn Hampel, Matthew Pollard
published similarity 0.57
Abstract · 8 Pages, 10 figures; To be published in IEEE Transactions on Radar Systems

Many optimization problems that arise in signal processing applications are based around optimizing vectors/matrices of numeric sequences. These problems are often inherently non-convex due to non-linear constraints. Such problems are frequently solved through convex relaxations of the original problem to allow for computationally simple algorithms to be leveraged, albeit with the potential for appreciable performance costs in the solution space. When the constraints of a problem can be implicitly satisfied through the structure of a Riemannian manifold, optimizing directly on said manifold affords the opportunity to solve the problem in an unconstrained fashion. Therefore, when feasible, recasting the constrained optimization problem in Euclidean space as an unconstrained optimization over a Riemannian manifold offers greater flexibility and improved efficiency over convex relaxation based approaches. This paper introduces the minimal smooth optimization theory required and adapts the notation to a radar signal design context. In addition, we apply our approach to two different problems in direct parallel to contemporary convex relaxation-based signal design literature.

0.37

Non-Euclidean Gradient Descent Has Many Edges of Stability

cs.LG math.OC ·2026-10-10 ·Peter Zaika, Zakhar Shumaylov
theory similarity 0.56
Abstract

Recent observations that deep learning models train at the edge of stability have renewed interest in understanding stability properties of classical optimization algorithms. For quadratic objectives, standard gradient descent has a sharp stability threshold: it converges from every initialization when $η<2/L$, diverges from almost every initialization when $η>2/L$, and diverges from every nonzero initialization when $η>2/μ$. For non-Euclidean gradient descent, the corresponding known guarantees are weaker: convergence holds for every initialization when $η<2/S$, where $S$ is the generalized sharpness, while every nonzero initialization diverges when $η>2/μ$. The behavior in the intermediate regime $2/S<η<2/μ$ is not fully characterized. We show that Hilbertian norms are the only ones for which $2/S$ is an almost-everywhere sharp threshold for every positive-definite quadratic objective. Using linear conjugacy between non-Euclidean and Euclidean gradient descent, we show that for general norms the intermediate regime can contain arbitrarily many edges of stability associated with distinct attracting directions. We identify a forward-invariant region of exponentially divergent directions beyond the generalized stability threshold. When the directions of minimum curvature are finite and nondegenerate, we prove that, sufficiently close to $2/μ$ from below, only their invariant directions remain convergent. We give smooth two-dimensional constructions with arbitrarily many distinct thresholds, arbitrarily large relative threshold separation and show these properties to be stable.

0.12

A Riemannian Geometry for Low-rank Adaptation

cs.LG ·2026-10-06 ·Shoichiro Takeda, Shin'ya Yamaguchi, Satoshi Suzuki, Yasunori Akagi
similarity 0.56
Abstract

Low-rank adaptation (LoRA) is widely used as a parameter-efficient fine-tuning technique for pre-trained deep neural networks, which approximates the weight update via full fine-tuning by a low-rank matrix $BA^\top$. This parameterization leads to the equivalence relation $(B, A) \sim (BG^{-1}, AG^\top)$ for any invertible matrix $G$ because $BA^\top = BG^{-1}(AG^\top)^\top$ and thus both pairs yield the same loss value. This relation induces a quotient manifold where matrices $(BG^{-1}, AG^\top)$ for all $G$ are identified, eliminating redundant directions along which the loss value remains unchanged. To respect the geometry of this manifold, the original search space is endowed with a Riemannian metric that is invariant under the equivalence relation. Such a metric induces preconditioning at each gradient step and ensures that each weight update via LoRA changes the loss value, leading to efficient optimization. In this paper, we propose a new Riemannian metric that is specifically tailored to LoRA to close the gap to full fine-tuning at the weight level. We theoretically show that LoRA with our preconditioning induced by this metric satisfies the following two properties at each iteration: (i) The weight update follows the direction closest to the gradient of full fine-tuning within the subspace of first-order weight changes allowed by the LoRA parameterization. (ii) The updated weight matrix is closer in Frobenius norm to that of full fine-tuning than the updated weight matrices of LoRA with conventional preconditioning and without preconditioning. These theoretical insights suggest that our preconditioning makes LoRA better approximate full fine-tuning, thereby leading to more efficient optimization. Experiments show the effectiveness and efficiency of our preconditioning for LoRA on fine-tuning tasks with language and vision domains.

0.07