作者 |?馬騰宇

編譯?|?陳萍、杜偉

來源?|?機器之心

非凸優(yōu)化問題被認為是非常難求解的，因為可行域集合可能存在無數(shù)個局部最優(yōu)點，通常求解全局最優(yōu)的算法復(fù)雜度是指數(shù)級的（NP 困難）。在近日的一篇文章中，斯坦福大學(xué)助理教授馬騰宇介紹了機器學(xué)習(xí)中的非凸優(yōu)化問題，包括廣義線性模型、矩陣分解、張量分解等。

非凸優(yōu)化在現(xiàn)代機器學(xué)習(xí)中普遍存在。研究人員設(shè)計了非凸目標函數(shù)，并使用現(xiàn)成的優(yōu)化器（例如隨機梯度下降及其變體）對其進行了優(yōu)化，它們利用了局部幾何并進行迭代更新。即使在最壞的情況下求解非凸函數(shù)都是 NP 困難的，但實踐中的優(yōu)化質(zhì)量通常也不是問題，人們普遍認為優(yōu)化器會找到近似全局最小值。

最近，在斯坦福大學(xué)助理教授馬騰宇（Tengyu Ma）的一篇文章中，他為這種有趣的現(xiàn)象假設(shè)了一種統(tǒng)一的解釋：實際使用目標的大多數(shù)局部最小值約為全局最小值，并針對機器學(xué)習(xí)問題的具體實例進行了嚴格地形式化。

文章地址：

https://arxiv.org/pdf/2103.13462.pdf

文章概覽

優(yōu)化非凸函數(shù)已成為現(xiàn)代機器學(xué)習(xí)和人工智能的標準算法技術(shù)。了解現(xiàn)有的優(yōu)化非凸函數(shù)啟發(fā)式方法非常重要，我們需要設(shè)計更有效的優(yōu)化器。其中最棘手的問題是尋找非凸優(yōu)化問題的全局極小值，甚至僅僅是一個 4 階多項式——NP 困難。因此，具有全局保證的理論分析依賴于優(yōu)化的目標函數(shù)的特殊屬性。為了描述真實世界目標函數(shù)的屬性特征，研究者假設(shè)機器學(xué)習(xí)問題的許多目標函數(shù)具有以下屬性：全部或者絕大多數(shù)局部極小值近似于全局極小值。

基于局部導(dǎo)數(shù)的優(yōu)化器可以在多項式時間內(nèi)求解這一系列函數(shù)（下文討論中也增加了一些額外的假設(shè)）。經(jīng)驗證據(jù)也表明機器學(xué)習(xí)和深度學(xué)習(xí)的實際目標函數(shù)可能具有這樣的屬性。

文章共分為七個章節(jié)，各章節(jié)主旨內(nèi)容如下：

• 第一章：非凸函數(shù)的基本內(nèi)容；

• 第二章：分析技術(shù)，包括收斂至局部極小值、局部最優(yōu) VS 全局最優(yōu)和流形約束優(yōu)化；

• 第三章：廣義線性模型，包括種群風(fēng)險分析和經(jīng)驗風(fēng)險集中；

• 第四章：矩陣分解問題，包括主成分分析和矩陣補全；

• 第五章：張量分解，包括正交張量分解的非凸優(yōu)化和全局最優(yōu)；

• 第六章：神經(jīng)網(wǎng)絡(luò)優(yōu)化的綜述與展望。

文章細節(jié)

廣義線性模型

第三章講了學(xué)習(xí)廣義線性模型的問題，并證明該模型的損失函數(shù)是非凸的，但局部極小值是全局的。在廣義線性模型里，假設(shè)標簽生成自，其中σ: R→R 是已知的單調(diào)激活函數(shù)，ε_i∈R 均為獨立同分布（i.i.d.）的均值零噪聲 (與 x_i 無關(guān))，是一個固定的未知真值系數(shù)向量。

研究者的目標是從數(shù)據(jù)中恢復(fù)ω*，然后最小化經(jīng)驗平方風(fēng)險：。是相應(yīng)的種群風(fēng)險（population risk）。

