Riemannian Dueling Optimization

Dueling optimization considers optimizing an objective with access to only a comparison oracle of the objective function. It finds important applications in emerging fields such as recommendation systems and robotics. Existing works on dueling optimization mainly focused on unconstrained problems in the Euclidean space. In this work, we study dueling optimization over Riemannian manifolds, which covers important applications that cannot be solved by existing dueling optimization algorithms. In particular, we propose a Riemannian Dueling Normalized Gradient Descent (RDNGD) method and establish its iteration complexity when the objective function is geodesically $L$-smooth or geodesically (strongly) convex. We also propose a projection-free algorithm, named Riemannian Dueling Frank–Wolfe (RDFW) method, to deal with the situation where projection is prohibited. We establish the iteration and oracle complexities for RDFW. We illustrate the effectiveness of the proposed algorithms through numerical experiments on both synthetic and real applications.

In applications like recommendation systems and robotics, obtaining exact numerical scores to evaluate an option is often difficult. Instead, asking for preferences ("is option A better than option B?") provides much more reliable feedback. Finding the best overall solution using only these comparisons is known as "dueling optimization." While existing dueling methods are limited to solving basic problems with no constraints or simple constraints, many real-world applications involve challenges where the solution needs to satisfy some geometric properties or structural restrictions, making them significantly harder to solve. This paper bridges that gap by introducing new algorithms designed specifically to handle these geometric structures using only pairwise comparisons. Tests on both simulated and real-world applications prove that our proposed methods are efficient.