# Optimal sample complexity for logistic regression with oracle access

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?

• 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. May 2 '21 at 12:21