Universal Rates for Interactive Learning
Nov 28, 2022
Speakers
Grigoris Velegkas
Speaker · 0 followers
Steve Hanneke
Speaker · 0 followers
Amin Karbasi
Speaker · 2 followers
Shay Moran
Speaker · 0 followers
About
Consider the task of learning an unknown concept from a given concept class; to what extent does interacting with a domain expert accelerate the learning process? It is common to measure the effectiveness of learning algorithms by plotting the "learning curve", that is, the decay of the error rate as a function of the algorithm's resources (examples, queries, etc). Thus, the overarching question in this work is whether (and which kind of) interaction accelerates the learning curve. Previous work in interactive learning focused on uniform bounds on the learning rates which only capture the upper envelope of the learning curves over families of data distributions. We thus formalize our overarching question within the distribution dependent framework of universal learning, which aims to understand the performance of learning algorithms on every data distribution, but without requiring a single upper bound which applies uniformly to all distributions. Our main result reveals a fundamental trichotomy of interactive learning rates, thus providing a complete characterization of universal interactive learning. As a corollary we deduce a strong affirmative answer to our overarching question, showing that interaction is beneficial. Remarkably, we show that in important cases such benefits are realized with label queries, that is, by active learning algorithms. On the other hand, our lower bounds apply to arbitrary binary queries and, hence, they hold in any interactive learning setting.Consider the task of learning an unknown concept from a given concept class; to what extent does interacting with a domain expert accelerate the learning process? It is common to measure the effectiveness of learning algorithms by plotting the "learning curve", that is, the decay of the error rate as a function of the algorithm's resources (examples, queries, etc). Thus, the overarching question in this work is whether (and which kind of) interaction accelerates the learning curve. Previous work…
Organizer
NeurIPS 2022
Account · 954 followers
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Dynamic Pricing with Monotonicity Constraint under Unknown Parametric Demand Model
Watch later
Su Jia, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Fair Multimodal Checklists for Interpretable Clinical Time Series Prediction
Watch later
Qixuan Jin, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
MultiScan: Scalable RGBD scanning for 3D environments with articulated objects
Watch later
Yongsen Mao, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Generic bounds on the approximation error for physics-informed (and) operator learning
Watch later
Tim De Ryck, …
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Fair and Socially Responsible ML for Recommendations
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%
Neural encoding and decoding of facial movements
Watch later
Total of 0 viewers voted for saving the presentation to eternal vault which is 0.0%