🤖 machine learning

From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

This paper introduces a curvature-adaptive Follow-the-Perturbed-Leader (FTPL) algorithm for online non-convex optimization that dynamically adjusts its perturbation scale based on past information to achieve $O(\sqrt{T})$ regret in the worst case while improving to $O(\log T)$ regret when cumulative curvature grows linearly, a tradeoff proven to be intrinsic by matching lower bounds.

Original authors: Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

Published 2026-06-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Moses Charikar, Chirag Pabbaraju, Ambuj Tewari

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a video game where the rules change every single round. Sometimes the terrain is flat and predictable; other times, it's a chaotic, bumpy landscape with hidden traps. Your goal is to make the best move possible at every step to minimize your total "pain" (or regret) by the end of the game.

This paper introduces a new strategy for playing this game, called AdaFTPL. It solves a problem that has puzzled computer scientists for a long time: How do you play perfectly when you don't know if the game will be easy (smooth and curved) or hard (jagged and non-convex)?

Here is the breakdown of their solution using simple analogies.

The Problem: One Size Does Not Fit All

In the past, players had two main strategies:

The "Steady Walker" (Standard FTPL): This strategy works well when the game is chaotic and unpredictable. It adds a little bit of "random noise" or "shaking" to its decisions to avoid getting stuck in local traps. It guarantees you won't do too badly, even in the worst-case scenario. However, if the game turns out to be smooth and easy, this strategy is too cautious and misses the chance to win big.
The "Straight Shooter" (Follow-the-Leader): This strategy looks at all the past moves and picks the absolute best one. It is incredibly fast and efficient when the game is smooth and curved (like a bowl). But, if the game is chaotic, this player gets confused, oscillates wildly, and fails miserably.

The Big Question: Can we build a player that is a "Steady Walker" when things are chaotic, but instantly switches to being a "Straight Shooter" when things become smooth?

The Solution: A Self-Adjusting Shaking Scale

The authors created AdaFTPL, a player that carries a "shaking scale" (a knob that controls how much random noise it adds to its decisions).

The Old Way: Previous methods used a fixed shaking scale. They decided at the start of the game, "I will shake this much," and stuck with it. If the game got easier, they kept shaking unnecessarily. If it got harder, they didn't shake enough.
The New Way (AdaFTPL): This player uses a time-varying shaking scale. It looks at its own history and asks, "How curvy has the game been so far?"
- If the game has been chaotic and bumpy, it keeps the shaking scale high to stay safe.
- If the game starts to look smooth and curved (like a bowl), it automatically lowers the shaking scale, allowing it to move more directly toward the best solution.

How It Works: The "Ghost" Move

To decide how much to shake, the player uses a clever trick involving a "Ghost Move."
Imagine the player is about to make a move. Before committing, it asks a "Ghost" version of itself: "If I had known the next rule in advance, what would I have done?"
By comparing its actual move to this Ghost move, the player can estimate how "curved" the landscape is.

If the Ghost and the actual player are far apart, the landscape is chaotic. The player says, "I need more shaking!"
If the Ghost and the actual player are close together, the landscape is smooth. The player says, "I can stop shaking so much and just follow the curve."

The Results: Best of Both Worlds

The paper proves mathematically that this adaptive player is the best of both worlds:

In the worst case (Chaotic/Non-convex): It performs just as well as the old "Steady Walker," guaranteeing a safe, sub-linear score (meaning your mistakes grow very slowly compared to the number of rounds).
In the best case (Smooth/Strongly Convex): As soon as the game reveals it is smooth, the player adapts and speeds up, achieving a logarithmic score (meaning your mistakes barely grow at all).

Crucially, the player doesn't need to know in advance which type of game it is playing. It figures it out on the fly, round by round.

The "No Free Lunch" Proof

The authors didn't just show their player works; they also proved that you can't do better than this. They showed that there is a fundamental trade-off: you cannot be perfectly fast in a chaotic game and perfectly fast in a smooth game at the same time without adapting. Their algorithm hits the theoretical "speed limit" for every possible type of game sequence.

