Dynamic Regret Minimization

Follow this topic Ask about this topic

Momentum

5 papers in the last four weeks, against 1 the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 17

Oct 7, 2026stat.ML

Data Reuse in Non-Stationary Learning

We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.

Tomer Gafni, Garud Iyengar, Assaf Zeevi

Columbia University

Statistical Learning Theory Dynamic Regret Minimization

Oct 7, 2026cs.LG

Logarithmic Regret via Passive Change Detection in Piecewise-Stationary Self-Tuning Regulation

We study minimum-variance control of an unknown autoregressive system with exogenous inputs and coefficients that change at unknown times. Under bounded independent disturbances, fixed detection gaps, stability and feasibility conditions, and sufficient time between changes, we prove

O((C+1)\log((T+1)/δ))

regret with probability at least

1-δ

, where

T

is the horizon and

C

the number of changes. Unlike switching bandits, where unselected arms can change unobserved, admissible plant changes provide information during exploitation: the correct feasible controller leaves only the disturbance in the output, whereas a detectable change raises output energy under the old controller. PIECE-CD explores initially and after alarms, then uses gated recursive least squares for control. Its energy test compares windowed output power with a threshold above the noise floor; the extension to unstable controller mismatches also monitors the reference controller's input proposal. We control false alarms across the horizon and prove logarithmic detection delay. Inputs are clipped to prescribed bounds. Logarithmic regret also holds under an explicit condition ensuring that clipping becomes inactive after a finite burn-in. Under the stated feasibility conditions, the extended detector covers destabilizing changes with detectable excess energy over a fixed window.

A. Ch. Madhusudanarao, Rahul Singh

Department of Computer Science and Automation Indian Institute of Science, Bengaluru, India · Laboratoire de Recherche de l’EPITA, Paris, France

Adaptive Control Dynamic Regret Minimization Stochastic Optimal Control Change-Point Detection

Oct 5, 2026cs.LG

Dynamic Minimax Regret Optimization for Robust LLM Post-Training

Modern LLM training increasingly relies on heterogeneous data sources spanning different domains, tasks, preference distributions, and difficulty levels. We study dynamic minimax regret for group-distributionally robust LLM post-training under instantaneous mini-batch-only bandit feedback. The framework views the training as a two-player sampler-optimizer process: a sampler adaptively selects among data sources using bandit feedback, while an optimizer updates the model parameters using stochastic gradients from the selected source. We focus on the practically restrictive setting where source losses evolve with model training but historical data are not re-evaluated, requiring the sampler to track instantaneous worst-sources from stale partial feedback. We propose DUCB-OGD, a simple and scalable algorithm that couples a Discounted Upper-Confidence-Bound sampler with an Online Gradient Descent optimizer. The sampler maintains exponential moving average loss estimates and confidence radii based on discounted effective sample sizes, avoiding costly re-evaluation of past data or intrusive changes to standard training pipelines. For

K

data sources and

T

training steps, we prove that DUCB-OGD achieves a dynamic minimax regret of

\tilde{O}(K^{1/4}T^{3/4})

, which is optimal up to logarithmic factors for the undiscounted objective under our feedback model. Extensive experiments across supervised fine-tuning, preference optimization, and reinforcement learning show that DUCB-OGD integrates seamlessly into modern LLM training pipelines and improves worst-group robustness with negligible computational overhead compared with standard sampling baselines.

Chengbo Zang, Haoyu Dong, Mehmet Kerem Turkcan +3

Department of Electrical Engineering, Columbia University · Department of Computer Science & Engineering, University of California, Santa Cruz · Department of Civil Engineering, Columbia University

Dynamic Regret Minimization Distributionally Robust Optimization Robust Multi-Armed Bandits LLM Post-Training LLM Training

Sep 28, 2026cs.LG

Universal Dynamic Portfolios

