論文の概要: Optimal Regularized Online Allocation by Adaptive Re-Solving
- arxiv url: http://arxiv.org/abs/2209.00399v2
- Date: Sun, 16 Jul 2023 02:26:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-19 00:27:44.340497
- Title: Optimal Regularized Online Allocation by Adaptive Re-Solving
- Title(参考訳): 適応解法による最適正規化オンライン割り当て
- Authors: Wanteng Ma and Ying Cao and Danny H.K. Tsang and Dong Xia
- Abstract要約: 本稿では、正規化されたオンラインリソース割り当て問題を解決するために、デュアルベースのアルゴリズムフレームワークを提案する。
資源制約を適応的に更新する戦略の下で、提案手法は経験的二重問題に対する近似解をある程度の精度で要求するのみである。
驚いたことに、二重目的関数の微妙な解析により、後悔境界における悪名高いログ係数を排除できる。
- 参考スコア(独自算出の注目度): 16.873430173722994
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper introduces a dual-based algorithm framework for solving the
regularized online resource allocation problems, which have potentially
non-concave cumulative rewards, hard resource constraints, and a non-separable
regularizer. Under a strategy of adaptively updating the resource constraints,
the proposed framework only requests approximate solutions to the empirical
dual problems up to a certain accuracy and yet delivers an optimal logarithmic
regret under a locally second-order growth condition. Surprisingly, a delicate
analysis of the dual objective function enables us to eliminate the notorious
log-log factor in regret bound. The flexible framework renders renowned and
computationally fast algorithms immediately applicable, e.g., dual stochastic
gradient descent. Additionally, an infrequent re-solving scheme is proposed,
which significantly reduces computational demands without compromising the
optimal regret performance. A worst-case square-root regret lower bound is
established if the resource constraints are not adaptively updated during dual
optimization, which underscores the critical role of adaptive dual variable
update. Comprehensive numerical experiments demonstrate the merits of the
proposed algorithm framework.
- Abstract(参考訳): 本稿では,非コンケーブ累積的報酬,ハードリソース制約,非分離的正規化子を含むオンラインリソース割り当て問題を解くための2元ベースのアルゴリズムフレームワークを提案する。
資源制約を適応的に更新する戦略の下では,提案手法は経験的二重問題に対する近似解をある程度の精度で要求するのみであり,局所的な2次成長条件下では最適対数後悔を与える。
驚いたことに、二重目的関数の微妙な解析により、後悔境界における悪名高いログ係数を排除できる。
フレキシブルなフレームワークは、有名な高速なアルゴリズム、例えば双対確率勾配降下を即座に適用する。
さらに, 最適後悔性能を損なうことなく計算要求を大幅に低減する, 頻繁な再解法を提案する。
リソース制約が2つの最適化の間に適応的に更新されない場合、最悪の平方根後悔の低い境界が確立される。
総合的な数値実験は,提案手法の利点を実証するものである。
関連論文リスト
- A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。
ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
論文 参考訳(メタデータ) (2024-05-03T10:37:34Z) - Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。
我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。
提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
論文 参考訳(メタデータ) (2022-11-14T21:54:31Z) - Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。
我々の知る限り、オンラインの非線形学習における最初の後悔である。
論文 参考訳(メタデータ) (2022-09-21T04:16:33Z) - Algorithm for Constrained Markov Decision Process with Linear
Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。
エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。
提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文 参考訳(メタデータ) (2022-06-03T16:26:38Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳(メタデータ) (2021-12-29T02:42:59Z) - Online Allocation with Two-sided Resource Constraints [44.5635910908944]
我々は,要求が順次到着する,リソース制約の低いオンラインアロケーション問題を考える。
提案手法では, リクエスト全体を知るオフライン問題に対して, 1-O (fracepsilonalpha-epsilon)$-competitive ratioを求めるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-12-28T02:21:06Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Online Optimization and Ambiguity-based Learning of Distributionally Uncertain Dynamic Systems [1.6709415233613623]
本稿では,分散的に不確実な力学系のクラスを対象とする最適化問題 (P) に対して,データ駆動型オンラインソリューションを構築するための新しい手法を提案する。
導入されたフレームワークは、パラメータ化された制御依存のあいまいさセットを通じて、分散システムの不確実性の同時学習を可能にする。
また、Nesterovの高速化段階アルゴリズムのオンライン版を導入し、その性能を分析して、分散性理論を用いてこの問題のクラスを解く。
論文 参考訳(メタデータ) (2021-02-18T01:49:06Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-27T17:38:51Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Simplified Swarm Optimization for Bi-Objection Active Reliability
Redundancy Allocation Problems [1.5990720051907859]
信頼性冗長性割り当て問題(RRAP)は、システム設計、開発、管理においてよく知られた問題である。
本研究では, コスト制約を新たな目標として変更することにより, 両対象RRAPを定式化する。
提案課題を解決するために,ペナルティ関数を備えた新しい簡易スワム最適化 (SSO) ,実効1型ソリューション構造,数値ベースの自己適応型新しい更新機構,制約付き非支配型ソリューション選択,および新しいpBest代替ポリシーを開発した。
論文 参考訳(メタデータ) (2020-06-17T13:15:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。