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

研究了 SGD 算法在高维参数空间下最简单在线版本的性能，通过对样本数量的阈值来确定参数估计的一致性，其阈值是多项式维度的，取决于信息指数。

高维推断中的非凸损失在线随机梯度下降

Online stochastic gradient descent on non-convex losses from  high-dimensional inference

We consider the problem of estimating the graph associated with a binary
Ising Markov random field. We describe a method based on $\ell_1$-regularized
logistic regression, in which the neighborhood of any given node is estimated
by performing logistic regression subject to an $\ell_1$-constraint. The method
is analyzed under high-dimensional scaling in which both the number of nodes
$p$ and maximum neighborhood size $d$ are allowed to grow as a function of the
number of observations $n$. Our main results provide sufficient conditions on
the triple $(n,p,d)$ and the model parameters for the method to succeed in
consistently estimating the neighborhood of every node in the graph
simultaneously. With coherence conditions imposed on the population Fisher
information matrix, we prove that consistent neighborhood selection can be
obtained for sample sizes $n=\Omega(d^3\log p)$ with exponentially decaying
error. When these same conditions are imposed directly on the sample matrices,
we show that a reduced sample size of $n=\Omega(d^2\log p)$ suffices for the
method to estimate neighborhoods consistently. Although this paper focuses on
the binary graphical models, we indicate how a generalization of the method of
the paper would apply to general discrete Markov random fields.

本文提出了一种基于 logistic 回归的方法来估计与二元 Ising 马尔可夫随机场相关联的图，并分析了该方法在高维情况下的表现，提出了一些充分条件，使其能够同时一致估计图中每个节点的邻域。