論文の概要: Multi-point Feedback of Bandit Convex Optimization with Hard Constraints
- arxiv url: http://arxiv.org/abs/2310.10946v1
- Date: Tue, 17 Oct 2023 02:43:22 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-18 18:04:20.113682
- Title: Multi-point Feedback of Bandit Convex Optimization with Hard Constraints
- Title（参考訳）: ハード制約付きバンディット凸最適化の多点フィードバック
- Authors: Yasunari Hikima
- Abstract要約: 本研究では,学習者が損失関数の部分的情報に基づいて決定列を生成することを目的とした制約付き帯域凸最適化について検討する。
我々は、累積的テクスト制約違反を制約違反の指標として採用する。
我々のアルゴリズムは、凸損失関数と時間変化制約に対して、$O(d2Tmaxc,1-c)$ regret bounds と $O(d2T1-fracc2)$ cumulative hard constraint violation bounds を得る。
- 参考スコア（独自算出の注目度）: 1.8130068086063336
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies bandit convex optimization with constraints, where the
learner aims to generate a sequence of decisions under partial information of
loss functions such that the cumulative loss is reduced as well as the
cumulative constraint violation is simultaneously reduced. We adopt the
cumulative \textit{hard} constraint violation as the metric of constraint
violation, which is defined by $\sum_{t=1}^{T} \max\{g_t(\boldsymbol{x}_t),
0\}$. Owing to the maximum operator, a strictly feasible solution cannot cancel
out the effects of violated constraints compared to the conventional metric
known as \textit{long-term} constraints violation. We present a penalty-based
proximal gradient descent method that attains a sub-linear growth of both
regret and cumulative hard constraint violation, in which the gradient is
estimated with a two-point function evaluation. Precisely, our algorithm
attains $O(d^2T^{\max\{c,1-c\}})$ regret bounds and $O(d^2T^{1-\frac{c}{2}})$
cumulative hard constraint violation bounds for convex loss functions and
time-varying constraints, where $d$ is the dimensionality of the feasible
region and $c\in[\frac{1}{2}, 1)$ is a user-determined parameter. We also
extend the result for the case where the loss functions are strongly convex and
show that both regret and constraint violation bounds can be further reduced.
- Abstract（参考訳）: 本稿では,学習者が損失関数の部分的情報に基づく決定列を生成し,累積損失を低減し,累積制約違反を同時に低減することを目的とした制約付きバンディット凸最適化について検討する。
これは $\sum_{t=1}^{T} \max\{g_t(\boldsymbol{x}_t), 0\}$ で定義される。
最大演算子のため、厳密な実現可能な解は、違反した制約の影響を、通常の値である \textit{long-term} 制約違反よりもキャンセルすることはできない。
本稿では, 2点関数評価で勾配を推定し, 後悔と累積的硬度制約違反の両方の線形成長を実現するペナルティに基づく近位勾配降下法を提案する。
正確には、このアルゴリズムは$o(d^2t^{\max\{c,1-c\}})$ regret 境界と$o(d^2t^{1-\frac{c}{2}})$ vex 損失関数と時変制約に対する累積的ハード制約違反境界を達成し、$d$ は実現可能な領域の次元であり $c\in[\frac{1}{2}, 1)$ はユーザ決定パラメータである。
また、損失関数が強く凸である場合にも結果を拡張し、後悔と制約違反の境界をさらに小さくすることができることを示す。
関連論文リスト
- Fixed-Budget Differentially Private Best Arm Identification [62.36929749450298]
差分プライバシー制約下における固定予算制度における線形包帯のベストアーム識別(BAI)について検討した。
誤差確率に基づいてミニマックス下限を導出し、下限と上限が指数関数的に$T$で崩壊することを示した。
論文 参考訳（メタデータ） (2024-01-17T09:23:25Z) - Distributed Online Convex Optimization with Adversarial Constraints:
Reduced Cumulative Constraint Violation Bounds under Slater's Condition [29.809415829907525]
本稿では,逆制約を伴う分散オンライン凸最適化について考察する。
エージェントはネットワークの後悔と累積的制約違反を最小限にするために協力する。
我々の知る限り、この論文は、(分散)オンライン凸最適化における(ネットワーク)累積制約違反境界を敵制約付きで達成した最初のものである。
論文 参考訳（メタデータ） (2023-05-31T19:39:15Z) - Projection-Free Online Convex Optimization with Stochastic Constraints [0.0]
我々は制約付きオンライン凸最適化のためのプロジェクションフリーアルゴリズムを開発した。
各種設定に対してサブ線形後悔と制約違反境界を推定する。
我々は、制約違反を減らして、後悔と同じ成長をすることができることを証明している。
論文 参考訳（メタデータ） (2023-05-02T11:27:34Z) - On Dynamic Regret and Constraint Violations in Constrained Online Convex
Optimization [17.412117389855222]
提案するアルゴリズムは,現在の動作の周囲に適度に選択された集合上の射影勾配勾配を追従する。
動的後悔と制約違反の両方が、連続する最適動作間の距離の和であるパス長によって順序的に束縛されていることを示す。
論文 参考訳（メタデータ） (2023-01-24T04:22:13Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Regret and Cumulative Constraint Violation Analysis for Online Convex
Optimization with Long Term Constraints [24.97580261894342]
本稿では,長期的制約を伴うオンライン凸最適化について考察する。
新たなアルゴリズムが最初に提案され、静的後悔のために$mathcalO(Tmaxc,1-c)$bound、累積制約違反のために$mathcalO(T(1-c)/2)$boundを達成する。
論文 参考訳（メタデータ） (2021-06-09T15:18:06Z) - Regret and Cumulative Constraint Violation Analysis for Distributed
Online Constrained Convex Optimization [24.97580261894342]
本稿では,エージェントネットワーク上の時間的制約を伴う分散オンライン凸最適化問題について考察する。
フルインフォメーションとバンディットフィードバックの2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-01T18:28:53Z) - On Lower Bounds for Standard and Robust Gaussian Process Bandit
Optimization [55.937424268654645]
有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。
本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
論文 参考訳（メタデータ） (2020-08-20T03:48:14Z) - Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。
パフォーマンス指標として動的後悔を選択します。
本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文 参考訳（メタデータ） (2020-07-07T14:10:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。