The problem of least squares regression of a $d$-dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded constraint set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit $O(1/k)$ upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the constraint set. We show that the variance term dominates the error and decreases with rate $1/k$, while the term which is related to the size of the constraint set decreases with rate $\log k/k^2$. We then compare the asymptotic ratio $\rho$ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that $\rho\leq 4$ under some mild conditions for all $d\geq 1$. We further improve the upper bound by showing that $\rho\leq 4/3$ for the case of $d=1$ and unbounded parameter set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with $\rho\leq 4/3$ even for large $d$ in practice.

探讨使用随机梯度下降的加权迭代平均算法，对确定的不可知参数进行最小二乘回归，分析了其收敛速度和误差，并提出了一种新的算法，取得了更好的性能表现。

最小二乘回归加权平均投影随机梯度下降算法