Real-World Context (From the Paper)

The paper mentions that this is useful for modern machine learning problems where you have a mix of:

Messy Data: Like a neural network learning a new task (which is often chaotic and non-convex).
Stabilizing Rules: Like a regularizer that keeps the model from forgetting old tasks (which adds smoothness/curvature).

In these scenarios, AdaFTPL automatically balances the chaos of the new data with the stability of the old rules, optimizing performance without the programmer needing to tune the settings manually.

In summary: This paper presents a smart, self-adjusting algorithm that knows when to be cautious and when to be aggressive, automatically tuning its behavior based on the "shape" of the problems it encounters, ensuring it never gets left behind whether the game is easy or hard.

Technical Summary: From Non-Convex to Strongly Convex: Curvature-Adaptive FTPL for Online Optimization

Problem Statement

The paper addresses a fundamental gap in online optimization theory regarding the adaptability of algorithms to the curvature of loss functions. Classical results establish that for convex, Lipschitz losses, the optimal regret scales as $O(\sqrt{T})$ , while for strongly convex losses, it improves to $O(\log T)$ . Adaptive methods (e.g., Bartlett et al., 2007) have successfully interpolated between these rates for convex settings. However, recent work (Suggala and Netrapalli, 2020) demonstrated that Follow-the-Perturbed-Leader (FTPL) achieves $O(\sqrt{T})$ regret for non-convex Lipschitz losses using an approximate offline optimization oracle, but these guarantees do not exploit curvature to achieve faster rates when strong convexity is present.

The central question posed is whether FTPL can be made curvature-adaptive in the non-convex regime, achieving $O(\sqrt{T})$ regret for general non-convex losses while automatically improving to $O(\log T)$ (or better) when sufficient cumulative strong convexity emerges, without prior knowledge of the curvature sequence.

Methodology

Algorithm: Adaptive FTPL (AdaFTPL)

The authors propose AdaFTPL, an extension of the standard FTPL framework. The core innovation is replacing the fixed perturbation scale $\rho$ with a time-varying noise scale $\rho_t$ .

Oracle Access: The algorithm assumes access to an $(\alpha, \beta)$ -approximate optimization oracle. Given a cumulative loss function $F_{t-1}$ and a perturbation vector $\sigma_t$ , the oracle returns a point $\hat{x}$ that approximately minimizes $F_{t-1}(x) - \langle \sigma_t, x \rangle$ .
Perturbation Mechanism: At each round $t$ , the learner generates a random vector $\sigma_t$ with i.i.d. exponential entries and scales it by $\rho_t$ . The prediction $x_t$ is obtained by querying the oracle with the perturbed cumulative loss $F_{t-1} - \rho_t \sigma_t$ .

Meta-Online Learning for Schedule Selection

The sequence $\rho_1, \dots, \rho_T$ is not fixed but chosen adaptively based on past information. The authors frame the selection of $\rho_t$ as a meta-online learning problem:

Regret Bound Parameterization: They derive a general regret bound (Theorem 1) that depends on the sequence $\rho_t$ and the cumulative strong convexity constants $S_t$ of the cumulative loss functions $F_t = \sum_{i=1}^t f_i$ . The bound involves a minimum of two terms: one reflecting non-convex stability (scaling with $1/\rho_t$ ) and one reflecting strong convexity (scaling with $1/S_t$ ).
Follow-the-Leader (FTL) Tuning: To choose $\rho_t$ without knowing future losses, the algorithm sets $\rho_t$ to minimize the past regret upper bound (a "Follow-the-Leader" move in the space of noise schedules). Specifically, $\rho_t$ is chosen to minimize the cumulative bound derived from rounds $1$ to $t-1$ .
Competitive Analysis: Theorem 2 proves that this simple FTL tuning strategy is constant-competitive with the best fixed schedule chosen in hindsight (the offline optimum).

