Temporal Variability in Implicit Online Learning

• URL: http://arxiv.org/abs/2006.07503v2
• Date: Fri, 6 Nov 2020 19:59:09 GMT
• Title: Temporal Variability in Implicit Online Learning
• Authors: Nicol\`o Campolongo, Francesco Orabona
• Abstract summary: tightest regret analyses only show marginal improvements over Online Mirror Descent. We prove a novel static regret bound that depends on the temporal variability of the sequence of loss functions. We present an adaptive algorithm that achieves this regret bound without prior knowledge of the temporal variability.
• Score: 15.974402990630402
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In the setting of online learning, Implicit algorithms turn out to be highly successful from a practical standpoint. However, the tightest regret analyses only show marginal improvements over Online Mirror Descent. In this work, we shed light on this behavior carrying out a careful regret analysis. We prove a novel static regret bound that depends on the temporal variability of the sequence of loss functions, a quantity which is often encountered when considering dynamic competitors. We show, for example, that the regret can be constant if the temporal variability is constant and the learning rate is tuned appropriately, without the need of smooth losses. Moreover, we present an adaptive algorithm that achieves this regret bound without prior knowledge of the temporal variability and prove a matching lower bound. Finally, we validate our theoretical findings on classification and regression datasets.

Related papers

• LEARN: An Invex Loss for Outlier Oblivious Robust Online Optimization [56.67706781191521]
  An adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown to the learner. We present a robust online rounds optimization framework, where an adversary can introduce outliers by corrupting loss functions in an arbitrary number of k, unknown.
  arXiv  Detail & Related papers  (2024-08-12T17:08:31Z)
• Normalization and effective learning rates in reinforcement learning [52.59508428613934]
  Normalization layers have recently experienced a renaissance in the deep reinforcement learning and continual learning literature. We show that normalization brings with it a subtle but important side effect: an equivalence between growth in the norm of the network parameters and decay in the effective learning rate. We propose to make the learning rate schedule explicit with a simple re- parameterization which we call Normalize-and-Project.
  arXiv  Detail & Related papers  (2024-07-01T20:58:01Z)
• Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
  We study unconstrained Online Linear Optimization with Lipschitz losses. Motivated by the pursuit of instance optimality, we propose a new algorithm. Central to these results is a continuous time approach to online learning.
  arXiv  Detail & Related papers  (2023-09-27T21:54:52Z)
• Learning Rate Schedules in the Presence of Distribution Shift [18.310336156637774]
  We design learning schedules that regret networks cumulatively learning in the presence of a changing data distribution. We provide experiments for high-dimensional regression models to increase regret models.
  arXiv  Detail & Related papers  (2023-03-27T23:29:02Z)
• Improved Online Conformal Prediction via Strongly Adaptive Online Learning [86.4346936885507]
  We develop new online conformal prediction methods that minimize the strongly adaptive regret. We prove that our methods achieve near-optimal strongly adaptive regret for all interval lengths simultaneously. Experiments show that our methods consistently obtain better coverage and smaller prediction sets than existing methods on real-world tasks.
  arXiv  Detail & Related papers  (2023-02-15T18:59:30Z)
• Dynamic Regret of Adaptive Gradient Methods for Strongly Convex Problems [0.0]
  We go through a variant of ADAGRAD (referred to as M-ADAGRAD) in a strong convex setting via the notion of dynamic regret. We demonstrate a regret bound in terms of the path-length of the minimizer sequence that essentially reflects the non-stationarity of environments.
  arXiv  Detail & Related papers  (2022-09-04T12:40:57Z)
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
  offline reinforcement learning seeks to utilize offline/historical data to optimize sequential decision-making strategies. We study the statistical limits of offline reinforcement learning with linear model representations.
  arXiv  Detail & Related papers  (2022-03-11T09:00:12Z)
• Online Control of Unknown Time-Varying Dynamical Systems [48.75672260851758]
  We study online control of time-varying linear systems with unknown dynamics in the nonstochastic control model. We study regret bounds with respect to common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies.
  arXiv  Detail & Related papers  (2022-02-16T06:57:14Z)
• Robust learning with anytime-guaranteed feedback [6.903929927172917]
  gradient-based learning algorithms are driven by queried feedback with almost no performance guarantees. Here we explore a modified "anytime online-to-batch" mechanism which admits high-probability error bounds. In practice, we show noteworthy gains on real-world data applications.
  arXiv  Detail & Related papers  (2021-05-24T07:31:52Z)
• Reducing Representation Drift in Online Continual Learning [87.71558506591937]
  We study the online continual learning paradigm, where agents must learn from a changing distribution with constrained memory and compute. In this work we instead focus on the change in representations of previously observed data due to the introduction of previously unobserved class samples in the incoming data stream.
  arXiv  Detail & Related papers  (2021-04-11T15:19:30Z)
• A closer look at temporal variability in dynamic online learning [19.468067110814808]
  This work focuses on the setting of dynamic regret in the context of online learning with full information. By assuming that the sequence of loss functions does not vary much with time, we show that it is possible to incur improved regret bounds compared to existing results.
  arXiv  Detail & Related papers  (2021-02-15T16:50:16Z)

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.