- 一种用于快速相似搜索的双指标框架
我们提出了一种新的 “双度量” 框架,用于设计最近邻数据结构。我们的框架基于两个不相似性函数:一个准确但计算代价高的基准度量,和一个廉价但不太准确的代理度量。我们在理论和实践中展示了如何仅使用代理度量构建数据结构,使查询过程达到基准度量的准 - 自适应组合最大化:超过近似贪心策略
我们研究了自适应组合最大化问题,在机器学习中是一个核心挑战,并应用于主动学习以及其他许多领域。我们研究贝叶斯设置下,考虑最大化目标在基数约束和最小成本覆盖下。我们提供了新的综合近似保证,包括之前的结果,并且更加加强了它们。我们的近似保证同时 - 分布式基于配对次模函数的大于内存子集选择
通过提出一种新颖的分布式界限算法,并使用多轮基于分区的分布式贪心算法,此论文解决了子集选择问题,能够在没有或极小损失质量的情况下,找到高质量的子集。
- 通过决策树解读核聚类
探索可解释的核聚类算法,提出构建决策树来近似核 k-means 引发的分区的算法,并展示了适当选择特征如何在不损失可解释模型的近似保证的情况下保持可解释性。
- 无尺寸采样核心集用于分类
通过敏感采样框架,我们对用于分类问题的核心集进一步细化和泛化。这种核心集寻求输入数据的最小可能子集,以便可以在核心集上优化损失函数,并且能够保证与原始数据的逼近保证。我们的分析提供了首个维度无关的核心集,因此大小不依赖于维度。此外,我们的结 - 梯度下降训练的神经网络的近似结果
用梯度流训练具有近似保证的神经网络对目标进行测量,并在连续的带状 d 维单位球上用 L2 正规化,网络为全连接的常数深度和增加的宽度,基于神经切向核(NTK)对非凸倒数第二层的分析,呈现出欠参数化的状态以满足近似所需的自然平滑性假设。
- 协作异构多智能体强化学习的均场控制近似
本论文介绍了平均场控制理论(Mean field control)在解决包含 $N_{pop}$ 个异构 agents 的协作多智能体强化学习问题中的应用,提出了三个不同的情况,分别考虑了错误率有不同的误差上限。最后,提出一个基于 自然策略 - AAAI在人类协助下的分类
本研究旨在设计分类器,使其在不同的自动化水平下运行时具有最佳性能。我们提出了一种用于支持向量机的算法,它有近似保证,并对合成和现实数据进行了实验证明,说明在人类协助下,训练以不同自动化水平运行的管理学习模型可以优于全自动化的模型和单独操作的 - 具有容量限制的设施选址问题:算法和机制设计角度
在一维设置中考虑设施位置问题及算法和机制设计的视角。从算法设计的角度出发,证明了相应的优化问题是 NP 难问题,但是在限制设施数量或设施容量完全相同时可以在多项式时间内计算出最优解。从机制设计的角度出发,提出一些新方法提高了策略性,并且获得 - 非子模无约束最小化的最优逼近
该论文介绍了如何将亚模模函数最小化算法扩展到近似最小化非亚模函数并给出了理论保证。
- ICML超模极大化 —— 非非负性保证、快速算法和应用
本文研究次模函数的优化和算法问题,提出了一种在 $k$-cardinality 约束下最大化 $g-c$ 的算法,并通过实验设计对其进行了验证。
- 两层神经网络的平均场理论:无维界限和核极限
本文探讨利用随机梯度下降学习两层神经网络,将神经网络权重的演化近似为概率分布在 R^D 空间中的演化,从而得到概率分布的梯度流方程。我们分析了隐藏单元数量与数据规律性之间的相关性,扩展了此结果到无界激活函数的情况,将此结果应用到噪声随机梯度 - AAAI带有分割骨架约束的曲率有界函数贪心最大化
本研究探讨了确定性 GREEDY 算法在分区拟阵约束下的函数最大化问题中的性能,特别是对于非单调子模函数或单调半可加函数的贪心最大化问题给出了近似保证,并讨论了其在最大化行列式函数、有向图上的最大割问题和组合拍卖游戏等三个实际问题中的适用性 - 针对自适应对手的图形草图方法应用于最小度算法
研究使用图形草图和本地采样构建的数据结构来处理在消除过程中矩阵近似填充度的问题,并导出可用于生成近似的贪婪最小度量排序的近线性时间算法,以及解决了内部随机性导致的失败问题。
- 多目标进化算法优化子模函数或单调近似子模函数
本论文研究基于多目标进化算法 GSEMO-C 的子模最大化问题(包括有 / 无大小约束的子模函数最大化问题,以及有大小约束的单调逼近子模函数最大化问题),证明了该算法可以在多项式期望运行时间内实现很好的近似效果。
- 弱次模可扩展的贪心特征选择
针对大型数据集中贪心算法的运行时间会非常高的问题,本文介绍了 2 种运用分布式计算和随机评估技术的更快逼近贪心向前选择算法,并且证明了弱次模性的泛化概念足以为这 2 种算法提供乘性逼近保证。同时,研究者还表明这些快速贪心逼近算法在人工数据和 - NIPS子模覆盖问题的高效数据流算法
在数据流模型中研究了经典的子模覆盖(SC)问题,提出了新的流式子模覆盖(SSC)问题。我们设计了首个高效的双目标子模覆盖流算法(ESC-Streaming),对其性能提供理论保证,并通过数值实验证明了其与近似最优的贪心算法可比的竞争力。
- 拍卖中的混沌代价
本文提出了一种通用的、模块化的理论来证明竞拍中的平衡近似保证,该理论补充了传统经济技术,着重于精确和最优解决方案,并因此局限于相对简化的设置。我们提出了三个用户友好的分析工具:平滑型不等式、扩展定理和组合定理,将这些工具结合起来,为许多广泛 - 随机化的威力:大规模数据集上的分布式子模最大化
该论文提出了一个简单的分布式算法来解决在机器学习中的受限次模最大化问题,该算法可以并行运行并且提供可证明的常数近似保证,即使在单个机器上无法解决的问题也可以通过该算法高效地解决。
- 分布式子模最大化
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接