Temporal Smoothing for Online Non-Convex Learning

This direction is merged into another direction: local optima convergence (stationary point convergence). Its last version stays readable and citable here.

Version 1 of 17 papers15 conceptsfrozen 2026-10-04

In the standard toolkit of online learning, we often assume the world is convex—a series of "bowls" where every step downhill leads us closer to a global optimum. However, modern machine learning frequently operates in non-convex landscapes: complex "mountain ranges" filled with peaks, valleys, and plateaus.

When these non-convex landscapes change over time (the "online" setting), a fundamental problem arises. If an adversary can change the terrain at every step, they can move the valley you just found to the other side of the map before you can react. This makes traditional "global regret"—the difference between your performance and the best single fixed decision in hindsight—mathematically impossible to minimize.

To solve this, researchers have converged on a powerful intuition: if we can't beat the adversary at high speeds, we must force the optimization landscape to slow down.

The Volatility Problem

In Efficient Regret Minimization in Non-Convex Games, Elad Hazan, Karan Singh, and Cyril Zhang highlight that an adversary can exploit non-convexity by creating rapidly changing landscapes. Without constraints, a learner is essentially chasing a ghost; by the time an algorithm computes a gradient and takes a step, the local geometry has shifted so radically that the step might actually increase the loss.

This volatility is the "final frontier" of online learning. While we have mature theories for online convex optimization, non-convexity usually breaks the link between local updates and global progress.

Temporal Smoothing via Sliding Windows

The core mechanism used to restore order is temporal smoothing. Instead of reacting to the loss function at the current moment $t$, the learner optimizes against an average of the most recent loss functions within a fixed "sliding window."

As explored by Nadav Hallak, Panayotis Mertikopoulos, and Volkan Cevher in Regret minimization in stochastic non-convex learning via a proximal-gradient approach, this window acts as a low-pass filter. It mitigates high-frequency adversarial perturbations and stochastic noise.

By averaging the objective functions over a time horizon, the algorithm is forced to respond to the persistent features of the environment rather than instantaneous spikes. This temporal averaging acts as a stabilizer, slowing down the "moving target" and allowing the learner to maintain a stable descent path even when the underlying environment is volatile.

From Global to Local Regret

Because finding a global optimum in a non-convex space is NP-hard even in offline settings, these papers shift the goalpost to local regret.

Local regret measures how well the learner performs relative to a sequence of points that are "locally optimal" or stationary. In Regret Minimization in Stochastic Non-Convex Learning via a Proximal-Gradient Approach, the authors demonstrate that by using a time-smoothed proximal-gradient approach, it is possible to achieve optimal regret bounds that bridge the gap between online learning and offline stochastic optimization.

Why It Works: The Proximal-Gradient Bridge

The reason this combination—sliding windows plus proximal-gradient steps—is so effective is that it balances two competing needs:

  1. Adaptivity: The sliding window ensures the learner eventually follows the changing environment.
  2. Stability: The proximal term prevents the learner from jumping too far in response to a single noisy or adversarial gradient.

By optimizing the average of the window, the learner effectively smooths out the "mountain range." This prevents the adversary from forcing high regret through rapid fluctuations, ensuring that the algorithm converges to meaningful stationary points even in the presence of non-smooth, non-convex, and stochastic feedback.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_temporal_smoothing_for_online_non_convex_7ab80a44,
  title = {Temporal Smoothing for Online Non-Convex Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-smoothing-for-online-non-convex-learning/rdr_7ab80a44ab3a4a0597dbbbb359feaa83},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_temporal_smoothing_for_online_non_convex_7ab80a44_v1,
  title = {Temporal Smoothing for Online Non-Convex Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/temporal-smoothing-for-online-non-convex-learning/rdr_7ab80a44ab3a4a0597dbbbb359feaa83/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}