<?xml version='1.0' encoding='UTF-8'?><?xml-stylesheet href='static/style.xsl' type='text/xsl'?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T09:19:44Z</responseDate><request verb="GetRecord" identifier="oai:ecommons.cornell.edu:1813/102985" metadataPrefix="dim">https://ecommons.cornell.edu/server/oai/request</request><GetRecord><record><header><identifier>oai:ecommons.cornell.edu:1813/102985</identifier><datestamp>2026-05-15T19:49:01Z</datestamp><setSpec>com_1813_35</setSpec><setSpec>col_1813_47</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:doc="http://www.lyncode.com/xoai" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author">Qian, Wei</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="chair">Chen, Yudong</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Weinberger, Kilian Quirin</dim:field>
   <dim:field mdschema="dc" element="contributor" qualifier="committeeMember">Renegar, James</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2021-03-12T17:40:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2021-03-12T17:40:24Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2020-08</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Submission ID: 12062</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="other">ProQuest Publication ID: 28002375</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">https://hdl.handle.net/1813/102985</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="doi">https://doi.org/10.7298/jjj2-wa43</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="bibid">13278010</dim:field>
   <dim:field mdschema="dc" element="description">149 pages</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract">We study the location estimation problem for a balanced mixture of k distributions. The geometry of this non-convex optimization problem differs according to the number of components. In the case of a balanced mixture of two Gaussians, the negative log-likelihood function has only two local minima, which both correspond to a true location parameter. This benign landscape allows for the global convergence of generic algorithms for solving the maximum likelihood estimator (MLE), such as gradient descent (GD) and the expectation-maximization (EM) algorithm. In particular, the iterates exhibit the following dynamics: (1) the l2 distance to a true parameter decreases at a linear rate; (2) the angle with a true parameter decreases at a linear rate. Generalizing the angle decreasing property, we further show that the EM-type algorithm efficiently learns a true location parameter from a random initialization in the case of a balanced mixture of two log-concave and rotation invariant distributions. However, when the number of components is at least three, the landscape of the negative log-likelihood function changes: there exist local minima other than the true parameter. As a result, popular algorithms for the mixture model such as the EM algorithm and Lloyd's algorithm could converge to a spurious local minimum with high probability. Nonetheless, we explicitly characterize the structure of all the local minima under a separation condition of the true clusters. Specifically, we prove that every local minimum of the k-means objective function, which is closely related to the negative log-likelihood function, has the following configuration: either multiple fitted centers are close to a true center, or a fitted center is in the middle of multiple true centers. This characterization pertains to a balanced mixture of k Gaussians or bounded distributions. On the one hand, this structural result corroborates existing empirical observations and provides justifications for several improved algorithms for clustering. On the other hand, it sheds light on methods to devise new algorithmic procedures to further improve a local solution.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso">en</dim:field>
   <dim:field mdschema="dc" element="subject">Expectation Maximization</dim:field>
   <dim:field mdschema="dc" element="subject">Gaussian Mixture Model</dim:field>
   <dim:field mdschema="dc" element="subject">K-means</dim:field>
   <dim:field mdschema="dc" element="subject">Non Convex Optimization</dim:field>
   <dim:field mdschema="dc" element="title">Local Minima in Mixture Problems and their Algorithmic Implications</dim:field>
   <dim:field mdschema="dc" element="type">dissertation or thesis</dim:field>
   <dim:field mdschema="dc" element="relation" qualifier="localuri">https://catalog.library.cornell.edu/catalog/13278010</dim:field>
   <dim:field mdschema="dc" element="format" qualifier="mimetype">application/pdf</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="discipline">Operations Research and Information Engineering</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="grantor">Cornell University</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="level">Doctor of Philosophy</dim:field>
   <dim:field mdschema="thesis" element="degree" qualifier="name">Ph. D., Operations Research and Information Engineering</dim:field>
   <dim:field mdschema="dcterms" element="license">https://hdl.handle.net/1813/59810</dim:field>
   <dim:field mdschema="dspace" element="entity" qualifier="type">Publication</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="collection" authority="https://cornell-ecommons.eks.prod.4science.cloud/handle/1813/47" confidence="600">Cornell Theses and Dissertations</dim:field>
   <dim:field mdschema="cris" element="virtual" qualifier="author">Qian, Wei</dim:field>
   <dim:field mdschema="cris" element="virtualsource" qualifier="collection">5893a6ea-7af3-41d7-abc6-04bcd26ab5df</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
   <dim:field mdschema="cerif" element="openaire" authority="" confidence="-1">&lt;Publication xmlns="https://www.openaire.eu/cerif-profile/1.1/" id="f03ea1a0-0efe-4c66-8d5b-4181357489cf">
	&lt;Type xmlns="https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types">http://purl.org/coar/resource_type/c_1843&lt;/Type>
	&lt;Language>en&lt;/Language>
   	&lt;Title>Local Minima in Mixture Problems and their Algorithmic Implications&lt;/Title>
   	&lt;PublishedIn>
    	&lt;Publication>
      	&lt;/Publication>
   	&lt;/PublishedIn>
   	&lt;PublicationDate>2020-08&lt;/PublicationDate>
   	&lt;DOI>https://doi.org/10.7298/jjj2-wa43&lt;/DOI>
   	&lt;Authors>
      	&lt;Author>
        	&lt;DisplayName>Qian, Wei&lt;/DisplayName>
         	&lt;Affiliation>
         		&lt;OrgUnit>
         		&lt;/OrgUnit>
         	&lt;/Affiliation>
      	&lt;/Author>
	&lt;/Authors>
   	&lt;Editors>
	&lt;/Editors>
    &lt;Publishers>
        &lt;Publisher>
            &lt;OrgUnit />
        &lt;/Publisher>
    &lt;/Publishers>
    &lt;Keyword>Expectation Maximization&lt;/Keyword>
    &lt;Keyword>Gaussian Mixture Model&lt;/Keyword>
    &lt;Keyword>K-means&lt;/Keyword>
    &lt;Keyword>Non Convex Optimization&lt;/Keyword>
   	&lt;Abstract>We study the location estimation problem for a balanced mixture of k distributions. The geometry of this non-convex optimization problem differs according to the number of components. In the case of a balanced mixture of two Gaussians, the negative log-likelihood function has only two local minima, which both correspond to a true location parameter. This benign landscape allows for the global convergence of generic algorithms for solving the maximum likelihood estimator (MLE), such as gradient descent (GD) and the expectation-maximization (EM) algorithm. In particular, the iterates exhibit the following dynamics: (1) the l2 distance to a true parameter decreases at a linear rate; (2) the angle with a true parameter decreases at a linear rate. Generalizing the angle decreasing property, we further show that the EM-type algorithm efficiently learns a true location parameter from a random initialization in the case of a balanced mixture of two log-concave and rotation invariant distributions. However, when the number of components is at least three, the landscape of the negative log-likelihood function changes: there exist local minima other than the true parameter. As a result, popular algorithms for the mixture model such as the EM algorithm and Lloyd&amp;apos;s algorithm could converge to a spurious local minimum with high probability. Nonetheless, we explicitly characterize the structure of all the local minima under a separation condition of the true clusters. Specifically, we prove that every local minimum of the k-means objective function, which is closely related to the negative log-likelihood function, has the following configuration: either multiple fitted centers are close to a true center, or a fitted center is in the middle of multiple true centers. This characterization pertains to a balanced mixture of k Gaussians or bounded distributions. On the one hand, this structural result corroborates existing empirical observations and provides justifications for several improved algorithms for clustering. On the other hand, it sheds light on methods to devise new algorithmic procedures to further improve a local solution.&lt;/Abstract>
	&lt;Access xmlns="http://purl.org/coar/access_right" 
    >
    &lt;/Access>
&lt;/Publication>
</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>