Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
Tight High Probability Bounds for Linear Stochastic Approximation with Fixed Stepsize
复制标题
DOI：
--
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Alain Durmus;É. Moulines;A. Naumov;S. Samsonov;Kevin Scaman;Hoi-To Wai
中科院分区：
文献类型：
--
作者：
Alain Durmus;É. Moulines;A. Naumov;S. Samsonov;Kevin Scaman;Hoi-To Wai
本文给出了固定步长线性随机逼近算法的非渐近分析。这一系列方法出现在许多机器学习任务中，用于获得线性系统$\bar{A}\theta = \bar{b}$的近似解，其中$\bar{A}$和$\bar{b}$只能通过随机估计$\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$访问。我们的分析是基于关于矩阵乘积的矩和高概率界的新结果，这些结果被证明是紧密的。我们在序列$\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$上较弱的条件下推导出LSA性能的高概率界。然而，相比之下，我们建立了多项式浓度界，其顺序取决于步长。我们表明，如果没有对随机矩阵$\{{\bf A}_n: n \in \mathbb{N}^*\}$序列的额外假设，我们的结论就不能得到改进，特别是高斯或指数高概率界不能成立。最后，我们特别注意建立与迭代次数和步长有关的有明显顺序的边界，其前导项包含出现在中心极限定理中的协方差矩阵。
This paper provides a non-asymptotic analysis of linear stochastic approximation (LSA) algorithms with fixed stepsize. This family of methods arises in many machine learning tasks and is used to obtain approximate solutions of a linear system $\bar{A}\theta = \bar{b}$ for which $\bar{A}$ and $\bar{b}$ can only be accessed through random estimates $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$. Our analysis is based on new results regarding moments and high probability bounds for products of matrices which are shown to be tight. We derive high probability bounds on the performance of LSA under weaker conditions on the sequence $\{({\bf A}_n, {\bf b}_n): n \in \mathbb{N}^*\}$ than previous works. However, in contrast, we establish polynomial concentration bounds with order depending on the stepsize. We show that our conclusions cannot be improved without additional assumptions on the sequence of random matrices $\{{\bf A}_n: n \in \mathbb{N}^*\}$, and in particular that no Gaussian or exponential high probability bounds can hold. Finally, we pay a particular attention to establishing bounds with sharp order with respect to the number of iterations and the stepsize and whose leading terms contain the covariance matrices appearing in the central limit theorems.