Cover's Universal Portfolio (Cover, 1991) matches the performance of the best constant rebalanced portfolio in hindsight. We generalize this framework to compete with an arbitrary comparator sequence

\mathbf{u}_1,\ldots,\mathbf{u}_T

, leading to a dynamic regret minimization problem for the log loss where existing methods break down due to potentially unbounded gradients. The log loss is exp-concave, a curvature property that classically yields fast rates for static regret, yet we show that this advantage generally disappears in the dynamic setting. In particular, a linear-loss-type

\sqrt{TP_T}

dependence is unavoidable, where

P_T=\sum_{t=2}^T\lVert\mathbf{u}_t-\mathbf{u}_{t-1}\rVert_1

is the standard path length. This limitation stems from the coarse nature of

P_T

, which obscures finer spatial and temporal structure of the comparator sequence. We therefore introduce two structure-aware measures---the Jensen-Shannon distance for spatial structure and the JS

^q

-path length for temporal structure---under which faster rates are attainable when the comparator sequence has favorable structure. To achieve sharp bounds for both measures simultaneously, we develop Universal Dynamic Portfolio, a parameter-free method that combines a new Dirichlet Hedge algorithm with a fixed-share update, while retaining a near-optimal

P_T

guarantee in the worst case. Finally, under an additional bounded-gradient assumption, we show that OPS admits the faster

T^{1/3}P_T^{2/3}

dynamic regret rate over all comparator sequences. We attain this rate with a tractable proper algorithm that applies more broadly to general online exp-concave optimization over arbitrary compact convex domains.

Yu-Jie Zhang, Yu-Xiang Wang, Peng Zhao +1

University of Washington · University of California, San Diego · State Key Laboratory for Novel Software Technology, Nanjing University School of Artificial Intelligence, Nanjing University

Online Convex Optimization Dynamic Regret Minimization Portfolio Optimization

Sep 28, 2026cs.LG

On the Relation Between Interval Regret and Dynamic Regret

Non-stationary online learning has attracted much attention in recent years, as static regret is insufficient to guide algorithm design in changing environments. To address this limitation, interval regret and dynamic regret have been introduced as two representative performance metrics that strengthen static regret in complementary directions. Interval regret requires an online algorithm to achieve competitive static regret over every local time interval, whereas dynamic regret evaluates performance against an arbitrary sequence of time-varying comparators. Despite their importance, the relation between these metrics has long remained unclear. Prior work has often regarded interval regret as the stronger notion, based on the intuition that local guarantees should naturally induce global guarantees. Consequently, it is widely conjectured that an algorithm with optimal interval regret should automatically attain optimal dynamic regret. In this paper, we first establish a negative result that refutes this intuition of a metric-level implication. Specifically, for both convex and curved functions (including exp-concave and strongly convex functions), we show that there exist instances in which an algorithm with optimal interval regret nevertheless fails to achieve optimal dynamic regret. We then show how to leverage local adaptivity to obtain optimal dynamic regret. In particular, optimal dynamic regret can be attained by invoking an interval regret minimization process over an enlarged Euclidean ball containing the original convex feasible domain and using a suitable domain-converted surrogate loss. This reduction applies to both convex and curved functions. As a byproduct, we obtain the first proper and efficient algorithm with optimal dynamic regret for exp-concave functions, improving prior results while significantly simplifying the analysis.

Yi-Han Wang, Peng Zhao, Zhi-Hua Zhou

State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Online Convex Optimization Dynamic Regret Minimization

Sep 27, 2026cs.LG

ASTRA: ADMM-Accelerated Topology Reconfiguration for Dynamic Satellite Constellations

