東華大學圖書館 |

語系: 繁體中文

說明(常見問題)

回圖書館首頁

手機版館藏查詢

登入

回首頁

切換: 標籤 | MARC模式 | ISBD

FindBook

Google Book

Amazon

博客來

Competitive and Universal Learning.

紀錄類型:	書目-電子資源 : Monograph/item
正題名/作者:	Competitive and Universal Learning./
作者:	Hao, Yi.
出版者:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
面頁冊數:	340 p.
附註:	Source: Dissertations Abstracts International, Volume: 83-02, Section: B.
Contained By:	Dissertations Abstracts International83-02B.
標題:	Electrical engineering. -
電子資源:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28490684
ISBN:	9798534661576

Competitive and Universal Learning.
Hao, Yi.

Competitive and Universal Learning. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 340 p.

Source: Dissertations Abstracts International, Volume: 83-02, Section: B.

Thesis (Ph.D.)--University of California, San Diego, 2021.

This item must not be sold to any third party vendors.

Modern data science calls for statistical inference algorithms that are both data-efficient and computation-efficient. We design and analyze methods that 1) outperform existing algorithms in the high-dimensional setting; 2) are as simple as possible but efficiently computable.One line of our work aims to bridge different fields and offer unified solutions to multiple questions. Consider the following canonical statistical inference tasks: distribution estimation, functional estimation, and property testing, sharing the model that provides sample access to an unknown discrete distribution. In a recent paper in NeurIPS '19, we showed that a single, simple, and unified estimator - profile maximum likelihood (PML), and its near-linear time computable variant are sample-optimal for estimating multiple distribution attributes. The result covers 1) any appropriately Lipschitz and additively separable functionals; 2) sorted distribution; 3) Renyi entropy; 4) l2 distance to the uniform distribution, yielding an optimal tester for distributions' closeness. This work makes PML the first unified sample- and time-optimal method for the learning tasks mentioned above. A single algorithm with such broad applicability is universal.Another line of our work focuses on instance-optimal learning that designs algorithms with near-optimal guarantees for every possible data input. A flagship problem is distribution estimation over discrete or continuous domains, where ordering and geometry play an essential role. Going beyond worst-case guarantees, researchers designed algorithms that compete with a genie estimator that knows the actual distribution but is reasonably restricted. To obtain state-of-the-art algorithms for both tasks, we leveraged the simple but nontrivial idea of "data binning''. For discrete settings, we group symbols that appear the same number of times. And for continuous settings, we partition the real domain and separate symbols according to pre-designed local quantiles. The respective algorithms run in near-linear-time, achieve the best-known estimation guarantees regarding the genie estimators, and appear in ICML'19 and NeurIPS '20. A genie-like algorithm adaptive to almost every data sample is competitive.We present a comprehensive understanding of universal and competitive algorithms for multiple fundamental learning problems. Our ideas and techniques may shed light on key challenges in modern data science and numerous applications beyond the scope of this dissertation.

ISBN: 9798534661576Subjects--Topical Terms:

649834
Electrical engineering.
Subjects--Index Terms:

Density estimation

Competitive and Universal Learning.
LDR:03904nmm a2200469 4500 001 2349531
005 20230509091105.5
006 m o d
007 cr#unu||||||||
008 241004s2021 ||||||||||||||||| ||eng d
020 $a 9798534661576
035 $a (MiAaPQ)AAI28490684
035 $a AAI28490684
040 $a MiAaPQ $c MiAaPQ
100 1 $a Hao, Yi. $3 3688941
245 1 0 $a Competitive and Universal Learning.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 340 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-02, Section: B.
500 $a Advisor: Orlitsky, Alon.
502 $a Thesis (Ph.D.)--University of California, San Diego, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a Modern data science calls for statistical inference algorithms that are both data-efficient and computation-efficient. We design and analyze methods that 1) outperform existing algorithms in the high-dimensional setting; 2) are as simple as possible but efficiently computable.One line of our work aims to bridge different fields and offer unified solutions to multiple questions. Consider the following canonical statistical inference tasks: distribution estimation, functional estimation, and property testing, sharing the model that provides sample access to an unknown discrete distribution. In a recent paper in NeurIPS '19, we showed that a single, simple, and unified estimator - profile maximum likelihood (PML), and its near-linear time computable variant are sample-optimal for estimating multiple distribution attributes. The result covers 1) any appropriately Lipschitz and additively separable functionals; 2) sorted distribution; 3) Renyi entropy; 4) l2 distance to the uniform distribution, yielding an optimal tester for distributions' closeness. This work makes PML the first unified sample- and time-optimal method for the learning tasks mentioned above. A single algorithm with such broad applicability is universal.Another line of our work focuses on instance-optimal learning that designs algorithms with near-optimal guarantees for every possible data input. A flagship problem is distribution estimation over discrete or continuous domains, where ordering and geometry play an essential role. Going beyond worst-case guarantees, researchers designed algorithms that compete with a genie estimator that knows the actual distribution but is reasonably restricted. To obtain state-of-the-art algorithms for both tasks, we leveraged the simple but nontrivial idea of "data binning''. For discrete settings, we group symbols that appear the same number of times. And for continuous settings, we partition the real domain and separate symbols according to pre-designed local quantiles. The respective algorithms run in near-linear-time, achieve the best-known estimation guarantees regarding the genie estimators, and appear in ICML'19 and NeurIPS '20. A genie-like algorithm adaptive to almost every data sample is competitive.We present a comprehensive understanding of universal and competitive algorithms for multiple fundamental learning problems. Our ideas and techniques may shed light on key challenges in modern data science and numerous applications beyond the scope of this dissertation.
590 $a School code: 0033.
650 4 $a Electrical engineering. $3 649834
650 4 $a Computer science. $3 523869
650 4 $a Statistics. $3 517247
650 4 $a Communication. $3 524709
650 4 $a International conferences. $3 3558960
650 4 $a Experiments. $3 525909
650 4 $a Dissertations & theses. $3 3560115
650 4 $a Computer engineering. $3 621879
650 4 $a Design. $3 518875
650 4 $a Information processing. $3 3561808
650 4 $a Algorithms. $3 536374
650 4 $a Information theory. $3 542527
650 4 $a Entropy. $3 546219
650 4 $a Bias. $2 gtt $3 1374837
650 4 $a Competition. $3 537031
653 $a Density estimation
653 $a High-dimensional statistics
653 $a Information theory
653 $a Optimization
653 $a Probability theory
653 $a Statistical machine learning
653 $a Nonparametric statistics
653 $a Universal learning
690 $a 0544
690 $a 0984
690 $a 0463
690 $a 0459
690 $a 0389
690 $a 0464
710 2 $a University of California, San Diego. $b Electrical and Computer Engineering. $3 3432690
773 0 $t Dissertations Abstracts International $g 83-02B.
790 $a 0033
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28490684