論文の概要: Makespan Minimization in Split Learning: From Theory to Practice

• arxiv url: http://arxiv.org/abs/2602.06693v1
• Date: Fri, 06 Feb 2026 13:22:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-09 22:18:26.4078
• Title: Makespan Minimization in Split Learning: From Theory to Practice
• Title（参考訳）: スプリットラーニングにおけるMakespanの最小化:理論から実践へ
• Authors: Robert Ganian, Fionn Mc Inerney, Dimitra Tsigkari,
• Abstract要約: 分割学習は、異種IoTデバイスを用いた分散機械学習のソリューションである。 支援者によるクライアント・ヘルパーの割り当てとタスクのスケジュールを共同で設計することで、トレーニング時間を最小化する方法を示す。
• 参考スコア（独自算出の注目度）: 19.128619079473413
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Split learning recently emerged as a solution for distributed machine learning with heterogeneous IoT devices, where clients can offload part of their training to computationally-powerful helpers. The core challenge in split learning is to minimize the training time by jointly devising the client-helper assignment and the schedule of tasks at the helpers. We first study the model where each helper has a memory cardinality constraint on how many clients it may be assigned, which represents the case of homogeneous tasks. Through complexity theory, we rule out exact polynomial-time algorithms and approximation schemes even for highly restricted instances of this problem. We complement these negative results with a non-trivial polynomial-time 5-approximation algorithm. Building on this, we then focus on the more general heterogeneous task setting considered by Tirana et al. [INFOCOM 2024], where helpers have memory capacity constraints and clients have variable memory costs. In this case, we prove that, unless P=NP, the problem cannot admit a polynomial-time approximation algorithm for any approximation factor. However, by adapting our aforementioned 5-approximation algorithm, we develop a novel heuristic for the heterogeneous task setting and show that it outperforms heuristics from prior works through extensive experiments.
• Abstract（参考訳）: 分散学習は、クライアントがトレーニングの一部を計算力のあるヘルパーにオフロードできる異種IoTデバイスによる分散機械学習のソリューションとして最近登場した。 分割学習における中核的な課題は、クライアント-ヘルパーの割り当てとヘルパーでのタスクのスケジュールを共同で設計することで、トレーニング時間を最小化することである。 まず、各ヘルパーが割り当て可能なクライアント数に対するメモリ濃度制約を持つモデルについて検討する。 複雑性理論を通じて、この問題の高度に制限された事例に対しても、正確な多項式時間アルゴリズムと近似スキームを除外する。 非自明な多項式時間5-近似アルゴリズムでこれらの負の結果を補完する。 これに基づいて、Tirana氏ら[INFOCOM 2024]が考えるより一般的な異種タスク設定に焦点を当てます。 この場合、P=NPがなければ、任意の近似係数に対して多項式時間近似アルゴリズムを適用できないことが証明される。 しかし、前述の5-近似アルゴリズムを適用することで、異種タスク設定のための新しいヒューリスティックを開発し、より広範な実験により、以前の作業からヒューリスティックスに勝ることを示す。

関連論文リスト

• Learning Intersections of Two Margin Halfspaces under Factorizable Distributions [56.51474048985742]
  ハーフスペースの交叉学習は計算学習理論における中心的な問題である。 たった2つのハーフスペースであっても、学習が時間内に可能かどうかという大きな疑問が残る。 本稿ではCSQ硬度障壁を確実に回避する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-11-13T00:28:24Z)
• Nonconvex Federated Learning on Compact Smooth Submanifolds With Heterogeneous Data [23.661713049508375]
  本稿では,クライアントの設定においてサブマニフォールド上で学習するアルゴリズムを提案する。 提案アルゴリズムは,新しい解析手法を用いて一階最適解の近傍に部分収束することを示す。
  論文  参考訳（メタデータ） (2024-06-12T17:53:28Z)
• DNCs Require More Planning Steps [7.837209773889032]
  暗黙的アルゴリズム解法の一般化に対する計算時間とメモリの影響について検討する。 計画予算が学習アルゴリズムの挙動を劇的に変える方法を示す。
  論文  参考訳（メタデータ） (2024-06-04T10:31:03Z)
• Limited Memory Online Gradient Descent for Kernelized Pairwise Learning with Dynamic Averaging [18.843097436906618]
  実例の独立性を必要としない軽量なOGDアルゴリズムを導入し、カーネル対学習に一般化する。 提案アルゴリズムは,ランダムな例と過去のデータを表す移動平均に基づいて勾配を構築し,その結果,O(T)$の複雑さに縛られたサブ線形後悔が生じる。 実世界のデータセットによるいくつかの実験では、複雑性技術がオフラインおよびオンラインシナリオでカーネルと線形勾配を上回ることが示されている。
  論文  参考訳（メタデータ） (2024-02-02T05:21:50Z)
• Workflow Optimization for Parallel Split Learning [12.554265727169742]
  資源制約されたデバイスがニューラルネットワーク(NN)をトレーニングし、フェデレートラーニング(FL)に参加することを可能にする手段として、スプリットラーニング(SL)が提案されている。 並列SLでは、複数のヘルパーが1つ以上のクライアントのモデル部分を処理することができるため、すべてのクライアント(makespan)に対する最大トレーニング時間が大幅に短縮される。 本稿では,その固有対称性を利用して問題を分解する解法と,完全にスケーラブルな第2の解法を提案する。
  論文  参考訳（メタデータ） (2024-02-01T14:16:10Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。 標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。 我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。 本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
  論文  参考訳（メタデータ） (2023-04-01T15:50:18Z)
• Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
  統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。 予測と高い確率で、新しい過剰なリスク境界を提供する。 我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
  論文  参考訳（メタデータ） (2022-11-03T12:40:24Z)
• Multi-task Supervised Learning via Cross-learning [102.64082402388192]
  我々は,様々なタスクを解くことを目的とした回帰関数の集合を適合させることで,マルチタスク学習と呼ばれる問題を考える。 我々の新しい定式化では、これらの関数のパラメータを2つに分けて、互いに近づきながらタスク固有のドメインで学習する。 これにより、異なるドメインにまたがって収集されたデータが、互いのタスクにおける学習パフォーマンスを改善するのに役立つ、クロス・ファーティライズが促進される。
  論文  参考訳（メタデータ） (2020-10-24T21:35:57Z)

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

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