“可預(yù)測(cè)的”非凸在線點(diǎn)對(duì)學(xué)習(xí)的遺憾界

中圖分類號(hào)： TP301. 5 文獻(xiàn)標(biāo)志碼：ADOI： 10.13705/j . issn. 1671-6841. 2023199

Abstract： Online pairwise learning is a machine learning model in which the loss functions depend on a pair of instances. Generalization is an important aspect of online pairwise learning theory research. Most of the existing works on online pairwise learning used adversarial loss functions and provided regret bounds only with convex loss functions. However， convexity was not typically applicable in practical scenarios. For non-convex online pairwise learning， the regret bound of online pairwise learning with a \" predictable\" loss function based on stability analysis was provided and the corresponding stability analysis was conducted. Through the relationship between stability and regret， a common way to measure the generalization ability of online pairwise learning， the regret bound was established with a \" predictable\" non-convex loss function. It was proved that when the learner obtained an offline oracle， \" predictable\" non-convex generalized online pairwise learning reached the regret bound of O（T^-3/2） . This study enriched the theoretical research on non-convex online pairwise learning and was superior to the existing theoretical guarantees.

Key words： online pairwise learning; non-convex; stability; regret bounds; offline optimization oracle

0 引言

在線點(diǎn)對(duì)學(xué)習(xí) 主要應(yīng)用于排序[ 1-3] 、度量學(xué)習(xí)[ 4] 等。 相較于傳統(tǒng)的批量學(xué)習(xí)，在線點(diǎn)對(duì)學(xué)習(xí)具有高效性、適應(yīng)性和實(shí)時(shí)性，更適用于實(shí)際應(yīng)用場(chǎng)景和大規(guī)模數(shù)據(jù)應(yīng)用，近年來得到了廣泛的關(guān)注。

在線點(diǎn)對(duì)學(xué)習(xí)的泛化能力是學(xué)習(xí)性能的重要表現(xiàn)之一，關(guān)于在線點(diǎn)對(duì)學(xué)習(xí)泛化性，有研究假設(shè)在線環(huán)境中有一系列獨(dú)立同分布的數(shù)據(jù)且損失函數(shù)一致有界的條件，通過在線轉(zhuǎn)批量的轉(zhuǎn)換界，首次提出在線點(diǎn) 對(duì) 學(xué) 習(xí) 的 超 過 泛 化 （ excess generalization ） 界O（T^-1）^[5-6] 。 Kar 等[ 7] 通過期望對(duì)稱化改進(jìn)了上述泛化界。 Ying 等[ 8-9] 基于非正則的再生核希爾伯特空間（RKHS） 的在線點(diǎn)對(duì)學(xué)習(xí)算法，放松了損失函數(shù)強(qiáng) 凸 性 和 有 界 性 的 假 設(shè) 條 件， 得 到 遺 憾 界O（T^-1/3logT） 。 Chen 等[ 10] 通過迭代序列更緊的一致約束，提高了算法最后迭代的收斂率，給出遺憾界O（T^-1/2） 。 Guo 等[ 11] 基于正則的 RKHS，對(duì)于特定的鉸 鏈 損 失 函 數(shù) 有 收 斂 結(jié) 果 O（T^-1/4logT1/2） 。Wang 等[ 12] 對(duì)具有多項(xiàng)式衰減步長(zhǎng)和多個(gè)正則化參數(shù)的在線點(diǎn)對(duì)學(xué)習(xí)算法，給出遺憾界 O（T^-2/3） 。 Hu等[ 13] 提出了基于分而治之策略的多正則化的分布式在線點(diǎn)對(duì)學(xué)習(xí)的誤差分析。

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

在線點(diǎn)對(duì)學(xué)習(xí)的理論研究中，通常假設(shè)損失函數(shù)是凸或強(qiáng)凸且基于對(duì)抗性選擇的，關(guān)于非凸損失函數(shù)的研究較為匱乏。 如果學(xué)習(xí)者（learner） 接收一個(gè)已知的“可預(yù)測(cè)的”損失函數(shù)序列，“ 可預(yù)測(cè)的” 是指具有關(guān)于損失函數(shù)序列先驗(yàn)知識(shí)的在線學(xué)習(xí)模式，比如方差[ 18] 和路徑長(zhǎng)度的界限[ 19] ，那么，遺憾界優(yōu)于對(duì)抗性選擇下的界[ 20] 。

