論文の概要: Online Learning for Function Placement in Serverless Computing

• arxiv url: http://arxiv.org/abs/2410.13696v2
• Date: Tue, 03 Jun 2025 12:52:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 04:22:50.418433
• Title: Online Learning for Function Placement in Serverless Computing
• Title（参考訳）: サーバレスコンピューティングにおける関数配置のためのオンライン学習
• Authors: Wei Huang, Richard Combes, Andrea Araldo, Hind Castel-Taleb, Badii Jouaber,
• Abstract要約: コストの最小化を目的とした仮想関数の配置について検討する。 マルチアームバンディットに基づくアイデアを用いた新しいアルゴリズムを提案する。 数値実験により,提案アルゴリズムは実用的な性能と控えめな計算複雑性を両立することを示した。
• 参考スコア（独自算出の注目度）: 6.810196737272974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the placement of virtual functions aimed at minimizing the cost. We propose a novel algorithm, using ideas based on multi-armed bandits. We prove that these algorithms learn the optimal placement policy rapidly, and their regret grows at a rate at most $O( N M \sqrt{T\ln T} )$ while respecting the feasibility constraints with high probability, where $T$ is total time slots, $M$ is the number of classes of function and $N$ is the number of computation nodes. We show through numerical experiments that the proposed algorithm both has good practical performance and modest computational complexity. We propose an acceleration technique that allows the algorithm to achieve good performance also in large networks where computational power is limited. Our experiments are fully reproducible, and the code is publicly available.
• Abstract（参考訳）: コストの最小化を目的とした仮想関数の配置について検討する。 マルチアームバンディットに基づくアイデアを用いた新しいアルゴリズムを提案する。 これらのアルゴリズムは最適な配置ポリシーを迅速に学習し、その後悔は最大で$O(N M \sqrt{T\ln T} )$で増加し、高い確率で実現可能性制約を尊重する一方で、$T$は全時間スロット、$M$は関数のクラス数、$N$は計算ノード数である。 数値実験により,提案アルゴリズムは実用的な性能と控えめな計算複雑性を両立することを示した。 本稿では,計算能力に制限のある大規模ネットワークにおいても,アルゴリズムによる性能向上を実現する高速化手法を提案する。 私たちの実験は完全に再現可能で、コードは公開されています。

関連論文リスト

• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint [18.290666675596984]
  非単調制約部分モジュラー・サブアニメーションは、様々な機械学習応用において重要な役割を果たす。 既存のアルゴリズムは、近似保証と実用効率のトレードオフにしばしば苦労する。 我々は,$0.385$-approximationの保証と$O(n+k2)$の低い,実用的なクエリ複雑性を組み合わせた新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-22T20:56:57Z)
• The Power of Resets in Online Reinforcement Learning [73.64852266145387]
  ローカルシミュレータアクセス(あるいはローカルプランニング)を用いたオンライン強化学習を通してシミュレータのパワーを探求する。 カバー性が低いMPPは,Qstar$-realizabilityのみのサンプル効率で学習可能であることを示す。 ローカルシミュレーターアクセス下では, 悪名高いExogenous Block MDP問題が抽出可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-23T18:09:53Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  最大満足度問題(MaxSAT)の解を近似できる単一の微分可能関数を導出する。 我々は,我々の微分可能な関数をモデル化する新しいニューラルネットワークアーキテクチャを提案し,バックプロパゲーションを用いてMaxSATを段階的に解く。
  論文  参考訳（メタデータ） (2024-02-06T02:33:00Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。 本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
  論文  参考訳（メタデータ） (2023-02-22T20:21:25Z)
• Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
  本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。 運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
  論文  参考訳（メタデータ） (2022-11-14T12:32:18Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Robust Methods for High-Dimensional Linear Learning [0.0]
  統計的に頑健で計算効率の良い線形学習法を高次元バッチ設定で提案する。 バニラスパース、グループスパース、低ランク行列回復など、いくつかのアプリケーションでフレームワークをインスタンス化する。 バニラ $s$-sparsity の場合、重いテールと $eta$-corruption の下で $slog (d)/n$ レートに達することができます。
  論文  参考訳（メタデータ） (2022-08-10T17:00:41Z)
• Training Neural Networks using SAT solvers [1.0152838128195465]
  本稿では,SATソルバを用いてニューラルネットワークのトレーニングを行うグローバル最適化手法を提案する。 実験では,パリティ学習などのタスクにおいて,ADAMオプティマイザに対するアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2022-06-10T01:31:12Z)
• PDE-Based Optimal Strategy for Unconstrained Online Learning [40.61498562988079]
  部分微分方程式(PDE)を解くことによって時間変化ポテンシャル関数を生成するフレームワークを提案する。 我々のフレームワークは、いくつかの古典的なポテンシャルを回復し、より重要なことは、新しいものを設計するための体系的なアプローチを提供する。 これは最適なリード定数を持つ最初のパラメータフリーアルゴリズムである。
  論文  参考訳（メタデータ） (2022-01-19T22:21:21Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  本稿では,ランダム化最小二乗値反復(RLSVI)アルゴリズムに着想を得たモデルレス強化学習アルゴリズムを提案する。 提案アルゴリズムは,スカラーノイズを用いたトレーニングデータを簡易に摂動させることにより,探索を促進する。 我々はこの理論を、既知の困難な探査課題にまたがる実証的な評価で補完する。
  論文  参考訳（メタデータ） (2021-06-15T02:23:07Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)

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

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