Introduction
In many modern machine learning applications—ranging from online ad auctions to complex recommender systems—an agent must make sequential decisions to maximize rewards without ever seeing the gradient of the reward function. This is known as zeroth-order optimization, where the learner only receives "bandit feedback": the reward for the specific action taken, with no information about the surrounding landscape.
This problem becomes significantly more difficult when the environment is non-convex (containing many local optima) and adversarial (where the reward function can change at every time step). This paper introduces Hierarchical Dual Averaging (HDA), a novel algorithm that addresses these challenges by combining a tree-based space-partitioning strategy with a sophisticated regularization framework. HDA is the first algorithm to achieve minimax optimal regret bounds in this specific adversarial zeroth-order setting.
The Challenge of Non-Convex Bandit Feedback
Optimizing in a zeroth-order, non-convex, and online environment presents a "triple threat" to standard optimization techniques:
- Non-convexity: The reward landscape is complex and "bumpy," making it easy for algorithms to get stuck in sub-optimal regions.
- Adversarial Dynamics: The reward function is not stationary; it can be manipulated by an adversary to punish the learner's previous choices.
- Bandit Feedback: The learner only observes the value of the function at the sampled point, making it difficult to estimate the global structure of the function.
Previous approaches typically relied on kernel smoothing or periodic restarts (the "doubling trick"). However, kernel methods scale poorly in high dimensions, and restarts often lead to sharp performance drops and instability. Furthermore, a theoretical gap remained between the best-known performance bounds and the theoretical limits for dynamic regret.
The HDA Algorithm
Hierarchical Dual Averaging (HDA) is built upon three primary pillars designed to overcome the limitations of previous methods:
1. Dimension-wise Hierarchical Splitting
Rather than using a fixed grid or splitting the search space into $2^d$ sub-boxes (which leads to exponential complexity), HDA employs a tree-based "zoom-in" mechanism. It splits the space dimension-wise—refining one dimension at a time in a round-robin fashion. This allows the algorithm to increase the granularity of its search at a manageable, logarithmic pace, effectively mitigating the curse of dimensionality.
2. Dual Averaging over Evolving Partitions
The algorithm adapts Nesterov’s dual averaging framework to work over these dynamic partitions. HDA maintains "scores" for different regions of the search space, which are then converted into a probability distribution. This distribution guides the selection of the next action, ensuring that the learner balances exploration of new regions with exploitation of known high-reward areas.
3. Fisher Information Regularization
While standard online learning algorithms often use global norms (like Euclidean distance) for regularization, HDA utilizes a regularizer adapted to the Fisher information metric (such as the Burg entropy or log-barrier). This Riemannian approach allows the learner to account for the "information content" of their policy. By using a strategy-dependent metric, HDA achieves much finer control over the bias and variance of its reward estimates, which is the mathematical "secret sauce" behind its improved performance.
Theoretical and Empirical Results
The primary contribution of the paper is the proof that HDA achieves minimax optimal regret bounds.
- Static Regret: HDA achieves a bound of $O(T^{rac{d+1}{d+2}})$, which is the best possible rate for this class of problems.
- Dynamic Regret: The paper confirms a long-standing conjecture by proving a dynamic regret bound of $O(T^{rac{d+2}{d+3}} V_T^{rac{1}{d+3}})$, where $V_T$ represents the total variation of the reward functions. This matches the theoretical lower bounds for adversarial zeroth-order settings.
Empirically, the authors tested HDA against "Grid" baselines (naive discretization) and state-of-the-art "Kernel" smoothing methods using synthetic non-convex environments (e.g., complex trigonometric "Sine" functions and adversarial "Gauss" distributions). In 1D and 2D simulations, HDA consistently demonstrated faster convergence and significantly lower variance across random seeds, proving to be more stable and efficient than its predecessors.
Conclusion and Future Work
HDA represents a significant step forward in zeroth-order optimization by providing an anytime algorithm—one that does not require restarts—that is theoretically optimal. While the current work focuses on 1D and 2D settings, the dimension-wise splitting strategy suggests better scalability for higher-dimensional problems.
Future research directions include reducing the algorithm's sensitivity to hyperparameters (such as the splitting schedule) and developing methods to estimate the total variation ($V_T$) of the environment in real-time, which would allow the algorithm to adapt even more effectively to highly dynamic rewards.
Summary updated