Question
Q. 樹籬算法(Hedge algorithm)的證明技巧?
Q. 樹籬算法(Hedge algorithm)的證明技巧?
Evidence: 2021:Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization
測度集中: 凸包, 證明D.Hedge, FTRL-CARE, Meta-Care.
測度集中(Concentration of Measure):
- 非i.i.d.的「測度集中(Concentration of Measure)
- 可用來upper bounds本文章的三種算法: D.Hedge, FTRL-CARE, Meta-Care.
- 要求「凸限制級(Convex constraint)」; 非凸的就使用到「凸包(Convex hull)」.
- 凸集: 原始可用分佈的混合(Mixtures).
- 專家與環境都可以任選分佈來產生資料.
凸限制五實例:
隨機帶檻(Stochastic-with-a-gap):
- 只有一個真值$\mu_{0}$
- 存在一個最好的專家, 其與第二好的專家差$\Delta$.
對抗(Adversarial):
- 限制: 所有的機率測度 —> 對抗設定
對抗帶檻(Adversarial-with-a-gap):
- 混合最好的專家, 滿足gap條件
與Lasso bandit很多很像.
對抗帶期望檻(Adversarial-with-an-E-gap):
- 期望版本
球環IID(Ball-around-I.I.D.):
- 靠近的機率測度.
測度集中定理
定理一:
- 每一輪的「最好專家」可能不同, 可以接著用Azuma-Hoeffding inequality.
- 就算每一輪最好專家不同, 「最有效專家」與「任何無效專家」的gap至少上漲得如「均勻次高斯隨機變數」, 其均值為$-\Delta_0$.
- 證明依賴於von Neumann’s minimax theorem.
整個很抽象！需要補很多脈絡！
適應性 = (有效專家個數, 有效隨機檻)
時間一致凸限制 (Time-homogeneous convex constraints):
- N個專家
- 損失函數: $l:\hat{Y} \times Y \mapsto [0,1]$.
- 機率測度: $M(\hat{Y} \times Y )$
- 資料產生機制: $\pi$.
- 專家預測的條件分佈, 是time-homogeneously constrined.
有效專家(Effective Experts): $I_0(D)$收集可能在某些round成為最好專家的那些專家們.- $N_0(D)$: 有效專家的個數
有效隨機檻(Effective Stochastic Gap)$\Delta_0$: 「無效專家(ineffective expert)」相比較於「有效專家(Effective expert)」的最小的額外損失- 利用「(有效專家個數, 有效隨機檻)」來描述問題的「適應性(Adaptivity)」
- 接著收集相對應的資料生成機制.
怎麼感覺Lasso bandit也與expert很像, 可以分有效專家, 無效專家.
Answer
A. 隨即群體公平的落差分析
🤔 更中間的adaptivity是否能達到group fairness? 或者, 達到adaptively minimax optimal的預測子, 其group fairness完成的如何?
這次的50分鐘體會了, 這真的是一篇很技術性的paper! 竟然將適應性討論到了有幾個「有效專家」的地步. 感覺這是要先很了解「樹籬算法」的人, 才能appreciate他的工作. 可以下週再來挑戰.
評論