acceptodds
Under review as a conference paper at ICLR 2027

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

10 views

Abstract

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 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.

Primary area:
optimization
Keywords:
Riemannian Optimization, Frechet Regression, Difference of Convex, Bounded Curvature, Variant Reduction

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_RuXFOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies signed Fr'echet regression for manifold-valued responses. At a query point, the fitted response minimizes a weighted sum of squared geodesic distances, where the regression weights may be negative. The resulting objective has a difference-of-convex structure, but positive curvature limits the global convexity of squared-distance losses. Existing implicit methods also require repeated full-gradient evaluations, which can be expensive for large datasets.

The authors propose VariancE-Reduced Implicit FRIDA (VERI-FRIDA). At each outer iteration, the method samples a small batch of positively weighted observations to retain a nonlinear distance model, estimates the positive and negative component gradients using variance-reduced estimators, and adds a tangent-space correction so that the model gradient at the current iterate exactly matches the estimated full signed gradient. An adaptive regularizer enforces strong geodesic convexity of each local model, which is then approximately minimized. The framework accommodates PAGE, SARAH/SPIDER, SVRG, SVRRM, SRVRG, STORM, and Hybrid-SGD estimators.

Under explicit local geometric and negative-weight assumptions, the paper proves an O(K−1)O(K^{-1}) bound on the expected squared Riemannian gradient norm at a uniformly selected iterate for refresh-based methods. For STORM and Hybrid-SGD, it proves almost sure convergence of the gradient norm to zero under a diminishing step-size schedule. Experiments on a torus, SO(3)SO(3) robot-motion regression, and S2×S1S^2\times S^1 comparing the proposed methods with explicit Riemannian baselines and deterministic FRIDA.

Critical strengths
  • Directly sampling the nonlinear Fréchet model introduces gradient noise that may persist even near a stationary point, making it difficult to retain the first-order accuracy needed for convergence. The paper addresses this challenge through a tangent-space correction that makes the sampled model's gradient at the current iterate exactly match the variance-reduced estimate of the full signed gradient.

  • Beyond proposing a stochastic implicit algorithm, the paper develops a common analysis that links gradient-estimation error and inexact inner solves to stationarity. It then applies this framework to several estimators, including PAGE, SARAH/SPIDER, SVRG, SVRRM, SRVRG, STORM, and Hybrid-SGD. The results distinguish the two sampling regimes: refresh-based variants obtain an O(1/K)O(1/K) expected stationarity bound, while refresh-free variants obtain almost-sure convergence under diminishing parameter schedules. This breadth makes the contribution more useful than an analysis of a single estimator.

Critical weaknesses
  • The paper is well organized, moving from the geometric setting to the algorithm, convergence results, and experiments. However, many symbols, tangent-space transports, geometric constants, and estimator variants are introduced in quick succession. It is difficult for readers who are in contact with manifold optimization for the first time to understand the research content quickly.

  • The convergence analysis requires all responses to lie in a sufficiently small geodesic ball (Assumption 2.1) and imposes W−<(R−r)/(2r)W^- < (R-r)/(2r) on the total negative weight (Assumption 2.2). These conditions are motivated by the proof, but their practical scope is not fully characterized. For example, W−=0.9W^-=0.9 requires R>2.8rR>2.8r, while RR must also satisfy the geometric restrictions in Assumption 2.1. The authors not clarify how these conditions can be verified for a given dataset and characterize the query points for which the convergence guarantees apply.

  • The paper reports that the STORM and Hybrid variants make substantially less progress than the other variants within the experimental iteration budget, but does not investigate the cause. Since both are included in the proposed unified framework, it would be useful to examine whether their behavior is driven by estimator variance, parameter choices, or the implicit subproblem solves.

  • Algorithm 1 specifies an acceptance condition for the implicit subproblem, but the paper does not state which numerical solver is used in the experiments. It also omits the solver’s initialization, stopping tolerance, iteration limit, and observed inner iteration counts. These omissions make the timing results difficult to reproduce. The authors should provide the implementation details for each manifold.

Questions for authors

In the algorithm framework, the value range of step size is (0,1](0,1], but in the numerical experiment, the step size is adjusted separately for each method. How to obtain the specific step size?

Reviewer_NBYaOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes VERI-FRIDA, a stochastic implicit optimization framework for empirical Fréchet regression with signed weights on Riemannian manifolds. To address the high computational cost of existing FRIDA methods, the authors combine stochastic sampling of positively weighted terms with variance-reduced gradient estimators and a tangent-space correction to construct efficient implicit subproblems. An adaptive regularization strategy is further introduced to ensure strong geodesic convexity of the sampled models. The paper establishes convergence guarantees for different variance-reduction schemes, including an (O(1/K)) bound on the expected squared Riemannian gradient norm for refresh-based methods and almost-sure convergence for fully stochastic variants. Experiments on the torus, SO(3), and product manifolds demonstrate the computational efficiency and optimization performance of the proposed framework compared with existing methods.

