基于穩(wěn)定性分析的非凸損失函數(shù)在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾界

郎璇聰 李春生,2 劉 勇 王 梅,2

1 （東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 黑龍江大慶 163318）

2 （黑龍江省石油大數(shù)據(jù)與智能分析重點(diǎn)實(shí)驗(yàn)室（東北石油大學(xué)） 黑龍江大慶 163318）

3 （中國(guó)人民大學(xué)高瓴人工智能學(xué)院 北京 100872）

4 （大數(shù)據(jù)管理與分析方法研究北京市重點(diǎn)實(shí)驗(yàn)室（中國(guó)人民大學(xué)） 北京 100071）（xuancongl@163.com）

點(diǎn)對(duì)學(xué)習(xí)（pairwise learning）在數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)中占有很重要的地位.在數(shù)據(jù)挖掘方面，主要的應(yīng)用場(chǎng)景有運(yùn)營(yíng)式傳統(tǒng)行業(yè)、互聯(lián)網(wǎng)領(lǐng)域、物聯(lián)網(wǎng)領(lǐng)域等[1]；在機(jī)器學(xué)習(xí)方面，包括排序[2-5]、接收機(jī)操作特性曲線(xiàn)的面積計(jì)算[6]、度量學(xué)習(xí)[7]等.

關(guān)于在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)泛化性的研究，Wang 等人[8]建立的損失函數(shù)是一致有界條件下的泛化分析，給出遺憾界O(T-1).Ying 等人[9-10]基于非正則的再生核希爾伯特空間（reproducing kernel Hilbert space, RKHS）的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法，在損失函數(shù)沒(méi)有強(qiáng)凸性和有界性的假設(shè)條件下，得到遺憾界O(T-1/3logT).Chen等人[11]假設(shè)迭代序列滿(mǎn)足更緊的一致約束，給出遺憾界O(T-1/2)，同時(shí)提高了算法最后一次迭代的收斂率.Guo等人[12]基于正則的RKHS，對(duì)于特定的鉸鏈損失函數(shù)有O(T-1/4logT1/2)收斂率.Wang等人[13]分析了具有多項(xiàng)式衰減步長(zhǎng)和多個(gè)正則化參數(shù)的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法最后一次迭代的收斂性，給出遺憾界O(T-2/3).文獻(xiàn)[14]提出了基于分而治之策略的多正則化項(xiàng)的分布式在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的誤差分析.

作為用來(lái)分析泛化性的重要工具之一，穩(wěn)定性分析已經(jīng)被廣泛應(yīng)用于單點(diǎn)學(xué)習(xí)算法的泛化邊界研究[15-16].但是，除了Shen 等人[17]和Lei 等人[18]的工作以外，關(guān)于點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性研究較少.Shen 等人[17]建立了隨機(jī)梯度下降（stochastic gradient descent, SGD）在凸和強(qiáng)凸損失函數(shù)中的穩(wěn)定性結(jié)果，從而給出了泛化邊界，并權(quán)衡了SGD 下的泛化誤差和優(yōu)化誤差，Lei 等人[18]提供了一個(gè)更細(xì)化的穩(wěn)定性分析，并將泛化邊界改進(jìn)為O(γlogn).

以上所述都是假設(shè)損失函數(shù)是強(qiáng)凸或一般凸，缺乏對(duì)非凸損失函數(shù)的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的理論分析.針對(duì)這一問(wèn)題，本文基于穩(wěn)定性分析，提出了非凸損失函數(shù)的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾界.本文包含2 點(diǎn)貢獻(xiàn)：1）提出了可以擴(kuò)展到非凸損失函數(shù)的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)框架；2）建立了該框架下穩(wěn)定性和遺憾界之間的關(guān)系，并給出了該框架的遺憾界及理論分析.

1 廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)框架

1.1 廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)

