★ 3
梯度下降、镜像下降与 FTRL 的精确形式遗憾界
论文从几何角度刻画在线梯度下降、镜像下降与跟随正则化领导者（FTRL）在何种偏差下实现无遗憾。作者提出“精确性”作为统一原则：相关位移场由标量势生成，或等价地对应的一形式在算法所用几何中精确。精确性在温和正则条件下带来次线性遗憾，非零环流则导致线性遗憾。研究还引入保守相关均衡并刻画其与相关均衡的关…
arXiv cs.LG52 天前
#遗憾界
共 12 篇相关资讯，按重要度与时间排序，每 3 小时更新。
★ 2
arXiv 论文提出 DUET 算法：组合半赌博机基线保护与对抗鲁棒性兼得
该论文针对组合半赌博机问题提出 DUET（Doubling Under Empirical Tests）分阶段混合方案，通过两个可观测测试决定何时加倍学习权重与经验遗憾预算。算法在未知时间跨度、间隙和环境类型的情况下，同时实现基线遗憾对数级、对抗损失下 O(√T) 遗憾以及随机损失下的多对数遗憾。
arXiv cs.LG4 天前
★ 2
COCO 问题实现多对数约束违反与近优遗憾
论文研究带对抗性凸损失与约束的在线凸优化（COCO），提出结合连续 Hedge 与收缩可行集消除的在线策略。该策略在保持 O(√(T log T)) 遗憾的同时，将累积约束违反从多项式级降至 O(log²T)，核心工具是 Grünbaum 不等式与自适应学习率势函数。
arXiv cs.LG26 天前
★ 2
无投影在线凸优化的最优遗憾权衡
论文刻画了仅能访问精确线性优化预言机时在线凸优化可达到的遗憾界。在每轮预言机调用次数受限条件下，给出与维度无关的极小极大期望遗憾紧确刻画，并构造匹配算法。结果涵盖总预算与每轮严格限制两种情形。
arXiv cs.LG30 天前
★ 2
贪心采样实现无 Eluder 维依赖的上下文老虎机
论文研究 KL 正则化上下文老虎机在奖励与偏好反馈下的表现，证明贪心采样可获得对数遗憾且不显式依赖 eluder 维。研究还揭示贪心采样与置信上界式探索之间的权衡：KL 正则化越强，贪心采样优势越明显。
arXiv cs.LG47 天前
★ 2
对抗多臂老虎机切换遗憾最优解
论文研究对抗性多臂老虎机中比较臂序列最多切换 S 次的切换遗憾问题。当 S 未知时，此前在自适应对手下被证明无法达到最优界。本文提出单一算法在 oblivious 对手下对任意 S 均达到最优期望遗憾，解决了 Auer 等人 2019 年的公开问题。
arXiv cs.LG47 天前
★ 2
Meta-LinEXP3：对抗线性上下文赌博机元学习
论文针对随机动作集下的对抗线性上下文赌博机（ALCB）元学习空白，提出 Meta-LinEXP3 在线嵌套在线算法，从已完成任务构建可预测的任务级先验指导内层 LinEXP3。已知上下文分布时给出内在维度 O(√n) 的每任务遗憾界，未知分布时提出仅用过去的正则矩估计器。研究还建立先验精度与迁移遗…
arXiv cs.LG52 天前
★ 1
论文给出在线线性优化在 ℓp 球上的极小极大小损失界
研究单位 ℓp 球上全信息在线线性优化的遗憾界，提出 FTRL 算法在不知 T 与 Δ_T 的情况下达到 O_p(1+min{Δ_T^{1-1/p}, d^{1/2-1/p}√Δ_T}) 的界。匹配下界证明该速率对每个固定 p 都是极小极大的，且常数 (2+o(1))p/log p 在 p→∞ 时…
arXiv cs.LG4 天前
★ 1
arXiv 论文对比主动推理与 Bayes-UCBVI 的信息价值
论文将主动推理（AIF）与 Bayes-UCBVI 置于同一表格 MDP 框架下比较，发现 AIF 的信息增益衰减过快，无法作为置信宽度。作者提出用平方根校准信息增益得到 calibrated AIF，在精确抽象下达到 √T 级遗憾。当奖励由对手从智能体数据中选择时，校准信息增益作为奖励无关的 ℓ…
arXiv cs.LG17 天前
★ 1
重尾噪声下无参数区间动态遗憾界
论文研究每轮仅一个无偏随机次梯度的在线凸优化，噪声条件p阶矩未知（1<p≤2）。提出学习器在无需G、σ、p、区间I等参数的情况下，对任意固定长度区间达到区间动态遗憾上界，并保持均值梯度与噪声的不同指数。分析还给出保留全时域最优保证的学习器噪声幂次下界。
arXiv cs.LG27 天前
★ 1
Hadamard流形分布式在线优化的曲率无关遗憾界
论文研究Hadamard流形上的去中心化在线黎曼优化，针对horospherical凸函数放宽了此前对截面曲率下界的依赖。提出分布式黎曼在线梯度下降（D-ROGD），结合局部h-次梯度更新与隐式Fréchet均值共识，分别取得O(√T)与O(log T)的静态遗憾界，网络依赖仅由谱隙决定。这是首个…
arXiv cs.LG47 天前
★ 1
在线逆优化：O(d)遗憾的高效确定性算法
论文给出在线逆线性优化的确定性算法，遗憾为O(d)且每轮耗时O(d²)，是首个高效且proper的此类界。方法基于变量度量框架，加入自归一化秩一更新，并用迹幂tr(H^{-1/2})替代log det势函数以消除ln T项，同时给出抗腐坏与秩自适应变体及凸最小化应用。
arXiv cs.LG47 天前