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