Online non-convex optimization with imperfect feedback

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

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.

Introduction

In online learning, convexity is a standard assumption that enables efficient algorithms like Online Gradient Descent to guarantee low regret. However, many real-world applications, such as neural network training or complex resource allocation, involve non-convex loss functions. In these settings, deterministic algorithms can be forced into "linear regret" traps by an adversary. To overcome this, learners must employ randomized (mixed) strategies.

This paper addresses the challenge of online non-convex optimization under imperfect feedback. Specifically, it considers scenarios where the learner receives either unbiased noisy feedback or "bandit" feedback—where only the loss of the chosen action is observed.

Methodology: Dual Averaging with Imperfect Feedback

The authors propose a framework based on Dual Averaging (DA). Unlike standard methods that update in the action space, DA maintains an aggregate "score" in a dual space. This score is mapped to a probability distribution over the action space via a "mirror map" derived from a regularizer.

Algorithm 1: Dual averaging with imperfect feedback

Key technical innovations include:

  • Continuous Action Space: Adapting DA for a continuum of actions rather than a discrete set.
  • Kernel Smoothing for Bandits: For bandit feedback, a kernel-based estimator is used to "spread" the single observed loss value to nearby points, constructing an inexact model of the full loss function.
  • Exploration-Exploitation: The Bandit Dual Averaging (BDA) variant incorporates explicit exploration to prevent premature convergence to local minima.

Key Insights and Theoretical Results

The choice of regularizer is critical in non-convex optimization. While it often only affects constants in convex settings, here it determines the regret rate. For instance, entropic regularization (the "Hedge" variant) proves more robust than $L^2$ regularization.

The paper establishes several tight regret bounds, summarized in the table below. Notably, it provides the first known dynamic regret guarantees for non-convex bandit settings, comparing performance against a policy that can change over time.

Summary of regret bounds for convex and non-convex losses under various feedback models.

Summary of Results:

  • Unbiased Feedback: Achieves $O(T^{1/2})$ static regret, matching the optimal rate for convex losses.
  • Bandit Feedback: Achieves $O(T^{\frac{n+2}{n+3}})$ static regret, where $n$ is the dimension.
  • Dynamic Regret: For unbiased feedback, the bound is $O(T^{2/3} V_T^{1/3})$, where $V_T$ represents the variation of the loss functions.

Numerical experiments validated these findings, showing that the kernel-based BDA method offers lower variance and faster convergence compared to traditional grid-based discretization strategies like EXP3.

Limitations and Future Directions

Despite its strengths, the approach faces the "curse of dimensionality" in bandit settings, as regret scales with the dimension $n$. Furthermore, the algorithm assumes a "sampling oracle" to draw actions from complex distributions, which may be computationally expensive in practice. Future work involves refining these sampling techniques and exploring parameter tuning for highly volatile environments.

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