Local differential privacy (LDP) is a model where users send privatized data\nto an untrusted central server whose goal it to solve some data analysis task.\nIn the non-interactive version of this model the protocol consists of a single\nround in which a server sends requests to all users then receives their\nresponses. This version is deployed in industry due to its practical advantages\nand has attracted significant research interest. Our main result is an\nexponential lower bound on the number of samples necessary to solve the\nstandard task of learning a large-margin linear separator in the\nnon-interactive LDP model. Via a standard reduction this lower bound implies an\nexponential lower bound for stochastic convex optimization and specifically,\nfor learning linear models with a convex, Lipschitz and smooth loss. These\nresults answer the questions posed in \\citep{SmithTU17,DanielyF18}. Our lower\nbound relies on a new technique for constructing pairs of distributions with\nnearly matching moments but whose supports can be nearly separated by a large\nmargin hyperplane. These lower bounds also hold in the model where\ncommunication from each user is limited and follow from a lower bound on\nlearning using non-adaptive \\emph{statistical queries}.\n