傳統(tǒng)的機(jī)器學(xué)習(xí)與在線(xiàn)學(xué)習(xí)模式不同，傳統(tǒng)的機(jī)器學(xué)習(xí)中，一次性地取全部訓(xùn)練樣本進(jìn)行學(xué)習(xí)，樣本分為訓(xùn)練樣本和測(cè)試樣本.而在線(xiàn)學(xué)習(xí)沒(méi)有訓(xùn)練樣本和測(cè)試樣本的區(qū)分，學(xué)習(xí)者（learner）實(shí)時(shí)獲取樣本，每獲取到1 個(gè)實(shí)例，就調(diào)整1 次假設(shè).

假設(shè)一個(gè)樣本空間Z=X×Y，其中X?Rd是一個(gè)輸入空間，Y?R是 一個(gè)輸出空間，x∈X和y∈Y分別是輸入和輸出.在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的學(xué)習(xí)過(guò)程迭代T輪，學(xué)習(xí)者每輪接收2 個(gè)實(shí)例 (xt,yt),(x′t,y′t)，并進(jìn)行預(yù)測(cè)，然后接收標(biāo)簽，再依損失函數(shù) ?t∈L遭受的損失更新假設(shè)wt+1∈W.

廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)表示為

顯而易見(jiàn)，與在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)模型相比，廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)是一個(gè)更魯棒、更廣義的框架.該框架中包含一個(gè) σ 項(xiàng) ， σ 項(xiàng) 是一個(gè)從e xp(η) （參數(shù)為η 的指數(shù)分布）采樣的隨機(jī)噪聲.引入隨機(jī)噪聲項(xiàng) σ避免過(guò)擬合，從而提高在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的泛化能力.因此，廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)是魯棒的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)，是一個(gè)更廣義的在線(xiàn)框架.FTRL（follow the regularized leader）是一種廣泛用于凸假設(shè)的非常有效的算法[19].事實(shí)上，當(dāng)廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)中的隨機(jī)噪聲為 μw時(shí)，F(xiàn)TRL 即為廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的一個(gè)特例：

1.2 離線(xiàn)神諭模型

直覺(jué)上，度量在線(xiàn)學(xué)習(xí)質(zhì)量的方式是學(xué)習(xí)者遭受的損失函數(shù)的累計(jì)加和，學(xué)習(xí)者的目標(biāo)是使累計(jì)損失盡可能的小，這也是一般學(xué)習(xí)模式性能度量的方式.但是，在線(xiàn)學(xué)習(xí)中的數(shù)據(jù)通常是對(duì)抗性生成的，對(duì)手知道學(xué)習(xí)者的所有信息，包括學(xué)習(xí)者給出的預(yù)測(cè)函數(shù)和損失函數(shù)等.因此，對(duì)手總是會(huì)給出與學(xué)習(xí)者預(yù)測(cè)值相反的標(biāo)簽，使得學(xué)習(xí)者的預(yù)測(cè)總是錯(cuò)誤的，并遭受最大的損失.在這種對(duì)抗環(huán)境中，累計(jì)損失的度量方式難以奏效，為了解決這個(gè)問(wèn)題，引入了專(zhuān)家（expert）這一概念.專(zhuān)家就是一個(gè)映射集合h:X→Y，對(duì)輸入x∈X給出預(yù)測(cè)h(x)，與學(xué)習(xí)者不同的是，專(zhuān)家是固定的，學(xué)習(xí)者會(huì)隨著時(shí)間根據(jù)損失進(jìn)行更新，而專(zhuān)家給出的預(yù)測(cè)不會(huì)受到對(duì)手影響.采用專(zhuān)家的損失作為參考，矯正學(xué)習(xí)者的預(yù)測(cè)，學(xué)習(xí)者在專(zhuān)家中選擇的時(shí)候，只需要選擇對(duì)輸入實(shí)例的累計(jì)損失函數(shù)值最小的專(zhuān)家，即最優(yōu)專(zhuān)家.有了專(zhuān)家的參與，在線(xiàn)學(xué)習(xí)性能度量方式就是學(xué)習(xí)者遭受的損失與最優(yōu)專(zhuān)家的損失之差的累計(jì)加和，以此避免對(duì)手的干擾.

