VERI-FRIDA: Geometry-Aware Implicit Variance Reduction for Fréchet Regression

Learning on rotations, covariance matrices, and other manifold-valued data calls for methods that respect their geometry. Fr\'echet regression is a recent, successful approach in which predictions are minimizers of weighted squared geodesic distances. However, weights depend on the predictor query and can be negative, particularly when extrapolating. Difference-of-convex (DC) methods build on this signed structure by linearizing the negative terms, and iteratively minimizing convex models; but most existing approaches are limited to Hadamard manifolds. Positively curved spaces pose additional challenges, as squared geodesic distances on these spaces are not globally convex. Building on local geometries, recently proposed curvature-aware methods have been shown to converge, yet still require repeated full-data model evaluations, thereby limiting their scalability. We propose VariancE-Reduced Implicit FRIDA (VERI-FRIDA), a stochastic implicit framework for affine combinations of squared-distance objectives on manifolds with bounded curvature. Our central idea is to sample the positively weighted terms and add a logarithmic correction to ensure that the model gradient equals variance-reduced estimates of the full gradient. We connect inexact implicit updates to estimator error, establishing two convergence guarantees under explicit geometric and negative-weight conditions. First, when the estimator is periodically or probabilistically reset to the exact full gradient, a sufficiently small step-size yields an $O(K^{-1})$ bound on the expected squared Riemannian gradient norm. Second, for recursive estimators that use only mini-batches, a suitable diminishing step-size schedule ensures that the gradient norm converges to zero almost surely. Numerical experiments show improved performance over other methods on various manifolds.