Online Learning with Set-Valued Feedback
We study a variant of online multiclass classification where the learner predicts a single label but receives a \textit{set of labels} as feedback. In this model, the learner is penalized for not outputting a label contained in the revealed set. We show that unlike online multiclass learning with single-label feedback, deterministic and randomized online learnability are \textit{not equivalent} even in the realizable setting with set-valued feedback. Accordingly, we give two new combinatorial dimensions, named the Set Littlestone and Measure Shattering dimension, that tightly characterize deterministic and randomized online learnability respectively in the realizable setting. In addition, we show that the Measure Shattering dimension characterizes online learnability in the agnostic setting and tightly quantifies the minimax regret. Finally, we use our results to establish bounds on the minimax regret for three practical learning settings: online multilabel ranking, online multilabel classification, and real-valued prediction with interval-valued response.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Stability Analysis of a Class of Discontinuous Discrete-Time Systems
The stability analysis of a class of discontinuous discrete-time systems is studied in this paper. The system under study is modeled as a feedback interconnection of a linear system and a set-valued nonlinearity. An equi…
A Complex-Valued Feedback Linearization-Based Controller for a Voltage Source Inverter Tied to the Grid via a Second-Order Filter
In this document, a nonlinear control law for a grid-tied converter is introduced. The converter topology consists of a voltage source inverter (VSI) linked to the grid through an inductive-capacitive second-order filter…
UnityEfficient Online Set-valued Classification with Bandit Feedback
Conformal prediction is a distribution-free method that wraps a given machine learning model and returns a set of plausible labels that contain the true label with a prescribed coverage rate. In practice, the empirical c…
ClassificationConformal PredictionDecision MakingRobust Output-Feedback MPC for Nonlinear Systems with Applications to Robotic Exploration
This paper introduces a novel method for robust output-feedback model predictive control (MPC) for a class of nonlinear discrete-time systems. We propose a novel interval-valued predictor which, given an initial estimate…
Model Predictive ControlRobot NavigationOnline Learning with Multiple Operator-valued Kernels
We consider the problem of learning a vector-valued function f in an online learning setting. The function f is assumed to lie in a reproducing Hilbert space of operator-valued kernels. We describe two online algorithms …
General Classification