有專(zhuān)家建議的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)是學(xué)習(xí)者和對(duì)手之間的重復(fù)游戲，其特征是學(xué)習(xí)者可以從含有N個(gè)專(zhuān)家的有限集合H中進(jìn)行選擇，對(duì)手從一組決策集合Y中選擇，還有一個(gè)損失函數(shù) ?t∈L.首先，在游戲開(kāi)始前，對(duì)手從Y中選擇一個(gè)任意的決策序列y1,y2,…，在游戲的每一輪t=1,2,…，學(xué)習(xí)者必須選擇（可能是隨機(jī)的）一個(gè)專(zhuān)家ht∈H，然后對(duì)手揭示其決策yt∈Y，學(xué)習(xí)者遭受損失.學(xué)習(xí)者每接收到一對(duì)實(shí)例z,z′∈Z后的目標(biāo)是使學(xué)習(xí)者遭受的損失與最優(yōu)假設(shè)w*∈W的損失之間的累積差盡可能的小，因此，遺憾界是衡量在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)性能的標(biāo)準(zhǔn)，對(duì)于算法 A定義為

基于神諭的學(xué)習(xí)模型可稱(chēng)之為“可優(yōu)化的專(zhuān)家”，該模型本質(zhì)上是經(jīng)典的在線(xiàn)學(xué)習(xí)模型，即學(xué)習(xí)者通過(guò)專(zhuān)家的建議和一個(gè)離線(xiàn)神諭進(jìn)行預(yù)測(cè).在“可優(yōu)化的專(zhuān)家”模型中，假設(shè)最初學(xué)習(xí)者對(duì)損失函數(shù) ?是未知的，并允許學(xué)習(xí)者通過(guò)神諭來(lái)獲取?.離線(xiàn)神諭模型是通過(guò)學(xué)習(xí)者提交一系列的損失函數(shù)，返回使得累積損失最小的假設(shè).定義1 給出離線(xiàn)神諭模型的一種近似神諭模型定義.

定義1.[20]一個(gè)離線(xiàn)神諭模型，其輸入是一個(gè)損失函數(shù) ? :W→R和 一個(gè)d維向量σ ， 輸出是一個(gè)w→?(w,z,z′)-〈σ,w〉的 近似最小值.若它返回的w*∈W滿(mǎn)足

則稱(chēng)其為“ (α,β)-近似神諭”.

為 方 便 起 見(jiàn)，將 一 個(gè) “ ( α,β)-近 似 神 諭” 記 為ORALα,β(?-〈σ,·〉).使用近似神諭是因?yàn)槲覀儾豢赡苤酪粋€(gè)假設(shè)是全局最小值還是僅為一個(gè)鞍點(diǎn).ORAL可以輸出一個(gè)w而不需要保證其最優(yōu)性.在大多數(shù)情況下，w實(shí)際上只是近似最優(yōu).離線(xiàn)神諭模型（返回w*∈arg min?(w) ） 與 (α,β)-近似神諭模型的區(qū)別在于，近似神諭模型有一個(gè)關(guān)于變量 α ， β， σ的擾動(dòng)項(xiàng).在指定變量 α 和 β的大小時(shí)可以獲得更好的遺憾界.近似神諭模型關(guān)于在線(xiàn)單點(diǎn)學(xué)習(xí)的應(yīng)用包括的實(shí)例有：當(dāng)Query-GAN算法采用近似神諭時(shí)，對(duì)于非凸損失函數(shù)以T-1/2的 速度收斂[21]，累積遺憾）；FTRL 和FTL（follow the leader）算法采用近似神諭時(shí)，對(duì)于半凸損失函數(shù)可以達(dá)到T-1的遺憾界[22]， α=T-1/2.在上述應(yīng)用中， β=0 ，只有 α被用作近似神諭的參數(shù).

2 非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性分析

2.1 非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法

非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法的原理是迭代T輪，每輪產(chǎn)生一個(gè)隨機(jī)向量 σ（該向量服從關(guān)于參數(shù) η的指數(shù)分布），并獲得一個(gè)假設(shè)w，該假設(shè)來(lái)自于 (α,β)-近似離線(xiàn)神諭模型，然后，學(xué)習(xí)者會(huì)遭受相應(yīng)損失并調(diào)整假設(shè).算法1 給出當(dāng)學(xué)習(xí)者可以訪(fǎng)問(wèn) (α,β)-近似離線(xiàn)神諭的非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的算法.

