Timeline for Rate of uniform approximation by piecewise constant functions
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Oct 12, 2022 at 15:07 | history | bounty ended | CommunityBot | ||
| S Oct 12, 2022 at 15:07 | history | notice removed | CommunityBot | ||
| Oct 6, 2022 at 13:53 | comment | added | ABIM | @PietroMajer I guess it reduces to bounding the Assouad dimension of $f([-M,M]^n)$ then? | |
| Oct 5, 2022 at 21:15 | comment | added | Pietro Majer | It seems the quantity you define on the LHS, (that is the point-set distance from $f$ to the space $H^{m,n,N}$) is itself a sort of "mean modulus of continuity", something weaker than the usual (uniform) modulus of continuity: it could actually be $cN^{-r}$ even if $f$ is not Hoelder, e.g. if it has a very thin, non Hoelder cuspid at a single point $x_0$ (then the cubes of the approximating h have to be very small around $x_0$, a lot of them, but that is possible if elsewhere f is more flat so that less cubes are needed) | |
| Oct 5, 2022 at 13:31 | history | edited | ABIM | CC BY-SA 4.0 |
added 69 characters in body
|
| Oct 5, 2022 at 13:20 | comment | added | ABIM | @PietroMajer Still, can we do better if we know the function's modulus of smoothness (I've updated the question). | |
| Oct 5, 2022 at 13:19 | comment | added | ABIM | @MattF. Ah, since the question stems from trying to mathematically understand why regression trees (en.wikipedia.org/wiki/Decision_tree_learning) do well (I was playing with some code on my free time and then I became curious). | |
| Oct 5, 2022 at 9:26 | comment | added | user44143 | I don’t know a reference — but why define piecewise constancy with box-shaped pieces? | |
| Oct 5, 2022 at 2:34 | history | edited | ABIM | CC BY-SA 4.0 |
added 118 characters in body
|
| Oct 5, 2022 at 2:32 | comment | added | ABIM | @PietroMajer So, as stated, the problem is only about packing numbers? | |
| Oct 5, 2022 at 1:56 | comment | added | ABIM | Matt and Pietro; Do you know of a reference? | |
| Oct 4, 2022 at 21:29 | comment | added | Pietro Majer | More generally, for a uniformly continuous $f$ with mod. of c. $\omega$, the distance from $f$ to $H^{(m,n,N)}$ should be around $\omega(MN^{-1/n}n^{1/2})$ (taking the locally constant function equal to $f$ in the center of each of $N$ cubes of equal size, and pretending $N$ is a power of $n$). So I’d say to get a distance $cN^{-r}$ from $H^{(m,n,N)}$ you need $f$ to be Hoelder of exponent $rn$. So $r=1/n$ should be ok, but for $f$ Lipschitz. | |
| Oct 4, 2022 at 15:03 | comment | added | user44143 | I think the key example is $m=1$, $f= w \sum \langle x,e_i \rangle$, with a minimum error achieved by dividing the big cube into smaller cubes all of the same size. If so, the limiting error is $2MN^{-1/n}nw$ and the desired rate is $r=1/n$. | |
| Oct 4, 2022 at 14:14 | history | edited | user44143 | CC BY-SA 4.0 |
standardized and simplified some phrasing, clarified final inequality, removed some conditions which have no effect
|
| S Oct 4, 2022 at 13:47 | history | bounty started | ABIM | ||
| S Oct 4, 2022 at 13:47 | history | notice added | ABIM | Authoritative reference needed | |
| Oct 2, 2022 at 17:00 | history | edited | ABIM | CC BY-SA 4.0 |
edited tags; edited title
|
| Sep 29, 2022 at 21:11 | history | asked | ABIM | CC BY-SA 4.0 |