研究如何在噪音下进行有效的学习,在保证计算效率的前提下设计了一种主动学习算法,并根据半空间的结构进行加权和风险最小化等方法的技术优化,解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。
Jun, 2020
我们研究了在分布无关的对抗性健壮 PAC 模型中半空间的计算复杂度,重点研究了 L_p 扰动。我们提出了一种计算有效的学习算法和一种几乎匹配的计算难度结果。我们发现的一个有趣的含义是,L_∞扰动的情况被证明比 2≤p<∞的情况更加计算上困难。
Jul, 2020
本文介绍了一种 Perceptron-like 在线主动学习算法,能够以近乎最优的标签复杂度和样本复杂度下,学习噪声容限在总概率最多为 ν,样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况,不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下,支持 5 罕见的瑕疵。
Dec, 2020
通过设计基于非凸优化的算法,本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题,其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。
Oct, 2023
本文首次提出了针对在 Tsybakov 噪声情况下 PAC 学习均匀半空间的可行的多项式时间算法,并且证明了该算法对于如对称型对数凹分布之类的广泛应用的分布成功率显著
Oct, 2020
研究分布无关的半空间在 Massart 噪声下的拟准确性学习问题,给出了一个计算复杂度为多项式时间且误分类错误率为 η+ε 的算法。
Jun, 2019
研究学习理论中使用的统计查询模型在学习含有 Massart 噪声的 Halfspaces 时的有效性,并证明了已知的算法与最优界的差距,解决了一个学习理论中长期存在的难题。
本文提供了一个计算有效的算法,用于解决高维空间中的 PAC 主动学习问题,其中数据遵循某些分布假设,该算法在少量的标记查询下使用稀疏的半空间学习,能够达到 O(t polylog(d,1/ϵ))的标记复杂度。
May, 2018
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
研究学习同质半空间的非说服学派问题,证明对于一类结构化分布,包括对数凹分布,在误分类误差 O(opt)+eps 下,非凸 SGD 有效地收敛到解决方案。相比之下,证明优化任何凸代理本质上会导致 ω(opt)的误分类误差,即使在高斯边际分布下。