乘法加权算法家族的紧密下界
本文考虑了一种带有两位专家和一位预测者的预测问题,探讨了一种基于经典乘法权重算法的自适应乘法权重算法的近似最优性,并发现了恶意专家的价值函数的上下界,结果表明乘法权重算法无法抵制恶意专家的腐败。
Mar, 2020
本文研究了在对手设置下采用几何停止时间进行专家建议的预测经典问题。对于 2 个专家的情况,Cover 提出了最优算法。对于三个专家的情况,我们设计了最优算法和对手,并证明了该算法与一个特定的随机对手的概率匹配算法(类似于汤普森抽样)是最优的,该证明显示概率匹配算法不仅针对这个特定的随机对手是最优的,而且是极小化的。同时我们通过主对偶(primal-dual) 方法同时发展了上限和下限,并为任意数量的专家设计了最优算法和对手的通用框架。
Sep, 2014
给出一种用于学习 Markov 随机场(MRF)或无向图模型的简单的、乘性权重更新算法 ——Sparsitron 算法,特别适用于学习 t 阶 MRFs 结构,并具有近乎最优的样本复杂度和多项式的运行时间。同时,该算法还可以学习 Ising 模型上的参数,生成接近真实 MRF 的统计距离假设,并给出了学习稀疏广义线性模型(GLMs)的解决方案。
Jun, 2017
提出了 REX3 算法来解决多臂对决问题中对于选择一对臂进行相对反馈而不是绝对反馈的问题,算法具有 O (sqrt (K ln (K) T)) 的期望有限时间遗憾上界,同时提供了从信息检索应用程序中使用真实数据的实验结果。
Jan, 2016
应用聚合策略进行预测时,需要自适应调整学习速率以避免复杂度和当前损失率之间的分析难题;本文基于 Kalai 和 Vempala(2003)的 “Follow the Perturbed Leader”(FPL)算法,在两种不同的专家类别下得出了可调学习速率的损失界限,其中前者的损失界限与迄今为止最佳结果匹配,而后者为新结果。
Apr, 2005
奥贾算法是一个众所周知的在线算法,主要用于随机主成分分析的背景中。我们进行了一个简单但新颖的观察,即当应用于共享公共特征向量的任意对称矩阵序列时,并不一定是随机的,奥贾算法的遗憾可以直接以预测专家建议问题的众所周知的乘积权重更新方法的遗憾为界限。讨论了在 $ eals^n$ 上的单位球上具有二次形式的优化的几个应用。
Oct, 2023
本文介绍一种新的概念 —— 最大加权损失差异度(MWLD),并研究其与群体公平性和韧性的关系,最后使用不同的加权函数在四个公平领域的数据集上估计 MWLD,并显示 “损失方差正则化” 可使分类器的损失方差减半,从而降低 MWLD,而不会显著降低准确性。
Jun, 2019
本文提出了一种具有 O (log k) 开销的协作学习算法,改进了之前文献中 O (log^2 k) 开销的算法,同时证明了当 k 由假设类的 VC 维度多项式限制时,必须存在 Omega (log k) 的开销。此外,我们在实际数据集上的实验研究表明,我们的算法比 Blum 等人的算法优越。
May, 2018
该研究建立了 PAC 学习高维图模型与图结构计数和采样的新联系,使用在线学习框架,给出了新的样本复杂度界限以及面向树形和给定和弦骨架的贝叶斯网络的多项式样本和时间算法。
May, 2024