4 papers
Optimal Recalibration of an Online Predictor
Lunjia Hu, Kevin Tian, Chutong Yang
We study the problem of recalibrating an online predictor [KE17, OKS24]: given an arbitrary "hint" sequence of forecasts, the learner must output new predictions that are calibrate…
Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction
Lunjia Hu, Kevin Tian, Chutong Yang
Omniprediction is a learning problem that requires suboptimality bounds for each of a family of losses against a family of comparator predictors . We ini…
Private Geometric Median in Nearly-Linear Time
Syamantak Kumar, Daogao Liu, Kevin Tian +1
Estimating the geometric median of a dataset is a robust counterpart to mean estimation, and is a fundamental problem in computational geometry. Recently, [HSU24] gave an $(\vareps…
Omnipredicting Single-Index Models with Multi-Index Models
Lunjia Hu, Kevin Tian, Chutong Yang
Recent work on supervised learning [GKR+22] defined the notion of omnipredictors, i.e., predictor functions over features that are simultaneously competitive for minimizing a f…