Efficient stochastic optimization algorithms for large-scale machine learning problems

Ph.D.Due to rapid growth in the data size, it becomes a more and more challenging issue concerning how to train machine learning models efficiently. In many industry applications, it is quite common to see that the problems are in the scale of millions or even billions nowadays. Traditional optimization methods, including both first-order and second-order methods, becomes intractable under such setting. As a result, stochastic optimization algorithms thus become standard ways for solving large-scale problems due to its low computation cost.Though can be tracked back into 1950s, stochastic optimization was not an active research area in optimization community, until the rise of big data. In recent years, a lot of progresses have been made by researchers on this topic.In this thesis, based on the latest results in recent years, we further study the applications of regularized stochastic optimization algorithms onto machine learning. The focus of our research is to develop efficient stochastic algorithms to solving large-scale problems with low computation cost and fast convergence rate, by exploiting possible structures in different classes of problems. We will show that better results can be expected by developing new methods that can take advantage of these structures.More specifically, we will first study general regularized stochastic optimization problems, and present our new algorithms for solving them, with an emphasis on how to deal with sparse data efficiently. Second, we will restrict our attention onto the problems with finite number of data samples, and develop an adaptive stochastic optimization methods that has linear convergence rate. Furthermore, when the function is twice differentiable, we show the possibility of combing second-order derivative information to further accelerate stochastic methods. Finally, we study a special class of machine learning models named generalized linear models. We present a way that is very different from existing methods for solving this class of problems, which only O(1) per-iteration complexity regardless of the problem size. We will demonstrate the efficiency of the above-mentioned methods over standard stochastic optimization methods via both theoretical and experimental approaches.由於數據規模的迅速增長，如何高效地訓練機器學習模型已經變成一個富有挑戰的問題。在目前的很多工業級應用中，我們已經可以經常看規模達到百萬甚至上億量級問題的出現。在這樣的情況下，傳統的優化算法，無論是一階方法還是二階方法，都變得不再適用了。而隨機優化算法則因為它較低的計算量成為了解決大規模機器學習問題的標準方法。雖然隨機優化方法的歷史最早可以追溯到20世紀50年代，但在優化算法的研究中它一直沒有被重視，直到最近大數據時代的到來。由於它在解決大規模問題時的有效性，近些年有不少研究人員在這類方法上做了許多研究，也取得了很多重要的研究進展。在本篇論文中，我們立足于最新的研究進展，更進一步的討論如何更有效地將隨機優化算法應用于在機器學習問題中。我們最主要的目標是，通過發掘不同問題中帶有的特殊結構，開發出能更有效解決這些大規模問題的隨機優化算法，并證明這算法能夠帶來更低的計算量和更快的收斂速度。具體來說，我們首先研究一般的帶正則化項的隨機優化問題，并提出一種新的算法來解決這類問題，這種新的算法在稀疏數據上比現有方法更為有效。第二，我們考慮訓練樣本數據是有限個的情況，并提出一種自適應的方法，在一定假設下我們可以證明它具有線性的收斂速度；此外，當目標函數是二階可導時，我們發現利用二階信息可以更進一步的減小隨機梯度的誤差，并利用這個思想開發出一種具有更快收斂速度的隨機算法。最後，我們考慮一類特殊的模型--廣義線性模型。在這類模型上，我們提出了一種與已有隨機方法很有不一樣的算法，它每輪迭代只需要與問題大小無關的常數計算量。我們均會通過理論分析和數值實驗來說明上述方法的有效性。Tan, Conghui.Thesis Ph.D. Chinese University of Hong Kong 2019.Includes bibliographical references (leaves 113-124).Abstracts also in Chinese.Title from PDF title page (viewed on 03, December, 2020)