1
$\begingroup$

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

enter image description here

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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) $\endgroup$
    – kd212149
    May 21, 2021 at 13:48
  • $\begingroup$ 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". $\endgroup$
    – Aryeh
    May 23, 2021 at 7:49
  • $\begingroup$ 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? $\endgroup$
    – kd212149
    May 24, 2021 at 11:16
  • $\begingroup$ The MLE only makes sense in the parametric case. $\endgroup$
    – Aryeh
    May 24, 2021 at 11:19
  • $\begingroup$ 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? $\endgroup$
    – kd212149
    May 24, 2021 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.