論文の概要: Fast Learning for Renewal Optimization in Online Task Scheduling
- arxiv url: http://arxiv.org/abs/2007.09532v2
- Date: Sat, 29 May 2021 03:05:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-09 06:08:39.004343
- Title: Fast Learning for Renewal Optimization in Online Task Scheduling
- Title（参考訳）: オンラインタスクスケジューリングにおけるリニューアル最適化のための高速学習
- Authors: Michael J. Neely
- Abstract要約: 本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
- 参考スコア（独自算出の注目度）: 18.935043109084543
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers online optimization of a renewal-reward system. A
controller performs a sequence of tasks back-to-back. Each task has a random
vector of parameters, called the task type vector, that affects the task
processing options and also affects the resulting reward and time duration of
the task. The probability distribution for the task type vector is unknown and
the controller must learn to make efficient decisions so that time average
reward converges to optimality. Prior work on such renewal optimization
problems leaves open the question of optimal convergence time. This paper
develops an algorithm with an optimality gap that decays like $O(1/\sqrt{k})$,
where $k$ is the number of tasks processed. The same algorithm is shown to have
faster $O(\log(k)/k)$ performance when the system satisfies a strong concavity
property. The proposed algorithm uses an auxiliary variable that is updated
according to a classic Robbins-Monro iteration. It makes online scheduling
decisions at the start of each renewal frame based on this variable and on the
observed task type. A matching converse is obtained for the strongly concave
case by constructing an example system for which all algorithms have
performance at best $\Omega(\log(k)/k)$. A matching $\Omega(1/\sqrt{k})$
converse is also shown for the general case without strong concavity.
- Abstract（参考訳）: 本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
コントローラは一連のタスクをバック・トゥ・バックで実行する。
各タスクは、タスクタイプベクターと呼ばれるランダムなパラメータのベクターを持ち、タスク処理オプションに影響を与え、結果として生じるタスクの報酬と期間にも影響する。
タスク型ベクトルの確率分布は未知であり、コントローラは時間平均の報酬が最適に収束するように効率的な決定を学ばなければならない。
このような更新最適化問題に関する以前の研究は、最適収束時間の問題を残している。
本稿では,$o(1/\sqrt{k})$のように崩壊する最適性ギャップを持つアルゴリズムを開発した。
同じアルゴリズムは、強い凹凸特性を満たす場合、より高速な$O(\log(k)/k)$性能を持つ。
提案アルゴリズムは,従来のrobbins-monro反復に従って更新される補助変数を用いる。
この変数と観察されたタスクタイプに基づいて、各更新フレームの開始時にオンラインスケジューリング決定を行う。
すべてのアルゴリズムが最大$\omega(\log(k)/k)$で性能を持つ例システムを構築することにより、強凹ケースに対するマッチングコンバースが得られる。
一致する$\Omega(1/\sqrt{k})$逆もまた、強い凹凸を持たない一般の場合にも示される。
関連論文リスト
- Data Classification With Multiprocessing [6.513930657238705]
Pythonのマルチプロセッシングは、異なる分類アルゴリズムでこの仮説をテストするために使われる。
我々は、アンサンブルは精度を向上し、マルチプロセッシングは選択したアルゴリズムの実行時間を短縮する、と結論付けた。
論文 参考訳（メタデータ） (2023-12-23T03:42:13Z) - Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。
本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
論文 参考訳（メタデータ） (2021-06-22T15:50:45Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。
本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。
次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-10T13:07:44Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。