Critical strengths
  1. The paper provides a relatively comprehensive theoretical analysis.

  2. The research motivation is clear and well justified.

Critical weaknesses

1. The applicability of the proposed method is relatively limited, and its practical significance has not been sufficiently demonstrated.

The paper primarily focuses on empirical Fréchet regression with signed weights, where the manifold-valued responses must satisfy specific geometric conditions. However, it remains unclear how many practical machine learning tasks require this particular formulation and what distinctive advantages it offers over alternative regression approaches.

Although the paper provides some practical motivation, it does not sufficiently demonstrate the necessity of the proposed framework across a broader range of real-world applications. Therefore, if its applicability is largely restricted to a small set of specialized manifold regression problems, its practical significance and overall impact may be limited.

2. The experimental validation is relatively limited.

The current experiments mainly focus on numerical optimization analyses on low-dimensional manifolds. Although the paper includes experiments using real-world robot motion data, the evaluations primarily emphasize gradient norms and computational efficiency, without sufficiently assessing actual prediction performance.

Furthermore, the proposed method has not been evaluated on more complex real-world tasks or higher-dimensional manifold optimization problems. As a result, the current experimental results do not fully demonstrate its practical utility and scalability.

Questions for authors

1. Computational efficiency of the proposed method.

Although the paper demonstrates significant computational advantages on SO(3), the wall-clock experiments in the appendix indicate that VERI-FRIDA achieves comparable or even worse runtime performance than some explicit Riemannian optimization methods on the torus. Could the authors further analyze the main factors contributing to these differences and clarify under which conditions the proposed implicit optimization framework provides substantial computational advantages over explicit methods?

2. Practical applicability and scalability.

It would be valuable to further evaluate the proposed method on more representative real-world applications and higher-dimensional or more complex manifold optimization problems. Additionally, could the authors include evaluation metrics such as prediction errors on actual Fréchet regression tasks to demonstrate whether the improvements in optimization efficiency translate into better downstream task performance?

Reviewer_Ny2sOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes VERI-FRIDA, a stochastic version of FRIDA for Fréchet regression on manifolds with bounded curvature, where the objective is an affine combination of squared geodesic distances whose weights can be negative. Each iteration minimizes a model that keeps a small sampled batch of the positively weighted terms, adds a correction term so that the model gradient at the current point equals a variance-reduced gradient estimate (PAGE, SARAH/SPIDER, SVRG, SVRRM, SRVRG, STORM or Hybrid-SGD), and adds a proximal term chosen so that the model is strongly geodesically convex. Under local curvature and negative-weight conditions, a general error-budget theorem gives an O(1/K)O(1/K) bound on the expected squared gradient norm for estimators with full-gradient refreshes, and almost-sure convergence for STORM and Hybrid-SGD. Experiments on a torus, on SO(3) with robot motion data, and on S2×S1S^2\times S^1 compare VERI-FRIDA with explicit Riemannian variance-reduced methods and deterministic FRIDA.

Critical strengths
  1. Well-motivated model construction. Matching the model gradient to a variance-reduced estimate is a simple way to combine a cheap sampled nonlinear model with variance reduction. The example in Appendix B.2.1 shows clearly why direct sampling of the model is not enough.
  2. Unified analysis. A single error-budget condition (18) covers seven estimators. The analysis handles positive curvature, the non-affine logarithm term and inexact inner solves.
  3. Experiments on real data. The SO(3) experiment uses real robot motion data, and the results report medians and interquartile ranges over ten seeds, as well as wall-clock time.
Critical weaknesses

W1. Limited novelty. The method combines FRIDA (Zhou & Uribe, 2026) with the Riemannian variance-reduced estimators unified in SERENA (Liu et al., 2025). The gradient correction is the Riemannian counterpart of gradient-corrected subproblems in the Euclidean setting (Shamir et al., 2014; Karagulyan et al., 2024), and stochastic DC methods with variance reduction already exist in the Euclidean setting (Le Thi et al., 2022). The convergence analysis follows the standard template for variance-reduced nonconvex methods: a descent inequality with an error term (Lemma B.8) and an accumulated-error bound for each estimator (Appendices B.4–B.5). The geometric parts, such as the local balls and the curvature-dependent regularization, largely follow FRIDA. I would appreciate it if the authors could clarify which parts of the method and the analysis are developed specifically for their setting, rather than obtained by combining these existing components.