算法1.非凸的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法.

輸入：參數(shù)η，近似神諭ORALα,β；

輸出：w*∈W.

①fort=1,2,…,Tdo

③ 學(xué)習(xí)者在時(shí)刻t的假設(shè)：

⑤ 學(xué)習(xí)者遭受損失?t；

⑥ end for

與在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)相比，廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)中包含一個(gè) σ項(xiàng)，是一個(gè)具有更強(qiáng)魯棒性、更廣義的算法.一些在線(xiàn)學(xué)習(xí)算法，如在線(xiàn)鏡像下降（online mirror descent，OMD）[23]、 在線(xiàn)梯度下降（online gradient decent ，OGD）[24]、FTL、FTRL 等，通常需要在凸甚至強(qiáng)凸的條件下實(shí)現(xiàn)收斂.文獻(xiàn)[20]通過(guò)損失函數(shù)的隨機(jī)擾動(dòng)來(lái)保證遺憾消失，這種隨機(jī)擾動(dòng)具有與FTRL 和OMD 中使用的顯式正則項(xiàng)類(lèi)似的作用，將廣義在線(xiàn)單點(diǎn)學(xué)習(xí)算法擴(kuò)展到非凸設(shè)置中，然而缺少關(guān)于非凸在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的內(nèi)容.針對(duì)這一問(wèn)題，本文將單點(diǎn)學(xué)習(xí)擴(kuò)展到點(diǎn)對(duì)設(shè)置中，通過(guò)穩(wěn)定性分析將在線(xiàn)點(diǎn)對(duì)中的點(diǎn)對(duì)耦合進(jìn)行解耦，從形式上把具有耦合的點(diǎn)對(duì)通過(guò)穩(wěn)定性分析變換成2 步假設(shè)之間的差，從而實(shí)現(xiàn)單點(diǎn)到點(diǎn)對(duì)學(xué)習(xí)的推廣.

2.2 穩(wěn)定性分析

算法穩(wěn)定性是機(jī)器學(xué)習(xí)理論分析中一個(gè)重要的概念.穩(wěn)定性可以衡量一個(gè)學(xué)習(xí)算法的輸出對(duì)訓(xùn)練數(shù)據(jù)集微小變化的敏感性.對(duì)于批量學(xué)習(xí)假設(shè)中獨(dú)立同分布的樣本，穩(wěn)定性是可學(xué)習(xí)性的一個(gè)關(guān)鍵特性.類(lèi)似地，對(duì)于在線(xiàn)學(xué)習(xí)的可學(xué)習(xí)性，穩(wěn)定性條件也是同樣有效的.一種特別常用的穩(wěn)定性度量方式是一致穩(wěn)定性，已經(jīng)被廣泛應(yīng)用到在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)中，除此以外，還有由定義2 給出的平均穩(wěn)定性.下文中用aTb或 〈a,b〉表 示a和b之 間 的 歐 幾 里 得 點(diǎn) 積.用‖·‖表示2 范 數(shù)， ‖·‖p來(lái) 表 示 一 個(gè) 特 定 的 ?p范 數(shù).若|f(x)-f(y)|≤G‖x-y‖,?x,y∈C ，則稱(chēng)f:C →R是關(guān)于‖·‖ 范 數(shù)G-Lipschitz 連續(xù)的.

定義2.[18,25]假設(shè)學(xué)習(xí)者遭受的損失序列是GLipschitz 連續(xù)的.若 ? γ ＞0使得

則稱(chēng)算法 A 是 γ-平均穩(wěn)定的.

顯然，平均穩(wěn)定性比一致穩(wěn)定性（||?t(wt,z,z′)-?t+1(wt+1,z,z′)||≤Gγ）更弱，因?yàn)榍罢咭蟮臈l件僅僅是wt的期望值和平均值滿(mǎn)足不等式（1）.本文主要研究平均穩(wěn)定性，所有定理采用的也是平均穩(wěn)定性，以此放松理論分析中的假設(shè)條件.

