通过增加极点来避免根搜索和优化中的不必要点
该研究探讨了使用函数值而不是梯度的无导数算法在随机和非随机凸优化问题中的应用,同时关注其收敛速率,经实验表明使用随机扰动的梯度估算方法具有比传统随机梯度方法更快的收敛速率,尤其在光滑和非光滑情况下,且可以扩展到多次评估的情况。
Dec, 2013
该研究考虑了针对一组正函数的最小化问题,给出了一个压缩表示法(coresets),用于形状拟合(shape fitting)和近似聚类(approxiate clustering)问题。他们将 epsilon-approximations 与 PAC Learning 和 VC dimension 相联系,并给出了一般函数集的 coresets 的线性时间近似计算方法。
Jun, 2011
提出了两个针对非凸情况的数值算法,用于快速解决优化问题。该算法基于可变度量介绍了近端项,这使得我们能够针对非凸结构优化问题构建新的近端分裂算法。在变量度量序列条件温和并且假设相关增广拉格朗日函数具有 Kurdyka-Lojasiewicz 性质的情况下,证明了该算法迭代可以收敛到 KKT 点,并获得了增广拉格朗日函数和迭代的收敛速度。
Jan, 2018
研究了多维欧氏空间中寻找一个 k 维子空间 F,使得一组 n 个点到该子空间的 p 次方欧氏距离和最小的问题。进一步探讨了在某些损失函数 M ()(如 Huber 和 Tukey 损失函数)下此问题的最优解。这些鲁棒子空间可替代奇异值分解(SVD)提供更有效的解决方案,对于典型的 M-Estimators,对离群值的鲁棒性更强。本文给出了一些这些鲁棒子空间逼近问题的算法和难度结果。
Oct, 2015
本篇论文提出了一种新的随机坐标下降方法,能够并行、加速和提高期望可分超逼近,此方法能够同时最小化依赖于少数坐标的多个凸函数的和,通过使用新的安全且大的步长,使得该方法不需要执行完整的矢量运算。
Dec, 2013
本文介绍了 “逐一” 坐标下降算法及其在 $ L_1 $- 惩罚回归(套索)、garotte 和弹性网络等相关方法中的应用,证明了该算法可以与广泛应用的 LARS(或同伦)过程竞争,在大规模 lasso 问题中引起了不少关注。但注意到它并不适用于 “融合 Lasso”,所以论文提出了一个广义算法,在比标准的凸优化器运行时间更短的时间内得出了解决方案。最后,将该过程推广到二维融合 Lasso,并展示了其在一些图像平滑问题上的性能。
Aug, 2007
该研究提出了一种基于坐标下降的方法来解决图模型中的 MAP 推理问题,并证明了该方法的迭代会收敛到算法的一个固定点,且在 O (1/ε) 次迭代内达到精度 ε>0。
Mar, 2024
本文研究了一个迭代算法在具有约束的非单调集值算子中寻找零点的收敛性,这个算法被称为 proximal-projection 算法,收敛结果基于 Opial 引理的新概括。我们展示了 proximal-projection 算法可以被应用于求解仅具有近似数据的 ILL-POSED 变分不等式和凸优化问题。此外,我们证明了 proximal point 算法(具有 Bregman 距离)的收敛性在算子具有顺序弱闭图形时仍然存在。
Nov, 2007
本论文提出了一种基于 Dirichlet 特征值的非凸图划分目标函数, 并设计了一种新颖的重排算法来达到最优, 可应用于几个聚类问题并拓展至半监督, 在合成数据、MNIST 手写数字和流形离散化图上都取得了有效结果。
Aug, 2013
本文提出了一种基于误差界的方法,通过与 Kurdyka-Łojasiewicz 不等式的相互作用和设计一维最坏情况的近似方法,分析了针对凸约束问题的首阶下降方法的复杂度。
Oct, 2015