論文の概要: Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints

• arxiv url: http://arxiv.org/abs/2508.16992v1
• Date: Sat, 23 Aug 2025 11:21:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-26 18:43:45.289037
• Title: Online Learning for Approximately-Convex Functions with Long-term Adversarial Constraints
• Title（参考訳）: 長期制約付き約凸関数のオンライン学習
• Authors: Dhruv Sarkar, Samrat Mukhopadhyay, Abhishek Sinha,
• Abstract要約: 本研究では, 長期的予算制約を伴うオンライン学習問題を, 対戦環境において検討する。 この問題では、各ラウンド$t$で、学習者は凸集合からアクションを選択し、その後、相手がコスト関数を明らかにする。 提案手法は, 保証を改善した$textttAdversas$問題に対して, 効率的なソリューションを提供する。
• 参考スコア（独自算出の注目度）: 8.314956969778692
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study an online learning problem with long-term budget constraints in the adversarial setting. In this problem, at each round $t$, the learner selects an action from a convex decision set, after which the adversary reveals a cost function $f_t$ and a resource consumption function $g_t$. The cost and consumption functions are assumed to be $\alpha$-approximately convex - a broad class that generalizes convexity and encompasses many common non-convex optimization problems, including DR-submodular maximization, Online Vertex Cover, and Regularized Phase Retrieval. The goal is to design an online algorithm that minimizes cumulative cost over a horizon of length $T$ while approximately satisfying a long-term budget constraint of $B_T$. We propose an efficient first-order online algorithm that guarantees $O(\sqrt{T})$ $\alpha$-regret against the optimal fixed feasible benchmark while consuming at most $O(B_T \log T)+ \tilde{O}(\sqrt{T})$ resources in both full-information and bandit feedback settings. In the bandit feedback setting, our approach yields an efficient solution for the $\texttt{Adversarial Bandits with Knapsacks}$ problem with improved guarantees. We also prove matching lower bounds, demonstrating the tightness of our results. Finally, we characterize the class of $\alpha$-approximately convex functions and show that our results apply to a broad family of problems.
• Abstract（参考訳）: 本研究では, 長期的予算制約を伴うオンライン学習問題を, 対戦環境において検討する。 この問題では、各ラウンド$t$において、学習者が凸決定セットからアクションを選択し、その後、相手がコスト関数$f_t$とリソース消費関数$g_t$とを明らかにする。 コストと消費関数は、凸性を一般化し、DR-部分モジュラー最大化、オンライン頂点被覆、正規化位相検索を含む多くの一般的な非凸最適化問題を包含する広いクラスである。 目標は、長期予算の制約を約$B_T$で満たしながら、長さの水平線上で累積コストを最小化するオンラインアルゴリズムを設計することである。 我々は,最大$O(B_T \log T)+ \tilde{O}(\sqrt{T})$リソースを全情報および帯域フィードバック設定の両方で消費しながら,最適な固定可能なベンチマークに対して$O(\sqrt{T})$$\alpha$-regretを保証する効率的な一階オンラインアルゴリズムを提案する。 バンドイットフィードバック設定では、Knapsacks を用いた $\texttt{Adversarial Bandits の効率の良い解が得られる。 また、一致した下限を証明し、その結果の厳密さを示す。 最後に、$\alpha$-aqua convex関数のクラスを特徴づけ、その結果が幅広い問題群に適用可能であることを示す。

関連論文リスト

• Beyond $\tilde{O}(\sqrt{T})$ Constraint Violation for Online Convex Optimization with Adversarial Constraints [16.99491218081617]
  逆制約を伴うオンライン凸最適化問題を再検討する。 我々は,$tildeO(sqrtdT+Tbeta)$ regretと$tildeO(dT1-beta)$ CCVを実現するオンラインポリシーを提案する。
  論文  参考訳（メタデータ） (2025-05-10T17:23:10Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• 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)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)

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

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