該研究通過對其 landscape 屬性的表征來分析的優(yōu)化，分析路徑包括兩個部分：a) 所有種群風(fēng)險的局部極小值都是全局極小值；b) 經(jīng)驗風(fēng)險具有同樣的屬性。

不再是凸的。在本節(jié)其余部分中，研究者對這個問題進行了規(guī)律性假設(shè)。為了便于闡述，這些假設(shè)比必要的假設(shè)更為有力。當σ是恒等函數(shù)時，即σ（t）=t 為線性回歸問題，損失函數(shù)是凸的。在實踐中，人們已經(jīng)把σ作為 sigmoid 函數(shù)，然后目標不再是凸的。在本節(jié)其余部分中，研究者對這個問題進行了規(guī)律性假設(shè)。為了便于闡述，這些假設(shè)比必要的假設(shè)更為有力。

PCA 與矩陣補全

第四章討論了基于矩陣分解的兩個優(yōu)化問題：主成分分析（PCA）和矩陣補全。它們與廣義線性模型的根本區(qū)別在于，目標函數(shù)具有非局部極小或全局極小的鞍點。這意味著擬凸條件或 Polyak-Lojasiewicz（PL）條件不適用于這些目標。因此，需要更復(fù)雜的技術(shù)來區(qū)分鞍點和局部極小值。

主成分分析的一種解釋是用最佳低秩近似來逼近矩陣。給出一個矩陣，求其最佳秩 r 逼近（Frobenius 范數(shù)或譜范數(shù)）。為了便于說明，研究者取，并假設(shè) M 是維數(shù)為 d×d 的對稱半正定。在這種情況下，最佳秩 1 近似的形式為。

矩陣補全是指從部分觀測項中恢復(fù)低秩矩陣的問題，在協(xié)同過濾和推薦系統(tǒng)、降維、多類學(xué)習(xí)等方面得到了廣泛的應(yīng)用。研究者討論了秩為 1 對稱矩陣補全。

張量分解

第五章分析了另一個機器學(xué)習(xí)優(yōu)化問題——張量分解。張量分解與矩陣分解或廣義線性模型的根本區(qū)別在于，這里的非凸目標函數(shù)具有多個孤立的局部極小值，因此局部極小值集不具有旋轉(zhuǎn)不變性，而在矩陣補全或主成分分析中，局部極小值集具有旋轉(zhuǎn)不變性。這從本質(zhì)上阻止只使用線性代數(shù)技術(shù)，因為它們本質(zhì)上是旋轉(zhuǎn)不變的。

研究者專注于一個最簡單的張量分解問題——正交四階張量分解。假設(shè)得到一個對稱的 4 階張量，它具有低秩結(jié)構(gòu)，即：

其中。研究者的目的是恢復(fù)底層組件 a_1, . . . , a_n。他假設(shè) a_1, . . . , a_n 是單位范數(shù) R^d 中的正交向量，則目標函數(shù)為：

作者簡介

馬騰宇是斯坦福大學(xué)計算機科學(xué)和統(tǒng)計學(xué)助理教授。他本科畢業(yè)于清華大學(xué)計算機科學(xué)系，之后在普林斯頓大學(xué)獲得計算機科學(xué)博士學(xué)位。期間，馬騰宇師從 Sanjeev Arora 教授，并在多個國際頂級學(xué)術(shù)會議和期刊上發(fā)表近 20 篇高質(zhì)量論文。

他的主要研究興趣為機器學(xué)習(xí)和算法方面的研究，包括非凸優(yōu)化、深度學(xué)習(xí)、強化學(xué)習(xí)、表征學(xué)習(xí)、分布式優(yōu)化、凸松弛以及高維統(tǒng)計等。

個人主頁：https://ai.stanford.edu/~tengyuma/

????

現(xiàn)在，在「知乎」也能找到我們了

進入知乎首頁搜索「PaperWeekly」

點擊「關(guān)注」訂閱我們的專欄吧

關(guān)于PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學(xué)術(shù)平臺。如果你研究或從事 AI 領(lǐng)域，歡迎在公眾號后臺點擊「交流群」，小助手將把你帶入 PaperWeekly 的交流群里。

總結(jié)

以上是生活随笔為你收集整理的斯坦福助理教授马腾宇：ML非凸优化很难，如何破？的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。