In the world of optimization, gradients are king. If you have them, you can navigate complex landscapes with ease. But what happens when you don't? In fields like robotics control, black-box optimization, or interactive learning, we often only have "zeroth-order" access—we can see the result of an action, but we don't know the slope of the hill we're climbing. This is the realm of Derivative-Free Optimization (DFO).
The problem? DFO usually scales terribly. As the number of dimensions ($d$) grows, the number of samples needed to find a good direction explodes. In a paper published at ICLR 2020, researchers propose a clever way out: Learned Manifold Random Search (LMRS).
TL;DR
High-dimensional derivative-free optimization is notoriously sample-inefficient because it searches in every possible direction. LMRS drastically reduces this complexity by learning a low-dimensional, non-linear manifold that captures the function's structure and then "guiding" the random search to stay within that manifold.
The Problem: The Needle in a High-Dimensional Haystack
Standard random search works by perturbing a point in random directions, measuring the change in the objective function, and estimating a gradient. However, the "sample complexity" (how many evaluations you need) typically scales linearly with the dimensionality of the space. For a complex robot like the MuJoCo Humanoid, which has dozens of degrees of freedom, searching the entire space is highly inefficient.
The authors lean on the manifold hypothesis: the idea that while data might exist in a high-dimensional space, it actually lies on a much lower-dimensional "manifold." If we could perform our search only on that manifold, we could ignore the irrelevant dimensions and find the optimum much faster. The catch is that we don't know what that manifold looks like ahead of time.
Methods: Joint Optimization and Manifold Learning
The core innovation of LMRS is joint optimization and manifold learning. Instead of assuming the manifold is known, the algorithm learns it on the fly.
- The Model: They use a neural network to represent the manifold. Specifically, they model the objective function as $f(x) \approx g(r(x; \theta); \psi)$, where $r$ maps the high-dimensional input to a low-dimensional latent space, and $g$ predicts the value.
- The Search: At each step, the algorithm samples directions from two sources:
- Exploitation: Directions within the tangent space of the currently learned manifold (using the Jacobian of the neural network).
- Exploration: Directions from the full high-dimensional space to ensure the manifold itself is being learned correctly.
- The Update: They use a "Follow the Regularized Leader" (FTRL) approach to update the manifold parameters ($\theta, \psi$) using all function evaluations collected so far. This ensures the manifold stays "up to date" as the optimizer moves into new regions of the search space.
Key Insights and Ideas
- Non-linear is Necessary: While previous methods tried to find linear subspaces, LMRS uses neural networks to capture non-linear manifolds. This is crucial for complex tasks like walking, where the relationship between joint angles and rewards is highly non-linear.
- Theoretical Speedup: The authors provide a proof showing that LMRS reduces sample complexity from a dependency on $d$ (ambient dimension) to roughly $n\sqrt{d}$ (where $n$ is the manifold dimension). When $n \ll d$, the savings are massive.
- Computational Efficiency: You might think training a neural network at every step would be slow. However, in DFO, the bottleneck is almost always the simulator (the "function evaluation"). The time spent updating the manifold is negligible compared to running a complex simulation.
Key Results
The authors evaluated LMRS across three distinct domains: MuJoCo Locomotion, the Pagmo Suite (classic continuous optimization functions), and Airfoil Optimization. LMRS consistently outperformed state-of-the-art baselines like Augmented Random Search (ARS) and CMA-ES.
- Humanoid-v1: This is the "boss level" of MuJoCo. LMRS reached the "solved" threshold in roughly 108,000 episodes, while the next best method (ARS) took over 220,000.
- Airfoil: LMRS found a wing shape with a Lift-Drag ratio of 1.97, significantly higher than ARS (0.56) or Bayesian Optimization (1.84).
- Ablations: The authors showed that "No Learning" (using a random manifold) and "No Search" (using only the model's predicted gradient) both failed, proving that the joint process of learning and searching is the secret sauce.
Limitations and Future Work
While powerful, LMRS isn't a silver bullet:
- Architecture Sensitivity: The performance depends on choosing a good neural network architecture for the manifold. If the network is too small, it can't represent the manifold; if it's too large, it might overfit.
- The Manifold Assumption: The method assumes a low-dimensional manifold actually exists. If the objective function is truly high-dimensional and "noisy" in every direction, the benefits of LMRS would diminish.
- Hyperparameters: Like many deep learning methods, it introduces new hyperparameters (like the mixing weight $\beta$ between exploration and exploitation) that may require tuning.
For researchers working on robotics or complex simulations where every sample counts, LMRS offers a mathematically grounded and empirically strong way to guide random search out of the high-dimensional wilderness.
Summary updated