Noise-tolerant learning near the information-theoretic bound
Nicolb Cesa-Bianchi Eli Dichterman DSI, Universit~ di Milano Department of Computer Science Via Comelico 39, Technion 1-20135 Milano, Italy Haifa 32000, Israel cesabian@dsi .u.nimi. it eli@cs. technion. ac. il Paul Fischer Hans Ulrich Simon Lehrstuhl Informatik II Universitat Dortmund D-44221 Dortmund, Germany {paulf, simon}@goedel. inf ormat ik. uni-dortmund. de We investigate the sample size necessary for PAC learning in the presence of malicious noise, a type of adversarial noise model introduced by Kearns and Li. We prove the first nontrivial sample complexity lower bound in this model by showing that order of &/A2 + d/A examples are necessary for PAC learning any target class of {O, 1}-valued functions of VC dimension d, where e is the desired accuracy and q = &/(1 + e) – A the malicious noise rate (it is well known that any nontrivial target class cannot be PAC learned with accuracy E and malicio-us noise rate q > &/(1 + &), this irrespective to sample complexity.) This result cannot be significantly improved in general. In fact, we show a learning algorithm for the same noise model that. for each d. learns the class of all subsets of d elements using a number of examples of the same order as that proven necessary by our lower bound (disregarding logarithmic factors). In contrast, we show that to learn any target class of VC-dimension d in the presence of a high malicious noise rate ~ (i.e. A = o(s)), the popular strategy choosing any hypothesis that minimizes disagreements on the sample needs fl(de/A2 ) examples. This implies that, for high noise rate and for any target class of VC-dimension large enough, there are distributions over the target domain where the minimum disagreement strategy is outperformed by our algorithm. Permiaaion to make digital/hard copies of all or pati of tlds material for personal or classroom use is granted without fee provided that the copies are not made or dktributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copyright is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers or to redkibute to lists, requires specific permission and/or fee. STOC’96, Philadelphia PA,USA ~ 1996 ACM &89791-785.5/96/05. .$3.50