針對(duì)上述問題，本文提出了基于穩(wěn)定性分析的“可預(yù)測(cè)的” 非凸在線點(diǎn)對(duì)學(xué)習(xí)的遺憾界。 本文主要工作有：1） 把原始的在線點(diǎn)對(duì)學(xué)習(xí)改寫為廣義的在線點(diǎn)對(duì)學(xué)習(xí)框架，并基于廣義在線點(diǎn)對(duì)學(xué)習(xí)提出“可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)算法;2） 建立了具有“可預(yù)測(cè)的” 非凸損失函數(shù)的廣義在線點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性分析;3） 根據(jù)穩(wěn)定性和遺憾之間的關(guān)系，證明了具有“可預(yù)測(cè)的” 非凸損失函數(shù)的廣義在線點(diǎn)對(duì)學(xué)習(xí)可達(dá)到最優(yōu)的遺憾界 。

1 在線點(diǎn)對(duì)學(xué)習(xí)

假設(shè)一個(gè)樣本空間 ， 其中： X?R^d 是一個(gè)輸入空間; Y?R 是一個(gè)輸出空間; 和y_λ∈Y 分別是輸入和輸出。 在線點(diǎn)對(duì)學(xué)習(xí)是學(xué)習(xí)一個(gè)預(yù)測(cè)函數(shù) 在一對(duì)實(shí)例（z，z^′） 上的性能由非負(fù)損失函數(shù) ?（w，z，z^′） 度量，即

排序和度量學(xué)習(xí)是點(diǎn)對(duì)學(xué)習(xí)經(jīng)典的應(yīng)用。 對(duì)于排序，函數(shù) 以與輸出一致的方式對(duì)實(shí)例 z= 進(jìn) 行 排 序， 即 若 ， 則 。 點(diǎn)對(duì)學(xué)習(xí)問題排序的形式化表述為 ， 其中：sgn 是符號(hào)函數(shù); ψ 可以是鉸鏈損失 ， 也可以是邏輯損失 。對(duì)于 Y={-1，1} 的監(jiān)督的度量學(xué)習(xí)，距離函數(shù)對(duì)具有相同標(biāo)簽的實(shí)例是相似的，而具有不同標(biāo)簽的實(shí)例彼此分離，一個(gè)常用的距離函數(shù)是 p（x，x^′）= ?w，（x-x^′）（x-x^′）^?? 。 點(diǎn)對(duì)學(xué)習(xí)問題度量學(xué)習(xí)的形式化表述為 ?（w，z，z^′）=ψ（τ（y，y^′）（1-p（x， ） ， 如果 y=y^′ ， 則 τ（y，y^′）=1 ， 否則為 ^-1 。

2 “可預(yù)測(cè)的”非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)

2. 1 廣義在線點(diǎn)對(duì)學(xué)習(xí)

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

廣義在線點(diǎn)對(duì)學(xué)習(xí)中包含一個(gè) σ 項(xiàng)，它是一個(gè)從 （參數(shù)為 η 的指數(shù)分布） 采樣的隨機(jī)噪聲。 引入隨機(jī)噪聲項(xiàng) σ 避免過擬合，提高在線點(diǎn)對(duì)學(xué)習(xí)的泛化能力。 因此，廣義在線點(diǎn)對(duì)學(xué)習(xí)是魯棒的在線點(diǎn)對(duì)學(xué)習(xí)更廣義的在線框架。 FTRL（ followthe regularized leader） 是 一 種 廣 泛 用 于 凸 假 設(shè) 的 算法[ 21] 。 當(dāng)廣義在線點(diǎn)對(duì)學(xué)習(xí)中的隨機(jī)噪聲為 μw 時(shí)，F(xiàn)TRL 即為廣義在線點(diǎn)對(duì)學(xué)習(xí)的一個(gè)特例，

