Improved learning of k-parities

 |  Login

Improved learning of k-parities

Altmetrics


 
 
Title: Improved learning of k-parities
Author(s): Bhattacharyya, Arnab ; Gadekar, Ameet ; Rajgopal, Ninad
Date: 2018-01-01
Language: en
Pages: 12
542-553
Department: Indian Institute of Science Bangalore
Professorship Chalermsook P.
University of Oxford
Department of Computer Science
ISBN: 9783319947754
Series: Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 10976 LNCS
ISSN: 0302-9743
1611-3349
DOI-number: 10.1007/978-3-319-94776-1_45
Subject: Theoretical Computer Science, Computer Science(all), 113 Computer and information sciences
Keywords: Theoretical Computer Science, Computer Science(all), 113 Computer and information sciences
 

» Show full item record

 
 
Citation:

Bhattacharyya , A , Gadekar , A & Rajgopal , N 2018 , Improved learning of k-parities . in Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings . Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) , vol. 10976 LNCS , Springer Verlag , pp. 542-553 , International Conference on Computing and Combinatorics Conference , Qing Dao , China , 02/07/2018 . DOI: 10.1007/978-3-319-94776-1_45

Abstract:

We consider the problem of learning k-parities in the online mistake-bound model: given a hidden vector (Formula Presented) where the hamming weight of x is k and a sequence of “questions” (Formula Presented), where the algorithm must reply to each question with (Formula Presented), what is the best trade-off between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et al. [BGM10] by an (Formula Presented) factor in the time complexity. Next, we consider the problem of learning k-parities in the PAC model in the presence of random classification noise of rate (Formula Presented). Here, we observe that even in the presence of classification noise of non-trivial rate, it is possible to learn k-parities in time better than (Formula Presented), whereas the current best algorithm for learning noisy k-parities, due to Grigorescu et al. [GRV11], inherently requires time (Formula Presented) even when the noise rate is polynomially small.

Rights:

restrictedAccess

Description:

| openaire: EC/H2020/759557/EU//ALGOCom
 
Permanent link to this item:  http://urn.fi/URN:NBN:fi:aalto-201808214682
 
Email this     Export to RefWorks     QR Code     Print     BibTex     Tweet    

Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account