Online Non-Convex Optimization with Imperfect Feedback

Amélie Héliou, Matthieu Martin, Panayotis Mertikopoulos, Thibaud Rahier

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."

Algorithm 1: Dual averaging with imperfect feedback
  1. 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$).
  2. 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.
  3. 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:

Regret bounds for convex and non-convex losses across different feedback types
  • 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

Abstract

We consider the problem of online learning with non-convex losses. In terms of feedback, we assume that the learner observes – or otherwise constructs – an inexact model for the loss function encountered at each stage, and we propose a mixed-strategy learning policy based on dual averaging. In this general context, we derive a series of tight regret minimization guarantees, both for the learner’s static (external) regret, as well as the regret incurred against the best dynamic policy in hindsight. Subsequently, we apply this general template to the case where the learner only has access to the actual loss incurred at each stage of the process. This is achieved by means of a kernel-based estimator which generates an inexact model for each round’s loss function using only the learner’s realized losses as input.
BibTeX
@inproceedings{heliou2020online,
  author = {Amélie Héliou and Matthieu Martin and Panayotis Mertikopoulos and Thibaud Rahier},
  title = {{Online Non-Convex Optimization with Imperfect Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=UJjkgPPtlpK},
}
Figure