As a projection-free algorithm, Frank-Wolfe (FW) method, also known as conditional gradient, has recently received considerable attention in the machine learning community. In this dissertation, we study several topics on the FW variants for scalable projection-free optimization. We first propose 1-SFW, the first projection-free method that requires only one sample per iteration to update the optimization variable and yet achieves the best known complexity bounds for convex, non-convex, and monotone DR-submodular settings. Then we move forward to the distributed setting, and develop Quantized Frank-Wolfe (QFW), a general communication-efficient distributed FW framework for both convex and non-convex objective functions. We study the performance of QFW in two widely recognized settings: 1) stochastic optimization and 2) finite-sum optimization. Finally, we propose Black-Box Continuous Greedy, a derivative-free and projection-free algorithm, that maximizes a monotone continuous DR-submodular function over a bounded convex body in Euclidean space.
翻译：作为不投影的算法,Frank-Wolfe (FW) 方法,又称有条件梯度,最近在机器学习界受到相当重视。在这个论文中,我们研究了关于可缩放投影不优化的FW变量的若干专题。我们首先提出了1-SFW,这是第一个不需要投影的方法,它要求每次循环只用一个样本来更新优化变量,但还是实现了最已知的 convex、非Convex和单体DR-Submodular设置的复杂界限。然后,我们向分布式设置前进,并开发了量化的Frank-Wolfe(QFW),这是一个通用的通信高效分布FW框架,用于连接和非convex目标功能。我们研究了QFW在两种广泛公认的环境中的绩效:1) 沙缩优化和2) 有限总和优化。最后,我们提出了一种无衍生物和投影化的Box持续腐蚀法,以最大限度地实现Eu Clevide 的单体连续DR-Submodal 函数。
相关内容
微信扫码咨询专知VIP会员