ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let F\mathcal{F} be a classifier family and let D\mathcal{D} be a distribution. For independent train sets S1,S2∼DnS_1,S_2\sim\mathcal{D}^n, let f1,f2f_1,f_2 be classifiers trained on S1,S2S_1,S_2, respectively. The test accuracy is the probability that f1(x)=yf_1(x)=y, while the agreement property. For certain classifier families F\mathcal{F} and distributions D\mathcal{D}, these probabilities are approximately equal:

Pr⁡[f1(x)=y]≈Pr⁡[f1(x)=f2(x)].\Pr[f_1(x)=y]\approx\Pr[f_1(x)=f_2(x)].

Moreover, with high probability over the trained classifiers f1,f2f_1,f_2, the corresponding probabilities over (x,y)∼D(x,y)\sim\mathcal{D} are approximately equal. This is proposed as an instantiation of the paper's indistinguishability conjecture; it is provable for 1-nearest neighbors in some settings, but the general claim's resolution is not specified.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.