Dai zheng ze xiang de fei tu you hua wen ti: ji yu wu cha jie xian lei tiao jian de yi jie suan fa shou lian xing fen xi

Ph.D.With the increasing demand of information and technology, researchers have been paid much attention to numerical algorithms for solving practical optimization problems with large size of datasets. One of the key elements to evaluate the performance of these iterative algorithms, is the convergence rate of those generated iterates towards an optimal solution. In the early existing results, many first-order methods can achieve a sub-linear rate for general smooth and convex functions, and a linear rate if strong convexity is assumed. However, this may be too rigid for many prevalent applications, like the most well-known Lasso, Group-Lasso and even the nonconvex matrix factorization problems.Actually, according to the numerical experiments, most first-order methods still exhibit linear convergence without strong convexity. Inspired by this delighted phenomenon, people began to investigate more about the problem structure, trying to find a theoretical explanation for this faster rate. Subsequently, various of so-called error bound-type conditions have been raised as working tools for convergence analysis, including error bound and Lojasiewicz inequality. They can be regarded as relaxed definitions of strong convexity. Once these conditions have been verified for specific structured problems, kinds of first-order algorithms can be proved to attain the linear rate of convergence.Yet, checking error bound-type conditions usually involves sophisticated mechanism. In this thesis, we consider two interesting applications of regularized optimization problems. The first case is the ℓ₁,ₚ-norm regularizer, which induces sparsity in machine learning, signal processing and many other popular domains. We identify that the error bound condition will hold when p ∈ [1, 2] or + ∞, and thus many first-order algorithms, like the Proximal Gradient(PG) method and the Block Coordinate Gradient Descent(BCGD) method, can converge linearly when the iterates fall close enough to the optimal set. Otherwise, for p ∈ (2, + ∞), we construct a counter-example when error bound fails.The other case is the prevailing matrix factorization problems with different regularizers for inducing desired structure. A nonconvex Alternating Direction Method of Multipliers(ADMM) is applied and is demonstrated to achieve local linear convergence to the global optimum under the Lojasiewicz inequality assumption. As illustration, several specific regularizers are discussed and are verified to satisfy the Lojasiewicz inequality. To be complete, numerical experiments are shown to support these theoretical results for both cases.隨著信息和科技的發展，科研工作者們開始越來越多地關注數值算法，來求解實際場景中很多帶有大規模數據集的優化問題。為了評估這些迭代算法的表現，最重要的一點就是關注算法產生的序列收斂到最優解的速率。在早期的結果中，很多一階算法都可以對一般的光滑的凸函數，達到次線性的收斂速度；而線性收斂則需要問題是強凸的。然而，這個假設在很多流行的模型和應用中太過苛刻，比如Lasso，Group Lasso，甚至還有一些非凸的矩陣分解問題。實際上，從數據實驗的結果來看，即使問題不是強凸的，很多一階算法都可以達到線性收斂的速率。受這一現象的啟發，研究者們開始更多地關注問題本身的結構，試著為這一現象找到合理的理論解釋。因此，很多所謂的誤差界限類的條件作為收斂分析的工具被提出來，這其中包括了誤差界限條件，Lojasiewicz不等式。他們可以被看作是強凸條件的弱化，一旦被驗證成立，很多一階算法都可以被證明達到線性收斂。然而，檢驗這些誤差界限類條件往往涉及到很複雜的分析。在這篇論文里，我們考慮兩個有趣的帶正則項的優化問題。第一個是帶ℓ₁,ₚ範數正則項的問題，這類問題往往作為引入參數稀疏性的模型，被用到機器學習，信號處理等很多領域中。我們證明了誤差界限條件在p ∈[1,2] 或者+ ∞時成立，因而很多一階算法可以被證明，在最優解集附近處有線性收斂速率。而當p ∈(2, + ∞)時，我們構造了一個範例，來證明誤差界限條件不成立。另一個被廣泛使用的例子是帶正則項的矩陣分解問題。我們討論了幾個特別的正則項，并檢驗了他們滿足Lojasiewicz不等式。基於這個很好的性質，ADMM算法可以用來很好的求解這個問題，並且達到線性收斂的速度。同時，數據實驗的結果也讓理論證明更具說服力。Zhang, Qi.Thesis Ph.D. Chinese University of Hong Kong 2018.Includes bibliographical references (leaves 98-107).Abstracts also in Chinese.Title from PDF title page (viewed on …).Zhang, Qi