<p>See our recent paper:
&quot;Non-parametric Binary regression in metric spaces with KL loss&quot;
<a href="https://arxiv.org/abs/2010.09886" rel="nofollow noreferrer">https://arxiv.org/abs/2010.09886</a></p>
<p>The setting is actually non-parametric and quite general. Our loss measures the expected log-likelihood -- which is more natural in the context of logistic regression than distance in parameter space. Notice that our loss is unbounded, as would be the <span class="math-container">$\ell_1$</span> or <span class="math-container">$\ell_2$</span> loss in parameter space.</p>

CC BY-SA 4.0
2021-05-21T13:48:51.323Z
Thanks! I'll certainly have a thorough look through your paper. Sort of felt like I'd landed in no-man's land, in that I'm used to seeing stats folks provide asymptotic guarantees for estimators (and associated losses), whereas CS folks provide non-asymptotic guarantees for risks. Was keen on getting a feel for the stats literature on non-asymptotic guarantees for parameters/ estimators. Could you suggest any umbrella topics/ references that tackle this? Also can your results translate to say the l-1 norm deviation? I'm interested in l-1/l-2 norms due to their natural geometric flavour(s)
kd212149
CC BY-SA 4.0
2021-05-23T07:49:42.213Z
There aren't really two natural objects whose $\ell_1$ distance you'd want to bound. Our model $h:X\to[0,1]$ is an *agnostic model* of the underlying joint distribution -- meaning, we don't assume any "ground truth".
Aryeh
CC BY-SA 4.0
2021-05-24T11:16:33.950Z
I understand there is the power of generality in the agnostic set up. However, statisticians have always been interested in working in settings where some ground truth is assumed. For eg: The asymptotic properties of MLEs. Of course, from thereon model misspecification and agnostic settings are of obvious interest, Though I do feel having a grounding in theory for specific set ups is more than useful in its own right. Given that, wouldn't there be work on the non-asymptotic #s of MLEs (after all that's what logistic regression coefficients are)? How about errors in the regression functions?
kd212149
CC BY-SA 4.0
2021-05-24T11:19:54.837Z
The MLE only makes sense in the parametric case.
Aryeh
CC BY-SA 4.0
2021-05-24T11:46:16.097Z
Agreed. How about for the regression function estimation? In either parametric or the non-parametric case, I'm looking for case studies. http://www.stat.cmu.edu/~larry/=sml/nonparclass.pdf (See Theorem 1 on pg. 2) - Are there specific classes of models for which the non-asymptotic error rate has been (near) sharply characterised for the "middle term", i.e., P(|m(x)-\hat{m(x)}|) (over dP_{x})? Any resources you could point me to for this?
kd212149
CC BY-SA 4.0
2021-05-21T08:43:27.187Z
2021-05-21T08:43:27.187Z
Aryeh
<p>I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and the estimated parameters for model classes such as that comprising of logistic regressions? As an example corresponding to linear regression, see below:</p>
<p><a href="https://i.sstatic.net/YfTqN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/YfTqN.png" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/6hQoH.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/6hQoH.png" alt="enter image description here" /></a></p>
<p>For the full proof of the aforementioned example see Thm. 2.2 on pgs 36 and 37 here: <a href="https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/MIT18_S997S15_CourseNotes.pdf" rel="nofollow noreferrer">https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/MIT18_S997S15_CourseNotes.pdf</a>. I think this is a special case because they're able to make use of linearity and sub-gaussian assumptions. I was wondering if a similar bound could be obtained for Logistic Regression parameters, or alternatively, are there any other classification models for which similar results could be obtained?</p>
<p>I know learning theory gives us risk bounds. Are there certain settings wherein those risk bounds translate to bounds on the deviations in estimated and true parameters? Saw a similar (but more specific) question in math stackexchange without any answers: <a href="https://math.stackexchange.com/questions/3846492/generalization-error-in-logistic-regression">https://math.stackexchange.com/questions/3846492/generalization-error-in-logistic-regression</a>. Is this simply impossible to ask for in the agnostic setting for general model classes? Can we hope to get such results for specific model classes, under specific assumptions (eg: the parameter space being compact)? Any related literature? Any insights would be appreciated.</p>
<p>P.S: I don't mean the number-of-iteration based bounds obtained in optimization settings, i.e. computation error, here I am referring to estimation error</p>

