# TURF: Two-Factor, Universal, Robust, Fast Distribution Learning Algorithm

Yi Hao, Ayush Jain, Alon Orlitsky, Vaishakh Ravindrakumar
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:8427-8445, 2022.

#### Abstract

Approximating distributions from their samples is a canonical statistical-learning problem. One of its most powerful and successful modalities approximates every distribution to an $\ell_1$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d$ polynomial, where $t\ge1$ and $d\ge0$. Letting $c_{t,d}$ denote the smallest such factor, clearly $c_{1,0}=1$, and it can be shown that $c_{t,d}\ge 2$ for all other $t$ and $d$. Yet current computationally efficient algorithms show only $c_{t,1}\le 2.25$ and the bound rises quickly to $c_{t,d}\le 3$ for $d\ge 9$. We derive a near-linear-time and essentially sample-optimal estimator that establishes $c_{t,d}=2$ for all $(t,d)\ne(1,0)$. Additionally, for many practical distributions, the lowest approximation distance is achieved by polynomials with vastly varying number of pieces. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation. Experiments combining the two techniques confirm improved performance over existing methodologies.
{"ft_lang_label":"__label__en","ft_lang_prob":0.81191903,"math_prob":0.9947731,"size":5027,"snap":"2022-40-2023-06","text_gpt3_token_len":1327,"char_repetition_ratio":0.107107304,"word_repetition_ratio":0.68636364,"special_character_ratio":0.25343147,"punctuation_ratio":0.15755627,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.998247,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-09-30T16:56:18Z\",\"WARC-Record-ID\":\"<urn:uuid:cf6b246d-8160-4552-93e5-3c15dd87d523>\",\"Content-Length\":\"16052\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5bc397f8-e4a0-44da-ab07-25848e4802dc>\",\"WARC-Concurrent-To\":\"<urn:uuid:be54aebd-d928-461b-950d-0f5d52d4fa9d>\",\"WARC-IP-Address\":\"185.199.110.153\",\"WARC-Target-URI\":\"https://proceedings.mlr.press/v162/hao22a.html\",\"WARC-Payload-Digest\":\"sha1:3VQJ5HRVKSLT5S33BXAG4JJYVT6NLXKZ\",\"WARC-Block-Digest\":\"sha1:AJDIEU5PBK2LV6US5Z3VSS2SBOL3IUIT\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-40/CC-MAIN-2022-40_segments_1664030335491.4_warc_CC-MAIN-20220930145518-20220930175518-00764.warc.gz\"}"}