Learning with Comparison Feedback: Online Estimation of Sample Statistics
We study an online version of the noisy binary search problem where feedback is generated by a non-stochastic adversary rather than perturbed by random noise. We reframe this as maintaining an accurate estimate for the median of an adversarial sequence of integers, $x_1, x_2, \dots$, in a model where each number $x_t$ can only be accessed through a single threshold query of the form ${1(x_t \leq q_t)}$. In this online comparison feedback model, we explore estimation of general sample statistics, providing robust algorithms for median, CDF, and mean estimation with nearly matching lower bounds. We conclude with several high-dimensional generalizations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Mode Estimation with Partial Feedback
The combination of lightly supervised pre-training and online fine-tuning has played a key role in recent AI developments. These new learning pipelines call for new theoretical frameworks. In this paper, we formalize cor…
Active LearningAdversarial learning for product recommendation
Product recommendation can be considered as a problem in data fusion-- estimation of the joint distribution between individuals, their behaviors, and goods or services of interest. This work proposes a conditional, coupl…
Generative Adversarial NetworkProduct RecommendationTwo-sample testingA Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedback
Inverse Reinforcement Learning (IRL) and Reinforcement Learning from Human Feedback (RLHF) are pivotal methodologies in reward learning, which involve inferring and shaping the underlying reward function of sequential de…
Decision Makingreinforcement-learningReinforcement LearningSequential Decision MakingA Deep Learning Framework for Hybrid Beamforming Without Instantaneous CSI Feedback
Hybrid beamformer design plays very crucial role in the next generation millimeter-wave (mm-Wave) massive MIMO (multiple-input multiple-output) systems. Previous works assume the perfect channel state information (CSI) w…
Deep LearningRegression with Comparisons: Escaping the Curse of Dimensionality with Ordinal Information
In supervised learning, we typically leverage a fully labeled dataset to design methods for function estimation or prediction. In many practical situations, we are able to obtain alternative feedback, possibly at a low c…
regression