{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/102774"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/102774","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Polynomial methods in statistical inference: Theory and practice","abstract":"Recent advances in genetics, computer vision, and text mining are accompanied by analyzing data coming from a large domain, where the domain size is comparable or larger than the number of samples. In this dissertation, we apply the polynomial methods to several statistical questions with rich history and wide applications. The goal is to understand the fundamental limits of the problems in the large domain regime, and to design sample optimal and time efficient algorithms with provable guarantees. The first part investigates the problem of property estimation. Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We obtain the minimax mean-square error within universal multiplicative constant factors if $n$ exceeds a constant factor of $k/\\log(k)$; otherwise there exists no consistent estimator. This refines the recent result on the minimal sample size for consistent entropy estimation. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound. We also consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \\frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of $\\epsilon k$ with probability at least 0.1 is within universal constant factors of $ \\frac{k}{\\log k}\\log^2\\frac{1}{\\epsilon} $, which improves the state-of-the-art result of $ \\frac{k}{\\epsilon^2 \\log k} $. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\\log^2 k)$ time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets. When the distribution is supported on a discrete set, estimating the support size is also known as the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing $ k $ balls based on $n$ samples drawn with replacements. Based on discrete polynomial approximation and interpolation, we propose an estimator with additive error guarantee that achieves the optimal sample complexity within $O(\\log\\log k)$ factors, and in fact within constant factors for most cases. The estimator can be computed in $O(n)$ time for an accurate estimation. The result also applies to sampling without replacement provided the sample size is a vanishing fraction of the urn size. One of the key auxiliary results is a sharp bound on the minimum singular values of a real rectangular Vandermonde matrix, which might be of independent interest. The second part studies the problem of learning Gaussian mixtures. The method of moments is one of the most widely used methods in statistics for parameter estimation, by means of solving the system of equations that match the population and estimated moments. However, in practice and especially for the important case of mixture models, one frequently needs to contend with the difficulties of non-existence or non-uniqueness of statistically meaningful solutions, as well as the high computational cost of solving large polynomial systems. Moreover, theoretical analysis of the method of moments are mainly confined to asymptotic normality style of results established under strong assumptions. We consider estimating a $k$-component Gaussian location mixture with a common (possibly unknown) variance parameter. To overcome the aforementioned theoretic and algorithmic hurdles, a crucial step is to denoise the moment estimates by projecting to the truncated moment space (via semidefinite programming) before solving the method of moments equations. Not only does this regularization ensures existence and uniqueness of solutions, it also yields fast solvers by means of Gauss quadrature. Furthermore, by proving new moment comparison theorems in the Wasserstein distance via polynomial interpolation and majorization techniques, we establish the statistical guarantees and adaptive optimality of the proposed procedure, as well as oracle inequality in misspecified models. These results can also be viewed as provable algorithms for generalized method of moments which involves non-convex optimization and lacks theoretical guarantees.","abstract_html":"Recent advances in genetics, computer vision, and text mining are accompanied by analyzing data coming from a large domain, where the domain size is comparable or larger than the number of samples. In this dissertation, we apply the polynomial methods to several statistical questions with rich history and wide applications. The goal is to understand the fundamental limits of the problems in the large domain regime, and to design sample optimal and time efficient algorithms with provable guarantees. The first part investigates the problem of property estimation. Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We obtain the minimax mean-square error within universal multiplicative constant factors if $n$ exceeds a constant factor of $k/\\log(k)$; otherwise there exists no consistent estimator. This refines the recent result on the minimal sample size for consistent entropy estimation. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound. We also consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \\frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of <span class=\"etd-inline-math\">&epsilon; k</span> with probability at least 0.1 is within universal constant factors of <span class=\"etd-inline-math\"> \\frac{k}{\\log k}\\log<sup>2</sup>\\frac{1}{&epsilon;} </span>, which improves the state-of-the-art result of <span class=\"etd-inline-math\"> \\frac{k}{&epsilon;<sup>2</sup> \\log k} </span>. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in <span class=\"etd-inline-math\">O(n+\\log<sup>2</sup> k)</span> time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets. When the distribution is supported on a discrete set, estimating the support size is also known as the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing $ k $ balls based on $n$ samples drawn with replacements. Based on discrete polynomial approximation and interpolation, we propose an estimator with additive error guarantee that achieves the optimal sample complexity within $O(\\log\\log k)$ factors, and in fact within constant factors for most cases. The estimator can be computed in $O(n)$ time for an accurate estimation. The result also applies to sampling without replacement provided the sample size is a vanishing fraction of the urn size. One of the key auxiliary results is a sharp bound on the minimum singular values of a real rectangular Vandermonde matrix, which might be of independent interest. The second part studies the problem of learning Gaussian mixtures. The method of moments is one of the most widely used methods in statistics for parameter estimation, by means of solving the system of equations that match the population and estimated moments. However, in practice and especially for the important case of mixture models, one frequently needs to contend with the difficulties of non-existence or non-uniqueness of statistically meaningful solutions, as well as the high computational cost of solving large polynomial systems. Moreover, theoretical analysis of the method of moments are mainly confined to asymptotic normality style of results established under strong assumptions. We consider estimating a $k$-component Gaussian location mixture with a common (possibly unknown) variance parameter. To overcome the aforementioned theoretic and algorithmic hurdles, a crucial step is to denoise the moment estimates by projecting to the truncated moment space (via semidefinite programming) before solving the method of moments equations. Not only does this regularization ensures existence and uniqueness of solutions, it also yields fast solvers by means of Gauss quadrature. Furthermore, by proving new moment comparison theorems in the Wasserstein distance via polynomial interpolation and majorization techniques, we establish the statistical guarantees and adaptive optimality of the proposed procedure, as well as oracle inequality in misspecified models. These results can also be viewed as provable algorithms for generalized method of moments which involves non-convex optimization and lacks theoretical guarantees.","abstract_has_math":true,"creators":["Yang, Pengkun"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wu, Yihong","Raginsky, Maxim","Hajek, Bruce","Srikant, Rayadurgam","Oh, Sewoong"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019-02-07T20:35:52Z","date_published":"2019-02-07T20:35:52Z","updated_at":"2026-07-22T22:24:42Z","subjects":["method of moments","polynomial methods","statistical inference","minimax estimation","polynomial approximation","efficient algorithm","fundamental limits"],"languages":["en"],"rights":["Copyright 2018 Pengkun Yang"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/102774","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wu, Yihong","Raginsky, Maxim","Hajek, Bruce","Srikant, Rayadurgam","Oh, Sewoong"]},{"key":"dc:creator","label":"Author","values":["Yang, Pengkun"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019-02-07T20:35:52Z","2021-02-08T10:15:36Z","2018-09-04","2018-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["method of moments","polynomial methods","statistical inference","minimax estimation","polynomial approximation","efficient algorithm","fundamental limits"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2018 Pengkun Yang"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/102774"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Recent advances in genetics, computer vision, and text mining are accompanied by analyzing data coming from a large domain, where the domain size is comparable or larger than the number of samples. In this dissertation, we apply the polynomial methods to several statistical questions with rich history and wide applications. The goal is to understand the fundamental limits of the problems in the large domain regime, and to design sample optimal and time efficient algorithms with provable guarantees. The first part investigates the problem of property estimation. Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We obtain the minimax mean-square error within universal multiplicative constant factors if $n$ exceeds a constant factor of $k/\\log(k)$; otherwise there exists no consistent estimator. This refines the recent result on the minimal sample size for consistent entropy estimation. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound. We also consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \\frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of $\\epsilon k$ with probability at least 0.1 is within universal constant factors of $ \\frac{k}{\\log k}\\log^2\\frac{1}{\\epsilon} $, which improves the state-of-the-art result of $ \\frac{k}{\\epsilon^2 \\log k} $. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\\log^2 k)$ time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets. When the distribution is supported on a discrete set, estimating the support size is also known as the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing $ k $ balls based on $n$ samples drawn with replacements. Based on discrete polynomial approximation and interpolation, we propose an estimator with additive error guarantee that achieves the optimal sample complexity within $O(\\log\\log k)$ factors, and in fact within constant factors for most cases. The estimator can be computed in $O(n)$ time for an accurate estimation. The result also applies to sampling without replacement provided the sample size is a vanishing fraction of the urn size. One of the key auxiliary results is a sharp bound on the minimum singular values of a real rectangular Vandermonde matrix, which might be of independent interest. The second part studies the problem of learning Gaussian mixtures. The method of moments is one of the most widely used methods in statistics for parameter estimation, by means of solving the system of equations that match the population and estimated moments. However, in practice and especially for the important case of mixture models, one frequently needs to contend with the difficulties of non-existence or non-uniqueness of statistically meaningful solutions, as well as the high computational cost of solving large polynomial systems. Moreover, theoretical analysis of the method of moments are mainly confined to asymptotic normality style of results established under strong assumptions. We consider estimating a $k$-component Gaussian location mixture with a common (possibly unknown) variance parameter. To overcome the aforementioned theoretic and algorithmic hurdles, a crucial step is to denoise the moment estimates by projecting to the truncated moment space (via semidefinite programming) before solving the method of moments equations. Not only does this regularization ensures existence and uniqueness of solutions, it also yields fast solvers by means of Gauss quadrature. Furthermore, by proving new moment comparison theorems in the Wasserstein distance via polynomial interpolation and majorization techniques, we establish the statistical guarantees and adaptive optimality of the proposed procedure, as well as oracle inequality in misspecified models. These results can also be viewed as provable algorithms for generalized method of moments which involves non-convex optimization and lacks theoretical guarantees.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-12-01","The student, Pengkun Yang, accepted the attached license on 2018-08-31 at 00:39.","The student, Pengkun Yang, submitted this Dissertation for approval on 2018-08-31 at 00:39.","This Dissertation was approved for publication on 2018-09-04 at 10:53.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12991 on 2019-02-07 at 14:16:27","Made available in DSpace on 2019-02-07T20:35:52Z (GMT). No. of bitstreams: 13 YANG-DISSERTATION-2018.pdf: 1945672 bytes, checksum: 9dc32fcabe0b9bf9d89f4c069da1090c (MD5) abs.tex: 5309 bytes, checksum: e82bd1df2cd8f17ea9e0be8414e29018 (MD5) ack.tex: 1985 bytes, checksum: d3ae46f0254cca1bc07c0d5ed5bba4b3 (MD5) approx.tex: 40505 bytes, checksum: a23a8e5e23b57a241a11a9697f68c0c9 (MD5) background.tex: 47987 bytes, checksum: ce7019cd83f3862aa44872ee4c02bf5b (MD5) compare.tex: 32374 bytes, checksum: 95b1ddf7060345e1041e18f3f8b8310b (MD5) ecethesis.tex: 11459 bytes, checksum: 4b85abeb639fd9c85d5a22ab1675c854 (MD5) entropy.tex: 85324 bytes, checksum: 298844d078bc1e0ce1a59a4848eca27f (MD5) framework.tex: 11159 bytes, checksum: bd4c4b7ae6efc7897e14bb9f637340f6 (MD5) gm.tex: 131673 bytes, checksum: 2d546c2573ee526283ab318de1e8aee6 (MD5) intro.tex: 15995 bytes, checksum: 6636c3a7e88047e5b496f64924d5bd0b (MD5) unseen.tex: 159209 bytes, checksum: db71000df1ccf82412dda68ce87ee2df (MD5) LICENSE.txt: 4209 bytes, checksum: fa5123468356d1c36a175dceed7d616e (MD5) Previous issue date: 2018-09-04","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:36:09Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:39:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:44:35Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 109798 on 2021-02-08T10:15:36Z."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Polynomial methods in statistical inference: Theory and practice"]}]}],"canonical_facts":{"dc:contributor":["Wu, Yihong","Raginsky, Maxim","Hajek, Bruce","Srikant, Rayadurgam","Oh, Sewoong"],"dc:creator":["Yang, Pengkun"],"dc:date":["2019-02-07T20:35:52Z","2021-02-08T10:15:36Z","2018-09-04","2018-12"],"dc:description":["Recent advances in genetics, computer vision, and text mining are accompanied by analyzing data coming from a large domain, where the domain size is comparable or larger than the number of samples. In this dissertation, we apply the polynomial methods to several statistical questions with rich history and wide applications. The goal is to understand the fundamental limits of the problems in the large domain regime, and to design sample optimal and time efficient algorithms with provable guarantees. The first part investigates the problem of property estimation. Consider the problem of estimating the Shannon entropy of a distribution over $k$ elements from $n$ independent samples. We obtain the minimax mean-square error within universal multiplicative constant factors if $n$ exceeds a constant factor of $k/\\log(k)$; otherwise there exists no consistent estimator. This refines the recent result on the minimal sample size for consistent entropy estimation. The apparatus of best polynomial approximation plays a key role in both the construction of optimal estimators and, via a duality argument, the minimax lower bound. We also consider the problem of estimating the support size of a discrete distribution whose minimum non-zero mass is at least $ \\frac{1}{k}$. Under the independent sampling model, we show that the sample complexity, i.e., the minimal sample size to achieve an additive error of $\\epsilon k$ with probability at least 0.1 is within universal constant factors of $ \\frac{k}{\\log k}\\log^2\\frac{1}{\\epsilon} $, which improves the state-of-the-art result of $ \\frac{k}{\\epsilon^2 \\log k} $. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in $O(n+\\log^2 k)$ time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets. When the distribution is supported on a discrete set, estimating the support size is also known as the distinct elements problem, where the goal is to estimate the number of distinct colors in an urn containing $ k $ balls based on $n$ samples drawn with replacements. Based on discrete polynomial approximation and interpolation, we propose an estimator with additive error guarantee that achieves the optimal sample complexity within $O(\\log\\log k)$ factors, and in fact within constant factors for most cases. The estimator can be computed in $O(n)$ time for an accurate estimation. The result also applies to sampling without replacement provided the sample size is a vanishing fraction of the urn size. One of the key auxiliary results is a sharp bound on the minimum singular values of a real rectangular Vandermonde matrix, which might be of independent interest. The second part studies the problem of learning Gaussian mixtures. The method of moments is one of the most widely used methods in statistics for parameter estimation, by means of solving the system of equations that match the population and estimated moments. However, in practice and especially for the important case of mixture models, one frequently needs to contend with the difficulties of non-existence or non-uniqueness of statistically meaningful solutions, as well as the high computational cost of solving large polynomial systems. Moreover, theoretical analysis of the method of moments are mainly confined to asymptotic normality style of results established under strong assumptions. We consider estimating a $k$-component Gaussian location mixture with a common (possibly unknown) variance parameter. To overcome the aforementioned theoretic and algorithmic hurdles, a crucial step is to denoise the moment estimates by projecting to the truncated moment space (via semidefinite programming) before solving the method of moments equations. Not only does this regularization ensures existence and uniqueness of solutions, it also yields fast solvers by means of Gauss quadrature. Furthermore, by proving new moment comparison theorems in the Wasserstein distance via polynomial interpolation and majorization techniques, we establish the statistical guarantees and adaptive optimality of the proposed procedure, as well as oracle inequality in misspecified models. These results can also be viewed as provable algorithms for generalized method of moments which involves non-convex optimization and lacks theoretical guarantees.","Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-12-01","The student, Pengkun Yang, accepted the attached license on 2018-08-31 at 00:39.","The student, Pengkun Yang, submitted this Dissertation for approval on 2018-08-31 at 00:39.","This Dissertation was approved for publication on 2018-09-04 at 10:53.","DSpace SAF Submission Ingestion Package generated from Vireo submission #12991 on 2019-02-07 at 14:16:27","Made available in DSpace on 2019-02-07T20:35:52Z (GMT). No. of bitstreams: 13 YANG-DISSERTATION-2018.pdf: 1945672 bytes, checksum: 9dc32fcabe0b9bf9d89f4c069da1090c (MD5) abs.tex: 5309 bytes, checksum: e82bd1df2cd8f17ea9e0be8414e29018 (MD5) ack.tex: 1985 bytes, checksum: d3ae46f0254cca1bc07c0d5ed5bba4b3 (MD5) approx.tex: 40505 bytes, checksum: a23a8e5e23b57a241a11a9697f68c0c9 (MD5) background.tex: 47987 bytes, checksum: ce7019cd83f3862aa44872ee4c02bf5b (MD5) compare.tex: 32374 bytes, checksum: 95b1ddf7060345e1041e18f3f8b8310b (MD5) ecethesis.tex: 11459 bytes, checksum: 4b85abeb639fd9c85d5a22ab1675c854 (MD5) entropy.tex: 85324 bytes, checksum: 298844d078bc1e0ce1a59a4848eca27f (MD5) framework.tex: 11159 bytes, checksum: bd4c4b7ae6efc7897e14bb9f637340f6 (MD5) gm.tex: 131673 bytes, checksum: 2d546c2573ee526283ab318de1e8aee6 (MD5) intro.tex: 15995 bytes, checksum: 6636c3a7e88047e5b496f64924d5bd0b (MD5) unseen.tex: 159209 bytes, checksum: db71000df1ccf82412dda68ce87ee2df (MD5) LICENSE.txt: 4209 bytes, checksum: fa5123468356d1c36a175dceed7d616e (MD5) Previous issue date: 2018-09-04","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:36:09Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:39:46Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","Embargo set by: Seth Robbins for item 109798 Lift date: 2021-02-07T20:44:35Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system","U of I Only Restriction Lifted for Item 109798 on 2021-02-08T10:15:36Z."],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/102774"],"dc:language":["en"],"dc:rights":["Copyright 2018 Pengkun Yang"],"dc:subject":["method of moments","polynomial methods","statistical inference","minimax estimation","polynomial approximation","efficient algorithm","fundamental limits"],"dc:title":["Polynomial methods in statistical inference: Theory and practice"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:42Z"}