基于廣義在線點(diǎn)對(duì)學(xué)習(xí)框架，學(xué)習(xí)者接收的損失序列是“可預(yù)測(cè)的”這種樂觀變體，可以得到更優(yōu)的遺憾界。 在某些應(yīng)用中，損失函數(shù)可能不是對(duì)抗性的，而是“ 可預(yù)測(cè)的”。 文獻(xiàn)[20] 表明，當(dāng)帶有自洽正則器的 FTRL 算法和在線鏡像下降（ online mir-roring descent，OMD）類型的算法包含一組可預(yù)測(cè)過程時(shí)，可以獲得更好的遺憾界。 在介紹廣義在線點(diǎn)對(duì)學(xué)習(xí)算法之前，簡(jiǎn)要介紹算法涉及的基本概念。

2. 2 離線神諭

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

基于神諭的學(xué)習(xí)模型可稱之為“ 可優(yōu)化的專家”，該模型本質(zhì)上是經(jīng)典的在線學(xué)習(xí)模型。 在“ 可優(yōu)化的專家”模型中，假設(shè)最初學(xué)習(xí)者對(duì)損失函數(shù) ? 是未知的，并允許學(xué)習(xí)者通過神諭來獲取 ? 。 離線神諭模型通過在線學(xué)習(xí)者提交一系列的損失函數(shù)，返回使累積損失最小的假設(shè)。 下面給出離線神諭模型的近似神諭模型定義。

定義 1^[22] 一個(gè)離線神諭模型，其輸入是一個(gè)損失函數(shù) 和一個(gè) d 維向量 σ ， 輸出是一個(gè) 的近似最小值。 若它返回的 w^*∈W 滿足

?（w^?，z，z^′）-?σ，w^??? 則稱其為“ （α，β） -近似神諭”。

方便 起 見， 將 一 個(gè) （α，β） - 近 似 神 諭 記 為 。 使用近似神諭是因?yàn)椴豢赡苤酪粋€(gè)假設(shè)是全局最小值或僅是一個(gè)鞍點(diǎn)。ORAL 可以輸出一個(gè) w 而不需要保證其最優(yōu)性。 在大多數(shù)情況下， w 只是近似最優(yōu)。 離線神諭模型（返回 與 （α，β） -近似神諭模型的區(qū)別在于，后者有一個(gè)關(guān)于變量 _α，β，σ 的擾動(dòng)項(xiàng)。 在指定 ^α，β 的大小時(shí)可獲得更好的遺憾界。近似神諭在在線單點(diǎn)學(xué)習(xí)中的應(yīng)用包括以下實(shí)例。

1） Query-GAN 算法。 當(dāng)采用近似神諭時(shí)， α= 為 累積遺憾），對(duì)于非凸損失函數(shù)以T^-1/2 的速度收斂 [ 23] ;

2） FTRL 和 FTL（ follow the leader） 算法。 當(dāng)采用近似神諭時(shí)， α=T^-1/2 ， 對(duì)于半凸損失函數(shù)可以達(dá)到 T - 1 的 遺 憾 界 [ 24] 。 C在實(shí)例 1） 和 2） 中， β=0 ， 只有 α 作為近似神諭的參數(shù)。

2. 3 “可預(yù)測(cè)的”非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)算法

假設(shè)損失函數(shù)是“可預(yù)測(cè)的”且學(xué)習(xí)者可以訪問一個(gè) （α，β） -近似離線優(yōu)化神諭。 令 g_t[?₁…?_t-1] 為第 χ_t 輪對(duì) ?_?t 的預(yù)測(cè)， g₁=0 。 給定 g_t ， 學(xué)習(xí)者可以訪問一個(gè) （α，β） -近似離線優(yōu)化神諭

則“可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)算法如算法 1。

算法 1 “ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)算法

輸入： η，ORAL_α，β ， 預(yù)測(cè)序列 g_t[?₁…?_t-1] 。

輸出： w^*∈W 。

1） for do

