6 papers · 1 filter
The Complexity of Sequential Prediction in Dynamical Systems
Vinod Raman, Unique Subedi, Ambuj Tewari
We study the problem of learning to predict the next state of a dynamical system when the underlying evolution function is unknown. Unlike previous work, we place no parametric ass…
A Characterization of Multioutput Learnability
Vinod Raman, Unique Subedi, Ambuj Tewari
We consider the problem of learning multioutput function classes in the batch and online settings. In both settings, we show that a multioutput function class is learnable if and o…
Multiclass Transductive Online Learning
Steve Hanneke, Vinod Raman, Amirreza Shaeiri +1
We consider the problem of multiclass transductive online learning when the number of labels can be unbounded. Previous works by Ben-David et al. [1997] and Hanneke et al. [2023b]…
Apple Tasting: Combinatorial Dimensions and Minimax Rates
Vinod Raman, Unique Subedi, Ananth Raman +1
In online binary classification under \emph{apple tasting} feedback, the learner only observes the true label if it predicts ``1". First studied by \cite{helmbold2000apple}, we rev…
Online Learning with Set-Valued Feedback
Vinod Raman, Unique Subedi, Ambuj Tewari
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 pe…
Smoothed Online Classification can be Harder than Batch Classification
Vinod Raman, Unique Subedi, Ambuj Tewari
We study online classification under smoothed adversaries. In this setting, at each time point, the adversary draws an example from a distribution that has a bounded density with r…