We develop and analyze stochastic optimization algorithms for problems in
which the expected loss is strongly convex, and the optimum is (approximately)
sparse. Previous approaches are able to exploit only one of these two
structures, yielding an $\order(\pdim/T)$ convergence rate for strongly convex
objectives in $\pdim$ dimensions, and an $\order(\sqrt{(\spindex \log
\pdim)/T})$ convergence rate when the optimum is $\spindex$-sparse. Our
algorithm is based on successively solving a series of $\ell_1$-regularized
optimization problems using Nesterov's dual averaging algorithm. We establish
that the error of our solution after $T$ iterations is at most
$\order((\spindex \log\pdim)/T)$, with natural extensions to approximate
sparsity. Our results apply to locally Lipschitz losses including the logistic,
exponential, hinge and least-squares losses. By recourse to statistical minimax
results, we show that our convergence rates are optimal up to multiplicative
constant factors. The effectiveness of our approach is also confirmed in
numerical simulations, in which we compare to several baselines on a
least-squares regression problem.

研究了基于 Nesterov 的对偶平均算法的随机优化算法，在预期损失是强凸的且最优解是（近似）稀疏的问题上进行优化，证明了在局部 Lipschitz 损失下，在 T 轮迭代后，我们的解决方案的误差最多为 O（（slogp）/T），并确立了我们的收敛率是最佳的，且在数值模拟中通过对最小二乘回归问题进行几个基准线的比较，证实了我们方法的有效性。