Feb, 2019
用于缩放子模块优化大规模问题的记忆化框架
A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems
Rishabh Iyer, Jeff Bilmes
TL;DR使用预计算复杂性模型和记忆化的方式来优化大规模子模量优化问题,该方法在许多约束和非约束的子模量最大化,最小化,差异最小化问题中都适用,且在数据子集选择和摘要方面表现出了明显的加速效果。
Abstract
We are motivated by large scale submodular optimization problems, where
standard algorithms that treat the submodular functions in the \emph{value
oracle model} do not scale. In this paper, we present a model called the
\emph{→
submodular optimizationprecomputational complexity modelmemoizationmachine learningdata summarization
发现论文,激发创造
水平可扩展次模最大化
该篇论文提出了一种针对固定容量的分布式子模型最大化的框架,应用于广泛的算法和约束条件,并且为任何可用容量提供近似因子的理论保证,并在多个数据集上进行了实证评估,表现竞争性与中心化贪婪算法相当。
May, 2016
基于快速半微分的次模函数优化
文章提出了一种基于离散半微分的无约束和有约束子模函数优化的实用强大新框架,旨在为子模最小化和最大化问题提供统一的范例,并为解决这些问题提供了新的算法,该算法能够多次计算和高效率优化子模半梯度。作者还分析了该算法的理论性质,并进行了支撑的经验实验,证明其在最大化问题上的优秀表现。
Aug, 2013
分布式子模最大化
本文提出了一种适用于分布式计算的子模函数最大化方法 GreeDi,该方法可在 MapReduce 框架下实现,初步实验表明该方法可应用于大规模机器学习任务中的子模优化问题,如稀疏高斯过程推断和样例聚类等问题,且在一定的自然条件下,可以达到接近于传统集中式计算模式下的性能表现。
Nov, 2014
分布式次模最大化的新框架
通过将现有算法从顺序设定应用到分布式设定,仅利用恒定数量的 MapReduce 循环,在许多设置中实现了接近最优的近似比率。我们的技术还为满足矩阵约束的非单调最大化提供了快速的顺序算法。
Jul, 2015
子模最大化问题的对称性和可近似性
研究了使用问题的多线性松弛的优化问题的一些最近结果,提出了一种与对称差相关的不可近似性结果的一般方法,证明了最大化基于 matroid 的非负次模函数问题不存在常数近似算法。
Oct, 2011
约束次模优化问题的全动态算法
本研究在完全动态的环境下,旨在最大化基数约束下的单调子模函数,研究结果为一个具有多项式对数的摊销更新时间和可得到 0.5-ε 近似解的随机算法,并结合经验研究证明了算法性能的优越性。
Jun, 2020