This is a question in which I think I am missing some key information. When discussing Naive Bayes, I've noticed that lecturers typically say that we really want is $p(y|x)$ (label given features), but that this becomes infeasible once $x$ is high-dimensional (since we won't observe many examples of $y$ for each specific instance of $x$). This is also what is stated in the Wikipedia article on Naive Bayes. Because of this, we use Bayes Rule to turn the problem on its head and estimate a generative model, and then use the "naive" assumption of feature independence given the class.
However, models such as linear regression and k-nearest neighbors do this just fine, albeit with the assumptions of neighboring points belonging to the same class (kNN) or with some linear relationship in the parameters (lin. reg.). This seems to contradict the general statement that estimating $p(y|x)$ becomes infeasible. Somethings missing?
Is it that the discussion of $p(y|x)$ in the context of Naive Bayes assumes Bernoulli/multinoulli distributions, for which the MLE is indeed sparse in this case? But that they leave out this information?