- 关于不精确模型下优化和变分不等式的非精确相对光滑度和强凸性
提出一种用于优化框架、鞍点问题和变分不等式的一般算法框架,通过构建主要问题组成部分即优化目标函数或者变分不等式运算符的不精确模型,不但可以产生许多已知的算法方法,同时可以构造新的算法方法,如具有复合结构的变分不等式的通用条件梯度法和相对光滑 - 无投影赌博凸优化改进遗憾界
本文提出一种基于条件梯度法的 projection-free 的算法,通过线性优化预测每一轮的动作并达到了 $O (T^{3/4})$ 的预期最小化损失 (expected regret)。
- 随机条件梯度 ++
本文提出了一种用于非显式随机优化问题的算法 SFW ++,使用该算法可以快速收敛于全局最优解,并通过一些简单的结构扩展,可以优化跨不同优化问题的条件梯度方法。
- 一种基于条件梯度的增广 Lagrangian 框架
本文研究了具有仿射约束的通用凸优化模板,提出了一种新的基于平滑和增广 Lagrangian 框架统一处理的条件梯度算法,证明了该方法在目标残差和可行性差距方面具有 O (1 / 根号 k) 的收敛速率,特别适用于各种半定规划应用。
- 可证明高效的最大熵探索
该研究采用条件梯度法,利用近似 MDP 求解器提供高效算法,解决了在没有奖励信号的情况下对一类内在目标进行优化的问题。
- 基于条件梯度方法的随机次模最大化:弥合差距
研究连续子模最大化问题,通过提供新颖的算法并使用随机持续优化作为接口,在满足约束条件的情况下获得了紧密的逼近保证。
- 基于凸低秩矩阵优化的深思决策:最佳存储
本文介绍了一种基于 SketchyCGM 的算法,使用低秩近似来解决凸矩阵优化问题,该算法修订了条件梯度法,仅存储矩阵变量的随机草图,最后从草图中提取出低秩近似解决方案。与非凸启发式相比,SketchyCGM 的保证不依赖于问题数据的统计模 - 结构多面体的线性内存和分解不变线性收敛条件梯度算法
提出了一种改进的条件梯度方法来解决约束凸优化问题,针对多面体进行了相应的分析及优化,降低了每次迭代时的计算及内存开销,并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。
- 在谱多面体上更快的无投影凸优化
提出了一种适用于相对熵锥内凸优化问题的条件梯度方法的修改算法,其每次迭代的复杂度与标准条件梯度方法的复杂度基本相同,对于最小化的强凸性和平滑性函数,该方法的期望逼近误差在使用 t 次迭代之后为 O (β/t),在所有已知的条件梯度变体中,该 - 结构化非凸非光滑优化:算法和迭代复杂度分析
本文介绍了一些带有或没有耦合的非凸优化模型,使用了相关的优化算法,如条件梯度和 ADMM, 为专门处理非凸和非光滑优化问题的理论和算法的发展提出了一步。通过数值实验,证明了这些算法的高效性,特别是在张量鲁棒 PCA 的场景下。
- NIPS边缘推断的障碍型 Frank-Wolfe
本文介绍了一种基于条件梯度法和最大后验概率调用的全局收敛算法,用于优化边际多面体上的树重新加权 (TRW) 变分目标,此算法模块化结构使我们能够利用黑盒 MAP 求解器 (精确和近似) 进行变分推理,并获得比优化本地一致性放宽的 tree - 非强凸函数的线性收敛离点条件梯度法
本研究利用简单的对偶算法和相应的误差边界提供了一种新的算法和分析,可以在紧凑型多面体集上最小化一个包含线性和强凸函数和线性转换组合的函数,同时具有线性收敛速度和附加线性项,允许通过条件梯度方法求解。
- 循环块条件梯度法用于凸优化问题
本文研究了一类具有特殊可分离形式的光滑函数和紧支撑非光滑项总和的凸问题。当以循环顺序选择块时,分析了广义条件梯度方法的块版本。对于在这类方法中常用的两种步长策略建立了全局次线性收敛率。提出的方法与经典条件梯度算法及其随机块版本进行的数值比较 - 基于线性优化预言机的大规模凸优化问题的复杂性
本文探讨了一类名为线性优化型凸规划算法的迭代优化算法,证明了它们解决一系列滑顺、非滑顺和某些鞍点问题的低复杂度下界; 验证了在大规模情况下,条件梯度法及其变种求解不同类别的凸规划问题的理论最优性或接近最优性; 推出了几种新的最优 LCP 方 - 次梯度法与条件梯度法之间的对偶性
本研究证明了镜面下降算法和条件梯度法广义化算法的等价性,并说明了在某些问题中,如具有非平滑损失或非平滑正则化器的监督式机器学习问题中,原始次梯度法和对偶条件梯度法是形式上等价的;对偶解释导致了镜面下降的线性搜索形式以及对原始 - 对偶证书的