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