Talk by Holakou Rahmanian (University of California Santa Cruz)


Speaker: Holakou Rahmanian (University of California Santa Cruz)

Title: Online Dynamic Programming

We consider the problem of repeatedly solving a variant of the same dynamic programming problem in successive trials. An instance of the type of problems we consider is to find a good binary search tree in a changing environment. At the beginning of each trial, the learner probabilistically chooses a tree with the n keys. The learner is then told the frequencies of the keys and is charged by the average search cost for the chosen tree. The problem is online because the frequencies can change between trials. The goal is to develop algorithms with the property that their total average search cost (loss) in all trials is close to the total loss of the best tree chosen in hindsight for all trials. The challenge, of course, is that the algorithm has to deal with exponential number of trees. We develop a general methodology for tackling such problems for arbitrary dynamic programming algorithms with min-sum recurrence relations. Our framework allows us to extend online learning algorithms like Expanded Hedge and Component Hedge to a significantly wider class of combinatorial objects than was possible before.

Contact: Kohei Hatano (Kyushu / AIP)


※ こちらのイベント情報は、外部サイトから取得した情報を掲載しています。
※ 掲載タイミングや更新頻度によっては、情報提供元ページの内容と差異が発生しますので予めご了承ください。
※ 最新情報の確認や参加申込手続き、イベントに関するお問い合わせ等は情報提供元ページにてお願いします。
理化学研究所 革新知能統合研究センター
〒103-0027 東京都中央区日本橋1-4-1 日本橋一丁目三井ビルディング 15階


TECH PLAYでイベントをはじめよう。

TECH PLAYでは、テクノロジーに関連したイベントの告知やグループ運営のための機能を無料でご利用いただけます。まずはグループを作ってみましょう。