Spatially Adaptive Online Prediction of Piecewise Regular Functions

Sabyasachi Chatterjee, Subhajit Goswami

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)275-309
Number of pages35
JournalProceedings of Machine Learning Research
StatePublished - 2023
Event34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore
Duration: Feb 20 2023Feb 23 2023


  • Adaptive Regret
  • Bounded Variation Function Estimation
  • Online Prediction
  • Oracle Risk Bounds
  • Piecewise Polynomial Fitting
  • Spatial/Local Adaptivity

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Spatially Adaptive Online Prediction of Piecewise Regular Functions'. Together they form a unique fingerprint.

Cite this