%PDF-1.6
%
3 0 obj
<>
endobj
186 0 obj
<>stream
application/pdf
Martin Azizyan, Aarti Singh, Larry Wasserman
Neural Information Processing Systems http://nips.cc/
Minimax Theory for High-dimensional Gaussian Mixtures with Sparse Mean Separation
Advances in Neural Information Processing Systems 26
2013
2013
Paper accepted and presented at the Neural Information Processing Systems Conference (http://nips.cc/)
While several papers have investigated computationally and statistically efficient methods for learning Gaussian mixtures, precise minimax bounds for their statistical performance as well as fundamental limits in high-dimensional settings are not well-understood. In this paper, we provide precise information theoretic bounds on the clustering accuracy and sample complexity of learning a mixture of two isotropic Gaussians in high dimensions under small mean separation. If there is a sparse subset of relevant dimensions that determine the mean separation, then the sample complexity only depends on the number of relevant dimensions and mean separation, and can be achieved by a simple computationally efficient procedure. Our results provide the first step of a theoretical basis for recent methods that combine feature selection and clustering.
C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger
Poster
en-US
Curran Associates
Conference Proceedings
2139
2147
PyPDF2
2014-01-25T02:05:23-05:00
2014-01-25T02:05:23-05:00
2014-01-25T02:05:23-05:00
uuid:c0618161-bd6c-4d40-9660-701e3ac11263
uuid:9808d52b-f6f6-f848-a2cb-1a446664498d
endstream
endobj
187 0 obj
<>
endobj
188 0 obj
<>
endobj
1 0 obj
<>
endobj
191 0 obj
<>
endobj
192 0 obj
<>
endobj
193 0 obj
<>
endobj
194 0 obj
<>
endobj
195 0 obj
<>
endobj
196 0 obj
<>
endobj
214 0 obj
<>
endobj
215 0 obj
<>
endobj
216 0 obj
<>
endobj
217 0 obj
<>
endobj
218 0 obj
<>
endobj
237 0 obj
<>stream
xZvF+0;s,'''3Rq(D"Jm=F|Y]]uV5h!^_|u*t\gW63f2{7;+\ş(u`Nh7DRSzLg416[0"B9Lg1NeJW/=%<Q-;B`b^vP9:N74
l6cA,$߯*E7JCJE묑RIgi%9혜6aDC+u[o'˄ uD*nN%&D8Q-^I
\Xo9I
CƉ&1brP`:~6#NВh`_kEP< -u@G25_(={^/JBXŁoVe'__ųC8GX-,?%Op@s]l\,:8
pd"B!.6A?`-dߧ:Z~Q)gCݚ/*' QCI`oRxRKڤm$Ǻqԋ\j5w#aQn0
c1-~
;n}6Yp 1j'rw?«壕!H1ZQ4فB/o*Bwu2IJtiBJ2Dа2aWS)P{ީ/il&sQHG(YLZP"aRp/:z0PyB#*2=qb4 MJ"nL'?)gmP((4 gea`Z@WuA1Kn +O/uǀqQ#v|
?|8#An618o)Bƹ!SpDtZPei!Q
+:
=<l6Fv3 :驁3WNђyp|+t2?3)liJo6}}Ejפ,7bΘiGN>ԇ#92tT>\9(IӘf>h-W)5N) :EN91ӈK{DT{L0zaz/Y:Jv\ MJ4ScCT^.7Ǽ~s5gzk^RPUZhz.Rr Gm=-JHWyzYYj6*:Hz[;_uӤQ
]Zzcބ 9ͣZܣDaMD2Rљ2)O2h&'z<1\`BuSؔ)v|OҚԔ`:#RDrEg-GnjM֫a\{+UDn~dX}$w@LPQ&Ȅaq../U&j(S5._gc s.'Y$dOL#)J6VbkHk e¢qk#
!
QkRT
xfI0[qUn
iI]p
:sBɱL8$Ȧ kЎdW,eN BB 7-zx^+
.>:wpimT'<