【斯坦福大学博士论文】凸优化和图算法的新基元，404页pdf

迭代方法，尤其是凸优化方法，构成了许多现代算法的基础。这类方法的成功依赖于它们的通用性:像梯度下降法和牛顿法这样的方法通常只需要对目标进行最小的假设就能收敛到高质量的最小化。然而，在许多现实环境中，这些算法所获得的理论保证在实践中往往是不够的。本文通过开发凸优化方法和利用问题特定结构的图算法来解决这个问题。

https://searchworks.stanford.edu/view/14239649

第一部分给出了求解拉普拉斯线性系统的最先进算法，以及求解最小成本流的更快算法。我们的结果是通过新颖的组合经典迭代方法，从凸优化与基于图的数据结构和预调节器。第二部分给出了若干类结构凸优化问题的新算法。给出了凸函数极小化的近似最优方法，包括球优化oracle和N个凸函数的最大值极小化，以及投影极小化和复合凸极小化的新算法。我们的结果是通过对经典加速梯度方法的更精细的理解实现的，并为各种重要的机器学习任务，如逻辑回归和硬边界支持向量机提供了新的算法。第三部分讨论了离散最优传输问题算法的进展，这是一个近年来由于深度学习的新应用而引起极大兴趣的任务。我们给出了简单的并行算法来逼近离散最优传输，并进一步证明了这些算法可以在空间界和流设置中实现。通过进一步利用我们的机制，我们还对半流模型中的图优化问题(如二部匹配和转运)给出了改进的复杂度边界。

专知便捷查看

便捷下载，请关注专知公众号（点击上方蓝色专知关注）

• 后台回复“CGP” 就可以获取《【斯坦福大学博士论文】凸优化和图算法的新基元，404页pdf》专知下载链接

                       

专知，专业可信的人工智能知识分发 ，让认知协作更快更好！欢迎注册登录专知www.zhuanzhi.ai，获取100000+AI(AI与军事、医药、公安等)主题干货知识资料！

欢迎微信扫一扫加入专知人工智能知识星球群，获取最新AI专业干货知识教程资料和与专家交流咨询！

点击“ 阅读原文 ”，了解使用 专知 ，查看获取100000+AI主题知识资料