2024/05/20 by Emanuel Malvetti, Christian Arenz, Malvetti, Emanuel +5 · 3 citations
Computer Science · Mathematics · #Stochastic Gradient Optimization Techniques #Markov Chains and Monte Carlo Methods #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.2405.12039
We analyze convergence of gradient-descent methods on Riemannian manifolds. In particular, we study randomization of Riemannian gradient algorithms for minimizing smooth cost functions (of Morse-Bott type). We prove that randomized gradient descent methods, where the Riemannian gradient is replaced by a random projection of it, converge to a single local optimum almost surely despite the existence of saddle points. We consider both uniformly distributed and discrete random projections. We also discuss the time required to pass a saddle point. As a major application, we consider ground-state preparation through quantum optimization over the unitary group. In mathematical terms our randomized algorithm applied to the trace function U → tr(AUρU^*) almost surely converges to its global minimum. The minimum corresponds to the smallest eigenvalue (ground state) of the selfadjoint operator A (Hamiltonian) if ρ is a rank-one projector (pure state). In this setting, one can efficiently replace the uniform random projections by implementing so-called discrete unitary 2-designs.