穩(wěn)定性分析首先將廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的期望遺憾與平均穩(wěn)定性建立聯(lián)系.如定理1 所示，構(gòu)建了廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的期望遺憾與平均穩(wěn)定性的相關(guān)性.

定理1.假設(shè)D為決策集W?Rd的界，學(xué)習(xí)者遭受的損失滿(mǎn)足 ?1范 數(shù)的G-Lipschitz 連續(xù)性.則廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾上界可以表示為

本文研究“遺忘的對(duì)手”設(shè)定，因此只需使用單一的隨機(jī)向量 σ，而不是在每次迭代中生成一個(gè)新的隨機(jī)向量.wt(σ)為非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)基于隨機(jī)擾動(dòng) σ ，在第t次迭代時(shí)的假設(shè).

對(duì)于任意w*∈W，都有

令γ(σ)=α+β‖σ‖1.由歸納法證明

步驟T= 1：由于w2是 ?1(w,z,z′)-〈σ,w〉的近似最小化，因此

式（3）中最后一個(gè)不等式對(duì)任何w*∈W均成立.即

歸納步驟：假設(shè)歸納對(duì)所有T≤T0-1成立，下面證明它對(duì)T0也成立.

其中①處是由于歸納對(duì)任何T≤T0-1都成立，而②處是由于wT0+1的近似最優(yōu)化.

由上述結(jié)果，得到非凸的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的期望遺憾上界：

由指數(shù)分布的屬性E[σi]=得證.證畢.

定理1 表明期望遺憾與平均穩(wěn)定性相關(guān).式（2）中的穩(wěn)定性即為定義2 中的平均穩(wěn)定性.定理1 的證明是受文獻(xiàn)[26]的啟發(fā)，證明了當(dāng)平均穩(wěn)定性的上界可得時(shí)，遺憾也可以實(shí)現(xiàn)收斂.因此，定理2 將著重于研究穩(wěn)定項(xiàng)E[‖wt-wt+1‖1]的上界.

定理2.wt(σ) 為 廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)在第t次迭代時(shí)的假設(shè)，其中， σ為隨機(jī)擾動(dòng).ei表 示第i個(gè)標(biāo)準(zhǔn)基向量，wt,i表 示wt在i坐標(biāo)上的假設(shè).對(duì)于任意c＞0，都有單調(diào)性成立：

其中①處是由于wt(σ′)的近似最優(yōu)化.結(jié)合式（4）中的第1 項(xiàng)和最后1 項(xiàng)，得

定理2 證明了包含隨機(jī)擾動(dòng)項(xiàng) σ的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性.通過(guò)觀(guān)察擾動(dòng)向量的變化對(duì)廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的輸出產(chǎn)生的影響，表明了其在一維情況下的單調(diào)性，由于在線(xiàn)學(xué)習(xí)中穩(wěn)定性是指相鄰2 次迭代得到的假設(shè)之間的距離，因此，定理2 得到的即為一維情況下的穩(wěn)定性.

定理3.wt(σ)為 廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)在第t次迭代時(shí)的假設(shè)，其中 σ為隨機(jī)擾動(dòng).ei表 示第i個(gè)標(biāo)準(zhǔn)基向量，wt,i表示wt在i坐標(biāo)上的假設(shè).假設(shè)‖wt(σ)-wt+1(σ)‖1≤有單調(diào)性成立：

其 中①處 是 由 于 ?t(·)的Lipschitz 連 續(xù) 性，②處 是 由于‖wt(σ)-wt+1(σ)‖1上 的 假 設(shè).由wt+1(σ′)的 近 似 最 優(yōu)化，得

其中①處是由于wt+1(σ)的近似最優(yōu)化.結(jié)合式（5）和式（6），得

同理

從定理2 中的單調(diào)性，得

結(jié)合上述不等式（7）～（10）得證.證畢.

定理3 證明了d維情況下廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性.雖然d維相較于一維的單調(diào)性證明會(huì)更具挑戰(zhàn)性，但可以通過(guò)分別改變擾動(dòng)項(xiàng)的每個(gè)坐標(biāo)來(lái)有效地將分析減少到一維.同理，定理2 由單調(diào)性表明在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性可得d維情況下的穩(wěn)定性.

