How Dual Adaptivity Powers Universal Algorithms to Minimize Adaptive Regret

Background

The dynamic nature of real‑world environments requires AI models that can learn online. To evaluate such models, researchers introduced the performance metric adaptive regret , defined as the maximum static regret over any interval.

Limitations of Existing Algorithms

Current online convex optimization (OCO) algorithms that minimize adaptive regret are often specialized to a single class of convex functions and need prior knowledge of parameters, limiting their practical applicability.

Dual‑Adaptivity Meta‑Expert Framework

Zhou Zhihua’s group at Nanjing University proposes a universal algorithm with dual adaptivity , which automatically adapts both to the function’s curvature (convex, exp‑concave, strongly convex) and to environmental changes (static or dynamic).

The core of the approach is a meta‑expert framework that dynamically creates multiple expert algorithms and aggregates them with a meta‑algorithm satisfying a second‑order bound.

Key Components

Expert algorithms : each minimizes static regret for a specific function class.

Interval set : each interval is associated with one or more experts responsible for minimizing regret on that interval.

Meta algorithm : combines the predictions of currently active experts at each round.

Universal Algorithms

UMA2 – Two‑Layer Universal Algorithm (Increasing Experts)

To handle the lack of prior knowledge, UMA2 creates a large pool of experts for each interval, allowing it to cover unknown function types and parameters. The meta‑algorithm used is Adapt‑ML‑Prod, extended with a “sleeping experts” mechanism so that experts are active only on their designated intervals.

Theoretical analysis shows UMA2 achieves optimal adaptive‑regret bounds for general convex, α‑exp‑concave, and λ‑strongly convex functions, even when the function class changes across intervals (e.g., I₁: convex, I₂: exp‑concave, I₃: strongly convex).

UMA3 – Three‑Layer Universal Algorithm (Enhancing Expert Capability)

Instead of increasing the number of experts, UMA3 improves each expert’s capability by employing a universal static‑regret algorithm (e.g., Maler) as a black‑box subroutine. The meta‑algorithm remains the same, resulting in a three‑layer structure that simplifies design and analysis while preserving the same adaptive‑regret guarantees as UMA2.

Extension to Online Composite Optimization

The team further tackles online composite optimization, where the loss at round t is a sum of a time‑varying convex function fₜ(·) and a fixed convex regularizer r(·). Directly feeding the composite loss into UMA2/UMA3 fails for exp‑concave components because the sum may lose exp‑concavity.

To overcome this, they design a new meta‑expert framework using Optimistic‑Adapt‑ML‑Prod as the meta‑algorithm, leveraging optimistic settings to obtain second‑order bounds even under time‑varying functions.

Two universal composite‑function experts are employed: one based on the original loss and another on a surrogate loss parameterized by different learning rates. This yields strong adaptive‑regret bounds for general convex, α‑exp‑concave, and λ‑strongly convex composite functions.

Practical Considerations and Future Work

Implementing these universal algorithms requires maintaining O(T) expert algorithms, leading to O(T) projection operations per round, which can be computationally heavy for complex feasible sets. Recent black‑box reduction techniques have reduced projection frequency to a single projection per round in related settings.

The authors plan to explore integrating such reduction methods into their framework to further lower projection costs and improve real‑world efficiency.