Research map / Bandits and online learning / Online convex optimization and games
Implicit Riemannian Optimism with Applications to Min-Max Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RIOD, an inexact implicit optimistic online learning algorithm on Hadamard manifolds that handles in-manifold constraints without curvature-dependent regret, and builds RIODA, a min-max solver achieving near-Euclidean gradient complexity.
Problem
Optimistic online learning and smooth g-convex, g-concave min-max optimization on Riemannian (Hadamard) manifolds, where prior methods cannot enforce in-manifold constraints and have geometry-dependent step sizes and rates that do not match Euclidean bounds.
Approach
A two-step implicit optimistic update (minimizing regularized loss and hint functions rather than linearizations) with inexact solves at a precision criterion; the regret bound has no curvature constant. Min-max is obtained by running RIOD on both players, with the subproblems solved by composite Riemannian gradient descent (CRGD), PRGD, or RGD.
Key results
- RIODA with CRGD achieves gradient oracle complexity of order L R^2/epsilon (and L/mu for strongly g-convex-concave), nearly matching Euclidean rates up to log factors and removing dependence on the geometric constant zeta.
- RIODA with RGD in the unconstrained setting improves complexity from zeta^4 to zeta^2 (factor zeta^2 over RAMMA-type bounds), without requiring knowledge of initial distance R.
- RIODA with PRGD in the constrained setting improves gradient oracle complexity by a factor of zeta^3.5 over the prior best rate, without knowing the Lipschitz constant.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RIOD instead of O-RCEG | Optimistic online learning on constrained Hadamard manifolds · Hadamard manifolds with in-manifold constraints | regret: removes the factor \oldzeta from \bigo{\frac{D^2}{\eta}+\eta \oldzeta \VT} to \bigo{\frac{D^2}{\eta}+\eta \VT} | Helped |
| Use RIODA-CRGD rather than RIODA-RGD | RIODA for unconstrained smooth min-max · Smooth g-convex, g-concave min-max, μ=0 | gradient oracle complexity: \bigotilde{\oldzeta_{ R} ^2\frac{L R^2}{\oldepsilon}} -> \bigotilde{\frac{L R^2}{\oldepsilon}} | Helped |
| Use RIODA-RGD rather than the [MRP24] method | Unconstrained smooth min-max implementation · Smooth g-convex, g-concave min-max, μ=0 | gradient oracle complexity: \bigotilde{\oldzeta_{ R} ^4\frac{L R^2}{\oldepsilon}} -> \bigotilde{\oldzeta_{ R} ^2\frac{L R^2}{\oldepsilon}} | Helped |
| Use RIODA-PRGD rather than RAMMA | Constrained smooth min-max · Constrained g-convex, g-concave min-max | gradient oracle complexity: improve ... by a factor of \bigotilde{\oldzeta_{\! R}^{3.5}} | Helped |
| Use RIODA-RGD rather than RIPPA | Unconstrained min-max without prior knowledge of initial distance · Smooth g-convex, g-concave min-max | gradient oracle complexity: reduced by a factor of \bigotilde{\oldzeta_{\! R} ^2} | Helped |
| Implement the implicit updates with CRGD rather than PRGD | RIOD min-max updates · Constrained min-max update implementation | gradient oracle calls per iteration: \bigotilde{\oldzeta_{D} \oldzeta_{\tilde{R}}} -> \bigotilde{1} | Helped |
| Use RIODA-CRGD rather than RIODA-PRGD | RIODA update implementation · Constrained min-max update implementation | gradient oracle calls per iteration: \bigotilde{\oldzeta_{D} \oldzeta_{\tilde{R}}} -> \bigotilde{1} | Helped |
Surprising findings
- The CRGD-based min-max method achieves nearly curvature-independent gradient complexity, which is unexpected given that smooth g-convex minimization rates still carry curvature-dependent penalties.
Limitations
- Implementing CRGD subproblem updates may be computationally hard.
- Lower bounds on hyperbolic space imply an implicit geometric dependence through the minimum condition number, so curvature-independence is only up to log factors and in certain regimes.
Experimental setup
Benchmarks: robust Karcher mean on symmetric positive definite manifold robust Karcher mean on hyperbolic space
Metrics: convergence rate gradient oracle complexity
Baselines: RAMMA RCEG ROOGD O-RCEG RIPPA Riemannian extragradient
Builds on: optimistic online mirror descent composite Riemannian gradient descent RAMMA RCEG
Closest papers by meaning
- Efficient Optimization with Orthogonality Constraint: a Randomized Riemannian Submanifold Method (ICML 2025 · similarity 0.88)
- Learning-Rate-Free Stochastic Optimization over Riemannian Manifolds (ICML 2024 · similarity 0.88)
- Finite-Time Analysis of Stochastic Nonconvex Nonsmooth Optimization on the Riemannian Manifolds (NeurIPS 2025 · similarity 0.88)
- Riemannian Accelerated Zeroth-order Algorithm: Improved Robustness and Lower Query Complexity (ICML 2024 · similarity 0.87)
- From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization (NeurIPS 2026 · similarity 0.87)
- A Framework for Bilevel Optimization on Riemannian Manifolds (NeurIPS 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.