{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T21:07:15Z","timestamp":1705093635199},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2009,7,9]],"date-time":"2009-07-09T00:00:00Z","timestamp":1247097600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We study the problem of learning <jats:italic>k<\/jats:italic>-juntas given access to examples drawn from a number of different product distributions. Thus we wish to learn a function <jats:italic>f<\/jats:italic>: {\u22121, 1}<jats:sup><jats:italic>n<\/jats:italic><\/jats:sup> \u2192 {\u22121, 1} that depends on <jats:italic>k<\/jats:italic> (unknown) coordinates. While the best-known algorithms for the general problem of learning a <jats:italic>k<\/jats:italic>-junta require running times of <jats:italic>n<jats:sup>k<\/jats:sup><\/jats:italic> poly(<jats:italic>n<\/jats:italic>, 2<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>), we show that, given access to <jats:italic>k<\/jats:italic> different product distributions with biases separated by \u03b3 &gt; 0, the functions may be learned in time poly(<jats:italic>n<\/jats:italic>, 2<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>, \u03b3<jats:sup>\u2212<jats:italic>k<\/jats:italic><\/jats:sup>). More generally, given access to <jats:italic>t<\/jats:italic> \u2264 <jats:italic>k<\/jats:italic> different product distributions, the functions may be learned in time <jats:italic>n<\/jats:italic><jats:sup><jats:italic>k<\/jats:italic>\/<jats:italic>t<\/jats:italic><\/jats:sup>poly(<jats:italic>n<\/jats:italic>, 2<jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>, \u03b3<jats:sup>\u2212<jats:italic>k<\/jats:italic><\/jats:sup>). Our techniques involve novel results in Fourier analysis, relating Fourier expansions with respect to different biases, and a generalization of Russo's formula.<\/jats:p>","DOI":"10.1017\/s0963548309990277","type":"journal-article","created":{"date-parts":[[2009,7,9]],"date-time":"2009-07-09T06:51:27Z","timestamp":1247122287000},"page":"183-199","source":"Crossref","is-referenced-by-count":1,"title":["Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles"],"prefix":"10.1017","volume":"19","author":[{"given":"JAN","family":"ARPE","sequence":"first","affiliation":[]},{"given":"ELCHANAN","family":"MOSSEL","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,7,9]]},"reference":[{"key":"S0963548309990277_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-007-0061-6"},{"key":"S0963548309990277_ref28","first-page":"113","volume-title":"43rd Symposium on Foundations of Computer Science: FOCS 2002","author":"Vempala","year":"2002"},{"key":"S0963548309990277_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535742"},{"key":"S0963548309990277_ref8","first-page":"359","article-title":"On using extended statistical queries to avoid membership queries","volume":"2","author":"Bshouty","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"S0963548309990277_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234564"},{"key":"S0963548309990277_ref27","first-page":"1134","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"S0963548309990277_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.05.014"},{"key":"S0963548309990277_ref7","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"S0963548309990277_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00063-5"},{"key":"S0963548309990277_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90084-1"},{"key":"S0963548309990277_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"S0963548309990277_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-0013-7"},{"key":"S0963548309990277_ref17","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"S0963548309990277_ref25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.003"},{"key":"S0963548309990277_ref11","first-page":"321","volume-title":"Advances in Neural Information Processing Systems 19: NIPS '06","author":"Crammer","year":"2006"},{"key":"S0963548309990277_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"S0963548309990277_ref20","unstructured":"[20] Kolountzakis M. N. , Markakis E. and Mehta A. (2005) Learning symmetric juntas in time no(k) . In Workshop on Interface between Harmonic Analysis and Number Theory (Marseille 2005). Available as technical report at http:\/\/arxiv.org\/abs\/math.CO\/0504246v1."},{"key":"S0963548309990277_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.002"},{"key":"S0963548309990277_ref12","first-page":"651","article-title":"Multiple-instance learning of real-valued data","volume":"3","author":"Dooly","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"S0963548309990277_ref16","first-page":"179","volume-title":"Proc. 4th Annual Workshop on Computational Learning Theory: COLT 1991","author":"Hancock","year":"1991"},{"key":"S0963548309990277_ref14","first-page":"317","volume-title":"Proc. 4th Annual Workshop on Computational Learning Theory: COLT 1991","author":"Furst","year":"1991"},{"key":"S0963548309990277_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03981-6"},{"key":"S0963548309990277_ref10","volume-title":"Advances in Neural Information Processing Systems 18: NIPS 2005","author":"Crammer","year":"2005"},{"key":"S0963548309990277_ref22","first-page":"112","volume-title":"20th Annual IEEE Conference on Computational Complexity: CCC '05","author":"Lipton","year":"2005"},{"key":"S0963548309990277_ref19","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"S0963548309990277_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_54"},{"key":"S0963548309990277_ref13","first-page":"501","volume-title":"46th Annual IEEE Symposium on Foundations of Computer Science: FOCS '05","author":"Feldman","year":"2005"},{"key":"S0963548309990277_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/168304.168382"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990277","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T16:32:17Z","timestamp":1556469137000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990277\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,9]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["S0963548309990277"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990277","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,9]]}}}