We consider the problem of stochastic convex optimization under convex
constraints. We analyze the behavior of a natural variance reduced proximal
gradient (VRPG) algorithm for this problem. Our main result is a non-asymptotic
guarantee for VRPG algorithm. Contrary to minimax worst case guarantees, our
result is instance-dependent in nature. This means that our guarantee captures
the complexity of the loss function, the variability of the noise, and the
geometry of the constraint set. We show that the non-asymptotic performance of
the VRPG algorithm is governed by the scaled distance (scaled by $\sqrt{N}$)
between the solutions of the given problem and that of a certain small
perturbation of the given problem -- both solved under the given convex
constraints; here, $N$ denotes the number of samples. Leveraging a
well-established connection between local minimax lower bounds and solutions to
perturbed problems, we show that as $N \rightarrow \infty$, the VRPG algorithm
achieves the renowned local minimax lower bound by H\`{a}jek and Le Cam up to
universal constants and a logarithmic factor of the sample size.

通过分析局部最小值下界与扰动问题解的关系，我们证明了方差减小的近端梯度算法在样本数量趋向无穷大时达到了局部最小值下界，除了普适常数和对数因子的样本大小外。