オンライン割当問題のための二重ミラー降下【JST・京大機械翻訳】

Lu Haihao; Balseiro Santiago; Mirrokni Vahab

プレプリント

J-GLOBAL ID：202202208658384818 整理番号：21P0025146

オンライン割当問題のための二重ミラー降下【JST・京大機械翻訳】

Dual Mirror Descent for Online Allocation Problems

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年02月24日プレプリントサーバーでの情報更新日： 2021年11月04日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

収入管理とオンライン広告における中心問題である凹型収入関数と資源制約を持つオンライン割当て問題を考察した。これらの設定において,要求は有限水平中に順次到達し,各要求に対して,意思決定者は,ある量の資源を消費し,収入を生成する行動を選択する必要がある。各要求の収入関数と資源消費は,意思決定者に未知である確率分布から独立して,ランダムで引き出される。目的は,資源の総消費に対する制約を受ける累積収入を最大化することである。著者らは,後視最適割当と比較して,準線形期待レグレットを達成する一般的クラスのアルゴリズムを設計した。提案アルゴリズムはLagrange二重空間で動作する:それらはオンラインミラー降下を用いて更新される各リソースに対して二重乗算器を維持する。参照関数を選択することによって,著者らは二重サブ勾配降下と二重指数重みアルゴリズムを回復する。得られたアルゴリズムは,単純,効率的であり,そして,地平の長さと資源の初期数が比例的にスケーリングされるとき,レグレットの最適次数を達成することを示した。予算制約と高エントロピーとのオンライン比例マッチングによる反復オークションにおけるオンライン入札への適用を論じた。【JST・京大機械翻訳】

, , , , , , ,
, , , , , 【Automatic Indexing@JST】

数理計画法 , 計算機網

, , ,

前のページに戻る