Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms
复制标题
DOI：
--
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Guy Bresler;Prateek Jain;Dheeraj M. Nagaraj;Praneeth Netrapalli;Xian Wu
中科院分区：
文献类型：
--
作者：
Guy Bresler;Prateek Jain;Dheeraj M. Nagaraj;Praneeth Netrapalli;Xian Wu
我们研究了最小二乘线性回归问题，其中数据点是相依的，并且是从马尔可夫链中抽样的。在不同的噪声环境下，我们用马氏链的混合时间$\tau_{\mathsf{Mix}}$建立了该问题的精确信息论极小极大下界。我们的结果表明，一般而言，使用马尔可夫数据的优化比使用独立数据的优化要困难得多，而一个平凡算法(SGD-DD)在每个近似独立的$tide{\theta}(\tau_{\mathsf{Mix})$个样本中只有一个有效，是极小极大最优的。事实上，在独立数据设置的回归中，它严格优于流行的固定步长的随机梯度下降(SGD)方法，否则它是极小极大最优的。除了最坏的情况分析之外，我们还调查了实际中看到的结构化数据集(如高斯自回归动态)是否可以允许更有效的优化方案。令人惊讶的是，即使在这种特定和自然的背景下，固定步长的随机梯度下降(SGD)仍然不比SGD-DD好。相反，我们提出了一种基于经验重播的算法--一种流行的强化学习技术--实现了显著更好的错误率。我们改进的比率是算法在有趣的马尔可夫链上优于SGD-DD的第一个结果之一，也是支持在实践中使用经验回放的第一个理论分析之一。
We study the problem of least squares linear regression where the data-points are dependent and are sampled from a Markov chain. We establish sharp information theoretic minimax lower bounds for this problem in terms of $\tau_{\mathsf{mix}}$, the mixing time of the underlying Markov chain, under different noise settings. Our results establish that in general, optimization with Markovian data is strictly harder than optimization with independent data and a trivial algorithm (SGD-DD) that works with only one in every $\tilde{\Theta}(\tau_{\mathsf{mix}})$ samples, which are approximately independent, is minimax optimal. In fact, it is strictly better than the popular Stochastic Gradient Descent (SGD) method with constant step-size which is otherwise minimax optimal in the regression with independent data setting. Beyond a worst case analysis, we investigate whether structured datasets seen in practice such as Gaussian auto-regressive dynamics can admit more efficient optimization schemes. Surprisingly, even in this specific and natural setting, Stochastic Gradient Descent (SGD) with constant step-size is still no better than SGD-DD. Instead, we propose an algorithm based on experience replay--a popular reinforcement learning technique--that achieves a significantly better error rate. Our improved rate serves as one of the first results where an algorithm outperforms SGD-DD on an interesting Markov chain and also provides one of the first theoretical analyses to support the use of experience replay in practice.