From Complexity to Simplicity: Adaptive ES-Active Subspaces for Blackbox Optimization

Krzysztof Choromanski, Aldo Pacchiano, Jack Parker-Holder, Yunhao Tang, Vikas SindhwaniNeurIPS 2019 · OpenReview

Overview

ASEBO (Adaptive ES-Active Subspaces for Blackbox Optimization) is a novel algorithm designed to dramatically improve the efficiency of high-dimensional blackbox optimization. By utilizing online Principal Component Analysis (PCA) and contextual bandits, ASEBO dynamically identifies and exploits low-dimensional "active subspaces" where gradients predominantly reside. This approach achieves state-of-the-art sample efficiency in reinforcement learning (RL) tasks, bypassing the heavy hyperparameter tuning typically required by previous methods.

The Challenge of High-Dimensional Optimization

Optimizing high-dimensional "blackbox" functions—where the output is observable but the underlying math or derivatives are inaccessible—is notoriously difficult. This is a frequent hurdle in Reinforcement Learning, where evaluating a policy (a set of neural network weights) requires running a slow, computationally expensive simulation.

Standard Evolution Strategy (ES) methods attempt to estimate gradients by sampling random directions. However, as the number of dimensions ($d$) grows, the number of samples needed to obtain a reliable estimate typically scales with $d$. This makes standard ES prohibitively expensive for complex neural networks. While some existing methods attempt to focus on specific subspaces, they often rely on fixed hyperparameters (such as a pre-set subspace size) that fail to adapt as the optimization progresses, frequently causing the algorithm to stall or perform poorly.

The ASEBO Approach

The authors introduce ASEBO, which combines three sophisticated techniques to create a smarter, more adaptive Evolution Strategy:

  1. Active Subspaces via Online PCA: The algorithm maintains a running covariance matrix of previous gradient estimates. It employs an efficient online version of PCA with decaying weights to identify the "active subspace"—the specific directions in the parameter space where the function's output changes the most.
  2. Dynamic Dimensionality: Unlike previous "Guided ES" methods that rely on a fixed-size buffer, ASEBO uses a variance threshold (e.g., 99%) to capture a specific percentage of the gradient variance. This allows the algorithm to automatically shrink or expand the search space based on the "hardness" of the current optimization stage.
  3. Contextual Bandits for Exploration: To avoid the bias of exclusively searching within a low-dimensional subspace, ASEBO incorporates a multi-armed bandit mechanism (specifically, an exponentiated sampling approach). This mechanism continuously measures the bias of the current model and decides whether to sample directions from the active subspace (exploitation) or its orthogonal complement (exploration).

Empirical Evaluation & Key Insights

The authors evaluated ASEBO against a suite of challenging benchmarks, including seven continuous control RL tasks from OpenAI Gym (MuJoCo) and standard high-dimensional (1000-D) optimization functions from the Nevergrad library.

Evolution of active subspace dimensionality and the number of samples required by ASEBO versus the baseline in HalfCheetah (HC) and Swimmer (SW) environments.

Key Findings

  • Gradient Redundancy: The research demonstrates that even in high-dimensional RL tasks, the vast majority of gradient information (e.g., 99.5% of variance) often resides in a much smaller subspace (e.g., 100 dimensions out of 212).
  • The "On-the-Fly" Advantage: The intrinsic dimensionality of a problem is not static. ASEBO reveals that the number of "important" directions changes throughout training. By adapting this dimensionality in real-time, the algorithm remains highly efficient from start to finish.
  • Superior Sample Efficiency: In RL tasks, ASEBO consistently outperformed or matched state-of-the-art methods like ARS (Augmented Random Search) and PPO (Proximal Policy Optimization) while requiring significantly fewer environment interactions.
  • Robustness and Consistency: While Covariance Matrix Adaptation (CMA-ES) is a gold standard, it is highly sensitive to population size and can fail if poorly tuned. ASEBO learns the optimal number of sensing directions automatically, making it much more robust. It was the only algorithm to perform consistently well across all seven RL environments tested.

Limitations and Future Work

While ASEBO offers significant advancements, the authors note a few limitations:

  • Computational Complexity: The online PCA update has a quadratic time complexity $O(d^2)$ per iteration. While the authors argue this is negligible compared to the cost of function queries in RL, it could become a bottleneck for extremely high-dimensional problems involving millions of parameters.
  • Linear Subspaces: The current method relies on PCA, which is restricted to finding linear subspaces. Exploring "active manifolds" (non-linear subspaces) could further improve performance in the future.
  • Hyperparameter Sensitivity: Although ASEBO reduces the need to tune the subspace size, it introduces its own hyperparameters, such as the decay rate ($\lambda$) and the PCA threshold ($\epsilon$). Fortunately, these appear to remain relatively stable across different tasks.

Summary updated

Abstract

We present a new algorithm (ASEBO) for optimizing high-dimensional blackbox functions. ASEBO adapts to the geometry of the function and learns optimal sets of sensing directions, which are used to probe it, on-the-fly. It addresses the exploration-exploitation trade-off of blackbox optimization with expensive blackbox queries by continuously learning the bias of the lower-dimensional model used to approximate gradients of smoothings of the function via compressed sensing and contextual bandits methods. To obtain this model, it leverages techniques from the emerging theory of active subspaces in a novel ES blackbox optimization context. As a result, ASEBO learns the dynamically changing intrinsic dimensionality of the gradient space and adapts to the hardness of different stages of the optimization without external supervision. Consequently, it leads to more sample-efficient blackbox optimization than state-of-the-art algorithms. We provide theoretical results and test ASEBO advantages over other methods empirically by evaluating it on the set of reinforcement learning policy optimization tasks as well as functions from the recently open-sourced Nevergrad library.
BibTeX
@inproceedings{choromanski2019from,
  author = {Krzysztof Choromanski and Aldo Pacchiano and Jack Parker-Holder and Yunhao Tang and Vikas Sindhwani},
  title = {{From Complexity to Simplicity: Adaptive ES-Active Subspaces for Blackbox Optimization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=lGDzY2cFFS},
}
Figure