贪心算法的逼近与学习
该研究使用 Chebyshev 贪心算法在 Banach 空间中构建基于给定字典的稀疏近似解,证明了收敛速率成 Lebesgue 型不等式的形式,适用于凸优化问题。
Dec, 2013
本论文证明具有低拟近似遗憾性质的学习算法在大类重复博弈中具有快速收敛到近似最优解的能力,包括使用基本对冲算法的算法。此外,作者对之前的结果进行了优化,并将该框架应用于动态人口博弈,并在大小和时间复杂度方面取得了改进。作者还提出了一种新的算法用于泊松回报任务,在效率和小损失方面都更有吸引力。
Jun, 2016
本文提出了两种基于随机梯度下降方法的可能非凸稀疏约束优化问题的贪心变体算法,证明了在指定容差范围内的期望收敛线性到解决方案。这种普适的框架适用于诸如压缩感知中的稀疏信号恢复、低秩矩阵恢复和协方差矩阵估计等问题,提供具有可证明的收敛保证的方法,通常优于其确定性对应物。我们还分析了仅能近似计算梯度和投影的情况,并证明了这些方法对这些近似是鲁棒的。我们包括许多数字实验,这些实验与理论分析相一致,并在多个不同的设置中展示这些改进。
Jul, 2014
该研究提出了一种贪心算法,Gradient Support Pursuit (GraSP),以近似任意形式损失函数的稀疏极小值,适用于稀疏逻辑回归等问题,算法性能通过在合成数据上的数值模拟进行评估。
Mar, 2012
探讨如何从函数族中选定合适的拟合函数,分析了已有的随机和确定性选取函数的方法,在提供额外信息的情况下可以成功的实现 $L_2$ 范数收敛,进一步阐述了这对于神经网络在建模和控制中的应用的含义。
Jun, 2015
本文提出一种基于一般价值函数逼近的强化学习算法,目的是建立一种没有对环境模型的显式假设的 RL 算法。如果价值函数能使用函数集合 F 近似,该算法将实现后悔界,为实际中使用的算法提供一个框架来证明其有效性。
May, 2020
通过选取最优的高斯过程先验,构建相应函数空间,提出的多个方法可以最小化某个函数的未知性,包括连续自适应边界算法和高斯过程基本概念,最优化方法如期望改进和随机搜索算法等。
Jan, 2011
本文介绍一种在线学习算法,该算法是收敛于再生核希尔伯特空间(RKHS)中的回归函数的正则化路径的顺序随机逼近。通过小心选择增益或步长序列,我们展示了可以生产出批量学习的最佳已知强收敛速率,并给出了弱收敛速率,其在文献中达到了最小化和个人较低速率的最优水平,并利用 Hilbert 空间中鞍点型不等式为鞍点型型不等式的马尔可夫过程推导出几乎肯定的收敛。通过类似于批量学习设置的偏差 - 方差分解,我们证明偏差包括沿正则化路径的逼近误差和漂移误差,这些误差显现了相同的收敛速率,而方差则来自样本误差,分析为反向鞍点型差分序列,上述速率通过偏差和方差之间的最佳折衷得到。
Mar, 2011