Dynamic topology reconfiguration is central to the reliability and efficiency of large satellite constellations, yet many existing approaches rely on idealized assumptions such as full constellation deployment or uniform orbital spacing. We present Adaptive Satellite Topology via Regret-Aware learning (ASTRA), a theoretically-grounded framework for dynamic satellite topology reconfiguration that builds on an online learning formulation and makes it computationally practical. ASTRA combines an ADMM-based offline solver with efficient online updates for both online gradient descent and online conditional gradient, yielding markedly cheaper constrained updates than generic optimization pipelines. On the theory side, we show that for a relevant class of entry-wise nonzero utility matrices, the objective is strongly convex, which yields logarithmic static regret for online gradient descent, and we further instantiate known dynamic-regret guarantees under inexact ADMM inner loops. Empirically, ASTRA matches or improves topology quality, presenting a good trade-off with computational time on synthetic constellations, and it remains effective on real Starlink data under partial deployment and non-uniform spacing, where idealized structural assumptions break down. These results position ASTRA as an efficient and theoretically grounded approach to topology reconfiguration in realistic Low Earth Orbit networks.

João Norberto, Ricardo Ferreira, Cláudia Soares

Department of Computer Science NOVA School of Science and Technology Caparica, Portugal

Dynamic Regret Minimization Wireless Communications LEO Satellite Networks

Sep 17, 2026cs.LG

From Switching to Dynamic Regret: A Simple Reduction via Unbiased Random Sequences

In non-stationary online learning, dynamic regret has attracted increasing attention as a measure of how well an online learner performs against a time-varying comparator sequence. Despite considerable advances, attaining optimal bounds for strongly convex and exp-concave losses often involves intricate analysis. In this paper, we present a \textit{simple} framework that reduces dynamic regret minimization to switching regret minimization. As a result, we can derive dynamic regret bounds by using off-the-shelf algorithms with switching regret guarantees. The key idea of our reduction is to construct, for \textit{any} comparator sequence, an auxiliary random sequence that is unbiased at each round, with the controlled variance and a manageable number of switches. Combining this construction with suitable surrogate losses, we can decompose dynamic regret into the expected switching regret against the random sequence and its controlled variance. Theoretically, for strongly convex and exp-concave losses, we establish the

\widetilde{O}(T^{1/3}P_T^{2/3})

dynamic regret bounds, where

T

denotes the time horizon and

P_T

denotes the path-length of the comparator sequence. Moreover, for general convex losses, the same reduction also recovers the

O(\sqrt{T(1+P_T)})

dynamic regret bound. Notably, all our findings match the minimax optimal results for these three types of losses, highlighting the versatility of our proposed framework.

Yibo Wang, Wenhao Yang, Sifan Yang +3

State Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University · School of Software Technology, Zhejiang University

Online Convex Optimization Dynamic Regret Minimization Regret Minimization

Sep 15, 2026cs.LG

Adapting to Decision-Relevant Non-Stationarity in Decentralized Heterogeneous Bandits

Decentralized bandit systems often contain heterogeneous agents: rewards can change at individual agents even when the best action for the network stays the same. These local changes may cancel when rewards are averaged across agents, so the number of local changes

\Stloc

can be much larger than the number of changes in the best common arm

\Stdec

. We introduce Decision-Relevant Fresh Comparison (DRFC), which uses new, balanced samples from all agents to compare arms at the network level and switches only when fresh global evidence indicates that the common best arm has changed. We prove a high-probability dynamic regret bound with no adaptation term depending on

\Stloc

, and show that every algorithm must still pay for identifying genuine decision switches and propagating them through the communication graph. Under a distinct time-average benchmark, an anytime-valid sliding-window extension handles gradual drift; experiments on synthetic, semi-real, and MovieLens-1M replays show that DRFC ignores decision-irrelevant local changes while the extension avoids false switches.

Zhaojun Peng

Multi-Armed Bandits Dynamic Regret Minimization Non-Stationary Bandits

Aug 10, 2026cs.LG

Online Learning of Scale Parameters in Score-Driven Filters