2） }jd= 1 ～ exp（η） / ? 生成隨機(jī)向量 σt? /

3） 學(xué)習(xí)者在 χ_t 時(shí)刻預(yù)測(cè)

5） 學(xué)習(xí)者遭受損失 ?_?t

6） end for

序列 g_t 相當(dāng)于在線點(diǎn)對(duì)學(xué)習(xí)中的先驗(yàn)知識(shí)，顯然當(dāng) g_t 近似 ?_ι 時(shí)，這種非凸且“可預(yù)測(cè)的”樂觀情況會(huì)有較小的遺憾。

3 穩(wěn)定性分析

算法穩(wěn)定性可以衡量一個(gè)學(xué)習(xí)算法的輸出對(duì)訓(xùn)練數(shù)據(jù)集微小變化的敏感性，是機(jī)器學(xué)習(xí)理論分析中一個(gè)重要的概念。 對(duì)于批量學(xué)習(xí)假設(shè)中獨(dú)立同分布的樣本，穩(wěn)定性是可學(xué)習(xí)性的一個(gè)關(guān)鍵特性。 類似地，穩(wěn)定性對(duì)于在線學(xué)習(xí)的可學(xué)習(xí)性具有同樣作用。 除常用的一致穩(wěn)定性以外，還有定義 2 所述的平均穩(wěn)定性。 接下來用 a^Tb 或 ?a，b? 表示 和 之間的歐幾里得點(diǎn)積; |?| 表示二范數(shù); |?|_p 表示一個(gè)特定的 ?_p 范數(shù)。 若 |f（x）-f（y）|?L|x-y| ，?x，y∈C ， 則稱 是關(guān)于 |?| 范數(shù) L -Lips-chitz 連續(xù)的。

定 義 2 [ 17，25] 假設(shè)學(xué)習(xí)者遭受的損失序列是 L. -Lipschitz 連續(xù)的。 若 ?γgt;0 使得 則稱算法 A 是 γ -平均穩(wěn)定的。

顯然，平均穩(wěn)定性比一致穩(wěn)定性 （ ）更弱，因?yàn)樗闪⒌臈l件僅僅是 w_t 的期望值和平均值滿足不等式（1）。 本文主要研究平均穩(wěn)定性，所有定理采用的也是平均穩(wěn)定性，以此作為理論分析中一種假設(shè)條件的放松。

穩(wěn)定性分析首先將廣義在線點(diǎn)對(duì)學(xué)習(xí)的期望遺憾與平均穩(wěn)定性建立聯(lián)系。 如定理 1 所示，構(gòu)建了“可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的期望遺憾與平均穩(wěn)定性的相關(guān)性。

定理 1 令 是 最小化，假設(shè) D 為決策集 W?R^d 的界，學(xué)習(xí)者遭受的損失滿足 ?₁ 范數(shù)的 -Lipschitz 連續(xù)性。 則 “ 可預(yù)測(cè)的”非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的上界為

證明 令 。 對(duì)于任意的 w^*∈W ，

歸納法證明，對(duì)于任意的 ，

均成立。

T=1 步驟： g₁=0 ， 由于 是 ?₁（w，z，z^′） -?σ，w? 的近似最小化，得

因此， w^*?

歸納步驟：假設(shè)歸納對(duì)所有 T?T₀-1 成立，則它對(duì) 也成立

T₀-1 其 中： [ ∑ ?t（ w T ，z，z′） + 〈 σ，w2 W +γ（ σ） （ T0 - 2） ] + [ gT （ w T ） - gT （ w T + 是由于對(duì)任意的 T?T₀-1 均成 是由于 w_T0 的近似最優(yōu)性。

綜上所述，得到“可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)有上界

證畢。

由定理 1 建立了穩(wěn)定性和“ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的遺憾界之間的關(guān)系，當(dāng)平均穩(wěn)定性的上界可得時(shí)，遺憾也可以實(shí)現(xiàn)收斂。 下面求穩(wěn)定性 的上界。

