This NeurIPS 2020 paper from researchers at Criteo AI Lab and Univ. Grenoble Alpes tackles a challenging frontier in machine learning: how to make optimal decisions in real-time when the "rules" (loss functions) are non-convex and the feedback you get is noisy or extremely limited.
TL;DR
The authors provide a theoretical framework for online non-convex optimization using a "dual averaging" approach that works even when the learner only receives imperfect or "bandit" feedback. They prove that sublinear regret is achievable in these difficult settings without needing to discretize the search space, answering a significant open question in the field.
The Challenge of Non-Convexity and Imperfect Feedback
In Online Convex Optimization (OCO), a learner repeatedly chooses actions and tries to minimize a cumulative loss. If the loss functions are convex, "gold standard" algorithms like Online Gradient Descent guarantee low "regret"—the difference between the learner's performance and the best possible fixed action in hindsight.
However, the real world is rarely convex. In deep learning, recommendation systems, and complex auctions, loss functions are often non-convex. In these adversarial cases, deterministic algorithms are easily "tricked," leading to poor performance. To succeed, learners must use randomized (mixed) strategies.
The specific gap this paper fills is the "feedback" problem. Previous work often assumed the learner sees the entire loss function after making a choice. This paper asks: What if we only have an inexact model of the loss? Or worse, what if we only see the single loss value for the specific action we took (the bandit setting)?
Methods: Dual Averaging for Continuous Spaces
The authors build their solution on Dual Averaging (DA), also known as "Follow the Regularized Leader."
- The Template: Instead of picking a single point, the learner maintains a probability distribution (a mixed strategy) over the action space. As shown in Algorithm 1, they track a "score" variable ($y_t$) that aggregates all previous inexact loss models and use a "mirror map" (a regularizer like negentropy) to turn those scores into the next probability distribution ($p_t$).
- Handling Continuous Spaces: Since the action space is continuous, the authors use Radon measures to define these distributions. They focus on "simple strategies" (piecewise constant densities) to make the math tractable.
- Bandit Dual Averaging (BDA): To handle the bandit setting (where you only see one data point), they use kernel smoothing. They construct a "fake" loss function by spreading the impact of the observed loss over a small neighborhood (the kernel). This creates a classic bias-variance tradeoff: a larger kernel is less noisy but more biased.
Key Insights
- Randomization is Mandatory: In non-convex adversarial settings, any deterministic algorithm can be forced into "linear regret" (failing as often as it succeeds). Randomization is the only way to stay competitive.
- The Choice of Regularizer is Critical: In convex optimization, many different regularizers yield the same $\mathcal{O}(T^{1/2})$ regret. In the non-convex world, the negentropy regularizer (which leads to the "Hedge" algorithm) is vastly superior to $L^2$ regularization. The $L^2$ version suffers a "catastrophic" dependence on the dimension of the space, while Hedge remains efficient.
- No "Cover" Required: A common trick for non-convex problems is to "discretize" the space into a grid (a cover). This paper shows that by using kernel smoothing, you can achieve sublinear regret in the bandit setting while treating the space as a continuum.
Key Results: Regret Bounds
This is a purely theoretical paper focusing on mathematical proofs and algorithmic convergence rates. The authors provide "tight" (near-optimal) regret bounds for several scenarios, summarized below:
- Unbiased Feedback: If the learner's model of the loss is noisy but correct on average, they achieve $\mathcal{O}(T^{1/2})$ static regret, matching the performance of the convex case.
- Bandit Feedback: In the much harder bandit setting, the algorithm (BDA) achieves a static regret of $\mathcal{O}(T^{\frac{n+2}{n+3}})$, where $n$ is the dimension of the space. While slower than $T^{1/2}$, it is still sublinear, meaning the learner gets better over time.
- Dynamic Regret: The authors also derive bounds for "dynamic regret," where the learner is compared against a competitor that can change actions over time. They show that as long as the environment doesn't change too wildly, the learner can still keep up.
Limitations and Future Work
- Sampling Complexity: While the paper proves the existence of these strategies, it assumes the learner has a "sampling oracle"—a way to easily draw a random action from the complex probability distributions generated by the algorithm. In high dimensions, this sampling can be computationally expensive.
- The Bandit Gap: The regret bound for the bandit case ($T^{\frac{n+2}{n+3}}$) is slightly worse than the theoretical lower bound for non-convex problems. The authors suspect their "explicit exploration" term might be unnecessary and that the bound could be tightened to $\mathcal{O}(T^{\frac{n+1}{n+2}})$.
- Kernel Tuning: The BDA algorithm requires carefully tuning the "smoothing radius" of the kernel over time. Finding a way to make this tuning adaptive to the unknown smoothness of the loss functions remains an open challenge.
Summary updated