`

Timezone: »

Oral
From Stochastic Mixability to Fast Rates
Nishant Mehta · Robert Williamson

Wed Dec 10 08:20 AM -- 08:40 AM (PST) @ Level 2, room 210
Empirical risk minimization (ERM) is a fundamental learning rule for statistical learning problems where the data is generated according to some unknown distribution $\mathsf{P}$ and returns a hypothesis $f$ chosen from a fixed class $\mathcal{F}$ with small loss $\ell$. In the parametric setting, depending upon $(\ell, \mathcal{F},\mathsf{P})$ ERM can have slow $(1/\sqrt{n})$ or fast $(1/n)$ rates of convergence of the excess risk as a function of the sample size $n$. There exist several results that give sufficient conditions for fast rates in terms of joint properties of $\ell$, $\mathcal{F}$, and $\mathsf{P}$, such as the margin condition and the Bernstein condition. In the non-statistical prediction with expert advice setting, there is an analogous slow and fast rate phenomenon, and it is entirely characterized in terms of the mixability of the loss $\ell$ (there being no role there for $\mathcal{F}$ or $\mathsf{P}$). The notion of stochastic mixability builds a bridge between these two models of learning, reducing to classical mixability in a special case. The present paper presents a direct proof of fast rates for ERM in terms of stochastic mixability of $(\ell,\mathcal{F}, \mathsf{P})$, and in so doing provides new insight into the fast-rates phenomenon. The proof exploits an old result of Kemperman on the solution to the general moment problem. We also show a partial converse that suggests a characterization of fast rates for ERM in terms of stochastic mixability is possible.
{"ft_lang_label":"__label__en","ft_lang_prob":0.6648857,"math_prob":0.99743706,"size":3679,"snap":"2021-31-2021-39","text_gpt3_token_len":918,"char_repetition_ratio":0.13959184,"word_repetition_ratio":0.24398625,"special_character_ratio":0.24191356,"punctuation_ratio":0.08585858,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9981499,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-27T12:27:24Z\",\"WARC-Record-ID\":\"<urn:uuid:3773909e-ef62-4419-b665-41f33962ec93>\",\"Content-Length\":\"41309\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:845e9fa2-9dd8-4e48-b8b0-1f0798ef64e7>\",\"WARC-Concurrent-To\":\"<urn:uuid:9382cb76-97db-45f1-bfb5-52bf41a18f97>\",\"WARC-IP-Address\":\"198.202.70.65\",\"WARC-Target-URI\":\"https://neurips.cc/Conferences/2014/ScheduleMultitrack?event=4335\",\"WARC-Payload-Digest\":\"sha1:RUJUHY4FCN65UFZQYUYZOXXJ7EBJ2SHR\",\"WARC-Block-Digest\":\"sha1:E2CPQ6SSBVYAKS3A2CYYBPTVULMAJ5OB\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780058450.44_warc_CC-MAIN-20210927120736-20210927150736-00333.warc.gz\"}"}