論文の概要: Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation

• arxiv url: http://arxiv.org/abs/2603.16200v1
• Date: Tue, 17 Mar 2026 07:27:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-18 17:42:07.147041
• Title: Online Semi-infinite Linear Programming: Efficient Algorithms via Function Approximation
• Title（参考訳）: オンライン半無限線形計画法:関数近似による効率的なアルゴリズム
• Authors: Yiming Zong, Jiashuo Jiang,
• Abstract要約: 決定空間が有限次元であるような動的資源配分問題を考える。 このソリューションは、ストリーミングデータやオラクルのフィードバックによって明らかにされる大量の、あるいは無限の制約を満たす必要があります。 関数近似を用いて制約の数を定数$q$に減らします。
• 参考スコア（独自算出の注目度）: 5.154847121294575
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the dynamic resource allocation problem where the decision space is finite-dimensional, yet the solution must satisfy a large or even infinite number of constraints revealed via streaming data or oracle feedback. We model this challenge as an Online Semi-infinite Linear Programming (OSILP) problem and develop a novel LP formulation to solve it approximately. Specifically, we employ function approximation to reduce the number of constraints to a constant $q$. This addresses a key limitation of traditional online LP algorithms, whose regret bounds typically depend on the number of constraints, leading to poor performance in this setting. We propose a dual-based algorithm to solve our new formulation, which offers broad applicability through the selection of appropriate potential functions. We analyze this algorithm under two classical input models-stochastic input and random permutation-establishing regret bounds of $O(q\sqrt{T})$ and $O\left(\left(q+q\log{T})\sqrt{T}\right)\right)$ respectively. Note that both regret bounds are independent of the number of constraints, which demonstrates the potential of our approach to handle a large or infinite number of constraints. Furthermore, we investigate the potential to improve upon the $O(q\sqrt{T})$ regret and propose a two-stage algorithm, achieving $O(q\log{T} + q/ε)$ regret under more stringent assumptions. We also extend our algorithms to the general function setting. A series of experiments validates that our algorithms outperform existing methods when confronted with a large number of constraints.
• Abstract（参考訳）: 決定空間が有限次元であるような動的資源配分問題を考えるが、この解はストリーミングデータやオラクルのフィードバックによって明らかにされる膨大なあるいは無限の制約を満たす必要がある。 我々は、この課題をオンライン半無限線形プログラミング(OSILP)問題としてモデル化し、それを解決するための新しいLP定式化を開発する。 具体的には、関数近似を用いて制約の数を定数$q$に減らします。 このことは、従来のオンラインLPアルゴリズムの重要な制限に対処する。 そこで本論文では,新たな定式化を解くための二元的アルゴリズムを提案する。 このアルゴリズムを2つの古典的入力モデルとランダムな置換確立残差付き$O(q\sqrt{T})$と$O\left(\left(q+q\log{T})\sqrt{T}\right)\right)$で解析する。 双方の後悔境界は制約の数とは独立であり、これは我々のアプローチが大きなあるいは無限の制約を扱う可能性を示していることに注意されたい。 さらに、より厳密な仮定の下で、$O(q\sqrt{T} + q/ε)$後悔を改善する可能性について検討し、2段階のアルゴリズムを提案し、$O(q\log{T} + q/ε)$後悔を達成する。 また、アルゴリズムを一般関数設定にまで拡張する。 一連の実験により、我々のアルゴリズムは、多くの制約に直面した場合、既存の手法よりも優れていることが検証された。

関連論文リスト

• Infrequent Resolving Algorithm for Online Linear Programming [3.247415064064425]
  既存のオンライン線形プログラミング(OLP)アルゴリズムは、LPベースアルゴリズムとLPフリーアルゴリズムの2つのカテゴリに分類される。 本稿では,LPを数個の時間点で解き,他の時間点で1次計算を行うアルゴリズムを提案する。 我々の研究は、販売ラインの開始と終了の両方で解決する価値を強調し、パフォーマンスの保証を証明するための新しいフレームワークを提供します。
  論文  参考訳（メタデータ） (2024-08-01T11:09:01Z)
• Projection-Free Online Convex Optimization with Time-Varying Constraints [19.993839085310643]
  逆時間制約によるオンライン凸最適化の設定について検討する。 固定可能な集合を投影することが難しいシナリオによって動機付けられ、線形最適化オラクル(LOO)を通してのみこの集合にアクセスするプロジェクションフリーアルゴリズムを考える。 我々は、長さ$T$のシーケンスで、全体$T$をLOOに呼び出し、$tildeO(T3/4)$ regret w.r.t.の損失と$O(T7/8)$制約違反を保証します。
  論文  参考訳（メタデータ） (2024-02-13T21:13:29Z)
• 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)
• Gradient-Variation Bound for Online Convex Optimization with Constraints [25.002868073267464]
  複数の機能的制約とユークリッド球のような比較的単純な制約セットからなる制約を持つオンライン凸最適化について検討する。 一階法は、$mathcalO(sqrtT)$ regret と $mathcalO(1)$ 制約違反を達成するが、問題の構造的情報を考慮してはならない。 本稿では,新しいオンライン原始双対ミラー-プロキシアルゴリズムによって得られる複雑な制約を伴って,オンライン凸最適化のインセンタンス依存バウンダリを提供する。
  論文  参考訳（メタデータ） (2020-06-22T17:38:14Z)
• Second-order Conditional Gradient Sliding [70.88478428882871]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

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

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