- 优化星型凸函数
该论文介绍了一种多项式时间算法,用于优化无限制的星凸函数,提出了一个随机化算法找到可行域的割面,并强调了该算法的理论吸引力,即在多项式时间算法的范围内引入很多有趣的病态类。
- 一种更快的次二次算法用于发现异常相关性
该研究介绍了用于检测强相关变量中的异常对的随机算法,并应用于学习稀疏布尔函数等问题。
- 随机无导数优化噪声凸函数
STARS 是一种基于随机化的无导数优化算法,适用于函数评估受到随机噪声干扰的情况。该算法通过动态噪声自适应平滑步长来最小化真实方向导数与其有限差分估计之间的最小二乘误差,并提供了用于求解具有加性或乘性噪声的凸问题收敛速率分析。实验结果显示 - KDD随机线性代数快速标签嵌入
本文介绍了一种利用等级约束估计和低维度标签嵌入之间的对应关系发现的快速标签嵌入算法,该算法适用于多类和多标签数据集,并且其运行时间比朴素算法快效果显著,该方法在两个大规模公共数据集上进行了验证,并获得了最先进的结果。
- 通过采样杠杆元素实现更紧凑的低秩近似
本文提出了一种新的随机算法,该算法采用特别偏向采样的方法,使误差最小化,可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近,并具有 better dependence on error ε,是一种高度可并行化的优化方法。此外,本论文 - MM体积和高斯体积的高斯冷却和 O*(n^3) 算法
我们提出了一种基于随机化算法的方法,用于估计具有会员 Oracle 的圆满凸体的体积。我们还提供了一种有改进的高斯分布采样算法,并分析了采样复杂性。
- MM利用随机投影降维仿射变分不等式
通过在随机子空间上适当投影,我们提出了一种解决亚流形中仿射变分不等式问题的高效算法,并通过数字实验验证了其实用性和高效性。
- 随机元素级矩阵稀疏化注释
本文提出一种基于随机采样的算法用于对矩阵进行稀疏处理,同时利用分布与矩阵元素平方和绝对值相关的信息提高了近似精度。
- NIPS连续时间扩散网络中的可扩展影响估计
本文提出了一种基于随机算法来进行影响估计的方法,该方法可以在连续的时间传播网络中估计每个节点的影响力,通过大规模的实验数据表明,该方法不仅精度高,而且能够扩展到数百万个节点的网络上。
- 一遍 AUC 最优化
本研究提出一种基于回归的算法和一种随机算法,用于一次遍历训练数据集并进行 AUC 优化,可以高效地处理高维数据,并且只需要在内存中维护训练数据的前两阶统计量。
- ICML大规模应用的分位数回归
提出一种随机算法来处理大规模数据量的分位数回归问题,该算法在近线性时间内计算给定分位数回归问题的(1+ϵ)近似解,并计算量子回归损失函数的低失真子空间保持嵌入。
- 驯服维数诅咒:通过哈希离散积分和优化
我们提出了一种随机算法,它通过解决一小部分带有随机生成校验约束的离散组合优化问题,从而在高概率下能够得到可靠的常数近似值,从而有效地逼近离散图模型的分区函数。
- 快速矩阵排名算法与应用
本文介绍了一种随机算法来计算矩阵的秩,可以在线性时间内找到一组线性无关的列,并解决了动态矩阵更新问题。这种方法可以有效地应用于数值线性代数、组合优化和动态数据结构中。
- 走在边缘上的建设性差异最小化
本文介绍了一个新的随机算法 — 边行走算法,用于寻找松散套的一个例子,这个算法的分析仅仅使用基本的线性代数,是一个新定理的证明,证明了 Spencer 定理和部分着色引理。
- ICML矩阵相关度和统计杠杆的快速近似计算
本文介绍了一种基于随机算法的矩阵统计杠杆分数的计算方法,并探讨了在矩阵完成、低秩矩阵逼近、大规模统计数据分析等问题中具有的实际应用以及可拓展的领域。
- 彩色三角计数和 MapReduce 实现
该论文介绍了一种新的随机算法,可以用于计算图中三角形数量的估计,论文给出了一种专门的不等式来评估估计结果是否准确,最后提供了一个基于 MapReduce 的实现。
- NIPS从稀疏优化角度看 CUR
本文探讨了 CUR 分解,从稀疏优化的角度出发,阐明了 CUR 分解是隐式地优化了一个稀疏回归目标函数,而且不能直接作为一个稀疏 PCA 方法来分类。此外,观察到 CUR 的稀疏度具有一种有趣的结构,因此提出了一种类 CUR 的稀疏 PCA - 正则二分图中的 O (nlogn) 时间完美匹配
本文提出了一种基于随机算法和修剪的自适应均匀采样策略,在 O (n log n) 时间内寻找 d - 正则图中完美匹配,并用于求解双随机矩阵的 Birkhoff-von Neumann 分解。
- 刚体理论下的低秩矩阵完备性唯一性
矩阵完成问题和距离几何问题之间具有类似性质,利用刚性理论的工具,可以设计出用于测试矩阵局部或全局唯一完成性的高效随机算法。
- 列子集选择、矩阵分解和特征值优化
提出了一种基于随机列抽样的多项式时间算法,用于选择具有良好谱特性的矩阵子集,具有较高的计算效率和实用价值,并结合 Grothendieck 因子分解构造了一种新的近似算法,以计算矩阵的(无穷大,1)范数。