Stochastic gradient descent (SGD) is a popular algorithm for optimization\nproblems arising in high-dimensional inference tasks. Here one produces an\nestimator of an unknown parameter from independent samples of data by\niteratively optimizing a loss function. This loss function is random and often\nnon-convex. We study the performance of the simplest version of SGD, namely\nonline SGD, from a random start in the setting where the parameter space is\nhigh-dimensional.\n We develop nearly sharp thresholds for the number of samples needed for\nconsistent estimation as one varies the dimension. Our thresholds depend only\non an intrinsic property of the population loss which we call the information\nexponent. In particular, our results do not assume uniform control on the loss\nitself, such as convexity or uniform derivative bounds. The thresholds we\nobtain are polynomial in the dimension and the precise exponent depends\nexplicitly on the information exponent. As a consequence of our results, we\nfind that except for the simplest tasks, almost all of the data is used simply\nin the initial search phase to obtain non-trivial correlation with the ground\ntruth. Upon attaining non-trivial correlation, the descent is rapid and\nexhibits law of large numbers type behavior.\n We illustrate our approach by applying it to a wide set of inference tasks\nsuch as phase retrieval, and parameter estimation for generalized linear\nmodels, online PCA, and spiked tensor models, as well as to supervised learning\nfor single-layer networks with general activation functions.\n