Improved learning of k-parities

Arnab Bhattacharyya; Ameet Gadekar; Ninad Rajgopal

doi:10.1007/978-3-319-94776-1_45

Improved learning of k-parities

Arnab Bhattacharyya, Ameet Gadekar^*, Ninad Rajgopal

^*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

1 Sitaatiot (Scopus)

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings
Kustantaja	SPRINGER
Sivut	542-553
Sivumäärä	12
ISBN (painettu)	9783319947754
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-319-94776-1_45
Tila	Julkaistu - 1 tammik. 2018
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Computing and Combinatorics Conference - Qing Dao, Kiina Kesto: 2 heinäk. 2018 → 4 heinäk. 2018 Konferenssinumero: 24

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Vuosikerta	10976 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	International Computing and Combinatorics Conference
Lyhennettä	COCOON
Maa/Alue	Kiina
Kaupunki	Qing Dao
Ajanjakso	02/07/2018 → 04/07/2018

Pääsy asiakirjaan

10.1007/978-3-319-94776-1_45

OpenUrl-saatavuus

Koko teksti

Muut tiedostot ja linkit

Link to publication in Scopus

Siteeraa tätä

Bhattacharyya, A., Gadekar, A., & Rajgopal, N. (2018). Improved learning of k-parities. teoksessa Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings (Sivut 542-553). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 10976 LNCS). SPRINGER. https://doi.org/10.1007/978-3-319-94776-1_45

@inproceedings{b5f8cf4bdb014fd4b1e71697f80c7d0e,

title = "Improved learning of k-parities",

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.",

author = "Arnab Bhattacharyya and Ameet Gadekar and Ninad Rajgopal",

note = "| openaire: EC/H2020/759557/EU//ALGOCom ; International Computing and Combinatorics Conference, COCOON ; Conference date: 02-07-2018 Through 04-07-2018",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-94776-1_45",

language = "English",

isbn = "9783319947754",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "SPRINGER",

pages = "542--553",

booktitle = "Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings",

address = "Germany",

}

Bhattacharyya, A, Gadekar, A & Rajgopal, N 2018, Improved learning of k-parities. julkaisussa 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), Vuosikerta 10976 LNCS, SPRINGER, Sivut 542-553, International Computing and Combinatorics Conference, Qing Dao, Kiina, 02/07/2018. https://doi.org/10.1007/978-3-319-94776-1_45

Improved learning of k-parities. / Bhattacharyya, Arnab; Gadekar, Ameet; Rajgopal, Ninad.

Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings. SPRINGER, 2018. s. 542-553 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 10976 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

TY - GEN

T1 - Improved learning of k-parities

AU - Bhattacharyya, Arnab

AU - Gadekar, Ameet

AU - Rajgopal, Ninad

N1 - Conference code: 24

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85049669490&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-94776-1_45

DO - 10.1007/978-3-319-94776-1_45

M3 - Conference contribution

AN - SCOPUS:85049669490

SN - 9783319947754

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 542

EP - 553

BT - Computing and Combinatorics - 24th International Conference, COCOON 2018, Proceedings

PB - SPRINGER

T2 - International Computing and Combinatorics Conference

Y2 - 2 July 2018 through 4 July 2018

ER -

Improved learning of k-parities

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

OpenUrl-saatavuus

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä