When the nonconvex problem is complicated by stochasticity, the sample
complexity of stochastic first-order methods may depend linearly on the problem
dimension, which is undesirable for large-scale problems. In this work, we
propose dimension-insensitive stochastic first-order methods (DISFOMs) to
address nonconvex optimization with expected-valued objective function. Our
algorithms allow for non-Euclidean and non-smooth distance functions as the
proximal terms. Under mild assumptions, we show that DISFOM using minibatches
to estimate the gradient enjoys sample complexity of $ \mathcal{O} ( (\log d) /
\epsilon^4 ) $ to obtain an $\epsilon$-stationary point. Furthermore, we prove
that DISFOM employing variance reduction can sharpen this bound to $\mathcal{O}
( (\log d)^{2/3}/\epsilon^{10/3} )$, which perhaps leads to the best-known
sample complexity result in terms of $d$. We provide two choices of the
non-smooth distance functions, both of which allow for closed-form solutions to
the proximal step. Numerical experiments are conducted to illustrate the
dimension insensitive property of the proposed frameworks.

非凸优化中采用维度无关的随机一阶方法 (DISFOM) 来解决样本复杂度问题，使用小批量估计梯度以达到 ε- 稳定点的样本复杂度为 O ((log d) / ε^4)，进一步利用方差缩减可将该界限提高至 O ((log d)^(2/3) / ε^(10/3))，并提供了两种非平滑距离函数的选择，数值实验验证了所提框架的维度无关性。