<machine-learning><lg.learning><st.statistics><vc-dimension><pac-learning>
Generalization bound for parameters rather than loss functions
kd212149
# Generalization bound for parameters rather than loss functions

(Asked by: username_0 on 2021-05-21)

I was wondering if it is possible to obtain high probability bounds (provided finite sample size of the training data) for the distance (say in the l-1 or l-2 norm) between the best parameter set and the estimated parameters for model classes such as that comprising of logistic regressions? As an example corresponding to linear regression, see below:

[![enter image description here](https://i.sstatic.net/YfTqN.png)](https://i.sstatic.net/YfTqN.png)

[![enter image description here](https://i.sstatic.net/6hQoH.png)](https://i.sstatic.net/6hQoH.png)

For the full proof of the aforementioned example see Thm. 2.2 on pgs 36 and 37 here: <https://ocw.mit.edu/courses/mathematics/18-s997-high-dimensional-statistics-spring-2015/lecture-notes/MIT18_S997S15_CourseNotes.pdf>. I think this is a special case because they're able to make use of linearity and sub-gaussian assumptions. I was wondering if a similar bound could be obtained for Logistic Regression parameters, or alternatively, are there any other classification models for which similar results could be obtained?

I know learning theory gives us risk bounds. Are there certain settings wherein those risk bounds translate to bounds on the deviations in estimated and true parameters? Saw a similar (but more specific) question in math stackexchange without any answers: <https://math.stackexchange.com/questions/3846492/generalization-error-in-logistic-regression>. Is this simply impossible to ask for in the agnostic setting for general model classes? Can we hope to get such results for specific model classes, under specific assumptions (eg: the parameter space being compact)? Any related literature? Any insights would be appreciated.

P.S: I don't mean the number-of-iteration based bounds obtained in optimization settings, i.e. computation error, here I am referring to estimation error

**Tags:** machine-learning, lg.learning, st.statistics, vc-dimension, pac-learning


---

## 1 answers

### Answer by username_1 on 2021-05-21. Score: 0

See our recent paper:
"Non-parametric Binary regression in metric spaces with KL loss"
<https://arxiv.org/abs/2010.09886>

The setting is actually non-parametric and quite general. Our loss measures the expected log-likelihood -- which is more natural in the context of logistic regression than distance in parameter space. Notice that our loss is unbounded, as would be the $\ell\_1$ or $\ell\_2$ loss in parameter space.

> **Comments:**
> **username_0**: Thanks! I'll certainly have a thorough look through your paper. Sort of felt like I'd landed in no-man's land, in that I'm used to seeing stats folks provide asymptotic guarantees for estimators (and associated losses), whereas CS folks provide non-asymptotic guarantees for risks. Was keen on getting a feel for the stats literature on non-asymptotic guarantees for parameters/ estimators. Could you suggest any umbrella topics/ references that tackle this? Also can your results translate to say the l-1 norm deviation? I'm interested in l-1/l-2 norms due to their natural geometric flavour(s)  
> **username_1**: There aren't really two natural objects whose $\ell_1$ distance you'd want to bound. Our model $h:X\to[0,1]$ is an *agnostic model* of the underlying joint distribution -- meaning, we don't assume any "ground truth".  
> **username_0**: I understand there is the power of generality in the agnostic set up. However, statisticians have always been interested in working in settings where some ground truth is assumed. For eg: The asymptotic properties of MLEs. Of course, from thereon model misspecification and agnostic settings are of obvious interest, Though I do feel having a grounding in theory for specific set ups is more than useful in its own right. Given that, wouldn't there be work on the non-asymptotic #s of MLEs (after all that's what logistic regression coefficients are)? How about errors in the regression functions?  
> **username_1**: The MLE only makes sense in the parametric case.  
> **username_0**: Agreed. How about for the regression function estimation? In either parametric or the non-parametric case, I'm looking for case studies. http://www.stat.cmu.edu/~larry/=sml/nonparclass.pdf (See Theorem 1 on pg. 2) - Are there specific classes of models for which the non-asymptotic error rate has been (near) sharply characterised for the "middle term", i.e., P(|m(x)-\hat{m(x)}|) (over dP_{x})? Any resources you could point me to for this?  

---

