Executive Summary
The paper introduces AdaRHD, the first fully adaptive algorithm for bilevel optimization on Riemannian manifolds. By employing an "inverse of cumulative gradient norm" strategy, AdaRHD eliminates the need for researchers to manually tune step sizes based on elusive parameters like manifold curvature or Lipschitz constants. Remarkably, it achieves this while maintaining the same theoretical convergence rates as traditional, non-adaptive methods.
The Challenge of Riemannian Bilevel Optimization
Bilevel optimization is essentially a "nested" optimization problem where one optimization task (the upper level) depends on the optimal solution of another (the lower level). This framework is a powerhouse for modern AI, frequently appearing in meta-learning, hyperparameter tuning, and neural architecture search.
When these problems are moved from flat Euclidean space to Riemannian manifolds—curved surfaces like spheres or the space of symmetric positive definite (SPD) matrices—the complexity increases significantly. Existing Riemannian Bilevel Optimization (RBO) algorithms are "parameter-hungry." To set a stable step size, they require prior knowledge of the manifold's curvature, the function's smoothness (Lipschitz constants), and the lower-level function's strong convexity. In practice, these values are often unknown or computationally expensive to estimate. Guessing incorrectly can cause the algorithm to diverge or crawl toward a solution at an impractically slow pace.
Introducing AdaRHD
The authors propose AdaRHD (Adaptive Riemannian Hypergradient Descent). The core innovation is a step-size strategy that adapts based on the history of observed gradients, similar in spirit to AdaGrad but specifically tailored for the nested and curved nature of RBO.
Key components of the algorithm include:
- Double-Loop Structure: The algorithm uses an inner loop to solve the lower-level problem and an outer loop to update the upper-level variables.
- Adaptive Step Sizes: Instead of a fixed learning rate $\eta$, the step size is determined by the inverse of the square root of the sum of squared previous gradient norms. This adaptive scaling is applied to both the lower-level updates and the upper-level hypergradient updates.
- Hypergradient Approximation: Because computing the exact hypergradient is often impossible, AdaRHD approximates it by solving a linear system using either adaptive Gradient Descent (AdaRHD-GD) or a Tangent Space Conjugate Gradient method (AdaRHD-CG).
- Retraction Support: Traditional Riemannian methods use "exponential mappings" to ensure updates stay on the manifold, which can be computationally heavy. The authors prove that AdaRHD works just as well with "retractions"—faster, first-order approximations of the manifold's geometry.
Experimental Setup
The researchers evaluated AdaRHD across several benchmarks to test its versatility:
- Simple Matrix Similarity: A synthetic problem involving the Stiefel manifold and SPD matrices.
- Deep Hyper-representation: A classification task using a 3-layer SPD network. They utilized a subset of the AFEW (Acted Facial Expressions in the Wild) dataset, which contains video frames of facial expressions categorized into seven emotions.
- Robust Optimization: Synthetic datasets were used to test the algorithm's ability to find the Karcher Mean (a method for averaging points on a manifold) and perform Maximum Likelihood Estimation (MLE).
Theoretical Guarantees and Insights
- Navigating Curvature: In Euclidean space, the distance between points is a straight line. On a manifold, curvature distorts these distances. The authors utilized complex trigonometric distance bounds to prove that their adaptive step size wouldn't cause the algorithm to fly off the manifold or diverge.
- Matching the Gold Standard: Despite being "tuning-free," AdaRHD achieves an iteration complexity of $\mathcal{O}(1/\epsilon)$. This matches the best-known rates for non-adaptive RBO methods, meaning users do not pay a theoretical penalty for the convenience of adaptivity.
- The "Warm Start" Advantage: The algorithm effectively uses the solution from the previous iteration to initialize the next inner-loop search, significantly reducing the total number of iterations needed as the algorithm hones in on the global solution.
Performance and Robustness
The most striking result from the experiments is AdaRHD's robustness. In the deep hyper-representation experiments, the non-adaptive state-of-the-art method (RHGD) failed to converge when the initial step size was set too high. In contrast, AdaRHD remained stable across a wide range of initializations.
- Efficiency: AdaRHD-CG consistently reached high validation accuracy (e.g., 85% on the AFEW dataset) faster than other variants.
- Stability: While non-adaptive methods required careful "goldilocks" tuning to function properly, AdaRHD converged reliably even with poor initial step size guesses, exhibiting much lower standard deviation in performance across multiple trials.
Future Directions
While AdaRHD represents a major step forward for optimization on manifolds, the authors highlight several areas for future growth:
- Stochastic Settings: The current work focuses on deterministic problems. Extending this to a fully stochastic setting—where only noisy samples of the gradient are available—is a logical next step for broader machine learning applications.
- Single-Loop Efficiency: The algorithm currently relies on a double-loop structure. Developing a "single-loop" adaptive Riemannian algorithm, where upper and lower levels are updated simultaneously, could further boost computational efficiency.
- Relaxing Convexity Constraints: Currently, the method assumes the lower-level problem is "geodesically strongly convex." Future research could explore relaxing this requirement to handle more complex, non-convex lower-level landscapes.