破解对称性的复杂性
两个算法可以用于发起决策方法中两个被选备选方案的权重相等化的操纵攻击,在使用蒙特卡洛模拟的理论研究中展示了偏好矩阵的大小、不一致度和操纵的易程度之间的关系。
Mar, 2024
通过解决 Talagrand 的熵问题,我们证明了:每个有界函数类的 L_2 覆盖数都与其 shattering 维度成指数关系。这扩展了 Dudley 关于 {0,1} 函数类的定理,对于这些函数,shattering 维度是他们的 Vapnik-Chervonenkis 维度。在凸几何中,这意味着凸体 K 的熵可以由其坐标投影中包含的固定边长的立方体的最大维度控制。该理论有很多后续影响,包括 Elton 的最优定理以及实值情况下统计中心极限定理的估计。
Mar, 2002
该论文研究了基于过去互动中选择的备选方案,来学习用户偏好的任务,提出了一种基于 lexicographic preferences trees (LP-trees) 的偏好模型及学习算法,并研究了与该算法相关的复杂性问题,包括 LP-tree 的学习样本复杂度和在线性 LP-trees 类中计算最小经验风险的算法复杂度等。
Sep, 2022
基于二进制决策图的方法在多目标整数规划问题上取得了最先进的结果,本文提出了一种基于变量顺序的新颖参数配置空间,并通过监督学习方法找到了有效的变量顺序,以降低枚举时间。
Jul, 2023
该研究探讨在对抗鲁棒性的背景下,证明攻击 ReLU 分类器是 NP 难题,而在训练期间确保它们的稳健性则是 Σ2_P 难题,同时提出一种名为 Counter-Attack 的方法来证明抵御攻击的有效性。
Jun, 2023
本文介绍了 Goemans (2010) 的构造方法,使用其构造的 permutahedron 凸包作为优化问题的松弛形式可以将变量和约束的数量从 Θ(n^2) 减少到 Θ(nlogn)。我们将其应用于 2-SUM 问题的凸优化形式中,并引入了一种更简单的正则化方案。经实验证明,使用该方案可以获得与 Fogel 等人 (2013) 相似的结果,并且计算时间更短。
Jul, 2014
通过将排序模式表达为辫子排列的切片,并且发现所有辫子切片,包括那些未关联到展开模型的切片,都与一个排列的房间一一对应,从中鉴定关联到展开模型的切片,我们得出排序模式的数量,并给出了忽略排列差异时排序模式数量的上限。
Feb, 2010
通过最小值极大分析推导出在线学习算法来应对困难的学习问题,利用本地顺序 Rademacher 复杂性与相关算法实现更快速的在线学习,并引入随机化方法以及其他的方法来完善算法性能。
Apr, 2012
使用并改编拓扑学中的 Borsuk-Ulam 定理来推导对列表可复制和全局稳定学习算法的限制,在组合学和拓扑学中进一步展示了我们方法的适用性,并发现在无初始假设能力类设置下,列表可复制和全局稳定学习均不可能。
Nov, 2023