W2. The theory does not show an advantage of the implicit update.

  • With the step-size condition ηk≤χ/(2Lf)\eta_k\le\chi/(2L_f), Lemma B.8 gives d(yk,yk+1)≤∣vk∣/(2Lf)d(y_k,y_{k+1})\le\\|v_k\\|/(2L_f), so each step is no longer than an explicit gradient step with stepsize 1/(2Lf)1/(2L_f). Moreover, the proof uses only three properties of the model φk\varphi_k in (13): grad,φk(yk)=vk\mathrm{grad}\\,\varphi_k(y_k)=v_k, strong convexity, and an upper bound on its Hessian. It does not use the sampled squared distances g^k(y)=W+bg∑i∈Skgd2(y,zi)\hat g_k(y)=\frac{W_+}{b_g}\sum_{i\in S_k^g}d^2(y,z_i) in φk\varphi_k. The same proof works, with λk\lambda_k adjusted, if g^k\hat g_k is removed from φk\varphi_k, which essentially gives an explicit gradient step. Hence the theory does not explain why VERI-FRIDA needs fewer iterations than explicit methods in the experiments.
  • The O(1/K)O(1/K) bound counts outer iterations only, and Appendix B.3.3 states that it does not bound the inner-solver work. There is no bound on the total number of component gradient evaluations in terms of mm and the target accuracy, although scalability in mm is the main motivation of the paper.

W3. Restrictive assumptions. All responses must lie in a small ball with Λ+D<π/2\sqrt{\Lambda_+}D<\pi/2, the total negative weight must satisfy W−<(R−r)/(2r)W_-<(R-r)/(2r), and the algorithm needs geometric constants such as δ\delta, δp\delta_p, Llog⁡L_{\log} and DD to set the regularization λk\lambda_k and the clipping radii. On SO(3), the data had to be filtered to a "certified pool" in a common normal neighborhood (Sec. 4). It is unclear how these constants can be obtained for other manifolds.

Minor.

  • Sec. 2 introduces grad, Hess and Exp only as notation. I suggest citing standard textbooks, e.g., Absil et al. (2008) and Boumal (2023), at the beginning of Sec. 2 for these notions.
  • In Sec. 4, Agricola et al. (2011) is cited for "real-world data on SO(3)", but that paper studies five-dimensional manifolds with an SO(3)-structure, not the rotation group or the robot data used here.
  • Sec. 3: "if W−W_- we ignore the negative terms" seems to miss "=0=0".

Summary. The model construction is well motivated and the analysis covers many estimators, but the method appears a fairly direct combination of FRIDA with existing variance-reduced estimators, the theory does not show an advantage of the implicit update over explicit methods, and the experiments are low-dimensional and show a clear wall-clock advantage only on SO(3). I would be glad to raise my score if the authors address these concerns and my questions.

References

  • P.-A. Absil, Robert Mahony, and Rodolphe Sepulchre. Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.

  • Ilka Agricola, Julia Becker-Bender, and Thomas Friedrich. On the topology and the geometry of SO(3)-manifolds. Annals of Global Analysis and Geometry, 40(1):67–84, 2011.

  • Nicolas Boumal. An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, 2023.

  • Avetik Karagulyan, Egor Shulgin, Abdurakhmon Sadiev, and Peter Richtárik. SPAM: Stochastic proximal point method with momentum variance reduction for non-convex cross-device federated learning. arXiv:2405.20127, 2024.

  • Hoai An Le Thi, Hoang Phuc Hau Luu, Hoai Minh Le, and Tao Pham Dinh. Stochastic DCA with variance reduction and applications in machine learning. Journal of Machine Learning Research, 23(206):1–44, 2022.

  • Yan Liu, Mingjie Chen, Chaojie Ji, Hao Zhang, and Ruxin Wang. SERENA: A unified stochastic recursive variance reduced gradient framework for Riemannian non-convex optimization. In Proceedings of the 42nd International Conference on Machine Learning (ICML), PMLR 267:38144–38168, 2025.

  • Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-efficient distributed optimization using an approximate Newton-type method. In Proceedings of the 31st International Conference on Machine Learning (ICML), PMLR 32:1000–1008, 2014.

  • Yamin Zhou and César A. Uribe. Proximal DCA for Fréchet regression on Riemannian manifolds with bounded curvature. arXiv:2605.23097, 2026.

Questions for authors
  1. Can the analysis show an advantage of the implicit model over explicit Riemannian variance-reduced methods, for example in the dependence on LfL_f or on the curvature?
  2. For the PAGE and SARAH variants, how many evaluations of individual gradients grad,ℓi\mathrm{grad}\\,\ell_i (i.e., of Logyzi\mathrm{Log}_y z_i), and how many inner iterations, are needed to reach E∣grad,f∣2≤ϵ\mathbb E\\|\mathrm{grad}\\, f\\|^2\le\epsilon? How does this compare with explicit Riemannian variance-reduced methods?
  3. How are δ\delta, δp\delta_p, Llog⁡L_{\log} and rˉ\bar r computed in the experiments, and how sensitive are the results to these values? How many of the 309,169 SO(3) pairs were removed when forming the "certified pool" in Sec. 4, and what criterion was used?
  4. How does VERI-FRIDA compare in wall-clock time with Riemannian gradient descent or Newton's method using full gradients on SO(3) with m=100,000m=100{,}000?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.