A score-driven filter multiplies its scaled log-likelihood score by a scale parameter. We call this coefficient the gain and learn it online. Given the current state and realised scaled score, each admissible gain selects a reachable next state and predictive density. A scalar gain moves along a line; diagonal gains control coordinatewise transmission and may change direction. We evaluate gain selection using a one-step predictive Kullback-Leibler objective. In the scalar unscaled case, the negative consecutive-score product is a stochastic gradient; the positive product used in accelerated recursions is a descent direction. Positive scalar score scaling changes only the effective learning rate. Strictly increasing, continuously differentiable gain links with positive derivative induce mirror-descent geometry, while persistence adds a Bregman pull towards a reference gain. Under convexity, compactness, integrability, and schedule conditions, projected and discounted mirror updates satisfy dynamic-regret bounds relative to time-varying, current-information comparators. Simulations isolate score scaling, link geometry, persistence, and coordinatewise gains. Across twelve equity indices, the bounded discounted-logistic gain records a lower out-of-sample mean negative log score than the constant gain in eleven markets, although market-level evidence is mixed. It also avoids the extreme transients of the numerically capped exponential-link benchmark.

Fabrizio Lillo, Giulia Livieri, Gianluca Palmari

Scuola Normale Superiore, Piazza dei Cavalieri 7, Pisa, Italy · Department of Statistics, London School of Economics and Political Science, Columbia House, 69 Aldwych, London, United Kingdom

Dynamic Regret Minimization Online Mirror Descent

Jul 29, 2026cs.LG

Parameter-Free Dynamic Regret under Heavy-Tailed Noise

We study online convex optimization with one unbiased stochastic subgradient per round and noise having a finite

p

-th central moment, where

p\in(1,2]

is unknown. For a bounded convex domain of diameter

D

, subgradients bounded by

G

, noise scale

σ

, and comparator path length

P_T

, let

Λ_T=1+P_T/D

. A single algorithm, using none of

G,σ,p,P_T

, attains expected dynamic regret

O_p\left(\min\{GD\sqrt{TΛ_T}+σDT^{1/p}Λ_T^{(p-1)/p},\,GDT\}\right)

against every fixed comparator sequence. Restarted AdaGrad experts produce the noise-path exponent

(p-1)/p

, and a prior favoring longer restart intervals removes horizon-dependent logarithmic overhead. We give an explicit bound uniform in

p

; its logarithm-free form has noise coefficient

O(1+\log(p/(p-1)))

, while the static-regret constant is universal. The analysis requires only marginal noise moments and permits dependent errors. Complete pathwise proofs retain both the expert-loss range and the gradient energies preceding comparator movement. Matching lower bounds hold on every bounded convex domain of positive diameter, under the same gradient-only information model. Together with a path-budget-tuned upper bound, they characterize the minimax rate with universal constants, including its linear-regret saturation.

Vaneet Aggarwal

Purdue University

Online Convex Optimization Dynamic Regret Minimization Minimax Regret Heavy-Tailed Noise Adaptive Gradient Methods Heavy-Tailed Stochastic Optimization

Jul 3, 2026cs.LG

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal

\widetilde O(T^{2/3}P_T^{1/3})

dependence, where

P_T

is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal

T^{2/3}P_T^{1/3}

dynamic-regret dependence for both linear bandits with general compact decision sets and

K

-armed contextual linear bandits.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

Department of Mathematics, The Hong Kong University of Science and Technology

Dynamic Regret Minimization Non-Stationary Bandits Contextual Bandits Linear Contextual Bandits

Jun 27, 2026cs.LG

Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs

