New online conformal prediction methods minimize strongly adaptive regret and achieve near-optimal coverage.
problem Uncertainty quantification in online settings with changing data distributions.
method Developed new online conformal prediction methods that minimize strongly adaptive regret.
result Achieve near-optimal strongly adaptive regret and approximately valid coverage.
New meta algorithm improves adaptability in changing environments.
problem Adapting to changing environments in online learning.
method Derives a new parameter-free algorithm for the LEA problem, inspired by coin betting.
result Strongly-adaptive regret bound is log ( T ) \sqrt{\log(T)} log ( T ) better than other algorithms. SA algorithms control dynamic regret in non-stationary settings with strong convexity or exp-concavity.
problem Non-stationary Online Convex Optimization with dynamic regret control.
method Strongly Adaptive (SA) algorithms view dynamic regret as path variation of the comparator sequence.
result SA algorithms achieve i l d e O ( T V T ∨ log T ) ilde O(\sqrt{TV_T} \vee \log T) i l d e O ( T V T ∨ log T ) and i l d e O ( d T V T ∨ d log T ) ilde O(\sqrt{dTV_T} \vee d\log T) i l d e O ( d T V T ∨ d log T ) dynamic regret for strongly convex and exp-concave losses, respectively. This paper describes a new parameter-free online learning algorithm for changing environments. In comparing against algorithms with the same time complexity as ours, we obtain a strongly adaptive regret bound that is a factor of at least log ( T ) \sqrt{\log(T)} log ( T ) better, where T T T is the time horizon. Empirical results show tha…
Optimal online linear regression in dynamic environments using discounted Vovk-Azoury-Warmuth forecaster.
problem Achieving optimal performance in dynamic online linear regression without prior knowledge.
method Developed a discounted variant of the Vovk-Azoury-Warmuth forecaster to achieve optimal dynamic regret guarantees.
result Achieved dynamic regret of the form $O\left(d\log(T)\vee \sqrt{dP_{T}^γ(\vec{u})T}
ight)$ , with a learnable discount factor.
New algorithms minimize dynamic regret for strongly convex losses.
problem Minimizing dynamic regret for strongly convex losses.
method Developed Strongly Adaptive algorithms exploiting KKT conditions.
result Achieved near optimal dynamic regret of O ( d 1 / 3 n 1 / 3 e x t T V [ u 1 : n ] 2 / 3 ∨ d ) O(d^{1/3} n^{1/3} ext{TV}[u_{1:n}]^{2/3} \vee d) O ( d 1/3 n 1/3 e x t T V [ u 1 : n ] 2/3 ∨ d ) . New algorithms minimize dynamic regret in non-stationary online learning.
problem Universal dynamic regret minimization under exp-concave and smooth losses.
method Strongly Adaptive algorithms with a path variational based on second order differences of the comparator sequence.
result Achieve a dynamic regret of i l d e O ( d 2 n 1 / 5 C n 2 / 5 ∨ d 2 ) ilde O(d^2 n^{1/5} C_n^{2/5} \vee d^2) i l d e O ( d 2 n 1/5 C n 2/5 ∨ d 2 ) , optimal modulo dependencies. New algorithm reduces dynamic regret for exp-concave losses.
problem Minimizing dynamic regret in online learning with exp-concave losses.
method Integrates KKT conditions to achieve optimal dynamic regret.
result Achieves dynamic regret of i l d e O ∗ ( n 1 / 3 C n 2 / 3 ∨ 1 ) ilde O^*(n^{1/3}C_n^{2/3} \vee 1) i l d e O ∗ ( n 1/3 C n 2/3 ∨ 1 ) . New proof confirms periodic orbit conjecture for Eulerisable flows.
problem Periodic orbit conjecture for non-vanishing vector fields on closed manifolds.
method Characterization of Eulerisable flows and use of strongly adapted one-forms.
result Periodic orbit conjecture holds for Eulerisable flows.
New approach optimizes policies in adversarial MDPs using adversarial learning.
problem Optimizing policies in adversarial Markov decision processes.
method Adversarial learning on advantage functions, extending previous reductions.
result Stronger regret criteria and performance guarantees for policy optimization.
Characterizes Anosov flows via contact geometry.
problem Understanding Anosov 3-flows through contact geometry.
method Investigates interactions with Reeb dynamics and proves a technical theorem.
result Space of adapted geometries homotopy equivalent to Anosov flows.
Modified dynamical systems retain Turing universality.
problem Embedding Turing machines into dynamical systems.
method Exploring flows with adapted 1-forms and homogeneity.
result Even slight modifications can lead to Turing universality.
Investigates connections adapted to a holomorphic Lie group action on bundles.
problem Finding connections adapted to a Lie group action on bundles.
method Analyzes connections on principal H H H -bundles over complex manifolds with holomorphic actions of Lie groups. result Identifies conditions for connections to be adapted to a given G G G -connection. New algorithm reduces TV-denoising to adaptive online learning.
problem Estimating TV-bounded functions from noisy samples.
method Deep connection to Strongly Adaptive online learning; O ( n log n ) O(n \log n) O ( n log n ) time algorithm. result Near minimax optimal rate of O ( n 1 / 3 C n 2 / 3 ) O(n^{1/3}C_n^{2/3}) O ( n 1/3 C n 2/3 ) under squared error loss. Legendrian arcs connect veering triangulations to Anosov flows.
problem Connecting veering triangulations to Anosov flows for study.
method Realizing edges as Legendrian arcs with a bicontact structure.
result Veering triangulations can be placed in steady position.
Recent work in distance metric learning has focused on learning transformations of data that best align with specified pairwise similarity and dissimilarity constraints, often supplied by a human observer. The learned transformations lead to improved retrieval, classification, and clustering algorithms due to the bette…
Paper proposes algorithms to minimize both dynamic and adaptive regret simultaneously.
problem Traditional regret minimization algorithms are suboptimal for changing environments.
method Developed novel online algorithms to minimize dynamic and adaptive regret simultaneously.
result Proposed algorithms minimize dynamic and adaptive regret over any interval.
New measure of policy regret shows compatibility with traditional external regret in adversarial games.
problem Incompatibility between traditional and new policy regret measures in adaptive adversaries.
method Revisited policy regret and compared it with external regret; introduced policy equilibrium.
result Policy regret and external regret are compatible in adversarial games.
The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.
This paper analyzes regret bounds for Gaussian process Thompson sampling.
problem Analyzing the performance of Gaussian process Thompson sampling (GP-TS) in Bayesian optimization.
method The paper derives several regret bounds for GP-TS, including a lower bound, upper bounds on the second moment of cumulative regret, expected lenient regret, and improved cumulative regret.
result The paper provides improved regret upper bounds for GP-TS, showing that it suffers from a polynomial dependence on 1 / δ 1/δ 1/ δ with probability δ δ δ . Efficiently minimizes regret in non-convex games with gradient-based methods.
problem Computational intractability of standard regret minimization in non-convex games.
method Defining a new notion of regret and using gradient-based optimization methods.
result Achieves optimal regret, leading to convergence to equilibrium.
New definition of regret for nonconvex online learning models.
problem Intractability of standard regret measures for nonconvex models.
method Introduced a local gradient based regret definition.
result Our definition provides more interpretable bounds for forecasting.
Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to a…
Balances the regret of different algorithms in bandit and RL problems.
problem Model selection in bandit and reinforcement learning.
method Estimates and balances the empirical regrets of algorithms.
result Achieves near-optimal regret compared to the optimal base algorithm.
Paper studies how to combine regret minimizers for solving complex games.
problem Solving large-scale extensive-form games with constraints.
method Derives a calculus for constructing regret minimizers for composite convex sets.
result Local regret minimizers for simpler sets can be combined into an aggregate for composite sets.
Study Thompson Sampling in adversarial bit prediction, finding regret bounds and optimal sequences.
problem Adversarial bit prediction with varying error weights.
method Thompson Sampling, analyzing sequences with largest and smallest regret.
result Regret bounds for adversarial bit prediction sequences, including optimal and worst-case scenarios.
Data-driven model selection reduces regret in sequential decisions.
problem Optimizing model selection in stochastic environments with bandit feedback.
method Data-driven regret balancing for model selection.
result Meta-learner selects the best base learner based on actual realized regret.
Optimistic Hedge achieves optimal regret bounds in two-player zero-sum games.
problem Achieving optimal regret bounds for optimistic Hedge in two-player zero-sum games.
method Refined regret analysis and optimization problem formulation.
result Optimistic Hedge achieves O ( log m log n ) O(\sqrt{\log m \log n}) O ( log m log n ) regret bounds, matching upper and lower bounds. New algorithm reduces regret in contextual bandits.
problem Minimizing regret in contextual bandits with side information.
method Contextual-Gap algorithm for simple regret minimization.
result Established performance guarantees on simple regret.
Optimal switching regret for all segmentations in online convex optimisation.
problem Non-stationary online convex optimisation problems.
method Developed an efficient algorithm to achieve optimal switching regret on every possible segmentation.
result Achieved asymptotically optimal switching regret on every possible segmentation simultaneously.
New approach for distributed online optimization of non-convex losses with sublinear regret.
problem Regret evaluation and consensus in distributed, multi-agent systems with non-convex losses.
method Composite regret metric and consensus-based online normalized gradient (CONGD) approach for pseudo-convex losses; offline optimization oracle for general non-convex losses.
result First sublinear regret bound for general distributed online non-convex learning.
New algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
The paper tackles efficient online learning by achieving minimal regret with respect to the best expert.
problem Achieving minimal regret in online learning problems where the goal is to match the lowest regret of K experts.
method A lazy form of the online subgradient algorithm is used to achieve minimal regret in 'easy' regimes.
result Minimal regret strategies exist for some 'hard' regimes, and the algorithm retains an O ( n ) O(\sqrt{n}) O ( n ) worst-case regret guarantee. Proximal online gradient minimizes dynamic regret in evolving environments.
problem Optimizing dynamic regret in online learning where the optimal solution changes over time.
method Proximal online gradient method, showing it is optimal for dynamic regret.
result Proximal online gradient matches the lower bound for dynamic regret, proving its optimality.
This paper considers the stability of online learning algorithms and its implications for learnability (bounded regret). We introduce a novel quantity called {\em forward regret} that intuitively measures how good an online learning algorithm is if it is allowed a one-step look-ahead into the future. We show that given…
Paper introduces a new G ⋆ G^\star G ⋆ regret measure for online convex optimization with smooth losses.
problem Online convex optimization with smooth losses.
method Introduces a new G ⋆ G^\star G ⋆ regret measure that depends on the cumulative squared gradient norm. result The G ⋆ G^\star G ⋆ regret can be arbitrarily sharper than existing measures when losses have vanishing curvature. Optimistic algorithms achieve logarithmic regret bounds for MDPs without diameter dependence.
problem Achieving logarithmic regret bounds for episodic MDPs without relying on diameter-like quantities.
method Novel 'clipped' regret decomposition applied to optimistic algorithms.
result Smooth interpolation between gap-dependent and minimax rates of convergence.
Paper improves adaptive regret for convex and smooth functions.
problem Online convex optimization in changing environments.
method Develops adaptive algorithms exploiting both convexity and smoothness.
result Regret bounds are comparable to worst-case results but tighter when comparators have small losses.
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
New minimax theorem connects Bayesian and minimax regret in partial monitoring.
problem Minimax regret in partial monitoring with no assumptions on adversary.
method Information-theoretic tools and minimax theorem.
result Clean analysis of easy and hard finite partial monitoring with new bounds.
Paper improves worst-case regret bounds for RLSVI in reinforcement learning.
problem Minimizing regret in reinforcement learning with randomized value functions.
method Introduces a clipping variant of Thompson Sampling for RLSVI.
result Achieves a i l d e O ( H 2 S A T ) ilde{\mathrm{O}}(H^2S\sqrt{AT}) i l d e O ( H 2 S A T ) worst-case regret bound. Paper solves no-swap regret minimization for combinatorial bandits with polylogarithmic dependence on N.
problem Design efficient no-swap regret algorithms for combinatorial bandits with exponentially large action space.
method Introduces a no-swap-regret learning algorithm with polylogarithmic dependence on N and demonstrates efficient implementation.
result Achieves no-swap regret with polylogarithmic dependence on N, resolving an open problem.
New algorithms reduce dynamic regret in non-stationary RL environments.
problem Optimizing policies in environments that change over time.
method POWER and POWER++ algorithms for policy optimization with dynamic regret analysis.
result POWER++ improves dynamic regret by actively adapting to non-stationarity.
New algorithms minimize simple and cumulative regret in contextual bandits.
problem Minimizing simple and cumulative regret in contextual bandit settings.
method Proposed new algorithms using conformal arm sets (CASs).
result Near-optimal minimax guarantees for simple regret and state-of-the-art guarantees for cumulative regret.
New framework reduces minimax regret for high-dimensional data.
problem Minimizing regret in high-dimensional data with logarithmic loss.
method Developed envelope complexity framework and spike-and-tails prior.
result Achieves minimax regret within a factor of two over high-dimensional ℓ 1 \ell_1 ℓ 1 -balls. Paper explores rate-preserving reductions between Blackwell approachability and no-regret learning.
problem Tackles rate-preserving reductions between Blackwell approachability and no-regret learning.
method Studies fine-grained reductions and optimal rates of convergence.
result Shows that rate-preserving reductions do not always hold, but provides conditions for when they do.
Algorithm minimizes regret and converges to equilibria in Markov games.
problem Regret minimization and convergence to equilibria in general-sum Markov games under adversarial opponents.
method Decentralized algorithm that uses policy optimization and controls path length to achieve sublinear regret.
result Sublinear regret guarantees for convergence to correlated equilibrium in Markov games.
New algorithm achieves both static and dynamic regret optimally against an oblivious adversary for deterministic losses.
problem Achieving optimal static and dynamic regret simultaneously in adversarial bandits.
method Extends impossibility result to deterministic losses, uses negative static regret and Blackwell approachability.
result First algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary.