该研究证明了最小二乘(OLS)估算器在从单个观察轨迹中识别线性动态系统方面达到了几乎最小化最优性能。
Feb, 2018
我们提出了一个针对普通最小二乘问题的样本和时间高效的差分隐私算法,误差线性依赖于维度并且与 $X^ op X$ 的条件数无关,其中 $X$ 是设计矩阵。我们的算法具有接近最优的准确性保证,适用于具有有限统计杠杆率和有界残差的任何数据集。
Apr, 2024
本文介绍了一种有效且实用的在线预测离散线性动态系统的算法,通过过参数化多项式对 LDS 的类别进行替代的方式,以获得损失函数的凸性,从而绕过了非凸最优化问题,并基于一种新颖的滤波技术进行了算法的构建。
Nov, 2017
本文提出了一种构建无偏估计器的普遍方法,使用自适应线性估计方程的思想,并建立渐近正常性的理论保证,以及实现接近最优渐近方差的讨论。
Jul, 2023
我们提出了一种新的校正方法 - 使用约束学习框架和 C-Learner 方法 - 来解决复杂干扰参数估计错误,并在多个数据集上进行实证分析,展示了其在因果估计中的高效性和性能优势。
May, 2024
我们证明了随机梯度下降算法可以高效地收敛于未知线性时不变动态系统的极大似然目标函数的全局极值。虽然该目标函数是非凸的,但我们在强但自然的假设下提供了多项式运行时间和样本复杂度界限。尽管线性系统识别已经研究了许多年,但据我们所知,这是我们所考虑的问题的第一个多项式保证。
Sep, 2016
该篇论文研究了使用线性模型描述随机动态的网络 (有向图) 的学习问题,并证明了在较高采样率的情况下,利用 $\ell_1$- 正则化最小二乘算法可以高效地推断出稀疏网络结构。
Nov, 2010
本文提出了一种在数据为超收缩分布、存在不可避免的敌对噪声情况下,基于平方和框架的线性模型学习算法,该算法的收敛速度与扰动的比例成幂率关系,能达到理论最优收敛速度且在先前研究中未被发现。
Jun, 2020
该研究针对不稳定线性系统的参数识别问题进行了研究,建立了针对重尾噪声分布和转移矩阵的一类较大误差最小二乘估计的有限时间界限,并与问题维度和真实转移矩阵的关键特征及噪声分布函数的性质相关联,并使用随机矩阵和鞅差序列的适当浓度不等式来实现这些结果。
Oct, 2017
研究了最小二乘线性回归的问题,其中数据点依赖于并从马尔可夫链中采样。在不同的噪声设置下,建立了关于底层马尔可夫链混合时间 $\tau_{mix}$ 的尖锐信息理论极小值下界来解决此问题。我们发现,与独立数据的优化相比,具有马尔可夫数据的优化通常更加困难,一个只在大约 $ ilde {\Theta}(\tau_{mix})$ 个样本中工作的平凡算法 (SGD-DD) 是极小化最优的。此外,我们还研究了实践中出现的结构化数据集,例如高斯自回归动态,它们能否拥有更高效的优化方案。令人惊讶的是,即使在这个特定的自然环境下,具有一定步长的随机梯度下降法与常数并没有比 SGD-DD 算法更好。相反,我们提出了一种基于体验复盘的算法 —— 一种流行的强化学习技术 —— 它可以实现更好的误差率。我们的改进速率是第一个在有趣的马尔可夫链上优于 SGD-DD 的算法之一,也为在实践中支持使用经验回放提供了首个理论分析。