Theoretical Analysis

The analysis relies on a "ghost" move decomposition. The authors introduce a hypothetical move $\bar{x}_{t+1}$ that uses the current noise scale $\rho_t$ but the updated cumulative loss $F_t$ . This allows them to decompose the regret into:

Stability: The distance between the actual move $x_t$ $x_{t}$ and the ghost move $\bar{x}_{t+1}$ $\overset{x}{ˉ}_{t + 1}$ . This is bounded in two ways:
- Non-convex bound: Derived from Lipschitz continuity and the properties of the exponential perturbation (following Suggala and Netrapalli, 2020).
- Strongly convex bound: Derived from the strong convexity of $F_t$ , yielding a bound proportional to $L/S_t$ .
Perturbation: The cost of the noise and oracle approximation errors.

By taking the minimum of the non-convex and strongly convex stability bounds at each step, the algorithm effectively interpolates between the two regimes.

Key Results

Upper Bounds

General Regret: The algorithm achieves a regret bound of $O(\sqrt{T})$ for arbitrary non-convex Lipschitz losses.
Curvature-Adaptive Regret: If the cumulative curvature $S_t$ $S_{t}$ grows as $t^\gamma$ $t^{γ}$ , the regret scales as follows (Corollary 3.1):
- $\gamma \leq 1/2$ : $O(\sqrt{T})$
- $1/2 < \gamma < 1$ : $O(T^{1-\gamma})$
- $\gamma = 1$ (Linear growth, i.e., Strong Convexity): $O(\log T)$
- $\gamma > 1$ : $O(1)$
Oracle Requirements: To achieve these rates, the oracle error parameters must satisfy $\alpha, \beta = O(1/T)$ .

Lower Bounds

The authors provide matching lower bounds (Theorem 3) for any algorithm, even in the restricted setting of one-dimensional convex losses. They show that for any prescribed sequence of cumulative curvatures, the minimax regret is lower-bounded by $\Omega(\text{OPT}_T^0(0))$ , which matches the upper bound achieved by AdaFTPL up to constant factors. This proves that the trade-off between worst-case non-convex regret and curvature-driven fast rates is intrinsic to the problem, not an artifact of the algorithm's analysis.

Empirical Validation

Synthetic experiments on quadratic functions with varying curvature (controlled by a probability parameter $p_+$ ) demonstrate that:

In low-curvature regimes ( $p_+$ small), AdaFTPL performs comparably to standard FTPL and FTL.
As curvature increases, AdaFTPL significantly outperforms non-adaptive FTPL, approaching the performance of FTL (which is optimal for strongly convex problems but fails in non-convex settings).
The algorithm adapts dynamically when curvature is introduced or removed mid-sequence.
In adversarial alternating-sign scenarios where FTL incurs linear regret, AdaFTPL maintains sublinear regret due to its perturbation mechanism.

Significance and Claims

The paper claims to provide the first FTPL method that achieves curvature adaptivity in the non-convex regime. Its significance lies in:

Bridging the Gap: It unifies the theoretical guarantees of adaptive methods for online convex optimization (e.g., Bartlett et al., 2007) with the non-convex guarantees of FTPL (Suggala and Netrapalli, 2020).
Oracle Efficiency: It maintains the computational efficiency of FTPL, relying only on an offline optimization oracle, which is crucial for structured decision sets where direct gradient methods are intractable.
Optimality: By providing matching lower bounds, the authors establish that the derived regret rates are minimax optimal for the given curvature sequences.
Practical Motivation: The work is motivated by composite loss structures in modern machine learning (e.g., continual learning, robust regression) where non-convex data terms interact with strongly convex regularizers, creating a dynamic curvature landscape that is unknown a priori.

The authors modestly note that their results extend adaptive regret rates significantly beyond online convex optimization, offering a robust framework for settings where the "best" algorithmic behavior depends on the unknown interplay between non-convexity and regularization.