Timeline for Covering number of Lipschitz functions
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2021 at 11:30 | comment | added | ABIM | @AryehKontorovich Thanks, actually I just did hehe: mathoverflow.net/questions/397935/… | |
| Jul 20, 2021 at 11:24 | comment | added | Aryeh Kontorovich | @james_t good question! Maybe ask it as a separate OP and I’ll think in the meantime… | |
| Jul 20, 2021 at 11:17 | comment | added | ABIM | What about for multivariate outputs (i.e. functions to $\mathbb{R}^m$ instead of $\mathbb{R}$)? | |
| Jun 10, 2018 at 14:19 | comment | added | Aryeh Kontorovich | It’s $(2D/\epsilon)^{ddim}$, where $D$ is the diameter. It’s a direct consequence of the definition of ddim. Start with $\epsilon =D/2$ and repeatedly apply the doubling property. | |
| Jun 10, 2018 at 8:24 | comment | added | gradstudent | @AryehKontorovich Your proof uses this intermediate result about $\epsilon-$covering number of metric spaces being upperbounded by $\left ( \frac{2}{\epsilon} \right )^{ddim}$. Is there a simple proof of this? | |
| Jun 3, 2018 at 17:32 | vote | accept | gradstudent | ||
| Jun 2, 2018 at 13:57 | comment | added | Pietro Majer | Also, in any case finitely many balls can't cover an unbounded set, e.g. the constant maps | |
| Jun 1, 2018 at 7:46 | comment | added | Aryeh Kontorovich | Regarding your first question on the bounded range: yes, it's necessary, even for Lipschitz functions $f:[0,1]\to [a,b]$. You can always rescale either the Lipschitz constant $L$ or the range $b-a$ to be 1, but if either is unbounded, the covering numbers will be infinite. | |
| Jun 1, 2018 at 7:45 | comment | added | Aryeh Kontorovich | Oops, you're right! I edited the answer, and linked to a paper where the proof appears. | |
| Jun 1, 2018 at 7:44 | history | edited | Aryeh Kontorovich | CC BY-SA 4.0 |
added 173 characters in body
|
| Jun 1, 2018 at 2:38 | comment | added | gradstudent | I think I am missing something. This Lemma 4.2 or its intermediate Lemma 2.1 dont seem to have been proven in your paper. I dont see the proofs anywhere! | |
| May 31, 2018 at 18:40 | comment | added | gradstudent | Thanks for the clarifications! So is it provably necessary that the domain and the range be bounded for such a count to be possible? Or is this need a weakness of our current methods? | |
| May 31, 2018 at 13:56 | history | answered | Aryeh Kontorovich | CC BY-SA 4.0 |