Near-Optimal Procedures for Model Discrimination with Non-Disclosure Properties

Code

• github.com/ostrodmit/testing-without-recovery
  OfficialIn papernone★ 0

Abstract

Let _0,_1 R^d be the population risk minimizers associated to some loss :R^d ZR and two distributions P_0,P_1 on Z. The models _0,_1 are unknown, and P_0,P_1 can be accessed by drawing i.i.d samples from them. Our work is motivated by the following model discrimination question: "What sizes of the samples from P_0 and P_1 allow to distinguish between the two hypotheses ^*=_0 and ^*=_1 for given ^*\_0,_1\?" Making the first steps towards answering it in full generality, we first consider the case of a well-specified linear model with squared loss. Here we provide matching upper and lower bounds on the sample complexity as given by \1/^2,r/\ up to a constant factor; here is a measure of separation between P_0 and P_1 and r is the rank of the design covariance matrix. We then extend this result in two directions: (i) for general parametric models in asymptotic regime; (ii) for generalized linear models in small samples (n r) under weak moment assumptions. In both cases we derive sample complexity bounds of a similar form while allowing for model misspecification. In fact, our testing procedures only access ^* via a certain functional of empirical risk. In addition, the number of observations that allows us to reach statistical confidence does not allow to "resolve" the two models - that is, recover _0,_1 up to O() prediction accuracy. These two properties allow to use our framework in applied tasks where one would like to identify a prediction model, which can be proprietary, while guaranteeing that the model cannot be actually inferred by the identifying agent.

Reproductions