acceptodds
Under review as a conference paper at ICLR 2027

Riemannian Bandit Convex Optimization with Self-Concordant Geometry

Abstract

We study adversarial bandit convex optimization on Riemannian manifolds without a global affine structure. Our intrinsic barrier-proximal method combines exponential-map Dikin exploration with single-step updates based on scalar logarithmic surrogates. A squared-distance analysis avoids aggregating tangent vectors across base points or assuming surrogate convexity. We bound the curvature-induced estimator-to-smoothing support error by under loss regularity. Conditional on compact-interior iterates and uniform smooth normal-tube data, we establish one-point regret against nonanticipating adversaries and provide a two-point extension. Covariance-tracking experiments on symmetric positive definite manifolds demonstrate effective parameter transfer and query-loss improvements over feedback-matched baselines under both one- and two-point feedback.

Primary area:
optimization
Keywords:
Online Learning, Riemannian Optimization, Self-Concordant Barrier

Reviews

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

This paper studies gradient-based convex optimization constrained to Riemannian manifolds, with a focus on adversarial bandits. The authors propose a proximal optimization algorithm based on the self-concordant Dikin exploration to construct gradient estimators from function evaluations. They establish expected regret bounds and pathwise bounds. The analysis also extends to two-point feedback, where improved regret bounds are proven.

Critical strengths
  • The paper is well-written, even for readers not familiar with geometry. The authors provide sufficient intuition and clearly explain the motivation behind their algorithm and analysis.
  • I went through the proofs briefly and they seem correct to me.
  • Proposition 2 proposes a Lyapunov-like function for hth_t. I found this derivation interesting, and the underlying technique seems potentially applicable to other areas in optimization and ML theory.
Critical weaknesses

Theoretical concerns:

  • Assumption 4 seems non-standard in the related literature. It imposes an additional condition on R(x)R(x) along geodesic paths. The paper provides no examples where this might hold, and no discussion of when it might fail. Since the paper's main contribution hinges on it, the authors should clarify which classes of manifolds and feasible sets satisfy this assumption and explicitly verify it in their experiments.
  • Theorem 1 requires the algorithm's iterates to remain in a fixed compact subset of the feasible set. While Proposition 3 verifies the geometric conditions on Hadamard manifolds, it also assumes this compact containment rather than proving it. The authors should provide sufficient conditions ensuring that Algorithm 1 satisfies this assumption.

Experiments don't seem to justify the advantages of the algorithm:

  • While the proximal methods outperform the projected Euclidean method, the Dikin and isotropic variants achieve nearly identical performance, particularly in the two-point setting. This makes it difficult to determine whether the improvements arise from the proposed Dikin algorithm or just from the Riemannian proximal update.
  • The one- and two-point methods are evaluated on different datasets, without a direct comparison under matched experimental conditions. Thus, the experiments don't provide empirical support for the theoretically improved regret bound in Theorem 2.
Questions for authors

See weaknesses

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

This submission extends online bandit convex optimization from Euclidean space to Riemannian manifolds. A Riemannian manifold is a space on which geometric notions like lengths and angles are defined. Euclidean space is one example of a Riemannian manifold. At each timestep, the learner chooses an action and observes (only) its loss, with the goal of minimizing regret with respect to the best-in-hindsight action. The authors build on the line of work from (Euclidean) bandit convex optimization which uses a self-concordant barrier function for exploration.

In each round, their algorithm queries a random point from the barrier’s Dikin ball around its current center, mapped onto the manifold. (At a high level, a Dikin ball is an ellipse around a point that is guaranteed to stay inside the domain and adapts its shape to how close the boundary is in each direction.) They turn the observed loss into a gradient estimate, then takes one proximal step that moves downhill while staying close to the current center and inside the domain. The authors show that their algorithm obtains O(T^{2/3}) regret against an adaptive adversary. If instead the learner may query two point per round and observes the loss at both, the authors show how to extend their methods to obtain O(T^{1/2}) regret.

Finally, the authors empirically evaluate their methods on a task constructed from a breast cancer dataset in the one-point setting and on tasks constructed from handwritten digit and stock data for the two-point setting.

Critical strengths

To the best of my knowledge, the authors are the first to study self-concordant barrier-based methods in online bandit optimization over Riemannian manifolds. Extending such methods to Riemannian manifolds is important because some learning problems may involve structured domains, where losses may be geodesically convex even when they are non-convex in Euclidean coordinates. The authors provide an algorithm which obtains O(T^{2/3}) regret under one-point feedback and O(T^{1/2}) under two-point feedback. This is important because is shows that their algorithm is a principled approach for solving the problem.

Critical weaknesses

The writing is extremely dense and very hard to follow, especially for someone who is not already familiar with Riemannian manifolds. It is also hard to place this paper's results within the broader literature, as the related work is relegated to an appendix. From my understanding after reading the appendix, there is some novelty in what the authors study, but it is limited.

Key details are also either missing or hard to find. For example, I couldn't find a runtime analysis of Algorithm 1, or much details on how the proximal update was computed in the experiments.

Another weakness is the experiments section. I realize that the primary contribution of this work is theoretical, but I had a hard time understanding what the actual experiments had to do with breast cancer, stocks, or handwritten digits. Also, if I am interpreting the results correctly, it appears that the authors' algorithm only marginally outperforms the baseline which does not account for the Riemannian geometry (e.g. a largest reported gain of 5.58% in Figure 1).

Questions for authors

What is the runtime of your algorithm?

Can the proximal objective be non-convex?

What was the wall-clock time for your experiments?

Does your regret analysis actually require global minimization of the proximal objective? Or would first-order stationarity suffice?

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

The paper studies online optimization on Riemannian manifolds when the learner observes loss values instead of gradients. It proposes a barrier-based method with conditional regret bounds of O~(T2/3)\tilde O(T^{2/3}) for one-point feedback and O~(T1/2)\tilde O(T^{1/2}) for two-point feedback. Experiments evaluate SPD covariance tracking.

Critical strengths
  • The theoretical derivation is easy to follow as the paper separating the error in estimating loss differences from the stability of the update.
  • The experiment results look promising, reporting one-point (T=1000,n=100T=1000, n=100) loss improvement of 5.08% with a 95% interval of [3.08, 7.07]% over 100 seeds.
Critical weaknesses
  • Theorem 1 assumes the iterates remain uniformly inside the feasible domain as the horizon grows, while Remark 1 explains that the barrier alone does not establish this condition. The application propositions also assume a suitable region.
  • The role of self-concordance is unclear. All the calculations appear to rely on compactness, positive-definite Hessians, and bounded local derivatives. The defining third-derivative self-concordance inequality does not appear necessary to the support or stability argument. Even the logarithmic comparator-barrier bound seems unused in the final regret calculation. The paper should explain why self-concordance is necessary, or formulate the result under the weaker conditions actually needed.
Questions for authors
  • Can you give a concrete curved-domain example where the actual algorithm provably satisfies the uniform interior assumption?
  • What benefit does self-concordance provide beyond the local conditions used in the feasibility and update arguments?
1 comment

Thank you for the rebuttal. The hyperbolic disk example addressed my concern on satisfying the uniform interior assumption on curved domain. I also appreciated the explanation on the role of the self concordance. The regret guarantee remains conditional, but these answers address my two main concerns. Therefore, I increased my score from 2 to 3.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.