- 主动学习在层次聚类中的应用
本研究通过对树叶对之间的相似度进行主动学习,研究树的层次聚类过程。 在实现的情况下,我们提供了完全重构树切割所需的查询数量的完整特征描述。 在非实现的情况下,我们依赖于已知的重要抽样过程来获得后悔和查询复杂度界限。 我们的算法具有对统计误差 - 子空间攻击:利用有前途的子空间进行查询高效黑盒攻击
本文介绍如何在黑箱攻击中利用参考模型的梯度来降低查询复杂度,提高黑箱攻击的效率和成功率,实验结果表明,与现有技术相比,本文提出的方法可以在查询数量上获得 2x 到 4x 的降低,并且具有更低的失败率。
- 基于 Hessian 感知的零阶优化黑盒对抗攻击
本文提出了一个基于 Hessian 矩阵的零阶优化算法 ZO-HessAware,用于黑盒对抗攻击,该算法的实验证明在结构化 Hessian 逼近的情况下,具有更好的零阶收敛率和查询复杂度。
- MM面向查询高效的黑盒攻击:一种无输入视角
本文提出了一种名为 “无需输入” 的攻击方法,用于深度神经网络的对抗攻击,该方法不需要进行大量的查询,可以通过任意图像添加可以感知的扰动来生成对抗性图像。该方法通过灰度图像的初始化和局部扰动与平铺技术来显着降低了查询复杂度,并成功击败了 C - 具近似最优适应性和查询复杂度的非单调次模最大化
研究分布式情况下近似最大化非单调子模函数时算法适应性和查询复杂度的方法及其应用
- AAAI使用少量查询合理分配多种货物
研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足 envy-freeness 最多一个 good (EF1) 的分配,并且这个 logarithmic 查询复杂性界限也适用于 - 具有近似最优的适应性和查询复杂度的子模最大化
本文研究自适应子模型优化的适应性和查询复杂度,提出了适用于最大基数约束的单调子模型函数的分布式算法,并将其推广到子模型覆盖问题。
- MM从最佳反应查询中学习凸分割和计算博弈论均衡
给定一个划分成 $n$ 个具有不同标签和内部不相交的凸区域的 $m$- 单纯形,可通过查询了解任何点的标签,本文提出了两种算法:CD-GBS 和 CR-GBS,并通过 Kakutani 的不动点定理证明了这些算法在计算近似均衡时提供了较佳的 - 四个代理人的改进无嫉妒蛋糕切割协议
本文研究了四个代理人的经典切蛋糕问题,提出了一种更简单并且运算复杂度比之前的算法低 3.4 倍的改进算法。
- NIPS半监督聚类的松弛预测
本研究讨论了半监督聚类中 “同簇” 查询的弱监督方法,并提出了一种处理不确定响应的有效算法。实验显示,我们的方法在克服监督不确定性和产生高质量聚类方面非常有效。
- 带侧信息的聚类查询复杂度
研究交互聚类的查询复杂度和相似度矩阵的信息理论下界及上界,证明相似度矩阵可以显著降低查询复杂度,在不知道 $k,f_+ 和 f_-$ 的前提下,算法高效且参数免费,并揭示其与常见社区检测模型的关联。
- 基于比较的选择
研究对比选择函数的查询复杂性和距离对比选择函数,并且指出任何一维比较选择函数都可以像基本的最大或最小选择函数一样高效地推断出来,这表明选择集效应不需要推断任何基本的算法障碍。
- 蛋糕切割的查询复杂度
研究的是蛋糕切割问题的询问复杂度,同时给出了计算近似无嫉妒、完美和公平分配的下限和上限,其中下限在计算 n=3 个玩家之间的连通无嫉妒分配以及 n=2 个玩家之间的完美和公平分配方面非常紧密,还阐明了移动刀具程序的形式化方法,并证明了这个大 - MM使用比较查询进行主动分类
研究一种扩展主动学习的方法,其中学习算法可以要求注释者比较两个示例与其标签类边界的距离,并使用半空间的框架展示这种方法的优越性。
- 使用横向磁场的 Grover 无结构搜索的近最优量子电路
为了寻找一根稻草,我们提出了一种基于电路的量子算法,该算法通过周期性地在系统中交替应用问题哈密顿量(oracle)和横向场来实现,使用自旋相干态分析复合幺正矩阵,在初始状态和目标状态之间进行了高度重叠的状态转换,并提示了了解 QAOA 电路 - 公平分配
研究分配问题,引入社交网络模型,通过局部比例和局部嫉妒性的概念,使用单人切割模型确定图形结构和嫉妒性代价下的最大效用分配。
- AAAI竞赛方案的查询复杂度
本文研究在仅查询尽可能少的边的情况下找到锦标赛的最佳顶点集合的问题,并给出了 Condorcet 非输家集合的计算方法,并证明了任何找到 Copeland 集合,Slater 集合,Markov 集合,双方集合,未覆盖集合,Banks 集合 - NIPS通过不完美标注者进行主动学习
研究活动学习的算法,其中标签器不仅可以返回不正确的标签,还可以放弃标记,利用放弃响应提出的算法在噪声和放弃率的自然假设下分析了其统计一致性和查询复杂度,并与下限相结合,证明在某些技术条件下,它实现了近乎最佳的查询复杂度 。
- 量子比特化算法进行的哈密顿模拟
本文介绍了一种使用 unitary oracle 和 qubitization 方法进行哈密顿模拟的算法,其中 qubitization 将任何哈密顿量编码到不变的 SU (2) 子空间中,并给出了 e^{-iHt} 等复合算子的查询复杂度 - 量子信号处理实现最优哈密尔顿模拟
通过简单的单量子比特旋转,优雅地提供了哈密顿模拟的一种最优算法,用以理解和设计许多量子算法,特别是物理系统的模拟。