論文の概要: Chasing Convex Functions with Long-term Constraints
- arxiv url: http://arxiv.org/abs/2402.14012v2
- Date: Fri, 12 Jul 2024 15:44:38 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-16 05:17:24.797281
- Title: Chasing Convex Functions with Long-term Constraints
- Title（参考訳）: 長期制約付きチャット凸関数
- Authors: Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, Prashant Shenoy,
- Abstract要約: 我々は,長期的制約を伴うオンライン計量問題群を紹介し,研究する。
このような問題は、持続可能なエネルギー/計算システムにおけるオンラインリソース割り当てへの幅広い応用を見出すことができる。
- 参考スコア（独自算出の注目度）: 11.029788598491077
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce and study a family of online metric problems with long-term constraints. In these problems, an online player makes decisions $\mathbf{x}_t$ in a metric space $(X,d)$ to simultaneously minimize their hitting cost $f_t(\mathbf{x}_t)$ and switching cost as determined by the metric. Over the time horizon $T$, the player must satisfy a long-term demand constraint $\sum_{t} c(\mathbf{x}_t) \geq 1$, where $c(\mathbf{x}_t)$ denotes the fraction of demand satisfied at time $t$. Such problems can find a wide array of applications to online resource allocation in sustainable energy/computing systems. We devise optimal competitive and learning-augmented algorithms for the case of bounded hitting cost gradients and weighted $\ell_1$ metrics, and further show that our proposed algorithms perform well in numerical experiments.
- Abstract（参考訳）: 我々は,長期的制約を伴うオンライン計量問題群を紹介し,研究する。
これらの問題において、オンラインプレーヤーは、計量空間$(X,d)$で$\mathbf{x}_t$を判定し、ヒットコスト$f_t(\mathbf{x}_t)$を同時に最小化し、計量によって決定される切り替えコストを最小化する。
時間が経つにつれて、プレイヤーは長期要求制約である$\sum_{t} c(\mathbf{x}_t) \geq 1$を満たさなければならない。
このような問題は、持続可能なエネルギー/計算システムにおけるオンラインリソース割り当てへの幅広い応用を見出すことができる。
我々は,有界ヒットコスト勾配と重み付き$\ell_1$メトリクスの場合に最適な競合性および学習強化アルゴリズムを考案し,さらに,提案アルゴリズムが数値実験で良好に動作することを示す。
関連論文リスト
- Monge-Kantorovich Fitting With Sobolev Budgets [6.748324975906262]
近似の性能をMonge-Kantorovich $p$-costで定量化する。
次に、ソボレフ予算の制約の下で、機能的$mathscrJ_p(f)$を最小化するものとして問題を再構築する。
論文 参考訳（メタデータ） (2024-09-25T01:30:16Z) - Dueling Optimization with a Monotone Adversary [35.850072415395395]
凸最適化の一般化である単調逆数を用いたデュエル最適化の問題点について検討する。
目的は、最小値$mathbfx*$の関数$fcolon XをmathbbRdに変換するために、オンラインアルゴリズムを設計することである。
論文 参考訳（メタデータ） (2023-11-18T23:55:59Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。
非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。
基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
論文 参考訳（メタデータ） (2021-07-03T13:04:41Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - 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) - A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with
Constraints [8.849815837266977]
制約付きマルコフ決定プロセス(CMDP)は、シーケンシャルな意思決定問題を定式化する。
本稿では, 有限水平CMDPの線形計画法を利用して, 繰り返し楽観的な計画を立てるオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-23T19:30:46Z) - Taking a hint: How to leverage loss predictors in contextual bandits? [63.546913998407405]
我々は,損失予測の助けを借りて,文脈的包帯における学習を研究する。
最適な後悔は$mathcalO(minsqrtT, sqrtmathcalETfrac13)$である。
論文 参考訳（メタデータ） (2020-03-04T07:36:38Z) - Naive Exploration is Optimal for Online LQR [49.681825576239355]
最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。
我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
論文 参考訳（メタデータ） (2020-01-27T03:44:54Z) - On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems [86.92205445270427]
非コンミニマックス問題、$min_mathbfx max_mathhidoty f(mathbfdoty)$を効率的に考える。
論文 参考訳（メタデータ） (2019-06-02T03:03:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。