Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability

• URL: http://arxiv.org/abs/2506.10616v1
• Date: Thu, 12 Jun 2025 12:00:08 GMT
• Title: Non-stationary Online Learning for Curved Losses: Improved Dynamic Regret via Mixability
• Authors: Yu-Jie Zhang, Peng Zhao, Masashi Sugiyama,
• Abstract summary: We show that dynamic regret can be substantially improved by leveraging the concept of mixability.<n>We demonstrate that an exponential-weight method with fixed-share updates achieves an $mathcalO(d T2/3 P_T2/3 log T)$ dynamic regret for mixable losses.
• Score: 65.99855403424979
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Non-stationary online learning has drawn much attention in recent years. Despite considerable progress, dynamic regret minimization has primarily focused on convex functions, leaving the functions with stronger curvature (e.g., squared or logistic loss) underexplored. In this work, we address this gap by showing that the regret can be substantially improved by leveraging the concept of mixability, a property that generalizes exp-concavity to effectively capture loss curvature. Let $d$ denote the dimensionality and $P_T$ the path length of comparators that reflects the environmental non-stationarity. We demonstrate that an exponential-weight method with fixed-share updates achieves an $\mathcal{O}(d T^{1/3} P_T^{2/3} \log T)$ dynamic regret for mixable losses, improving upon the best-known $\mathcal{O}(d^{10/3} T^{1/3} P_T^{2/3} \log T)$ result (Baby and Wang, 2021) in $d$. More importantly, this improvement arises from a simple yet powerful analytical framework that exploits the mixability, which avoids the Karush-Kuhn-Tucker-based analysis required by existing work.

Related papers

• Any-stepsize Gradient Descent for Separable Data under Fenchel--Young Losses [17.835960292396255]
  We show arbitrary-stepsize gradient convergence for a general loss function based on the framework of emphFenchel--Young losses.<n>We argue that these better rate is possible because of emphseparation margin of loss functions, instead of the self-bounding property.
  arXiv  Detail & Related papers  (2025-02-07T12:52:12Z)
• On the Dynamics Under the Unhinged Loss and Beyond [104.49565602940699]
  We introduce the unhinged loss, a concise loss function, that offers more mathematical opportunities to analyze closed-form dynamics. The unhinged loss allows for considering more practical techniques, such as time-vary learning rates and feature normalization.
  arXiv  Detail & Related papers  (2023-12-13T02:11:07Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  We propose an online convex optimization approach with two different levels of adaptivity. We obtain $mathcalO(log V_T)$, $mathcalO(d log V_T)$ and $hatmathcalO(sqrtV_T)$ regret bounds for strongly convex, exp-concave and convex loss functions.
  arXiv  Detail & Related papers  (2023-07-17T09:55:35Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond [23.91519151164528]
  We show that in a proper learning setup, Strongly Adaptive algorithms can achieve the near optimal dynamic regret. We also derive near optimal dynamic regret rates for the special case of proper online learning with exp-concave losses.
  arXiv  Detail & Related papers  (2022-01-21T22:08:07Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  We show that Strongly Adaptive (SA) algorithms can be viewed as a principled way of controlling dynamic regret. We derive a new lower bound on a certain penalized regret which establishes the near minimax optimality of online Kernel Ridge Regression (KRR)
  arXiv  Detail & Related papers  (2021-11-22T21:52:47Z)
• Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
  We consider the problem of the Zinkevich (2003)-style dynamic regret minimization in online learning with exp-contrivial losses. We show that whenever improper learning is allowed, a Strongly Adaptive online learner achieves the dynamic regret of $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ where $C_n$ is the total variation (a.k.a. path length) of the an arbitrary sequence of comparators that may not be known to the learner ahead of time.
  arXiv  Detail & Related papers  (2021-04-23T21:36:51Z)
• Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
  We investigate online convex optimization in non-stationary environments. We choose the dynamic regret as the performance measure. We show that it is possible to further enhance the dynamic regret by exploiting the smoothness condition.
  arXiv  Detail & Related papers  (2020-07-07T14:10:57Z)
• The Heavy-Tail Phenomenon in SGD [7.366405857677226]
  We show that depending on the structure of the Hessian of the loss at the minimum, the SGD iterates will converge to a emphheavy-tailed stationary distribution. We translate our results into insights about the behavior of SGD in deep learning.
  arXiv  Detail & Related papers  (2020-06-08T16:43:56Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  We consider online learning for episodically constrained Markov decision processes (CMDPs) We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model. Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
  arXiv  Detail & Related papers  (2020-03-02T05:02:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.