In a changing decision problem, standard dynamic-regret analyses have often equated the cost of non-stationarity to how far loss moves. However, it is simultaneously possible for a loss sequence to travel far and retain the same optimal policy, or for a small movement in loss to force the optimal policy to change completely. Thus, the size of the movement through loss variation, transition variation, or comparator path length describe the adversary's motion, but not the cost of that motion to the control problem. For a more faithful analytic interpretation, this paper develops a normal-fan geometry for finite-horizon adversarial MDPs with fixed transitions. Occupancy measures form a polytope, and each loss vector exposes an optimal face of that polytope. Non-stationarity in rewards is therefore a path through the normal fan, where motion inside one cone leaves the optimal face unchanged, while crossing a wall may carry regret. We pose the notion of a face-crossing price, which is the minimum regret incurred by remaining on the previous optimal face under the new loss. For any learner that tracks the previous face, dynamic regret decomposes exactly into intrinsic priced face motion plus within-face selection error. The resulting theory separates consequential from harmless non-stationarity, where loss variation can be arbitrarily large at zero price, and identical one-coordinate variation can hide horizon-scale differences in regret.

Kai Hidajat

Komori Research

Non-Stationary RL Markov Decision Processes Dynamic Regret Minimization

Jun 8, 2026stat.ML

Multi-Armed Bandits with Arriving Arms: Sequential Screening, Dynamic Regret, and Sublinear Guarantees

We study a stochastic multi-armed bandit problem in which the set of available arms expands over time. This setting arises in sequential experimentation when new actions or treatments become available during an ongoing study, making regret against a single best arm in hindsight inappropriate. We instead evaluate performance relative to the best arm currently available, leading to a dynamic-regret criterion for arriving-arm environments. To address the resulting challenges of arrival information discrepancy (AID) and a drifting benchmark (DB), we propose UCB for Arriving Arms (UCB-AA), an elimination-based procedure with an aiding preliminary screening step for newly arrived arms before full competition with incumbent arms. We show that UCB-AA attains regret bounds that depend explicitly on the arrival process, achieves sublinear dynamic regret under regularity conditions on gap evolution, and admits an online extension for unknown horizons. Simulation results show that UCB-AA reduces wasted pulls and maintains a smaller active arm set while preserving competitive regret performance.

Deqi Zheng, Xiaoyang Xu, Yuhong Yang

Qiuzhen College, Tsinghua University · Yau Mathematical Sciences Center, Tsinghua University

Multi-Armed Bandits Dynamic Regret Minimization Sequential Decision Making UCB Algorithms

May 25, 2026stat.ML

Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent

We study nonstationary generalized linear bandits (GLBs), where the expected reward is modeled through a nonlinear link function with an unknown time-varying parameter. This framework encompasses a broad class of reward models, including linear, Bernoulli, and binomial rewards. Existing approaches are predominantly based on maximum-likelihood estimation (MLE), using sliding-window, restart, or discounting mechanisms to handle nonstationarity. Although these methods achieve statistically efficient regret guarantees, they generally require revisiting past observations at every round, which leads to computation and memory costs that grow with time; moreover, several of them rely on a non-convex projection step. In this paper, we propose DOMD-GLB, a new algorithm for nonstationary GLBs that utilizes discounted online mirror descent (DOMD) for parameter estimation, thereby incurring only

O(1)

computation and memory costs per round. We prove dynamic regret bounds of order

\tilde{O} \big(c_μ^{-1/2} d^{3/4} P_T^{1/4} T^{3/4}\big)

in drifting environments and

\tilde{O}\big(c_μ^{-1/3} d^{2/3} Γ_T^{1/3} T^{2/3}\big)

in piecewise-stationary environments, where

d

denotes the feature dimension,

T

the time horizon,

P_T

the path length,

Γ_T

the number of change points, and

c_μ

a curvature parameter associated with the link function, while substantially improving computational efficiency over prior work. To the best of our knowledge, this is the first algorithm for nonstationary GLBs with per-round computation and memory costs independent of time.

Joongkyu Lee, Min-hwan Oh

Seoul National University

Multi-Armed Bandits Dynamic Regret Minimization Non-Stationary Bandits Online Mirror Descent Contextual Bandits Generalized Linear Models+1

May 21, 2026cs.LG

Bandit Convex Optimization with Gradient Prediction Adaptivity

Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions

m_t

, we seek regret bounds that scale with the cumulative prediction error

S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2.

We first establish a negative result: under the single-point feedback protocol, an unavoidable

Ω(\sqrt{T})

regret lower bound persists even when

S_T=o(T)

, showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose \emph{Two-Point Variance-Reduced Optimistic Gradient Descent} (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of

O\big(\sqrt{d\,\mathbb{E}[S_T]}\big),

where

d

is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as

Ω(\sqrt{\mathbb{E}[S_T]})

, providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of

\sqrt d

. We further develop adaptive variants that eliminate the need for prior knowledge of

\mathbb{E}[S_T]

or the horizon

T

, and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.

Shuche Wang, Adarsh Barik, Vincent Y. F. Tan

Department of Mathematics, National University of Singapore, Singapore · Department of Computer Science and Engineering, Indian Institute of Technology Delhi, India · Department of Electrical and Computer Engineering, National University of Singapore, Singapore

Online Convex Optimization Dynamic Regret Minimization Bandit Convex Optimization Variance Reduction

Apr 17, 2026cs.LG

DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees

We study model-free reinforcement learning (RL) in non-stationary finite-horizon episodic Markov decision processes (MDPs) without prior knowledge of the non-stationarity. We focus on the piecewise stationary (PS) setting, where both rewards and transition dynamics can change at unknown times. We first revisit existing state-of-the-art approaches and identify theoretical and practical limitations that change the current landscape of performance guarantees. To characterize the difficulty of the problem, we establish the first minimax lower bounds for PS-RL in tabular and linear MDPs. We then introduce Detection Augmented Reinforcement Learning (DARLING), a modular wrapper for PS-RL that applies to both tabular and linear MDPs, without knowledge of the changes. In tabular MDPs, under change-point separability and reachability conditions, DARLING improves the best known dynamic regret bounds and matches our minimax lower bound. In linear MDPs, DARLING matches the minimax lower bound when the relevant reachability parameters are known, and our analysis clarifies the structural obstacles that distinguish this setting from the tabular case. Finally, through extensive experimentation across diverse non-stationary benchmarks, we show that DARLING consistently surpasses the state-of-the-art methods.

Argyrios Gerogiannis, Yu-Han Huang, Venugopal V. Veeravalli

ECE and CSL, The Grainger College of Engineering University of Illinois at Urbana-Champaign

Non-Stationary RL Regret Minimization in RL Markov Decision Processes Dynamic Regret Minimization Linear Markov Decision Processes Model-Free RL

Feb 4, 2026cs.LG

Improved Dimension Dependence for Bandit Convex Optimization with Gradient Variations

Gradient-variation online learning has drawn increasing attention due to its deep connections to game theory and optimization. It has been studied extensively in the full-information setting, but is underexplored with bandit feedback. In this work, we focus on gradient variation in Bandit Convex Optimization (BCO) with two-point feedback. By proposing a refined analysis of the non-consecutive gradient variation, a fundamental quantity in gradient variation with bandit feedback, we improve the dimension dependence for both convex and strongly convex functions compared with the best known results (Chiang et al., 2013). Our improved analysis of the non-consecutive gradient variation also implies other favorable problem-dependent guarantees, such as gradient-variance and small-loss regret bounds. Beyond the two-point setup, we demonstrate the versatility of our technique by achieving the first gradient-variation bound for one-point bandit linear optimization over hyper-rectangular domains. Finally, we validate the effectiveness of our results in more challenging tasks such as dynamic and universal regret minimization, establishing the first gradient-variation dynamic and universal regret bounds for two-point BCO.

Hang Yu, Yu-Hu Yan, Peng Zhao

State Key Laboratory for Novel Software Technology, Nanjing University, China · School of Artificial Intelligence, Nanjing University, China

Online Convex Optimization Dynamic Regret Minimization Bandit Convex Optimization