去中心化在分散式學習中對錯誤率的影響

Abstract

我們探討在去中心化假說檢定的問題中，考慮一眾類於[11]所提出之演算法的做法下的理論極限。文獻[11]所提出的演算法保有良好的去中心化特性，網路中的各節點可自由選擇給予其各鄰居的權重，並在每回合根據自身所抽取的樣本及自己的概似函數構成與相鄰節點交換的訊息。然就錯誤機率而論，其演算法所能達到的錯誤率和經典假說檢定問題中的錯誤率之間存在著明顯的落差，而此落差正是受到在去中心化的情況下網路中某種“不平衡”影響而產生。 我們將此情形下的錯誤率刻畫為一最佳化問題，並提出原始演算法的推廣來補償此網路的不平衡性。佐以些許網路的全域訊息，我們證明在我們提出的廣義演算法下，網路中各節點進行假說檢定的錯誤率的首項漸進項能表現的和中心化的情況下一樣好。接著，我們也透過更高次項的漸進項來刻畫去中心化的代價—去中心化最多對錯誤率帶來常數倍的影響。 對於如何讓各節點獲得所需的全域訊息，我們也提出了相似的估計演算法，並刻畫估計量的收斂速度。除了理論結果之外，我們也針對數種情形進行模擬，模擬結果也支持我們提出的演算法以及前述的理論結果。最後，我們也提供了後續的討論以及如何將我們的結果延伸至較一般的問題。