强健在线学习的最优性
本文研究任意函数类和一般损失的在线回归问题,并确定了最小极大率。结果表明,当函数类的复杂度低于某一阈值时,最小极大率取决于损失函数的曲率和序列复杂度。而当复杂度高于该阈值时,损失的曲率不再影响率。此外,对于平方损失,当顺序和独立同分布的经验熵匹配时,统计和在线学习的速率相同。我们还提供了一种通用的预测器,它具有确定的最优率,并提供了一种设计在线预测算法的方法,用于某些问题可以是计算量有效的。
Jan, 2015
本文考虑在再生核希尔伯特空间中的非规则化在线学习算法,给出了分类的显式收敛速率以及对于一般损失函数的非规则化成对学习算法的首次收敛性证明和收敛速率。
Mar, 2015
本文将扩展反推理论以解决在线学习中的回归问题,提出了两种弱学习算法模型,并提出一种在线梯度推进算法将弱学习算法转化为强学习算法,同时介绍了一种更简单的反推算法,并证明了其最优性。
Jun, 2015
我们提出了一种新颖的扩散方案,用于在网络上进行基于内核的在线学习,通过使用Random Fourier Features,将解决方案近似为固定大小的向量,并提供了渐近收敛和网络遗憾的限制条件。
Mar, 2017
本文研究了无正则化的RKHS在线梯度下降算法的收敛性和收敛速率条件,探讨了平均迭代和最后一次迭代的过度泛化误差和收敛速率,首次提出了无强凸性的 online gradient descent 的高概率收敛速率。
Aug, 2017
该研究提出了一种新型算法框架用于在线学习的模型选择,通过采用随机演出的基于新型算法框架的“多尺度”算法进行预测,可以在最小结构假设下,获得在线模型选择预言不等式,实现了一种通用的元算法框架,并进一步为矩阵类、非嵌套凸集等特殊模型提供了新的预言不等式。
Dec, 2017
本文研究了在线情况下健壮线性回归问题,提出了一种基于随机梯度下降方法和L1损失函数的高效算法,能够在存在污染数据情况下有效检测和去除异常值,算法复杂度与污染比例相关。
Jul, 2020
在线学习设置下,研究了在两个无限维希尔伯特空间之间的线性运算符学习问题。通过证明定理,得出了具有统一有界p-Schatten范数的线性运算符类是可在线学习的,但具有统一有界操作符范数的线性运算符类是不可在线学习的结论。同时,通过识别出一类有界线性运算符,证明了在线统一收敛和学习性之间的差异。最后,证明了上述的不可学习性结果和统一收敛性与学习性之间的差异性在agnostic PAC设置下仍然成立。
Sep, 2023
我们研究具有Lipschitz损失的无约束在线线性优化问题,提出一种新的连续时间启发式算法,通过连续时间模型和离散时间对偶的方式实现渐进的梯度自适应和比较器范数自适应,克服了传统方法中梯度方差的缺陷并消除了未知Lipschitz常数的问题。
Sep, 2023