論文の概要: Infrequent Resolving Algorithm for Online Linear Programming
- arxiv url: http://arxiv.org/abs/2408.00465v3
- Date: Sun, 29 Sep 2024 03:47:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-01 21:57:50.197215
- Title: Infrequent Resolving Algorithm for Online Linear Programming
- Title（参考訳）: オンライン線形計画法における頻繁な解法
- Authors: Guokai Li, Zizhuo Wang, Jingwei Zhang,
- Abstract要約: 既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。
本稿では,LPを時間的水平線上でのO(loglog T)$倍だけ解きながら,常に後悔するアルゴリズムを提案する。
我々のアルゴリズムは、LPの$O(loglog T)$ timesと$Oleft(T(1/2+epsilon)Mright)$ regretを、LPの$M$ timesを解くことで、絶え間ない後悔を保証できる。
- 参考スコア（独自算出の注目度）: 3.247415064064425
- License:
- Abstract: Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications, such as online auction, network revenue management and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former one typically guarantees better performance, even offering a constant regret, but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithm only requires first-order computations but induces a worse performance, lacking a constant regret bound. In this work, we study the case where the inputs are drawn from an unknown finite-support distribution, and bridge the gap between these two extremes by proposing an algorithm that achieves a constant regret while solving LPs only $O(\log\log T)$ times over the time horizon $T$. Moreover, when we are allowed to solve LPs only $M$ times, we propose an algorithm that can guarantee an $O\left(T^{(1/2+\epsilon)^{M-1}}\right)$ regret. Furthermore, when the arrival probabilities are known at the beginning, our algorithm can guarantee a constant regret by solving LPs $O(\log\log T)$ times, and an $O\left(T^{(1/2+\epsilon)^{M}}\right)$ regret by solving LPs only $M$ times. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.
- Abstract（参考訳）: オンラインリニアプログラミング(OLP)は、オンラインオークション、ネットワーク収益管理、広告などの幅広い応用により、研究者と実践者の両方から大きな注目を集めている。
既存のOLPアルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。
前者は典型的にはパフォーマンスの向上を保証し、常に後悔しても良いが、計算コストのかかる大量のLPを解く必要がある。
対照的に、LPフリーアルゴリズムは1次計算しか必要としないが、より悪い性能を誘導し、絶え間ないリフレッシュバウンドを欠いている。
本研究では、未知の有限支持分布から入力が引き出される場合について検討し、この2つの極端間のギャップを、時間的地平線上でのO(\log\log T)$倍のLPを解きながら、絶え間なく後悔するアルゴリズムを提案して橋渡しする。
さらに、LPをわずかに$M$回だけ解ける場合、$O\left(T^{(1/2+\epsilon)^{M-1}}\right)を許すアルゴリズムを提案する。
さらに、最初に到着確率が分かると、我々のアルゴリズムはLPs$O(\log\log T)$ times と $O\left(T^{(1/2+\epsilon)^{M}}\right)$ regret を LPs$M$ times で解くことで、絶え間ない後悔を保証できる。
提案アルゴリズムの効率性を示すために, 数値実験を行った。
関連論文リスト
- Online Learning Quantum States with the Logarithmic Loss via VB-FTRL [2.059931105362387]
対数損失を持つオンライン学習量子状態(LL-OLQS)は、30年以上にわたってオンライン学習の分野で古典的なオープンな問題である。
ここでは、LL-OLQS に対して VB-FTRL を一般化する。
それぞれのアルゴリズムは半定値プログラムで構成されており、カットプレーン法などによって時間内に実装することができる。
論文 参考訳（メタデータ） (2023-11-06T15:45:33Z) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳（メタデータ） (2023-10-28T13:01:10Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Learning Infinite-Horizon Average-Reward Markov Decision Processes with
Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。
我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。
これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文 参考訳（メタデータ） (2022-01-31T23:52:34Z) - 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) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳（メタデータ） (2021-02-13T12:57:51Z) - Online Linear Optimization with Many Hints [72.4277628722419]
本研究では,学習者が決定に先立って各ラウンドでK$"hint"ベクトルにアクセス可能なオンライン線形最適化(OLO)問題について検討する。
この設定では、コストベクトルと正の相関を持つ$K$ヒントの凸結合が存在する場合、対数後悔を求めるアルゴリズムを考案する。
論文 参考訳（メタデータ） (2020-10-06T23:25:05Z) - Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。
ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
論文 参考訳（メタデータ） (2020-06-05T13:48:26Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。