Agnostic learning with unknown utilities
summary
Framework studies agnostic supervised learning where the utility U is arbitrary and only the hypothesis class F is restricted, and it introduces a K-comparison oracle that asks humans to compare bundles of K contexts. A two-step plug-in estimator estimates per-point utility gains via bundle comparisons and binary search, then returns the empirical utility maximizer; it uses O(n log K) queries, has excess risk = complexity term + (1/K)·(ERM misprediction error), and is minimax optimal* with a lower bound Ω(1/K).
AI-written summary · about
chapters (4)
related talks
46mLearning the Privacy-Utility Trade-off with Bayesian Optimization
35mSublinear-Time Algorithms in Learning
44mParsimonious Learning-Augmented Algorithms
40mApproximation Algorithms for Optimization under Uncertainty
59mTesting Assumptions of Learning Algorithms
34mPandora's Box with Correlations: Learning and Approximation
48mPredicting from Noisy and Incomplete Data: Some Perspectives from Computational Learning Theory
01h 11mA Theory of Multi-objective Machine Learning