論文の概要: Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints

• arxiv url: http://arxiv.org/abs/2501.16919v1
• Date: Tue, 28 Jan 2025 13:04:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-29 16:40:57.051384
• Title: Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints
• Title（参考訳）: 逆制約を考慮したオンライン凸最適化のための投影自由アルゴリズム
• Authors: Dhruv Sarkar, Aprameyo Chakrabartty, Subhamon Supantha, Palash Dey, Abhishek Sinha,
• Abstract要約: 本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。 この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。 我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。
• 参考スコア（独自算出の注目度）: 10.047668792033033
• License:
• Abstract: We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this problem, after selecting a feasible action from the convex decision set $X,$ a convex constraint function is revealed alongside the cost function in each round. Our goal is to design a computationally efficient learning policy that achieves a small regret with respect to the cost functions and a small cumulative constraint violation (CCV) with respect to the constraint functions over a horizon of length $T$. It is well-known that the projection step constitutes the major computational bottleneck of the standard OCO algorithms. However, for many structured decision sets, linear functions can be efficiently optimized over the decision set. We propose a *projection-free* online policy which makes a single call to a Linear Program (LP) solver per round. Our method outperforms state-of-the-art projection-free online algorithms with adversarial constraints, achieving improved bounds of $\tilde{O}(T^{\frac{3}{4}})$ for both regret and CCV. The proposed algorithm is conceptually simple - it first constructs a surrogate cost function as a non-negative linear combination of the cost and constraint functions. Then, it passes the surrogate costs to a new, adaptive version of the online conditional gradient subroutine, which we propose in this paper.
• Abstract（参考訳）: 本稿では,オンライン凸最適化(OCO)フレームワークの時間的逆制約による一般化について検討する。 この問題では、凸判定セットから実行可能な動作を選択した後、各ラウンドのコスト関数とともに凸制約関数を$X,$とする。 我々のゴールは、コスト関数に対する小さな後悔と、長さ$T$の地平線上の制約関数に対する小さな累積制約違反(CCV)を実現する、計算効率のよい学習ポリシーを設計することである。 プロジェクションステップが標準OCOアルゴリズムの主要な計算ボトルネックを構成することはよく知られている。 しかし、多くの構造化された決定集合に対して、線形関数は決定集合に対して効率的に最適化することができる。 我々は,一ラウンドに1回,線形プログラム(LP)ソルバに1回コールする*プロジェクションフリー*オンラインポリシーを提案する。 提案手法は,現状のプロジェクションフリーなオンラインアルゴリズムを逆制約で性能良くし,後悔とCCVの両面において$\tilde{O}(T^{\frac{3}{4}})を改良したバウンダリを実現する。 提案アルゴリズムは概念的には単純であり,まずコスト関数と制約関数の非負線形結合として代用コスト関数を構成する。 そこで,本論文では,サロゲートコストをオンライン条件付き勾配サブルーチンの適応版に適用する。

関連論文リスト

• Tight Bounds for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。 我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
  論文  参考訳（メタデータ） (2024-05-15T12:37:03Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Optimal Algorithms for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  COCOでは、そのラウンドのアクションを選択した後、学習者に凸コスト関数と凸制約関数を明らかにする。 我々は、オンラインポリシーが、制限的な仮定なしで、同時に$O(sqrtT)$ regretと$tildeO(sqrtT)$ CCVを達成できることを示します。
  論文  参考訳（メタデータ） (2023-10-29T09:55:41Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Safe Online Bid Optimization with Return-On-Investment and Budget Constraints subject to Uncertainty [87.81197574939355]
  最適化問題と学習問題の両方について検討する。 我々は、潜在的に線形な数の制約違反を犠牲にして、サブ線形後悔を保証するアルゴリズム、すなわちGCBを提供する。 より興味深いことに、我々はGCB_safe(psi,phi)というアルゴリズムを提供し、サブ線形擬似回帰と安全性w.h.p.の両方を、耐性 psi と phi を受け入れるコストで保証する。
  論文  参考訳（メタデータ） (2022-01-18T17:24:20Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• On Constraints in First-Order Optimization: A View from Non-Smooth Dynamical Systems [99.59934203759754]
  本稿では,スムーズな制約付き最適化のための一階法について紹介する。 提案手法の2つの特徴は、実現可能な集合全体の投影や最適化が避けられることである。 結果として得られるアルゴリズムの手順は、制約が非線形であっても簡単に実装できる。
  論文  参考訳（メタデータ） (2021-07-17T11:45:13Z)
• A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback [22.17503016665027]
  各アクションが未知の関節分布からランダムな報酬、コスト、ペナルティを返す問題を考える。 我々は、$tt LyOn$という新しい低複雑さアルゴリズムを提案し、$O(sqrtBlog B)$ regretと$O(log B/B)$ constraint-violationを達成することを証明した。 計算コストの低い$tt LyOn$は、Lyapunovをベースとしたアルゴリズム設計手法が制約付き帯域最適化問題の解決に有効であることを示唆している。
  論文  参考訳（メタデータ） (2021-06-09T16:12:07Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)

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

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