ICMLApr, 2018

一种条件梯度框架用于复合凸最小化及半定规划应用

PDF
TL;DR我们提出了一个基于条件梯度法的复合凸优化模板，该方法结合了平滑和同伦技术，在 CGM 框架下实现了最优的 O（1 /sqrt（k））收敛速度，并证明了在线性子问题具有加法或乘法误差时，同样的速率保持不变。此外，与相关工作相比，我们能够描述非平滑项为指示函数时的收敛性质。
conditional gradient frameworkcomposite convex minimizationsmoothing techniqueshomotopy techniquesoptimal convergence
发现论文，激发创造
  • 一种基于条件梯度的增广 Lagrangian 框架

    本文研究了具有仿射约束的通用凸优化模板，提出了一种新的基于平滑和增广 Lagrangian 框架统一处理的条件梯度算法，证明了该方法在目标残差和可行性差距方面具有 O (1 / 根号 k) 的收敛速率，特别适用于各种半定规划应用。

    Jan, 2019

  • 几乎必然受限凸优化

    我们提出了一种随机梯度框架，用于解决具有（可能）无限数量的线性包含约束条件的随机复合凸优化问题，而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件，无需矩阵投影，并且通过数值实验表明，我们的算法实现了最先进的实用性能。

    Jan, 2019

  • 一种平滑的原始对偶优化框架用于非光滑复合凸最小化

    本文介绍了一种新的一阶原始 - 对偶优化框架，利用平滑、加速和同伦等三个经典思想，实现了具有许多广泛应用的凸优化，达到了最佳的收敛效果，针对只包含非平滑函数的情况。同时提供了重新启动策略，大大提高了实际性能，并展示了与增广拉格朗日方法的关系以及如何利用严格收敛率保证来利用强凸目标。最后提供了两个实例验证，表明新的方法可以优于 Chambolle-Pock 和交替方向乘法算法等现有的算法。

    Jul, 2015

  • 一种线性收敛的条件梯度算法及其在在线和随机优化中的应用

    本研究介绍了一种基于条件梯度算法的优化模型，可用于求解线性优化问题和非线性凸优化问题，并给出了一种基于此算法的在线凸优化算法，具有线性收敛速度和最优的遗憾保证。

    Jan, 2013

  • 基于条件梯度的复合非线性和随机优化方法

    本文提出了一种条件梯度类型（CGT）方法，用于解决一类由（弱）光滑项和（强）凸正则化项组成的复合优化问题，该方法在实现时不需要额外计算（子）梯度且具有较优度收敛率，并且还将这些方法推广到了随机设置中。

    Feb, 2016

  • 基于条件梯度算法的范数正则化平滑凸优化

    通过研究在信号处理和机器学习中的应用，本论文讨论了两类具有挑战的凸优化问题，提出了一种解决方案，并给出了条件梯度算法的版本以及相应的效率估计和应用。

    Feb, 2013

  • 超越凸性和 Lipschitz 梯度连续性的一阶方法及其在二次逆问题中的应用

    利用可适应性光滑函数的概念和 Bregman 基础的近端梯度方法，在解决具有复杂目标函数的非凸、非光滑最小化问题时，实现全局收敛。

    Jun, 2017

  • 复合最小化问题的近端牛顿框架：无需 Cholesky 分解和矩阵求逆的图学习

    提出了一种基于新的近端牛顿算法的凸优化方法，应用于图学习问题中的稀疏逆协方差矩阵估计，避免了矩阵求逆，适合并行实现。

    Jan, 2013

  • 复合极小值的近端法

    该论文研究了由凸或 Prox-regular 函数组成的函数与光滑向量函数的复合函数最小化问题，提出了一种基于线性逼近和正则化项的子问题算法框架，并探讨了该子问题的局部解的性质、全局收敛性和含有原问题解的活动流形的识别性质。初步的计算结果具有良好的性能。

    Dec, 2008

  • 关于不精确模型下优化和变分不等式的非精确相对光滑度和强凸性

    提出一种用于优化框架、鞍点问题和变分不等式的一般算法框架，通过构建主要问题组成部分即优化目标函数或者变分不等式运算符的不精确模型，不但可以产生许多已知的算法方法，同时可以构造新的算法方法，如具有复合结构的变分不等式的通用条件梯度法和相对光滑度算子的变分不等式算法。

    Jan, 2020