Riemannian Dueling Optimization

This paper introduces Riemannian Dueling Normalized Gradient Descent (RDNGD) and Riemannian Dueling Frank-Wolfe (RDFW) algorithms to extend dueling optimization from Euclidean spaces to Riemannian manifolds, providing theoretical complexity guarantees and demonstrating effectiveness through numerical experiments on both synthetic and real-world applications.

The Gist

Imagine you are trying to find the lowest point in a vast, foggy valley. In the world of standard math and machine learning, you usually have a map or a compass that tells you exactly which way is "down" (the gradient). You take a step, check the map, take another step, and eventually, you find the bottom.

But what if you don't have a map? What if you can't even see the height of the ground? All you have is a friend who can only answer one question: "Is point A lower than point B?"

This is the challenge of Dueling Optimization. You don't know the numbers; you only know the preferences.

Now, imagine that valley isn't flat like a park. It's a curved surface, like the skin of a basketball or the inside of a saddle. This is a Riemannian Manifold. In this curved world, "straight lines" don't exist; you have to walk along curves called geodesics.

This paper introduces a new way to find the bottom of that curved valley when you only have your "preference friend" and no map.

The Core Problem: The Curved, Blind Hiker

The authors, Yuxuan Ren, Abhishek Roy, and Shiqian Ma, realized that many modern AI problems (like training robots or recommending movies) happen on these curved surfaces.

• Robots: A robot arm moves in 3D space. Its possible positions form a curved shape (like a sphere).
• Recommendations: To understand complex user tastes, computers often use "hyperbolic space" (a weird, expanding geometry).

In these places, standard math tools break. If you try to walk "straight" on a sphere, you fall off. And if you can't see the height (the loss function), you can't use standard gradient descent. You only have duels: "Is this robot pose better than that one?"

The Solution: Two New Algorithms

The paper proposes two main strategies to solve this "Curved, Blind Hiker" problem.

1. The "Gentle Nudge" Method (RDNGD)

Imagine you are standing on the curved hill. You can't see down, so you ask your friend: "If I take a tiny step in this random direction, is it better than taking a tiny step in the exact opposite direction?"

