Time：Friday, Dec.20, 15:30--16:30 Venue: Room 602, ITCS
1.主讲人介绍
Mingchen Ma is a fourth-year PhD student at UW-Madison advised by Prof. Christos Tzamos and Prof. Ilias Diakonikolas. He obtained his B.S. in mathematics from Nanjing University in 2020 and spent one year as a visiting student at ITCS, SUFE before joining UW-Madison. His research lies in the field of computational learning theory with a focus on interactive learning and (robust) supervised learning.
2.讲座介绍
Title: Active Learning of General Halfspaces: Label Queries vs Membership Queries
author: Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma
Abstract: We study the problem of learning general (i.e., not necessarily homogeneous) halfspaces under the Gaussian distribution on R^d in the presence of some form of query access. In the classical pool-based active learning model, where the algorithm is allowed to make adaptive label queries to previously sampled points, we establish a strong information-theoretic lower bound ruling out non-trivial improvements over the passive setting. Specifically, we show that any active learner requires label complexity of Ω(d/(log(m)ϵ)), where m is the number of unlabeled examples. Specifically, to beat the passive label complexity of O(d/ϵ), an active learner requires a pool of 2^poly(d) unlabeled samples. On the positive side, we show that this lower bound can be circumvented with membership query access, even in the agnostic model. Specifically, we give a computationally efficient learner with query complexity of O(min{1/p, 1/ϵ} + dpolylog(1/ϵ)) achieving error guarantee of O(opt + ϵ). Here p ∈ [0, 1/2] is the bias and opt is the 0-1 loss of the optimal halfspace. As a corollary, we obtain a strong separation between the active and membership query models. Taken together, our results characterize the complexity of learning general halfspaces under Gaussian marginals in these models.
编审：唐志皓 江波
