Discounted Adaptive Online Learning: Towards Better Regularization

• URL: http://arxiv.org/abs/2402.02720v2
• Date: Tue, 18 Jun 2024 18:47:21 GMT
• Title: Discounted Adaptive Online Learning: Towards Better Regularization
• Authors: Zhiyu Zhang, David Bombara, Heng Yang,
• Abstract summary: We study online learning in adversarial nonstationary environments. We propose an adaptive (i.e., instance optimal) algorithm that improves the widespread non-adaptive baseline. We also consider the (Gibbs and Candes, 2021)-style online conformal prediction problem.
• Score: 5.5899168074961265
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning in adversarial nonstationary environments. Since the future can be very different from the past, a critical challenge is to gracefully forget the history while new data comes in. To formalize this intuition, we revisit the discounted regret in online convex optimization, and propose an adaptive (i.e., instance optimal), FTRL-based algorithm that improves the widespread non-adaptive baseline -- gradient descent with a constant learning rate. From a practical perspective, this refines the classical idea of regularization in lifelong learning: we show that designing good regularizers can be guided by the principled theory of adaptive online optimization. Complementing this result, we also consider the (Gibbs and Cand\`es, 2021)-style online conformal prediction problem, where the goal is to sequentially predict the uncertainty sets of a black-box machine learning model. We show that the FTRL nature of our algorithm can simplify the conventional gradient-descent-based analysis, leading to instance-dependent performance guarantees.

Related papers

• Online-BLS: An Accurate and Efficient Online Broad Learning System for Data Stream Classification [52.251569042852815]
  We introduce an online broad learning system framework with closed-form solutions for each online update. We design an effective weight estimation algorithm and an efficient online updating strategy. Our framework is naturally extended to data stream scenarios with concept drift and exceeds state-of-the-art baselines.
  arXiv  Detail & Related papers  (2025-01-28T13:21:59Z)
• Adaptive Conformal Inference by Betting [51.272991377903274]
  We consider the problem of adaptive conformal inference without any assumptions about the data generating process. Existing approaches for adaptive conformal inference are based on optimizing the pinball loss using variants of online gradient descent. We propose a different approach for adaptive conformal inference that leverages parameter-free online convex optimization techniques.
  arXiv  Detail & Related papers  (2024-12-26T18:42:08Z)
• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  gradient-variation online learning aims to achieve regret guarantees that scale with variations in gradients of online functions. Recent efforts in neural network optimization suggest a generalized smoothness condition, allowing smoothness to correlate with gradient norms. We provide the applications for fast-rate convergence in games and extended adversarial optimization.
  arXiv  Detail & Related papers  (2024-08-17T02:22:08Z)
• 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)
• Adaptive Fairness-Aware Online Meta-Learning for Changing Environments [29.073555722548956]
  The fairness-aware online learning framework has arisen as a powerful tool for the continual lifelong learning setting. Existing methods make heavy use of the i.i.d assumption for data and hence provide static regret analysis for the framework. We propose a novel adaptive fairness-aware online meta-learning algorithm, namely FairSAOML, which is able to adapt to changing environments in both bias control and model precision.
  arXiv  Detail & Related papers  (2022-05-20T15:29:38Z)
• 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)
• Last Layer Marginal Likelihood for Invariance Learning [12.00078928875924]
  We introduce a new lower bound to the marginal likelihood, which allows us to perform inference for a larger class of likelihood functions. We work towards bringing this approach to neural networks by using an architecture with a Gaussian process in the last layer.
  arXiv  Detail & Related papers  (2021-06-14T15:40:51Z)
• COMBO: Conservative Offline Model-Based Policy Optimization [120.55713363569845]
  Uncertainty estimation with complex models, such as deep neural networks, can be difficult and unreliable. We develop a new model-based offline RL algorithm, COMBO, that regularizes the value function on out-of-support state-actions. We find that COMBO consistently performs as well or better as compared to prior offline model-free and model-based methods.
  arXiv  Detail & Related papers  (2021-02-16T18:50:32Z)
• LQF: Linear Quadratic Fine-Tuning [114.3840147070712]
  We present the first method for linearizing a pre-trained model that achieves comparable performance to non-linear fine-tuning. LQF consists of simple modifications to the architecture, loss function and optimization typically used for classification.
  arXiv  Detail & Related papers  (2020-12-21T06:40:20Z)

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.