Estimating Stochastic Linear Combination of Non-linear Regressions
  Efficiently and Scalably
  Recently, many machine learning and statistical models such as non-linear
regressions, the Single Index, Multi-index, Varying Coefficient Index Models
and Two-layer Neural Networks can be reduced to or be seen as a special case of
a new model which is called the \textit{Stochastic Linear Combination of
Non-linear Regressions} model. However, due to the high non-convexity of the
problem, there is no previous work study how to estimate the model. In this
paper, we provide the first study on how to estimate the model efficiently and
scalably. Specifically, we first show that with some mild assumptions, if the
variate vector $x$ is multivariate Gaussian, then there is an algorithm whose
output vectors have $\ell_2$-norm estimation errors of $O(\sqrt{\frac{p}{n}})$
with high probability, where $p$ is the dimension of $x$ and $n$ is the number
of samples. The key idea of the proof is based on an observation motived by the
Stein's lemma. Then we extend our result to the case where $x$ is bounded and
sub-Gaussian using the zero-bias transformation, which could be seen as a
generalization of the classic Stein's lemma. We also show that with some
additional assumptions there is an algorithm whose output vectors have
$\ell_\infty$-norm estimation errors of
$O(\frac{1}{\sqrt{p}}+\sqrt{\frac{p}{n}})$ with high probability. We also
provide a concrete example to show that there exists some link function which
satisfies the previous assumptions. Finally, for both Gaussian and sub-Gaussian
cases we propose a faster sub-sampling based algorithm and show that when the
sub-sample sizes are large enough then the estimation errors will not be
sacrificed by too much. Experiments for both cases support our theoretical
results.
  To the best of our knowledge, this is the first work that studies and
provides theoretical guarantees for the stochastic linear combination of
non-linear regressions model.
