度量约束优化的并行投影方法
本文提出了一种称为鲁棒测度学习的方法,旨在从嘈杂的侧面信息中学习距离度量,将学习任务最初制定为组合优化问题,并将其优雅地转换为凸规划问题,提出了一种基于平滑优化的高效学习算法,最后在 UCI 数据集上的实验研究证明了所提出方法的有效性。
Mar, 2012
通过学习近似度度量方法,提出了一种新颖的学习优化方法,用于加速解决受限制的优化问题,对于包括广义二次规划问题在内的实际问题形式,通过不可微优化可以学习到更好的近似度度量,以增强优化算法的收敛性,并揭示了学习到的近似度度量与优化问题最优解的活动约束之间的强连接,将学习近似度度量视为一种主动集学习的形式。
Apr, 2024
该论文研究了随机受限多层优化的无投影算法。介绍了新的无投影方差缩减算法并分析了它们在不同条件下的复杂性,包括梯度映射和 Frank-Wolfe 间隙准则,并通过分阶段适应进一步获得了凸函数和强凸函数的复杂性,数值实验证明了该方法的有效性。
Jun, 2024
提出了一种新颖的随机成对约束方法,用于多个关键聚类目标函数,可用于建模应用程序的收缩和分析,如聚类中的公平性和半监督学习中的 Must-link 约束,并提供了近似算法的具有可证明保证的通用框架。
Mar, 2021
在线凸优化中,考虑具有对抗性时变约束的情景,在这种情况下,行动必须相对于固定约束集是可行的,同时在平均上还需要近似满足附加的时变约束。我们提出了一种算法,通过线性优化预言机(LOO)访问这个集合来保证在一个长度为 T 的序列上,通过总共 T 次对 LOO 的调用,相对于损失函数产生的后悔为 $ ilde {O}(T^{3/4})$,对于约束的违反是 $O (T^{7/8})$(忽略除了 $T$ 以外的所有量)。尤其地,这些边界适用于序列中的任何区间。我们还提出了一种更高效的算法,它仅需要对软约束进行一阶预言机访问,并在整个序列上获得类似的边界。我们将后者扩展到了强化学习的场景,并在期望上获得了类似的边界(作为 $T$ 的函数)。
Feb, 2024
给定一组点,聚类是找到一个点集合的分区,使分配给一个点的中心尽可能接近。对于中心为点的目标,我们显示了一个收敛速度为 O (sqrt (k/n)) 的收敛界限。对于中心为 j 维子空间的子空间聚类,我们显示了一个收敛速度为 O (sqrt ((kj^2)/n)) 的收敛界限。对于广义 $k$-means 的投影聚类特例,我们证明了一个收敛速度为 Omega (sqrt ((kj)/n)) 的必要界限。
Oct, 2023
本文提出了一种新的受限聚类算法,该算法可以在考虑已有对比信息的情况下最大程度地满足约束条件,而不会将已知的链接信息转化为距离信息,以此来高效地学习核与度量,并在各种公共数据集上的表现明显优于现有方法。同时,本文还探讨了该方法如何应用于大数据处理,可以有效提高可扩展性。
Mar, 2022