論文の概要: Infrequent Resolving Algorithm for Online Linear Programming

• arxiv url: http://arxiv.org/abs/2408.00465v2
• Date: Fri, 2 Aug 2024 03:56:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-05 12:28:46.201250
• Title: Infrequent Resolving Algorithm for Online Linear Programming
• Title（参考訳）: オンライン線形計画法における頻繁な解法
• Authors: Guokai Li, Zizhuo Wang, Jingwei Zhang,
• Abstract要約: 本稿では,LPを時間的水平線上でのO(loglog T)$倍だけ解きながら,常に後悔するアルゴリズムを提案する。 我々のアルゴリズムは、LPの$O(loglog T)$ timesと$Oleft(T(1/2+epsilon)Mright)$ regretを、LPの$M$ timesを解くことで、絶え間ない後悔を保証できる。
• 参考スコア（独自算出の注目度）: 3.247415064064425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 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次計算しか必要としないが、より悪い性能を誘導し、絶え間ないリフレッシュバウンドを欠いている。 本研究では, LP を時間的地平線上での O(\log\log T)$ 倍だけ解きながら, 常に後悔するアルゴリズムを提案することにより, 両極間のギャップを埋める。 さらに、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 で解くことで、絶え間ない後悔を保証できる。 提案アルゴリズムの効率性を示すために, 数値実験を行った。

関連論文リスト

• Beyond $\mathcal{O}(\sqrt{T})$ Regret: Decoupling Learning and Decision-making in Online Linear Programming [7.518108920887426]
  本稿では,LP双対問題が一定の誤差境界条件を示す場合に,$mathcalO ( sqrtT )$の結果を改善するための一般的な枠組みを確立する。 連続的なサポート設定において,1次学習アルゴリズムが$o(sqrtT )$後悔し,非退化仮定以外の有限サポート設定において$mathcalO (log T)$後悔することを示す。
  論文  参考訳（メタデータ） (2025-01-06T04:57:44Z)
• Wait-Less Offline Tuning and Re-solving for Online Decision Making [10.984414655748095]
  LP法と1次LP法の長所を組み合わせた新しいアルゴリズムを提案する。 我々のアルゴリズムは、$mathscrO(log (T/f) + sqrtf)$ regretを達成し、「待機なし」オンライン意思決定プロセスを提供する。
  論文  参考訳（メタデータ） (2024-12-12T18:58:14Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Online Learning Quantum States with the Logarithmic Loss via VB-FTRL [1.8856444568755568]
  対数損失を伴う量子状態のオンライン学習(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)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  我々は[Zhang et al., 2022]に導入された参加制約を伴う計画の問題を考える。 この問題では、プリンシパルが決定プロセスのアクションを選択し、プリンシパルとエージェントの別々のユーティリティが生成される。 有限ホライズン設定では,これまでは$varepsilon$-approximationという付加値しか知られていなかった。
  論文  参考訳（メタデータ） (2022-05-16T15:47:41Z)
• 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)
• 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)

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

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