定理 2 令 w_t（σ） 是“ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)在第 χ_t 次的預(yù)測(cè)，對(duì)于任意的 cgt;0 有以下單調(diào)性成立 其中： σ 為隨機(jī)擾動(dòng); e_i 表示第 i 個(gè)標(biāo)準(zhǔn)基向量; w_t，i 表示 w_t 在 i 坐標(biāo)上的假設(shè)。

證明 令 =σ+ce_i，γ（σ）=α+β|σ|₁ 為離線神諭的近似誤差，由 w_t（σ） 的近似最優(yōu)化，可得 c（w_t，i（σ^′）-w_t，i（σ））+γ（σ）+γ（σ^′）， ，其 中： 是 由 于w_t（σ^′） 的近似最優(yōu)化，結(jié)合第一項(xiàng)和最后一項(xiàng)，得

證畢。

定理 2 證明了“ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性。 通過觀察擾動(dòng)向量的變化對(duì)廣義在線點(diǎn)對(duì)學(xué)習(xí)的輸出產(chǎn)生的影響，表明了其在一維情況下的單調(diào)性，由于在線學(xué)習(xí)中穩(wěn)定性是指相鄰兩次迭代得到的假設(shè)之間的距離，所以定理 2 所得即為一維情況下的穩(wěn)定性。

定理 3 w_t（σ） 為“ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)在第 χ_t 次迭代時(shí)的假設(shè)，假設(shè) - ， 對(duì)于任意的 σ^′=σ+100L_tde_i ， 可得

其中： σ 為隨機(jī)擾動(dòng); e_i 表示第 i 個(gè)標(biāo)準(zhǔn)基向量; w_t，i

表示 w_t 在 i 坐標(biāo)上的假設(shè)。證 明 令 為離線神諭的近似誤差， 由w_t（σ） 的近似最優(yōu)化，可得

其中： ， 是由于 ?_t（?） 的Lipschitz 連 續(xù) 性; + 是由于 上的假設(shè)。 由 w_t+1（σ^′） 的近似最優(yōu)化，得

其中： 是由于 w_t+1（σ） 的近似最優(yōu)化。 結(jié)合式 （3）～（4） ，得

同理

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

結(jié)合式（4） ～ （7） ，得證。

定理 3 證明了 d 維情況下“ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性。 雖然 d 維區(qū)別于一維的單調(diào)性證明會(huì)更具挑戰(zhàn)性，但可以通過分別改變擾動(dòng)項(xiàng)的每個(gè)坐標(biāo)有效地將分析減少到一維的情況，同理于定理 2 中由單調(diào)性表明在線點(diǎn)對(duì)學(xué)習(xí)的穩(wěn)定性，可得 d 維情況下的穩(wěn)定性。

4 “ 可預(yù)測(cè)的” 非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的遺憾界

定理 4 假設(shè) D 為決策集 W?R^d 的界。 假設(shè)預(yù)測(cè)序列 g_t 對(duì)于任意的 t∈[T] ， （g_t-?_t） 都滿足?₁ 范數(shù)下的 L_t -Lipschitz 連 續(xù) 性。 學(xué) 習(xí) 者 可 訪 問Φ（α，β）Φ- 近似優(yōu)化神諭。 對(duì)于任意的 η ， “ 可 預(yù) 測(cè)的”非凸廣義在線點(diǎn)對(duì)學(xué)習(xí)的預(yù)測(cè)都滿足以下遺憾界

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

因此，由 的界，可得 的界。 對(duì)于任意的 i∈[d] ， 定義 為

E_μ-i[σ∣w_μi，i（σ）α-w_μi+1，i（σ）α|α]：=

其中： σ_j 是 σ 在坐標(biāo)等于 j 的值。

令 w_max，i（σ）=max（w_t，i（σ），w_t+1，i（σ）） 。 類似地，令 w_min，i（σ）=min（w_t，i（σ），w_t+1，i（σ）） 。 則

定義

對(duì)下式中的 T₁，T₂ 求取下界