3 非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾界

利用定理1 所給出的非凸的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)穩(wěn)定性分析，對(duì)其遺憾界進(jìn)行研究.由于定理2 和定理3 分別給出了一維和高維情況穩(wěn)定性E[‖wt-wt+1‖1]的界，結(jié)合定理2 和定理3 引導(dǎo)定理4，對(duì)定理4 進(jìn)行討論.

定理4.假設(shè)D為 決策集W?Rd的界.學(xué)習(xí)者遭受的損失滿(mǎn)足 ?1范 數(shù)的G-Lipschitz 連續(xù)性.學(xué)習(xí)者可訪(fǎng)問(wèn) ( α,β) -近似神諭.對(duì)于任意 η，廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的假設(shè)都滿(mǎn)足遺憾界：

證明.使用與定理2 和定理3 中相同的符號(hào)定義，E[‖wt(σ)-wt+1(σ)‖1]也記作

因此，由E[||wt,i(σ)-wt+1,i(σ)||],?i∈[d]的界，可得E[‖wt(σ)-wt+1(σ)‖1]的 界.對(duì) 于 任 意 的i∈[d]，定 義E-i[||wt,i(σ)-wt+1,i(σ)||]為

其中σj是 σ第j個(gè)坐標(biāo)值.

令wmax,i(σ)=max(wt,i(σ),wt+1,i(σ)).類(lèi) 似 地，令

定義

對(duì)式（12）中的T1,T2求取下界：

由于第i個(gè)坐標(biāo)的域位于某個(gè)長(zhǎng)度為D的 區(qū)間內(nèi)，并且由于T1和E-i[wmax,i(σ)]是這個(gè)區(qū)間的點(diǎn)，它們的差值被D所 界限.所以T1的 下界為E-i[wmax,i(σ)]-D.將T2重新定義為：

改變積分中的1 個(gè)變量，令 σi=σ′i+100Gd且σ′=(σ1,σ2,…,σi-1,σ′i,σi+1,…)是 將在第i個(gè) 坐標(biāo)的 σ替換為得到的向量，得

則T2=exp(-100ηGd)E-i[wmin,i(σ+100Gdei)].將T1,T2的下界代入式（12）中，可得

則E-i[wmin,i(σ)]下界：

其中式（13）中第1 個(gè)不等式來(lái)自于定理2 和定理3，第2 個(gè) 不 等 式 來(lái) 自 于 εc的 定 義.由P-i(ε)≤1，可 得

其中①處是由于.得exp(w)≥1+w

將式（15）代入到式（11）中，可得穩(wěn)定性界：

將式（16）代入式（2）中，得證.證畢.

Table 1 Comparison of Online Pairwise Learning Regret Bounds表1 在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)遺憾界對(duì)比

由表1 可知，本文對(duì)具有非凸損失函數(shù)的廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)得到了O(T-1/2)的遺憾界優(yōu)于已有的遺憾界.

4 結(jié)束語(yǔ)

本文通過(guò)引入隨機(jī)噪聲提出了廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)框架.基于文獻(xiàn)[26]提出的近似神諭的近似最優(yōu)假設(shè)，提出了非凸廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)算法.進(jìn)一步，對(duì)廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)進(jìn)行泛化性研究，通過(guò)穩(wěn)定性分析，得到廣義在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾界O(T-1/2).

基于在線(xiàn)梯度下降算法，可進(jìn)一步研究具有非凸損失函數(shù)的在線(xiàn)點(diǎn)對(duì)學(xué)習(xí)的遺憾界.此外，本文中的遺憾界和平均穩(wěn)定性結(jié)果是建立在期望意義下的，而如何得到高概率的界也是未來(lái)可進(jìn)行的工作.

作者貢獻(xiàn)聲明：郎璇聰負(fù)責(zé)研究方案的設(shè)計(jì)、證明推導(dǎo)，以及論文的撰寫(xiě)和修改；李春生指導(dǎo)論文撰寫(xiě)與修改；劉勇提出論文研究思路、設(shè)計(jì)研究方案；王梅指導(dǎo)論文結(jié)構(gòu)設(shè)計(jì).