Online Classification with Predictions

• URL: http://arxiv.org/abs/2405.14066v1
• Date: Wed, 22 May 2024 23:45:33 GMT
• Title: Online Classification with Predictions
• Authors: Vinod Raman, Ambuj Tewari,
• Abstract summary: We study online classification when the learner has access to predictions about future examples. We show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning.
• Score: 20.291598040396302
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study online classification when the learner has access to predictions about future examples. We design an online learner whose expected regret is never worse than the worst-case regret, gracefully improves with the quality of the predictions, and can be significantly better than the worst-case regret when the predictions of future examples are accurate. As a corollary, we show that if the learner is always guaranteed to observe data where future examples are easily predictable, then online learning can be as easy as transductive online learning. Our results complement recent work in online algorithms with predictions and smoothed online classification, which go beyond a worse-case analysis by using machine-learned predictions and distributional assumptions respectively.

Related papers

• Building Defect Prediction Models by Online Learning Considering Defect Overlooking [1.5869998695491834]
  Building defect prediction models based on online learning can enhance prediction accuracy. A module predicted as "non-defective" can result in fewer test cases for such modules. erroneous test results are used as learning data by online learning, which could negatively affect prediction accuracy.
  arXiv  Detail & Related papers  (2024-04-17T03:20:46Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. Prior research in this context was focused on a paradigm where the predictor is pre-trained on past data and then used as a black box. In this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge.
  arXiv  Detail & Related papers  (2024-03-12T08:40:21Z)
• EANet: Expert Attention Network for Online Trajectory Prediction [5.600280639034753]
  Expert Attention Network is a complete online learning framework for trajectory prediction. We introduce expert attention, which adjusts the weights of different depths of network layers, avoiding the model updated slowly due to gradient problem. Furthermore, we propose a short-term motion trend kernel function which is sensitive to scenario change, allowing the model to respond quickly.
  arXiv  Detail & Related papers  (2023-09-11T07:09:40Z)
• Software Defect Prediction by Online Learning Considering Defect Overlooking [1.655352281097533]
  Building defect prediction models based on online learning can enhance prediction accuracy. It continuously rebuilds a new prediction model when adding a new data point. However, predicting a module as "non-defective" (i.e., negative prediction) can result in fewer test cases for such modules.
  arXiv  Detail & Related papers  (2023-08-25T15:02:22Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  We propose a new ticketed model for learning--unlearning. We provide space-efficient ticketed learning--unlearning schemes for a broad family of concept classes.
  arXiv  Detail & Related papers  (2023-06-27T18:54:40Z)
• Learning Sample Difficulty from Pre-trained Models for Reliable Prediction [55.77136037458667]
  We propose to utilize large-scale pre-trained models to guide downstream model training with sample difficulty-aware entropy regularization. We simultaneously improve accuracy and uncertainty calibration across challenging benchmarks.
  arXiv  Detail & Related papers  (2023-04-20T07:29:23Z)
• ASPEST: Bridging the Gap Between Active Learning and Selective Prediction [56.001808843574395]
  Selective prediction aims to learn a reliable model that abstains from making predictions when uncertain. Active learning aims to lower the overall labeling effort, and hence human dependence, by querying the most informative examples. In this work, we introduce a new learning paradigm, active selective prediction, which aims to query more informative samples from the shifted target domain.
  arXiv  Detail & Related papers  (2023-04-07T23:51:07Z)
• 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)
• Online TSP with Predictions [3.8411077568039866]
  We study the classical online traveling salesman problem (OLTSP) Unlike the prediction models in other previous studies, each actual request in the OLTSP, associated with its arrival time and position, may not coincide with the predicted ones. Our main result is to study different prediction models and design algorithms to improve the best-known results in the different settings.
  arXiv  Detail & Related papers  (2022-06-30T15:35:53Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  We introduce a general design approach for algorithms that learn predictors. We apply techniques from online learning to learn against adversarial instances, tune robustness-consistency trade-offs, and obtain new statistical guarantees. We demonstrate the effectiveness of our approach at deriving learning algorithms by analyzing methods for bipartite matching, page migration, ski-rental, and job scheduling.
  arXiv  Detail & Related papers  (2022-02-18T17:25:43Z)
• Online Learning with Radial Basis Function Networks [0.0]
  We consider the sequential and continual learning sub-genres of online learning. We find that the online learning techniques outperform the offline learning ones.
  arXiv  Detail & Related papers  (2021-03-15T14:39:40Z)

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.