由于第 χ_i 個(gè)坐標(biāo)的域位于某個(gè)長(zhǎng)度為 D 的區(qū)間內(nèi)，并且由于 T₁ 和 是這個(gè)區(qū)間的點(diǎn)，它們 的 差 值 被 D 所 界 限。 所 以 T₁ 的 下 界 為 。 將 T₂ 重新定義為 改變上述積分中的一個(gè)變量，令 σ_i=σ_i^′+ 100L_td 且σ^′=[σ₁，…，σ_i-1，σ_i^′，σ_i+1，…] 是將在第 i 個(gè)坐標(biāo)的σ 替換為 σ_i^′ 得到的向量，得

則 e - 100ηLtd E - i [ w min，i（ σ + 100L t dei ） ] 。 將 T1 ，T2 的下界代入式（9）中，可得

則 E_Ω-i[w_min，i（σ）] 下界為

其中： P_-i（ε）：=P（ε∣{σ_j}_j≠i） 。 由定理 2 和定理3 證明的單調(diào)性，得 E_λ-i[ψ_min，i（σ）] 下界。 γ（σ）= ， 則

其中：不等式 $＼frac { 1 } { 1 0 } ＼mid ＼pmb { w } _ { ＼iota ， i } （ ＼pmb { ＼sigma } ） ＼ - ＼ ＼pmb { w } _ { ＼iota + 1 ， i } （ ＼pmb { ＼sigma } ） ＼mid ＼ - ＼frac { 3 ＼gamma （ ＼pmb { ＼sigma } ） } { 1 0 0 L _ { ＼iota } d } ＼ - ＼textit { ＼textbf { ＼beta } } ＼mid ＼pmb { ＼varepsilon } ＼mid ＼ +$ 來自于定理 2 和定理 3，不等式 來自 ∣ε^c 的定義。 由 ，得

由于 ， 所以上式的最后一步成立則

由于上述界對(duì)任意 {σ_j}_j≠i 均成立，因此可得無條件期望的界，

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

將式（11） 代入式（2） 中，得證。

由于定理 4 的假設(shè)是學(xué)習(xí)者可接收 （α，β）- 近似優(yōu)化神諭、損失函數(shù)是可預(yù)測(cè)的且是 -Lipschitz連續(xù)的，因此當(dāng) η = d3 / 2 T1 / 2 - d， 定理 4 可得遺憾界O（d^3/2T^-3/2+α+βd^3/2T^-1/2） 。 若取 ，β=O（T³） ， 可得最佳的遺憾界 $ { ＼mathcal ? O ? } （ T ^ { - 3 / 2 } ）$ 。

5 結(jié)語

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

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

參考文獻(xiàn)：

[1] 原晉江， 農(nóng)慶琴. 平行批排序最小化最大完工時(shí)間在線算法的一個(gè)注記 [ J]. 鄭州大學(xué)學(xué)報(bào)（ 理學(xué)版），2006， 38（3） ： 1-3.YUAN J J， NONG Q Q. A note on an on-line algorithm-for the parallel-batching scheduling to minimize makespan[ J] . Journal of Zhengzhou university （ natural scienceedition） ， 2006， 38（3） ： 1-3.

[2] 李文杰， 馬冉. 最大化接收工件個(gè)數(shù)的在線分批排序 問題 研 究 [ J] . 鄭 州 大 學(xué) 學(xué) 報(bào) （ 理 學(xué) 版 ） ， 2016， 48 （2） ：24-28. LI W J， MA R. Research on the online batch scheduling to maximize total number of the accepted jobs[ J] . Journal of Zhengzhou university （ natural science edition ） ， 2016， 48（2） ：24-28.

[ 3] REJCHEL W. On ranking and generalization bounds[ J] . Journal of machine learning research， 2012， 13： 1373 - 1392.

[ 4] WEINBERGER K Q， SAUL L K. Distance metric learning for large margin nearest neighbor classification [ J ] . Journal of machine learning research， 2009， 10： 207 - 244.

[5] WANG B， KHARDON R， PECHYONY D， et al. Generalization bounds for online learning algorithms with pairwise loss functions[ C]∥Annual Conference Computational Learning Theory. Berlin： Springer Press， 2012：1-22.

