期刊
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
卷 62, 期 11, 页码 5974-5981出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TAC.2017.2705559
关键词
Convex optimization; empirical risk minimizer (ERM); projected stochastic gradient descent (SGD); weighted averaging
资金
- AFOSR MURI [FA 9550-10-1-0573]
- ONR [N00014-13-1-003]
- NSF [CNS-1161404]
- Cyber Security Research Center at Ben-Gurion University of the Negev
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 that is related to the size of the constraint set decreases with rate log k/k(2). We then compare the asymptotic ratio. 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 <= 4 for all d >= 1 when the random entries of the sensing vector are uncorrelated and identically distributed. We further improve the upper bound by showing that rho <= 4/3 for the case of d = 1 and unbounded parameter set when the random sensing entries are equal across time. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with rho <= 4/3 even for large d in practice.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据