Transductive and Learning-Augmented Online Regression

• URL: http://arxiv.org/abs/2510.03917v1
• Date: Sat, 04 Oct 2025 19:41:37 GMT
• Title: Transductive and Learning-Augmented Online Regression
• Authors: Vinod Raman, Shenghao Xie, Samson Zhou,
• Abstract summary: We study online regression when the learner has access to predictions about future examples.<n>In the extreme case, called transductive online learning, the sequence of examples is revealed to the learner before the game begins.<n>We develop an online learner whose minimax expected regret matches the worst-case regret, improves smoothly with prediction quality, and significantly outperforms the worst-case regret when future example predictions are precise.
• Score: 26.376512210026988
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case, called transductive online learning, the sequence of examples is revealed to the learner before the game begins. For this setting, we fully characterize the minimax expected regret in terms of the fat-shattering dimension, establishing a separation between transductive online regression and (adversarial) online regression. Then, we generalize this setting by allowing for noisy or \emph{imperfect} predictions about future examples. Using our results for the transductive online setting, we develop an online learner whose minimax expected regret matches the worst-case regret, improves smoothly with prediction quality, and significantly outperforms the worst-case regret when future example predictions are precise, achieving performance similar to the transductive online learner. This enables learnability for previously unlearnable classes under predictable examples, aligning with the broader learning-augmented model paradigm.

Related papers

• Online Classification with Predictions [20.291598040396302]
  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.
  arXiv  Detail & Related papers  (2024-05-22T23:45:33Z)
• 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)
• Random Representations Outperform Online Continually Learned Representations [68.42776779425978]
  We show that existing online continually trained deep networks produce inferior representations compared to a simple pre-defined random transforms. Our method, called RanDumb, significantly outperforms state-of-the-art continually learned representations across all online continual learning benchmarks. Our study reveals the significant limitations of representation learning, particularly in low-exemplar and online continual learning scenarios.
  arXiv  Detail & Related papers  (2024-02-13T22:07:29Z)
• Discounted Adaptive Online Learning: Towards Better Regularization [5.5899168074961265]
  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.
  arXiv  Detail & Related papers  (2024-02-05T04:29:39Z)
• 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)
• 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)
• 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)
• 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)
• New Insights on Reducing Abrupt Representation Change in Online Continual Learning [69.05515249097208]
  We focus on the change in representations of observed data that arises when previously unobserved classes appear in the incoming data stream. We show that applying Experience Replay causes the newly added classes' representations to overlap significantly with the previous classes. We propose a new method which mitigates this issue by shielding the learned representations from drastic adaptation to accommodate new classes.
  arXiv  Detail & Related papers  (2022-03-08T01:37:00Z)
• 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)
• New Perspectives on the Use of Online Learning for Congestion Level Prediction over Traffic Data [6.664111208927475]
  This work focuses on classification over time series data. When a time series is generated by non-stationary phenomena, the pattern relating the series with the class to be predicted may evolve over time. Online learning methods incrementally learn from new data samples arriving over time, and accommodate eventual changes along the data stream.
  arXiv  Detail & Related papers  (2020-03-27T09:44:57Z)

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.