論文の概要: Online Learning via Offline Greedy Algorithms: Applications in Market
Design and Optimization
- arxiv url: http://arxiv.org/abs/2102.11050v1
- Date: Thu, 18 Feb 2021 19:05:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-23 15:07:16.145000
- Title: Online Learning via Offline Greedy Algorithms: Applications in Market
Design and Optimization
- Title（参考訳）: オフライングレーディアルゴリズムによるオンライン学習:市場設計と最適化への応用
- Authors: Rad Niazadeh (1), Negin Golrezaei (2), Joshua Wang (3), Fransisca
Susan (2), Ashwinkumar Badanidiyuru (3) ((1) Chicago Booth School of
Business, Operations Management, (2) MIT Sloan School of Management,
Operations Management, (3) Google Research Mountain View)
- Abstract要約: 我々は局所的エラーに頑健な欲望アルゴリズムを用いて,定数係数近似に適応可能なオフライン問題に焦点を当てた。
このような問題に対して,オフラインロバストなアルゴリズムをオンラインに効率的に変換する汎用フレームワークを提供する。
得られたオンラインアルゴリズムは、完全な情報設定の下で、$O(sqrtT)$ (approximate) の後悔を持つことを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Motivated by online decision-making in time-varying combinatorial
environments, we study the problem of transforming offline algorithms to their
online counterparts. We focus on offline combinatorial problems that are
amenable to a constant factor approximation using a greedy algorithm that is
robust to local errors. For such problems, we provide a general framework that
efficiently transforms offline robust greedy algorithms to online ones using
Blackwell approachability. We show that the resulting online algorithms have
$O(\sqrt{T})$ (approximate) regret under the full information setting. We
further introduce a bandit extension of Blackwell approachability that we call
Bandit Blackwell approachability. We leverage this notion to transform greedy
robust offline algorithms into a $O(T^{2/3})$ (approximate) regret in the
bandit setting. Demonstrating the flexibility of our framework, we apply our
offline-to-online transformation to several problems at the intersection of
revenue management, market design, and online optimization, including product
ranking optimization in online platforms, reserve price optimization in
auctions, and submodular maximization. We show that our transformation, when
applied to these applications, leads to new regret bounds or improves the
current known bounds.
- Abstract（参考訳）: 時間変化型コンビネーション環境でのオンライン意思決定を動機に、オフラインアルゴリズムをオンラインのコンビネーションに変換する問題を研究します。
局所誤差に対して堅牢なグリーディアルゴリズムを用いて、一定の因子近似に耐えうるオフラインコンビネーション問題に焦点を当てます。
このような問題に対して,我々は blackwell approachability を用いてオフラインロバストなアルゴリズムをオンラインアルゴリズムに効率的に変換する汎用フレームワークを提供する。
得られたオンラインアルゴリズムは、完全な情報設定の下で、$O(\sqrt{T})$(近似)後悔を持つことを示す。
さらに、Bandit Blackwell approachabilityと呼ばれるBlackwell approachabilityのBandit拡張についても紹介します。
我々はこの概念を利用して、強固なオフラインアルゴリズムをバンドイット設定で$o(t^{2/3})$(約)の後悔に変換する。
当社のフレームワークの柔軟性を示すために,オンラインプラットフォームにおける製品ランキング最適化,オークションにおけるリザーブ価格の最適化,サブモジュラリティの最大化など,収益管理,マーケットデザイン,オンライン最適化の交差点にあるいくつかの問題に,オフラインからオンラインへの変換を適用します。
これらのアプリケーションに適用した場合、我々の変換が新たな後悔境界をもたらすか、現在の既知の境界を改善するかを示す。
関連論文リスト
- Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。
本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。
そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
論文 参考訳（メタデータ） (2023-10-31T16:34:49Z) - Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - A Batch-to-Online Transformation under Random-Order Model [23.817140289575377]
本稿では,オンラインアルゴリズムの開発に利用可能な変換フレームワークについて紹介する。
オンライン$(k,z)$-clustering,オンライン行列近似,オンライン回帰など,さまざまな問題に適用する。
われわれのアルゴリズムは、一部のオンラインアプリケーションで望まれる低整合性も享受している。
論文 参考訳（メタデータ） (2023-06-12T14:50:21Z) - Online and Streaming Algorithms for Constrained $k$-Submodular
Maximization [25.15934533974176]
制約付き$k$-submodularは、広告アロケーション、インフルエンス、パーソナライズされたレコメンデーションなど、多くの個別の最適化問題をキャプチャする一般的なフレームワークである。
本研究では,モノトーンと一般(おそらく非モノトーン)の両方の目的に制約された$k$サブモジュールのシングルパスストリーミングとオンラインアルゴリズムを開発する。
論文 参考訳（メタデータ） (2023-05-25T12:53:17Z) - Learning-Assisted Algorithm Unrolling for Online Optimization with
Budget Constraints [27.84415856657607]
我々はLAAU(Learning-Assisted Algorithm Unrolling)と呼ばれる新しい機械学習支援アンローリング手法を提案する。
バックプロパゲーションによる効率的なトレーニングには、時間とともに決定パイプラインの勾配を導出します。
また、トレーニングデータがオフラインで利用可能で、オンラインで収集できる場合の2つのケースの平均的なコスト境界も提供します。
論文 参考訳（メタデータ） (2022-12-03T20:56:29Z) - Optimal Parameter-free Online Learning with Switching Cost [47.415099037249085]
オンライン学習における自由とは、後ろ向きの最適決定に対するアルゴリズムの適応性を指す。
本稿では,パラメータフリーで要求される楽観的な更新を,スイッチングコストを前提として,そのようなアルゴリズムを設計する。
本稿では,オンライン線形最適化 (OLO) のための簡易かつ強力なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-05-13T18:44:27Z) - Safe Online Bid Optimization with Return-On-Investment and Budget
Constraints subject to Uncertainty [87.81197574939355]
最適化問題と学習問題の両方について検討する。
我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。
より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
論文 参考訳（メタデータ） (2022-01-18T17:24:20Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Boosting for Online Convex Optimization [64.15578413206715]
多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。
弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。
ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-02-18T12:30:49Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Online Optimization with Memory and Competitive Control [43.974996526016305]
本稿では,メモリを用いたオンライン最適化問題に対する競合アルゴリズムを提案する。
本稿では,メモリによるオンライン最適化と,対向的障害を伴うオンライン制御の関連性を示す。
論文 参考訳（メタデータ） (2020-02-13T02:58:11Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。