[6] WANG Y Y， KHARDON R， PECHYONY D， et al. Online learning with pairwise loss functions [ J] . Journal of machine learning research，2013，14：1-37.

[7] KAR P， SRIPERUMBUDUR B K， JAIN P， et al. On the generalization ability of online learning algorithms for pairwise loss functions [ EB / OL] . （ 2013-05-11） [ 2023- 07-22 ] . https： ∥ api. semanticscholar. org / CorpusID： 8366093.

[ 8] YING Y M， ZHOU D X. Unregularized online learning algorithms with general loss functions[ J] . Applied and computational harmonic analysis， 2017， 42（2）： 224-244.

[ 9] YING Y M， ZHOU D X. Online pairwise learning algorithms[J]. Neural computation， 2016， 28（4）： 743-777.

[ 10] CHEN X M， LEI Y W. Refined bounds for online pairwise learning algorithms [ J ] . Neurocomputing， 2018， 275： 2656-2665.

[11] GUO Z C， YING Y M， ZHOU D X. Online regularized learning with pairwise loss functions [ J ] . Advances in computational mathematics， 2017， 43（1） ： 127-150.

[ 12] WANG C， HU T. Online regularized pairwise learning with least squares loss [ J ] . Analysis and applications， 2020， 18（1） ： 49-78.

[13] HU T， FAN J， XIANG D H. Convergence analysis of distributed multi-penalty regularized pairwise learning [ J ] . Analysis and applications， 2020， 18（1）： 109-127.

[14] BOUSQUET O， ELISSEEFF A. Stability and generalization[ J] . Journal of machine learning research， 2002， 2： 499-526.

[15] ELISSEEFF A， EVGENIOU T， PONTIL M. Stability of randomized learning algorithms [ J] . Journal of machine learning research， 2005， 6： 55-79.

[16] SHEN W， YANG Z H， YING Y M， et al. Stability and optimization error of stochastic gradient descent for pairwise learning [ J] . Analysis and applications， 2020， 18 （5） ： 887-927.

[17] LEI Y W， LEDENT A， KLOFT M. Sharper generalization bounds for pairwise learning[ J] . Advances in neural information processing systems， 2020， 33： 21236-21246.

[ 18] HAZAN E， KALE S. Extracting certainty from uncertainty： regret bounded byvariation incosts[ J] . Machine learning， 2010， 80（2 / 3） ： 165-188.

[19] CHIANG C K， YANG T B， LEE C J， et al. Online optimization with gradual variations [ C ] ∥ Conference on Learning Theory. Berlin： Springer Press， 2012：1-20.

[20] RAKHLIN A， SRIDHARAN K. Online learning with predictable sequences [ EB / OL ] . （ 2012-08-18） [ 2023-07- 23] . https：∥arxiv. org / abs / 1208. 3728. pdf.

[ 21] MCMAHAN B. Follow-the-regularized-leader and mirror descent： equivalence theorems and l1 regularization[ C]∥ Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics. Cambridge： MIT Press， 2011： 525-533.

[22] AGARWAL N， GONEN A， HAZAN E. Learning in nonconvex games with an optimization oracle [ EB / OL ] . （ 2018-10-17 ） [ 2023-07-23 ] . https： ∥ arxiv. org / abs / 1810. 07362. pdf.

[ 23] FINE M. Certifiably accurate private data release with generative adversarial networks[ D] . Boston： Harvard University， 2020.

[24] GRNAROVA P， LEVY K Y， LUCCHI A， et al. An online learning approach to generative adversarial networks [ EB / OL] . （ 2017-06-10） [ 2023-07-22] . https：∥arxiv. org / pdf / 1706. 03269.

[ 25] ROSS S， BAGNELL J A. Stability conditions for online learnability [ EB / OL ] . （ 2011-08-16 ） [ 2023-07-22 ] . https：∥arxiv. org / pdf / 1108. 3154.

[26] SUGGALA A S， NETRAPALLI P. Online non-convex learning： following the perturbed leader is optimal [ EB / OL] . （2019-03-19） [ 2023-07-22] . https：∥arxiv. org / abs / 1903. 08110. pdf.