{"entities":{"Q2113265":{"pageid":2124008,"ns":120,"title":"Item:Q2113265","lastrevid":57737634,"modified":"2026-04-01T04:36:53Z","type":"item","id":"Q2113265","labels":{"en":{"language":"en","value":"Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \\(O(\\sqrt{n})\\) iterations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7488303"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$946B41EE-82E6-4302-B9DA-17695EC08B19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"26c5fc304badda99e9aa26410ae56802c52543d0","datavalue":{"value":{"text":"Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in \\(O(\\sqrt{n})\\) iterations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2113265$121B438B-F66B-48E1-95D3-B17CEEC90B7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a79acd6f316934b4b80fc3052f7586747191f70f","datavalue":{"value":"1493.62350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113265$BC66A900-AFF9-42A2-9254-3690551D8C91","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec7ba8ec367fd4020a1ca6efc2c48ad452538902","datavalue":{"value":"10.4171/MSL/29","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113265$AB636B07-5859-4C85-BEAD-F0F6F1A15AA3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$2F302AA7-0222-4A19-973C-4D9E7B7886DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"dc21fa656a72c5bd4c84cbb6daa1826bf1ab50a3","datavalue":{"value":{"entity-type":"item","numeric-id":778886,"id":"Q778886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$4CC68295-12A8-4329-B751-1582AB294CAE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"932a926f48f1a99d5c676a3e09211363b2f1c4d4","datavalue":{"value":{"time":"+2022-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2113265$B362E853-2E49-4060-B9A6-421D29C33EAC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fc171377e47cc90c9ba2600c27f2d305b96b665d","datavalue":{"value":"https://arxiv.org/abs/1908.10935","type":"string"},"datatype":"url"},"type":"statement","id":"Q2113265$6BA48505-A868-4102-B1B8-ECB7B0558BF0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d3dd4bb53f826e82d66ec203ae91383287b36319","datavalue":{"value":"Summary: We analyze the classical EM algorithm for parameter estimation in the symmetric two-component Gaussian mixtures in \\(d\\) dimensions. We show that, even in the absence of any separation between components, provided that the sample size satisfies \\(n=\\Omega (d \\log^4 d)\\), the randomly initialized EM algorithm converges to an estimate in at most \\(O(\\sqrt{n})\\) iterations with high probability, which is at most \\(O((d/n)^{1/4} \\log n)\\) in Euclidean distance from the true parameter and within logarithmic factors of the minimax rate of \\((d/n)^{1/4}\\). Both the nonparametric statistical rate and the sublinear convergence rate are direct consequences of the zero Fisher information in the worst case. Refined pointwise guarantees beyond worst-case analysis and convergence to the MLE are also shown under mild conditions.  This improves the previous result of \\textit{S. Balakrishnan} et al. [Ann. Stat. 45, No. 1, 77--120 (2017; Zbl 1367.62052)], which requires strong conditions on both the separation of the components and the quality of the initialization, and that of \\textit{C. Daskalakis}, \\textit{C. Tzamos} and \\textit{M. Zampetakis} [``Ten steps of EM suffice for mixtures of two Gaussians'', Proc. Mach. Learn. Res. (PMLR) 65, 704--710 (2017)], which requires sample splitting and restarting the EM iteration.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$116DD844-7D21-4111-836E-B91C60E6B2F4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"bdc6d0880d442fd646c082c9721ab30d50d3f825","datavalue":{"value":"62H15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113265$B1B38B40-9487-43CC-81E7-07F35CC3ED32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fdbabfc5abdb416cc161a49c9478fb1dae15efc","datavalue":{"value":"62C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113265$5CF9963A-A8CB-40A9-96CB-E0DF3C6960D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2983e09eca2f4e22adebd73397b42584b2972c38","datavalue":{"value":"7488303","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113265$BEC5CA28-19C5-4CD6-958A-23D8A8A4DB9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6bd8768bef4e832f96736fc80a17ca4c6f61f40","datavalue":{"value":"EM algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$6BB5DE11-8DC7-4234-830B-4B44A8850D47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a22275d1ce5c98a8dffd7ce34cb37ef1ee0ef9a","datavalue":{"value":"Gaussian mixture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$F997A594-DF1D-4815-BF0E-E4B3DB640FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e537d649575b4cfef3de45d291d6360be51ed9a","datavalue":{"value":"minimax rates","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$9971E6CB-0971-4026-8A3B-94EBA6444D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"956b5338cafa302061b4a95b98cd1e6d97dcef0d","datavalue":{"value":"convergence rate","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$BCA7FCD0-B437-4662-8659-A720393DB9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"935ee375cebac07103c2b9fff57cead79a9b9614","datavalue":{"value":"random initialization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113265$12B59654-C610-4CCD-BB99-8698765D7925","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$A2CBE337-97BE-4EA3-A007-7D2015318CC4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"305212113d261b930195898b4c3337e2c26e1178","datavalue":{"value":{"entity-type":"item","numeric-id":524451,"id":"Q524451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$1909B066-BEE3-45C5-BEB9-9D92256236CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7945528a8ef56c222ad8be2ddb4f126dc6bdec5","datavalue":{"value":{"entity-type":"item","numeric-id":951824,"id":"Q951824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$7F3DDD40-A87C-4586-9924-A82127939B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60cd2fafc50d162249e27f585bb22aaad299ae62","datavalue":{"value":{"entity-type":"item","numeric-id":2443213,"id":"Q2443213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$1D43F678-3464-4A46-8CA0-11ED714A9464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0b5e62d0f4abd3140c433f2b42a8cec20c02d53","datavalue":{"value":{"entity-type":"item","numeric-id":2425162,"id":"Q2425162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$68488A2F-58ED-4967-AB9B-1457CCECAE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a3cbe45f424037c23ed3803891b4246000a06c4","datavalue":{"value":{"entity-type":"item","numeric-id":4508925,"id":"Q4508925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$776E36F4-2396-421E-99F6-1CEECC353D30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f07818b634e459fdfbede08defa40c8e8ef26894","datavalue":{"value":{"entity-type":"item","numeric-id":4139463,"id":"Q4139463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$82861284-4BFB-4CC8-BF94-1F230DDB1655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00db44f241bdca6f28034378de07d0aba734ea15","datavalue":{"value":{"entity-type":"item","numeric-id":1996764,"id":"Q1996764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$F397159B-C39E-4391-A724-9DC1A486E8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e41ac2fcb923bf3e606e0bdd7c73ba06db5d00fb","datavalue":{"value":{"entity-type":"item","numeric-id":495556,"id":"Q495556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$C00218B1-ECC1-4DFC-A45A-DAB21298F2FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d3497f9dd50f07ee7e273875a71b51f7fcb42bf","datavalue":{"value":{"entity-type":"item","numeric-id":1848816,"id":"Q1848816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$1B6AEA03-1D60-4852-94AE-AE1A30C06933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d95db18868cad36790a1713b3d873b041d7c21d","datavalue":{"value":{"entity-type":"item","numeric-id":1848903,"id":"Q1848903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$BF1280A8-765B-4693-8532-F78F412BB74F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1dfb379b707749ad2fa41b8201af1086cfdbe13","datavalue":{"value":{"entity-type":"item","numeric-id":510696,"id":"Q510696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$934CCAC5-11A9-4337-804D-0EA78E8427DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c73d0c51ab799d533462a4b5b6cfdcb9c56d9cba","datavalue":{"value":{"entity-type":"item","numeric-id":951825,"id":"Q951825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$E8D1967B-9F67-44C6-9858-84D97B955426","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53999ae9eef8ce9a774a5e78075a1496f934325c","datavalue":{"value":{"entity-type":"item","numeric-id":1848826,"id":"Q1848826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$E3CC2235-AE60-4DFA-B5EB-F25A577744B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a22027cedcc18f191ea2da44a5900ef6bb5159e2","datavalue":{"value":{"entity-type":"item","numeric-id":1991675,"id":"Q1991675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$45A46856-070D-4647-8D10-0E3703D17089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a479401e6427303ca29acc3f57ac0dc2e738add","datavalue":{"value":{"entity-type":"item","numeric-id":2977032,"id":"Q2977032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$88D49822-1710-4DB6-BAC1-FF58613E28C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"150006981e23d7f4993eb19b16530c0198f235e0","datavalue":{"value":{"entity-type":"item","numeric-id":3321233,"id":"Q3321233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$F0991F86-F469-4887-A33B-7B8DDD51BAE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c8f526c33d54ac39db19d3ed1300cf7d55a2ee9","datavalue":{"value":{"entity-type":"item","numeric-id":2196192,"id":"Q2196192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$899C029E-A10F-44C1-963C-736D7E6EEC45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"862577ac7255093c4e174b790b8b682ffb5362c6","datavalue":{"value":{"entity-type":"item","numeric-id":3040075,"id":"Q3040075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$2C283078-9262-4E77-84C8-3E2594507835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b69bab5509f33b3cbdba0d47ea4e054f93891dd","datavalue":{"value":{"entity-type":"item","numeric-id":1336571,"id":"Q1336571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$ACE5CE0E-8AAB-4FFC-9772-8378591296D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7664c6caee19246b2c4a42e88c801b86cc012b06","datavalue":{"value":{"entity-type":"item","numeric-id":3655724,"id":"Q3655724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$15E00239-2EB7-410A-8922-EDE9F289CA81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f65cf39a0b40f437f492397a4493868fdc5f1fd","datavalue":{"value":{"entity-type":"item","numeric-id":4223514,"id":"Q4223514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$2776C406-19F3-4FC5-9334-B874D12E2ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6269b1bbdd7c7793a9d2df84796a096969dc6f","datavalue":{"value":{"entity-type":"item","numeric-id":5272035,"id":"Q5272035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$924CCC41-BF79-4258-A912-31D758494F16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ddbbfa9eb92c895a4a2000a88b9c72889da946a","datavalue":{"value":{"entity-type":"item","numeric-id":2215721,"id":"Q2215721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$69A67255-687A-4D47-ADFE-402D7004E1CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e5ac3c143edc65f42d8ab2d315096f84ab42c91","datavalue":{"value":{"entity-type":"item","numeric-id":1578277,"id":"Q1578277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$8A0B2299-161B-4BE0-B674-5AF158A9E894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c22af11be4d0a9766016e22499c71dd3ef44cf0b","datavalue":{"value":{"entity-type":"item","numeric-id":5325830,"id":"Q5325830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113265$86B51F5E-C04C-4394-B17E-5E4DF251043F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c752430b01cde7314ae06aff122929015fef8a75","datavalue":{"value":{"entity-type":"item","numeric-id":434890,"id":"Q434890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b80049ab6005029d269b65b2f3a84bc8ead9862","datavalue":{"value":{"amount":"+0.88618106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2113265$7DBC59EA-E38C-4227-B197-17EACB5FF0AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed72369990d245200331c58fca1c4fac309a5e5","datavalue":{"value":{"entity-type":"item","numeric-id":1857734,"id":"Q1857734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41dccad4bb23c98d75013a56ef99c34387c4f7be","datavalue":{"value":{"amount":"+0.8811422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2113265$65AFFD19-43C1-4BC0-8C32-98CFEBC402EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ea8011f8b2d328c75fa4b758bad029c13546e02","datavalue":{"value":{"entity-type":"item","numeric-id":3374990,"id":"Q3374990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9e6e871a444d7173f56f96f2ef2c00e0efa9081","datavalue":{"value":{"amount":"+0.880256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2113265$E476DA51-1422-4851-B891-B31E1A36FF98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20982127d0efd3afb7a36b99d48d5b08aebd59c5","datavalue":{"value":{"entity-type":"item","numeric-id":2858834,"id":"Q2858834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301a3564ab0928ece7a85a9ec8b4bc062f5397f0","datavalue":{"value":{"amount":"+0.87948227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2113265$F7C3CCC3-2B76-4EBC-A3BD-DD21A0C2400F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89cb793911205087783daca7f4a2b779fd79a411","datavalue":{"value":{"entity-type":"item","numeric-id":4563129,"id":"Q4563129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d226331d969a86a8c6f0888969da82b54d8051c8","datavalue":{"value":{"amount":"+0.87909293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2113265$2C425EFD-0F8C-4A05-8A5F-7FF687B3B6F7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2113265","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2113265"}}}}}