×

Learning mixtures of spherical Gaussians: moment methods and spectral decompositions (extended abstract). (English) Zbl 1362.68246

Proceedings of the 4th conference on innovations in theoretical computer science, ITCS’13, Berkeley, CA, USA, January 9–12, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1859-4). 11-20 (2013).

MSC:

68T05 Learning and adaptive systems in artificial intelligence
62H12 Estimation in multivariate analysis
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] D. Angluin and M. Krik¸is. Learning from di.erent teachers. Mach. Learn., 51(2):137 163, 2003. · Zbl 1027.68106
[2] M. Anthony, G. Brightwell, and J. Shawe-Taylor. On specifying Boolean functinos by labelled examples. Discrete Applied Mathematics, 61(1):1 25, 1995. · Zbl 0826.06008
[3] F. J. Balbach. Measuring teachability using variants of the teaching dimension. Theoret. Comput. Sci., 397(1 3):94 113, 2008. · Zbl 1145.68020
[4] F. J. Balbach and T. Zeugmann. Teaching learners with restricted mind changes. In Proc. 16th ALT, volume 3734, pages 474 489. Springer, 2005. · Zbl 1168.68390
[5] F. J. Balbach and T. Zeugmann. Teaching randomized learners. In Proc. 19th COLT, volume 4005, pages 229 243. Springer, 2008. · Zbl 1143.68409
[6] F. J. Balbach and T. Zeugmann. Recent developments in algorithmic teaching. In Proc. 3rd Int l Conf. on Language and Automata Theory and Applications, pages 1 18, 2009. · Zbl 1234.68165
[7] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. Occam s razor. Inf. Process. Lett., 24:377 380, 1987. · Zbl 0653.68084
[8] S. Floyd. On space-bounded learning and the Vapnik-Chervonenkis dimension.PhD thesis, University of California, Berkeley, Berkeley, CA, 1989. · Zbl 0747.68041
[9] S. Floyd and M. Warmuth. Sample compression, learnability, and the Vapnik-Chervonenkis dimension. Mach. Learn., 21:269 304, 1995.
[10] R. Freivalds, E. B. Kinber, and R. Wiehagen. On the power of inductive inference from good examples. Theoret. Comput. Sci., 110(1):131 144, 1993. · Zbl 0821.68110
[11] H. Freudenthal. LINCOS: Design of a language for cosmic intercourse. North-Holland, Amsterdam, 1960. · Zbl 0095.00506
[12] S. A. Goldman and M. J. Kearns. On the complexity of teaching. J. Comput. Syst. Sci., 50(1):20 31, 1995. · Zbl 0939.68770
[13] S. A. Goldman and H. D. Mathias. Teaching a smarter learner. J. Comput. Syst. Sci., 52(2):255 267, 1996. · Zbl 1152.68451
[14] O. Goldreich, B. Juba, and M. Sudan. A theory of goal-oriented communication. J. ACM, 59(2):8:1 8:65, 2012. · Zbl 1281.94004
[15] R. Impagliazzo, V. Kabanets, and A. Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672 694, 2002. · Zbl 1059.68047
[16] R. Impagliazzo and A. Wigderson. P=BPP unless E has subexponential circuits: Derandomizing the XOR lemma. In Proc. 29th STOC, pages 220 229, 1997. · Zbl 0962.68058
[17] J. Jackson and A. Tomkins. A computational model of teaching. In Proc. 5th COLT, pages 319 326, 1992.
[18] V. Kabanets and R. Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1 46, 2004. · Zbl 1089.68042
[19] N. Littlestone. From on-line to batch learning. In Proc. COLT 89, pages 269 284, 1989. · Zbl 0752.68066
[20] N. Littlestone and M. K. Warmuth. Relating data compression and learnability. Unpublished manuscript, 1986.
[21] H. D. Mathias. A model of interactive teaching. J. Comput. Syst. Sci., 54(3):487 501, 1997. · Zbl 0882.68123
[22] N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorica, 12(4):449 461, 1992. · Zbl 0759.68024
[23] R. L. Rivest. Learning decision lists. Mach. Learn., 2(3):229 246, 1987.
[24] D. Schuurmans and R. Greiner. Sequential PAC learning. In Proc. 8th COLT, pages 377 384, 1995.
[25] R. A. Servedio. On the limits of e.cient teachability. Inf. Process. Lett., 79(6):267 272, 2001. · Zbl 1032.68662
[26] A. Shinohara and S. Miyano. Teachability in computational learning. New Generation Comput., 8(4):337 347, 1991. · Zbl 0712.68084
[27] L. G. Valiant. A theory of the learnable. Communications of the ACM, 18(11):1134 1142, 1984. · Zbl 0587.68077
[28] S. Zilles, S. Lange, R. Holte, and M. Zinkevich. Models of cooperative teaching and learning. JMLR, 12:349 384, 2012. APPENDIX A. TAIL BOUND DERIVATION Here we prove: Reminder of Theorem 3.2 Let X1,...,Xt be independent Bernoulli random variables such that E · Zbl 1280.68224
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.