Spatially Adaptive Online Prediction of Piecewise Regular Functions

• URL: http://arxiv.org/abs/2203.16587v1
• Date: Wed, 30 Mar 2022 18:15:56 GMT
• Title: Spatially Adaptive Online Prediction of Piecewise Regular Functions
• Authors: Sabyasachi Chatterjee and Subhajit Goswami
• Abstract summary: We consider the problem of estimating piecewise regular functions in an online setting. We propose a modified version of a recently developed online learning algorithm called the sleeping experts aggregation algorithm.
• Score: 12.18340575383456
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of estimating piecewise regular functions in an online setting, i.e., the data arrive sequentially and at any round our task is to predict the value of the true function at the next revealed point using the available data from past predictions. We propose a suitably modified version of a recently developed online learning algorithm called the sleeping experts aggregation algorithm. We show that this estimator satisfies oracle risk bounds simultaneously for all local regions of the domain. As concrete instantiations of the expert aggregation algorithm proposed here, we study an online mean aggregation and an online linear regression aggregation algorithm where experts correspond to the set of dyadic subrectangles of the domain. The resulting algorithms are near linear time computable in the sample size. We specifically focus on the performance of these online algorithms in the context of estimating piecewise polynomial and bounded variation function classes in the fixed design setup. The simultaneous oracle risk bounds we obtain for these estimators in this context provide new and improved (in certain aspects) guarantees even in the batch setting and are not available for the state of the art batch learning estimators.

Related papers

• Scalable Gaussian process modeling of parametrized spatio-temporal fields [2.005299372367689]
  We develop a scalable framework for learning of parametized equations over fixed or parameter-temporal domains.<n>A key feature of our approach is the efficient computation of the posterior variance at essentially the same computational cost as the posterior mean.<n>Results establish the proposed framework as an effective tool for data-driven surrogate modeling, particularly when uncertainty estimates are required for downstream tasks.
  arXiv  Detail & Related papers  (2026-02-27T20:16:21Z)
• Optimal training-conditional regret for online conformal prediction [20.643619398558315]
  We study online conformal prediction for non-stationary data streams subject to unknown distribution drift.<n>We specifically focus on independently generated data with two types of distribution shift: abrupt change points and smooth drift.<n>We establish non-asymptotic regret guarantees for our online full conformal algorithm, which match the minimax lower bound under appropriate restrictions on the prediction sets.
  arXiv  Detail & Related papers  (2026-02-18T15:31:15Z)
• A Polynomial-time Algorithm for Online Sparse Linear Regression with Improved Regret Bound under Weaker Conditions [75.69959433669244]
  We study the problem of online sparse linear regression (OSLR) where the algorithms are restricted to accessing only $k$ out of $d$ per instance for prediction.<n>We introduce a new extend-time algorithm, which significantly improves previous regret bounds.
  arXiv  Detail & Related papers  (2025-10-31T05:02:33Z)
• Learning-Augmented Online Bidding in Stochastic Settings [34.40612230021777]
  We study online bidding under learning-augmented settings that incorporate either the prediction oracle or the algorithm itself.<n>In the first part, we study bidding under robustnessal predictions, and find algorithms that offer the best-possible tradeoff between the consistency and the distribution of the algorithm.<n>In the second part, we study the power and limitations of randomized bidding algorithms, by presenting upper and lower bounds on the consistency/robustness tradeoffs.
  arXiv  Detail & Related papers  (2025-10-29T14:47:18Z)
• A naive aggregation algorithm for improving generalization in a class of learning problems [0.0]
  We present a naive aggregation algorithm for a typical learning problem with expert advice setting. In particular, we consider a class of learning problem of point estimations for modeling high-dimensional nonlinear functions.
  arXiv  Detail & Related papers  (2024-09-06T15:34:17Z)
• Score-based change point detection via tracking the best of infinitely many experts [5.156484100374059]
  We suggest a novel algorithm for online change point detection based on sequential score function estimation and tracking the best expert approach. The algorithm shows a promising performance in numerical experiments on artificial and real-world data sets.
  arXiv  Detail & Related papers  (2024-08-26T07:56:17Z)
• Structured Prediction in Online Learning [66.36004256710824]
  We study a theoretical and algorithmic framework for structured prediction in the online learning setting. We show that our algorithm is a generalisation of optimal algorithms from the supervised learning setting. We consider a second algorithm designed especially for non-stationary data distributions, including adversarial data.
  arXiv  Detail & Related papers  (2024-06-18T07:45:02Z)
• Online Estimation via Offline Estimation: An Information-Theoretic Framework [75.80823630681323]
  Motivated by connections between estimation and interactive decision making, we ask: is it possible to convert offline estimation algorithms into online estimation algorithms? We introduce a new framework, Oracle-Efficient Online Estimation (OEOE), where the learner can only interact with the data stream indirectly through a sequence of offline estimators produced by a black-box algorithm operating on the stream.
  arXiv  Detail & Related papers  (2024-04-15T20:19:18Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  We revisit the likelihood-based inference principle and propose to use likelihood ratios to construct valid confidence sequences. Our method is especially suitable for problems with well-specified likelihoods. We show how to provably choose the best sequence of estimators and shed light on connections to online convex optimization.
  arXiv  Detail & Related papers  (2023-11-08T00:10:21Z)
• High-Probability Risk Bounds via Sequential Predictors [20.741036493022442]
  We show that online to batch conversions applied to general online learning algorithms can bypass regret bounds. We obtain nearly optimal high-probability risk bounds for several classical statistical estimation problems. Our analysis relies on the fact that many online learning algorithms are improper, as they are not restricted to use predictors from a given reference class.
  arXiv  Detail & Related papers  (2023-08-15T06:19:31Z)
• A Regression Approach to Learning-Augmented Online Algorithms [17.803569868141647]
  We introduce this approach in this paper, and explore it in the context of a general online search framework. We show nearly tight bounds on the sample complexity of this regression problem, and extend our results to the agnostic setting. From a technical standpoint, we show that the key is to incorporate online optimization benchmarks in the design of the loss function for the regression problem.
  arXiv  Detail & Related papers  (2022-05-18T04:29:14Z)
• Scalable computation of prediction intervals for neural networks via matrix sketching [79.44177623781043]
  Existing algorithms for uncertainty estimation require modifying the model architecture and training procedure. This work proposes a new algorithm that can be applied to a given trained neural network and produces approximate prediction intervals.
  arXiv  Detail & Related papers  (2022-05-06T13:18:31Z)
• Domain-Adjusted Regression or: ERM May Already Learn Features Sufficient for Out-of-Distribution Generalization [52.7137956951533]
  We argue that devising simpler methods for learning predictors on existing features is a promising direction for future research. We introduce Domain-Adjusted Regression (DARE), a convex objective for learning a linear predictor that is provably robust under a new model of distribution shift. Under a natural model, we prove that the DARE solution is the minimax-optimal predictor for a constrained set of test distributions.
  arXiv  Detail & Related papers  (2022-02-14T16:42:16Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  We provide the first oracle-efficient, no-regret algorithms in this setting. We show that if a function class is learnable in the classical setting, then there is an oracle-efficient, no-regret algorithm for contextual bandits.
  arXiv  Detail & Related papers  (2022-02-09T19:22:34Z)

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.