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
- 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) - A Gaussian Process-based Streaming Algorithm for Prediction of Time Series With Regimes and Outliers [0.0]
Recently proposed INTEL algorithm provides a product of experts approach to online prediction of time series under possible regime switching.
We introduce LINTEL, which uses the exact filtering distribution at time $t$ with constant-time updates.
We show experimentally that our proposed approach is over five times faster than INTEL under reasonable settings with better quality predictions.
arXiv Detail & Related papers (2024-06-01T22:55:33Z) - 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) - Nonparametric Linear Feature Learning in Regression Through
Regularisation [0.0]
This study focuses on supervised learning scenarios where the information resides within a lower-dimensional linear subspace of the data.
We propose a novel method for linear feature learning with non-parametric prediction, which simultaneously estimates the linear subspace.
Our approach employs empirical risk minimisation augmented with a penalty on derivatives, ensuring versatility.
arXiv Detail & Related papers (2023-07-24T12:52:55Z) - 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.