Achieving All with No Parameters: AdaNormalHedge

[nocotan]

一言でいうと

Parameter-freeな適応的最適化手法であるAdaNormalHedgeを提案．

論文リンク

著者/所属機関

Haipeng Luo (Princeton University), Robert E. Schapire (Microsoft Research)

投稿日付(yyyy/MM/dd)

2015/02/20

概要

エキスパート付き予測問題のオンライン学習において，複数の目的関数を事前知識なしに同時に最適化するparameter-freeな適応的アルゴリズムを提案．
提案手法であるAdaNormalHedgeはNormalHedge.DT algorithm (Luo and Schapire, 2014)の改良版になっている．

提案手法は，

• 損失が小さい時はリグレットも小さくなり，
• 損失が確率的な時はリグレットがほぼ定数になる

ことを保証している．

新規性・差分

NormalHedge.DTからの改善として

• AdaNormalHedgeは未知の目的関数を同時に最適化できる．
• AdaNormalHedgeはリグレットのバウンドが各ステップにおけるリグレットの累積に基づいて保証される．このバウンドは常にNormalHedge.DTより小さいことが保証される．

手法

結果

コメント

• Luo, Haipeng, and Robert E. Schapire. 2014. “A Drifting-Games Analysis for Online Learning and Applications to Boosting.” In Advances in Neural Information Processing Systems, edited by Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, 27:1368–76. Curran Associates, Inc.