• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Error Bound-Based Convergence Analyses of Certain Classes of Algorithms for Structured Optimization Problems in Machine Learning and Signal Processing
【24h】

Error Bound-Based Convergence Analyses of Certain Classes of Algorithms for Structured Optimization Problems in Machine Learning and Signal Processing

机译：机器学习和信号处理中结构优化问题的某些算法的基于误差界的收敛性分析

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Besides being an interesting subject in convex analysis and variational analysis, the concept of error bound also plays an important role in the study of optimization algorithms. Specifically, it has been utilized to establish the asymptotic convergence rate of various first- and second-order algorithms. The advantage of error bound-based analysis is that it does not require strong convexity nor the non-degeneracy of the optimal solutions, making it the sought-after theory for high-dimensional optimization problems in modern applications which often lacks strong convexity. The primary goal of this study is to extend the class of optimization algorithms that allows an error bound-based analysis and to lay down the theoretical foundation of these algorithms.;We first consider the class of convex composite minimization which has a wide range of applications in machine learning, statistics, compressed sensing, signal processing, etc. After reviewing the Luo-Tseng framework for proving linear convergence of the proximal gradient method, we turn our attention to the proximal Newton method. As our first contribution, we propose a new family of proximal Newton methods for solving the convex composite minimization problems and establish its global convergence and asymptotic convergence rate. Our analysis is novel and is based on the classical Luo-Tseng error bound.;We then study the cubic regularization method for smooth non-convex minimization problems. Polyak and Nesterov proved under some assumptions that the algorithms converges to set of second-order critical points, and the local convergence rate is quadratic if a certain non-degeneracy condition is further assumed. We remove the non-degeneracy assumption in the convergence rate result by developing a new convergence rate analysis based on a certain error bound condition, thus generalizing the convergence rate result to a much broader class of problems. A proof of concept study with the phase retrieval problem will be carried out.;Finally, we consider the angular synchronization problem, which admits a natural non-convex quadratically constrained quadratic optimization formulation. A popular but computationally expensive approach to the optimization formulation is the convex semidefinite relaxation. An alternative low-cost approach is to directly solve the non-convex problem by the generalized power method. Remarkably, we show that, under the same noise power assumption as the semidefinite relaxation approach, the generalized power method converges to a global optimum at a linear rate. At the heart of our analysis is a new error bound inequality for the non-convex problem. Our result also settles a recently proposed open question about the rate of convergence of the generalized power method.
机译：误差界限的概念除了是凸分析和变分分析中有趣的话题外，在优化算法的研究中也起着重要的作用。具体而言，已用于建立各种一阶和二阶算法的渐近收敛速率。基于错误边界的分析的优点是它不需要强凸性，也不需要最优解的不变性，这使其成为现代应用中高维优化问题的热门理论，而该问题通常缺乏强凸性。这项研究的主要目的是扩展允许基于错误边界分析的优化算法的类别并奠定这些算法的理论基础。我们首先考虑具有广泛应用范围的凸复合最小化类别。在机器学习，统计，压缩感测，信号处理等方面。在回顾了Luo-Tseng框架以证明近邻梯度方法的线性收敛性之后，我们将注意力转向近邻牛顿方法。作为我们的第一项贡献，我们提出了一系列新的近邻牛顿方法，以解决凸复合最小化问题，并建立其全局收敛性和渐近收敛率。我们的分析是新颖的，并且基于经典的Luo-Tseng误差界。；然后，我们研究了针对光滑非凸最小化问题的三次正则化方法。 Polyak和Nesterov在某些假设下证明了该算法收敛到二阶临界点集，如果进一步假设某个非简并性条件，则局部收敛速度是二次的。通过基于特定误差约束条件开发新的收敛速度分析，我们消除了收敛速度结果中的非退化假设，从而将收敛速度结果推广到更广泛的问题中。最后将进行相位同步问题的概念验证研究。最后，我们考虑角度同步问题，它接受了自然的非凸二次约束二次优化公式。优化公式的一种流行但计算上昂贵的方法是凸半定松弛。另一种低成本方法是通过广义幂方法直接解决非凸问题。值得注意的是，我们表明，在与半定松弛法相同的噪声功率假设下，广义功率方法以线性速率收敛到全局最优。我们分析的核心是针对非凸问题的新的误差界不等式。我们的结果还解决了有关功率泛函方法收敛速度的最近提出的开放问题。

著录项

  • 作者

    Yue, Man Chung.;

  • 作者单位

    The Chinese University of Hong Kong (Hong Kong).;

  • 授予单位 The Chinese University of Hong Kong (Hong Kong).;
  • 学科 Applied mathematics.;Operations research.;Computer science.
  • 学位 Ph.D.
  • 年度 2017
  • 页码 137 p.
  • 总页数 137
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号