Let $x\in R^d$ be feature vector, and $y\in\{0,1\}$ be label generated as $P(y=1| x) = 1/(1+\exp(-\theta^\top x))$. Assuming we have oracle access to this joint distribution, i.e., for any feature vector $x$ we can draw $P(y=1|x)$, what is the optimal sampling complexity in order to estimate $\theta$? More specifically, if we want to estimate $\theta$ up to some error $\epsilon$ with high probability, what is the minimum number of samples $N$ needed, if we are allowed to query labels for any arbitrary feature vector?

  • 1
    $\begingroup$ if you know $P(y=1|X)$ you must know $\theta$ or can reverse engineer it so I'm not clear on the premise of the question. $\endgroup$ May 2 '21 at 12:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.