Question
Q. 樹籬算法(Hedge algorithm)的公平性基礎?
Q. 樹籬算法(Hedge algorithm)的公平性基礎?
Evidence: 2021:Best-Case Lower Bounds in Online Learning
此作能達到anytime group fairness
DTOL(Decision-Theoretic Online Learning)裡面的group fairness: 每一組的平均損失一樣:
- 每一輪, Learner會面對一個group $g_{t}$, 接著要play action $w_{t}$
- 每個專家, 會在群體層面平衡失誤.
- 專家j, 在特定組別的時間, 犯的錯加起來, 成為$L_{T(g),j}$.
- 任兩組的「平均損失」是均衡的, 成為「孤獨公平(Fair in isolation)」.
達到公平的做法:Interleaved Hedge:
- 常數學習率, 已知時間界線
- 在每一群體自己跑「樹籬算法(Hedge)」–> 每個子序列自己跑.
- Interleaved Hedge的後悔為$O(\sqrt{T})$.
Interleaved Hedge的群體公平保證:
- 另外有「群體公平保證」, 任兩組的公平差異大概是$O(\sqrt{\frac{\log d}{T_0}})$
- 這個文章可以給更好的regret bound, 不只是rate, 而是真實的upper bound.
- 原作法需要知道「每個子序列的長度」, 但這個文章用anytime best-case lower bound來做, 可以給很大的改善.
- 他們的貢獻可以得到「anytime群體公平」. 很酷👍.
- 此文章講了一些adaptivity下, 可以重新檢視group-fair adversarial online learning.
我們可以想: adversarial online learning的group fairness可能達不太到; 此文章的adaptivity的狀況可以達到group fairness; 那麼更中間的adaptivity是否能達到group fairness?
隨時公平, 計算公平性落差的框架
公平性落差(Fairness Gap)的證明策略:
- 改證明的策略: 每一群體, 找出損失最少的那個專家
- 每群體自己跑樹籬算法, 找出損失最少那個群體
- 用此文章的bound, 可以算fairness optimality gap.
- 用Decreasing Hedge, 可以證明另外一個bound. 藉此達到fairness gap的證明
隨時公平(Anytime Fairness):
- 固定horizon看fairness不是太有用
- 定義anytime fairness的概念
- 會讓這個定義只是「大概approximately」滿足
- 藉此證明一個anytime fairness的結果.
在應用上, 怎樣的是group呢? 可否用Multi-agent的框架來? distributed learning? 如何描述?
四種Adaptivity: 決策邊界免疫, 最優專家後悔, 資料幾何適應, 最好專家序列(負後悔)
-
- Anytime 算法: 不用知道決策邊界
-
- Timeless算法: 後悔決定於最優的專家
-
- AdaGrad: 適應資料的幾何 (Duchi et al., 2011)
-
- Shifting regret, tracking regret: 與最好專家序列對戰(產生負後悔) (Herbster and Warmuth, 1998)
Answer
A. 隨即群體公平的落差分析
🤔 更中間的adaptivity是否能達到group fairness?
這次的50分鐘體會了, 原來適應性有四種, 還可以得到「負的regret」！這樣玩一玩感覺都有新框架. 而這個文章將這個第四框架設定為best-case lower bounds, 在這裡面研究regret的表現. 不知道這種算法, 跟bandit搭配起來是如何, 感覺是理論上很有趣的問題. 裡面還有提到湯姆森取樣在adversarial bit prediction的比較, 好好玩!
評論