Robust Optimization for Non-Convex Objectives - todo314 @ ウィキ

Robust Optimization for Non-Convex Objectives

• Robert Chen, Brendan Lucier, Yaron Singer, Vasilis Syrgkanis
• NIPS 2017

概要

• シナリオごとの最適化をしたい→関数族の上で最悪時を扱います（ロバスト最適化）
• $$\alpha$$-近似ベイズ信託があれば良い
• 応用
  • ニューラルネットでの統計的学習…色んな損失関数をロバストに最適化
  • 影響最大化…Robust Influence Maximizationを踏襲してるが、なんでも使える

問題定式化と提案手法

• 解きたい $$ \min_{x \in {\cal X}} \max_{i \in [m]} L_i(x) = \tau $$
• 諦める $$ \min_{{\cal P} over {\cal X}} \max_{i \in [m]} \mathsf{E}_{x \sim {\cal P}}[L_i(x)] = \tau^* $$
• α近似ベイズ信託 $$ \min_{x \in {\cal X}} \sum_{i \in [m]} w_t[i]L_i(x) $$
• 提案手法は、Multiplicative Weights風味

近似の結果

• 返された分布Pのスコア $$ \leq \alpha \tau + \sqrt{\frac{2 \log(m)}{T}} $$
  • 実際には、$$\tau$$じゃなくて、$$\tau^*$$でもOK
  • どっちかというとポートフォリオ
• 凸な場合
  • Xが凸空間で、L_iが凸関数 : 平均ベクトルを返せば良い
• 劣モジュラな場合
  • 和をとった単一集合を返す：$$ k\cdot \frac{\log m}{\tau \epsilon^2} $$サイズになる…

実験

• 簡単のため、fはタダの到達可能頂点数
• {G_1, …, G_m}上の最悪時最適化
• (1)各グラフを貪欲で解いて、重み1/mのポートフォリオ
• (2)平均で貪欲
• (3)なんか重いを変えてやるらしい…

まとめ

• 要はポートフォリオですよね？
• そう考えると、分布から取り出して使う、という用例はあまり…

NIPS ロバスト最適化 劣モジュラ 影響最大化

2018/08/05