論文の概要: Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods
- arxiv url: http://arxiv.org/abs/2402.07108v2
- Date: Tue, 28 May 2024 20:43:21 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-30 23:31:04.287924
- Title: Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods
- Title（参考訳）: Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods
- Authors: Wenzhi Gao, Chunlin Sun, Chenyu Xue, Dongdong Ge, Yinyu Ye,
- Abstract要約: 意思決定から学習を分離する新しいアルゴリズムフレームワークを導入する。
初めて、この新しいフレームワークで、一階述語メソッドが、$mathcalO(sqrtT)$を後悔できることを示す。
- 参考スコア（独自算出の注目度）: 7.518108920887426
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical success of first-order methods, they typically achieve a regret no better than $\mathcal{O}(\sqrt{T})$, which is suboptimal compared to the $\mathcal{O}(\log T)$ bound guaranteed by the state-of-the-art linear programming (LP)-based online algorithms. This paper establishes several important facts about online linear programming, which unveils the challenge for first-order-method-based online algorithms to achieve beyond $\mathcal{O}(\sqrt{T})$ regret. To address the challenge, we introduce a new algorithmic framework that decouples learning from decision-making. For the first time, we show that first-order methods can attain regret $\mathcal{O}(T^{1/3})$ with this new framework.
- Abstract（参考訳）: オンライン線形プログラミングは、収益管理と資源配分の両方において重要な役割を担い、近年では効率的な一階オンライン学習アルゴリズムの開発に重点を置いている。
一階法の実証的な成功にもかかわらず、それらは一般に$\mathcal{O}(\sqrt{T})$に劣らない後悔を達成し、これは、最先端の線形プログラミング(LP)ベースのオンラインアルゴリズムによって保証される$\mathcal{O}(\log T)$に比して最適である。
本稿では,オンライン線形プログラミングに関するいくつかの重要な事実を整理し,一階法に基づくオンラインアルゴリズムが$\mathcal{O}(\sqrt{T})を超えることの難しさを明らかにする。
この課題に対処するために、意思決定から学習を分離する新しいアルゴリズムフレームワークを導入する。
初めて、この新しいフレームワークで一階法が後悔する$\mathcal{O}(T^{1/3})$が得られることを示す。
関連論文リスト
- Efficient Methods for Non-stationary Online Learning [67.3300478545554]
本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。
本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
論文 参考訳（メタデータ） (2023-09-16T07:30:12Z) - PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。
我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。
これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
論文 参考訳（メタデータ） (2022-01-19T22:21:21Z) - Nearly Optimal Linear Convergence of Stochastic Primal-Dual Methods for
Linear Programming [5.126924253766052]
提案手法は,高い確率で鋭いインスタンスを解くための線形収束率を示す。
また、制約のない双線型問題に対する効率的な座標ベースのオラクルを提案する。
論文 参考訳（メタデータ） (2021-11-10T04:56:38Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Efficient Online-Bandit Strategies for Minimax Learning Problems [21.300877551771197]
いくつかの学習問題は、例えば、実験的な分散ロバスト学習や、非標準集約的損失による最小化といった、min-max問題の解決に関係している。
具体的には、これらの問題は、モデルパラメータ$winmathcalW$と、トレーニングセットの実証分布$pinmathcalK$で学習を行う凸線型問題である。
効率的な手法を設計するために、オンライン学習アルゴリズムを(組合せ)帯域幅アルゴリズムと対戦させる。
論文 参考訳（メタデータ） (2021-05-28T16:01:42Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Strongly Adaptive OCO with Memory [49.319621885036035]
本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。
このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
論文 参考訳（メタデータ） (2021-02-02T17:26:08Z) - Online Linear Optimization with Many Hints [72.4277628722419]
本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。
この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
論文 参考訳（メタデータ） (2020-10-06T23:25:05Z) - Online Learning with Imperfect Hints [72.4277628722419]
オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。
我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
論文 参考訳（メタデータ） (2020-02-11T23:06:09Z) - Faster Projection-free Online Learning [34.96927532439896]
我々は、一般的なオンライン凸最適化に対してT2/3$の後悔を保証する効率的なプロジェクションフリーアルゴリズムを提案する。
提案手法はFollow-the-Perturbed-Leader法を用いて導出し,オンライン・プライマリ・デュアル・フレームワークを用いて解析する。
論文 参考訳（メタデータ） (2020-01-30T21:18:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。