• The Trick: You pick a random direction, take a tiny step forward and a tiny step backward. You ask the friend: "Which one was better?"
• The Result: If the "forward" step was better, you know the "downhill" direction is roughly in that direction.
• The Innovation: The authors figured out how to do this on a curved surface. They use a mathematical tool called the Exponential Map to take steps that stay on the surface (like walking along the Earth's surface rather than drilling through the core).
• Why it's special: They proved that even with this "blind" guessing, you can mathematically guarantee that you will eventually find the bottom, and they calculated exactly how many steps it would take.

2. The "No-Projection" Method (RDFW)

Sometimes, the rules of the game are strict. Imagine you are on a sphere, and you are only allowed to stay on the surface. If you take a step that goes slightly inside the sphere, you have to be "projected" (pushed) back onto the surface. This "pushing back" is computationally expensive and slow.

The authors created a second method, Riemannian Dueling Frank-Wolfe, which is like a "projection-free" hiker.

• The Analogy: Instead of walking in a direction and then getting pushed back to the surface, this method asks: "If I could walk in a straight line from here, where would I hit the boundary of the allowed area?"
• It finds the best "boundary point" based on the preference duel and walks directly toward it. This is much faster for complex shapes where "pushing back" is hard to calculate.

Real-World Examples

The paper shows these methods work in two very different scenarios:

1. Hacking Neural Networks (The "Adversarial Attack"):
   Imagine a hacker trying to trick an AI into misidentifying a stop sign as a speed limit sign. The hacker can't see the AI's internal "score" (the loss function), they can only ask: "Does this slightly altered image fool the AI more than that one?"

   • The Result: The new algorithm found the "perfect" trick image much faster than previous methods, using fewer questions to the AI.

2. Leveling a Horizon (The "Camera Fix"):
   Imagine taking a photo of a sunset, but the camera was tilted. You want to rotate the image until the horizon is perfectly straight. You don't have a "tilt meter." You just have a human (or a simple algorithm) who looks at two rotated versions and says, "This one looks straighter."

   • The Result: The algorithm rotated the image on a mathematical "sphere" of possible rotations and found the perfect straight line using only these "which looks better?" comparisons.

Why This Matters

Before this paper, if you wanted to optimize something on a curved surface (like a robot arm or a complex recommendation system) and you didn't have exact numbers (only preferences), you were stuck. You had to use slow, inefficient guesswork.

This paper provides the first reliable toolkit for these situations. It bridges the gap between:

1. Curved Geometry (Riemannian manifolds).
2. Blind Optimization (Dueling/Preference-based feedback).

It's like giving a hiker a compass that works even when they are blindfolded and walking on a curved planet. This opens the door for smarter robots, better AI recommendations, and more efficient machine learning in the real world.

Technical Summary

1. Problem Definition

The paper addresses Riemannian Dueling Optimization, a problem setting where the goal is to minimize an objective function $f(x)$ over a Riemannian manifold $\mathcal{M}$, but the algorithm has access only to a pairwise comparison oracle rather than function values or gradients.

• Objective: $\min_{x \in \mathcal{X} \subseteq \mathcal{M}} f(x)$
• Oracle: Given two points $x, y \in \mathcal{M}$, the oracle returns $Q_f(x, y) = 2 \cdot \mathbb{1}(f(x) > f(y)) - 1$. This indicates which point yields a lower objective value but reveals no magnitude information.
• Context: This setting arises in applications like recommendation systems (user preferences), robotics (trajectory comparison), and adversarial attacks on deep neural networks (black-box settings), where the decision space is inherently non-Euclidean (e.g., hyperbolic space, $SO(3)$, Stiefel manifolds).
• Challenge: Standard Riemannian optimization relies on gradients or function values. Dueling feedback is noisy and lacks magnitude, while the curvature of the manifold breaks standard Euclidean linearization and trigonometric assumptions used in existing dueling optimization methods.

2. Methodology

The authors propose two primary algorithms tailored to different constraints and smoothness properties of the objective function.

A. Riemannian Dueling Normalized Gradient Descent (RDNGD)

This method extends the Euclidean dueling normalized gradient descent to manifolds.

• Gradient Estimator: The core innovation is a Riemannian gradient direction estimator using a single random perturbation direction $u$ on the tangent space $T_x\mathcal{M}$:
  $$h_\nu(x) = Q_f(\text{Exp}_x(\nu u), \text{Exp}_x(-\nu u)) \cdot u$$
  Here, $\text{Exp}_x$ is the exponential map, ensuring perturbed points remain on the manifold.
• Theoretical Insight: The authors prove that $h_\nu(x)$ is approximately aligned with the normalized gradient $\frac{\text{grad}f(x)}{\|\text{grad}f(x)\|}$. They establish a tighter bound on the alignment constant $\hat{C}$ (improving from $1/20$ in prior Euclidean work to $1/\sqrt{2\pi} \approx 0.4$) and remove logarithmic factors in the bias analysis.
• Update Rule:
  $$x_{k+1} = P_\mathcal{X}(\text{Exp}_{x_k}(-\eta_k h_\nu(x_k)))$$
  where $P_\mathcal{X}$ is the projection onto the constraint set $\mathcal{X}$.
• Variants:
  • RDNGD: For geodesically $L$-smooth (non-convex) and geodesically convex objectives.
  • RRDNGD (Recurrent): A multi-phase algorithm for geodesically strongly convex objectives that achieves a linear convergence rate by adaptively reducing the target sub-optimality in each phase.

B. Riemannian Dueling Frank-Wolfe (RDFW)

To address scenarios where projection onto the constraint set is computationally prohibitive (e.g., complex matrix constraints), the authors propose a projection-free method.

• Mechanism: Instead of projecting, RDFW solves a linear minimization subproblem on the manifold:
  $$z_k = \arg\min_{z \in \mathcal{X}} \langle \bar{h}_k, \text{Log}_{x_k}(z) \rangle$$
  where $\bar{h}_k$ is a batch-averaged gradient estimator to reduce variance.
• Update Rule: The iterate is updated along the geodesic connecting $x_k$ and $z_k$:
  $$x_{k+1} = \text{Exp}_{x_k}(s_k \text{Log}_{x_k}(z_k))$$
• Variance Control: The paper highlights that Frank-Wolfe is highly sensitive to noise in the gradient direction (unlike projected methods). Therefore, RDFW employs a batch size $M_k$ that grows with iterations to ensure the variance of the search direction decreases sufficiently for convergence.

3. Key Contributions

1. First Framework for Riemannian Dueling Optimization: The paper establishes the first theoretical framework for optimizing over manifolds using only comparison oracles, bridging the gap between preference-based learning and Riemannian geometry.
2. Improved Theoretical Bounds:
   • RDNGD: Establishes iteration complexities of $O(d\epsilon^{-2})$ for non-convex and $O(d\epsilon^{-1})$ for convex objectives.
   • RRDNGD: Achieves linear convergence $O(d \log(1/\epsilon))$ for strongly convex objectives.
   • RDFW: Provides the first convergence result for projection-free dueling optimization on manifolds with oracle complexity $O(d/\epsilon^2)$.
3. Refined Analysis: The authors improve upon existing Euclidean dueling optimization results (e.g., Saha et al., 2021) by:
   • Removing logarithmic factors in step-size constraints.
   • Providing tighter constants for gradient alignment.
   • Adapting bounds to intrinsic manifold curvature (sectional curvature $\kappa$) rather than just ambient dimension.
4. Projection-Free Solution: The RDFW algorithm enables optimization in settings where projection is intractable, a significant advancement for constrained manifold problems.

4. Experimental Results

The authors validate their methods on both synthetic and real-world datasets:

• Synthetic Problems:
  • Rayleigh Quotient Maximization: RDNGD achieves performance comparable to Zeroth-Order Riemannian Gradient Descent (ZO-RGD) which requires function values, despite using only comparisons.
  • Karcher Mean: RDNGD successfully finds the geometric mean of SPD matrices. RDFW is shown to solve the constrained Karcher mean problem (where projection is hard) effectively.
• Real Applications:
  • Adversarial Attacks on DNNs: The method is applied to generate adversarial examples on CIFAR-10 under $\ell_2$-norm constraints (sphere manifold). RDNGD outperforms ZO-RGD in query efficiency, requiring significantly fewer samples (10 vs. 500) to achieve high adversarial loss.
  • Horizon Leveling: The algorithm corrects image horizon tilt by optimizing over $SO(2)$ using pairwise human-like preferences (simulated via a loss function), converging to high accuracy within 30 iterations without gradient access.

5. Significance

This work is significant because it generalizes the powerful concept of "dueling feedback" (which is robust to noise and applicable in human-in-the-loop systems) to the non-Euclidean domains prevalent in modern machine learning (e.g., embeddings, rotations, covariance matrices).

• Theoretical Impact: It overcomes the geometric barriers of curvature in dueling optimization, providing rigorous convergence guarantees that were previously missing.
• Practical Impact: It offers viable algorithms for black-box optimization in robotics and computer vision where gradients are unavailable, and projection operations are too expensive.
• Efficiency: The results demonstrate that dueling optimization can be highly efficient in high-dimensional settings, often outperforming zeroth-order methods that rely on function value estimates.

In summary, the paper provides a comprehensive toolkit for optimizing complex, constrained, non-Euclidean problems using only relative feedback, with strong theoretical backing and empirical validation.