# Generalization bound for parameters rather than loss functions

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:

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

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.

• 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) May 21, 2021 at 13:48
• 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". May 23, 2021 at 7:49
• 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? May 24, 2021 at 11:16
• The MLE only makes sense in the parametric case. May 24, 2021 at 11:19
• Agreed. How about for the regression function estimation? In either parametric or the non-parametric case, I'm looking for case studies. 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? May 24, 2021 at 11:46