NDLI: Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy

Content Provider	Springer Nature Link
Author	Balcan, Maria Florina Feldman, Vitaly
Copyright Year	2014
Abstract	We describe a framework for designing efficient active learning algorithms that are tolerant to random classification noise and are differentially-private. The framework is based on active learning algorithms that are statistical in the sense that they rely on estimates of expectations of functions of filtered random examples. It builds on the powerful statistical query framework of Kearns (JACM 45(6):983–1006, 1998). We show that any efficient active statistical learning algorithm can be automatically converted to an efficient active learning algorithm which is tolerant to random classification noise as well as other forms of “uncorrelated” noise. The complexity of the resulting algorithms has information-theoretically optimal quadratic dependence on $$1/(1-2\eta )$$ , where $$\eta $$ is the noise rate. We show that commonly studied concept classes including thresholds, rectangles, and linear separators can be efficiently actively learned in our framework. These results combined with our generic conversion lead to the first computationally-efficient algorithms for actively learning some of these concept classes in the presence of random classification noise that provide exponential improvement in the dependence on the error $$\epsilon $$ over their passive counterparts. In addition, we show that our algorithms can be automatically converted to efficient active differentially-private algorithms. This leads to the first differentially-private active learning algorithms with exponential label savings over the passive case.
Starting Page	282
Ending Page	315
Page Count	34
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	72
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2014-11-11
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Active learning Statistical query framework Computationally efficient algorithms Random classification noise Differential privacy Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

On Exact Quantum Query Complexity

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

Preprocess, Set, Query!

On Resilient Graph Spanners

Quantum and Classical Query Complexities of Local Search Are Polynomially Related

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

Efficient Algorithms for k Maximum Sums

Sample Complexity for Computational Classification Problems

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy

Similar Documents

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

On Exact Quantum Query Complexity

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

Preprocess, Set, Query!

On Resilient Graph Spanners

Quantum and Classical Query Complexities of Local Search Are Polynomially Related

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups

Efficient Algorithms for k Maximum Sums

Sample Complexity for Computational Classification Problems

Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy