論文の概要: Online Learning under Budget and ROI Constraints via Weak Adaptivity

• arxiv url: http://arxiv.org/abs/2302.01203v3
• Date: Sat, 2 Mar 2024 17:26:22 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-05 21:12:34.530715
• Title: Online Learning under Budget and ROI Constraints via Weak Adaptivity
• Title（参考訳）: 弱適応性による予算・ROI制約下のオンライン学習
• Authors: Matteo Castiglioni, Andrea Celli, Christian Kroer
• Abstract要約: 制約付きオンライン学習問題に対する既存の原始双対アルゴリズムは、2つの基本的な仮定に依存している。 このような仮定は、標準の原始双対テンプレートを弱適応的後悔最小化器で与えることによって、どのように回避できるのかを示す。 上記の2つの前提が満たされていない場合に保証される、世界の最高の保証を証明します。
• 参考スコア（独自算出の注目度）: 57.097119428915796
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning problems in which a decision maker has to make a sequence of costly decisions, with the goal of maximizing their expected reward while adhering to budget and return-on-investment (ROI) constraints. Existing primal-dual algorithms designed for constrained online learning problems under adversarial inputs rely on two fundamental assumptions. First, the decision maker must know beforehand the value of parameters related to the degree of strict feasibility of the problem (i.e. Slater parameters). Second, a strictly feasible solution to the offline optimization problem must exist at each round. Both requirements are unrealistic for practical applications such as bidding in online ad auctions. In this paper, we show how such assumptions can be circumvented by endowing standard primal-dual templates with weakly adaptive regret minimizers. This results in a ``dual-balancing'' framework which ensures that dual variables stay sufficiently small, even in the absence of knowledge about Slater's parameter. We prove the first best-of-both-worlds no-regret guarantees which hold in absence of the two aforementioned assumptions, under stochastic and adversarial inputs. Finally, we show how to instantiate the framework to optimally bid in various mechanisms of practical relevance, such as first- and second-price auctions.
• Abstract（参考訳）: 我々は、予算と投資リターン(roi)の制約に固執しながら、期待する報酬を最大化することを目的として、意思決定者が一連のコストのかかる意思決定をしなければならないオンライン学習問題を研究する。 敵対的入力下でのオンライン学習問題を制約するために設計された既存の原始的アルゴリズムは、2つの基本的な仮定に依存している。 まず、意思決定者は、問題の厳密な実現可能性(すなわちスレーターパラメータ)の度合いに関連するパラメータの値を事前に知る必要がある。 第二に、オフライン最適化問題に対する厳密な解決法が各ラウンドに存在する必要がある。 どちらの要件も、オンライン広告オークションの入札のような実用的な応用には非現実的である。 本稿では,弱適応型後悔最小値を持つ標準原始的テンプレートを内挿することで,このような仮定を回避できることを示す。 これにより `dual-balancing'' フレームワークが作成され、スレーターのパラメータに関する知識がなくても、双対変数が十分に小さく保たれることが保証される。 我々は、前述した2つの仮定の欠如を確率的かつ逆の入力の下で保持する、初めて両世界の最高のノンレグレット保証を証明する。 最後に、第1および第2価格オークションのような実用的妥当性の様々なメカニズムを最適に入札するためのフレームワークのインスタンス化方法を示す。

関連論文リスト

• Deep Generative Demand Learning for Newsvendor and Pricing [7.594251468240168]
  我々は、機能ベースのニュースベンダ問題において、データ駆動の在庫と価格決定について検討する。 本稿では,これらの課題に対処するために条件付き深層生成モデル(cDGM)を活用する新しいアプローチを提案する。 我々は、利益予測の整合性や最適解への決定の収束など、我々のアプローチに対する理論的保証を提供する。
  論文  参考訳（メタデータ） (2024-11-13T14:17:26Z)
• Selling Joint Ads: A Regret Minimization Perspective [7.288063443108292]
  オンライン小売によるモチベーションにより、一品(広告スロットなど)を2つの非排除購入者(商店、ブランド等)に販売する問題を考える。 この問題は、例えば、マーチャントとブランドが商品を宣伝するために競売に協力して入札する状況と、表示されている広告の恩恵を捉えている。 メカニズムは2つの入札を収集し、どちらを割り当てるか、どの支払いを行うかを決定する。
  論文  参考訳（メタデータ） (2024-09-12T07:59:10Z)
• Near-Optimal Solutions of Constrained Learning Problems [85.48853063302764]
  機械学習システムでは、振る舞いを縮小する必要性がますます顕在化している。 これは、双対ロバスト性変数を満たすモデルの開発に向けた最近の進歩によって証明されている。 この結果から, 豊富なパラメトリゼーションは非次元的, 有限な学習問題を効果的に緩和することが示された。
  論文  参考訳（メタデータ） (2024-03-18T14:55:45Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Online Learning with Knapsacks: the Best of Both Worlds [54.28273783164608]
  オンライン学習の課題として,意思決定者が,リソース制約の有限セットに違反することなく,期待する報酬を最大化したい,という課題を提起する。 当社のフレームワークは,意思決定者がそのエビデンスを柔軟かつコスト論的に扱えるようにします。
  論文  参考訳（メタデータ） (2022-02-28T12:10:48Z)
• Online Allocation with Two-sided Resource Constraints [44.5635910908944]
  我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。 提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-28T02:21:06Z)
• Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems [1.6709415233613623]
  本稿では,分散的に不確実な力学系のクラスを対象とする最適化問題 (P) に対して,データ駆動型オンラインソリューションを構築するための新しい手法を提案する。 導入されたフレームワークは、パラメータ化された制御依存のあいまいさセットを通じて、分散システムの不確実性の同時学習を可能にする。 また、Nesterovの高速化段階アルゴリズムのオンライン版を導入し、その性能を分析して、分散性理論を用いてこの問題のクラスを解く。
  論文  参考訳（メタデータ） (2021-02-18T01:49:06Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  本稿では,オンライン分散ロバスト最適化(DRO)のクラスを解決するための実用的なオンライン手法を提案する。 本研究は,ネットワークの堅牢性向上のための機械学習における重要な応用を実証する。
  論文  参考訳（メタデータ） (2020-06-17T20:19:25Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。