Online allocation and homogeneous partitioning for piecewise constant mean-approximation
In the setting of active learning for the multi-armed bandit, where the goal of a learner is to estimate with equal precision the mean of a finite number of arms, recent results show that it is possible to derive strategies based on finite-time confidence bounds that are competitive with the best possible strategy. We here consider an extension of this problem to the case when the arms are the cells of a finite partition P of a continuous sampling space X \subset \Real^d. Our goal is now to build a piecewise constant approximation of a noisy function (where each piece is one region of P and P is fixed beforehand) in order to maintain the local quadratic error of approximation on each cell equally low. Although this extension is not trivial, we show that a simple algorithm based on upper confidence bounds can be proved to be adaptive to the function itself in a near-optimal way, when |P| is chosen to be of minimax-optimal order on the class of \alpha-Hölder functions.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningSimilar Papers 제목 키워드 기반
Discrete minimax estimation with trees
We propose a simple recursive data-based partitioning scheme which produces piecewise-constant or piecewise-linear density estimates on intervals, and show how this scheme can determine the optimal $L_1$ minimax rate for…
Nonlinear Control Allocation Using A Piecewise Multi-Linear Representation
Nonlinear control allocation is an important part of modern nonlinear dynamic inversion based flight control systems which require highly accurate model of aircraft aerodynamics. Generally, an accurately implemented onbo…
Neural Network-Based Piecewise Survival Models
In this paper, a family of neural network-based survival models is presented. The models are specified based on piecewise definitions of the hazard function and the density function on a partitioning of the time; both co…
Fast Partitioning of Vector-valued Images
We propose a fast splitting approach to the classical variational formulation of the image partitioning problem, which is frequently referred to as the Potts or piecewise constant Mumford--Shah model. For vector-valued i…
Rank-one partitioning: formalization, illustrative examples, and a new cluster enhancing strategy
In this paper, we introduce and formalize a rank-one partitioning learning paradigm that unifies partitioning methods that proceed by summarizing a data set using a single vector that is further used to derive the final …
ClusteringDenoising