論文の概要: On the Necessity of Collaboration in Online Model Selection with Decentralized Data
- arxiv url: http://arxiv.org/abs/2404.09494v1
- Date: Mon, 15 Apr 2024 06:32:28 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-16 13:19:30.736609
- Title: On the Necessity of Collaboration in Online Model Selection with Decentralized Data
- Title(参考訳): 分散データを用いたオンラインモデル選択における協調の必要性について
- Authors: Junfan Li, Zenglin Xu, Zheshun Wu, Irwin King,
- Abstract要約: 我々は、100万ドル以上のクライアントに分散データを用いたオンラインモデル選択について検討する。
各クライアントの計算コストを$o(K)$に制限した場合、$K$は仮説空間の候補数である。
- 参考スコア(独自算出の注目度): 53.244188985271606
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider online model selection with decentralized data over $M$ clients, and study a fundamental problem: the necessity of collaboration. Previous work gave a negative answer from the perspective of worst-case regret minimization, while we give a different answer from the perspective of regret-computational cost trade-off. We separately propose a federated algorithm with and without communication constraint and prove regret bounds that show (i) collaboration is unnecessary if we do not limit the computational cost on each client; (ii) collaboration is necessary if we limit the computational cost on each client to $o(K)$, where $K$ is the number of candidate hypothesis spaces. As a by-product, we improve the regret bounds of algorithms for distributed online multi-kernel learning at a smaller computational and communication cost. Our algorithms rely on three new techniques, i.e., an improved Bernstein's inequality for martingale, a federated algorithmic framework, named FOMD-No-LU, and decoupling model selection and predictions, which might be of independent interest.
- Abstract(参考訳): 我々は、100万ドル以上のクライアントに分散化されたデータを用いたオンラインモデル選択について検討し、コラボレーションの必要性という根本的な問題について研究する。
過去の作業は、最悪のケースの後悔の最小化の観点から否定的な答えを与えましたが、後悔の計算コストのトレードオフの観点からは、別の答えを与えました。
我々は、コミュニケーション制約のないフェデレーション付きアルゴリズムを別々に提案し、後悔する境界を証明した。
(i)各クライアントの計算コストを制限しない場合は、協力は不要である。
(ii)各クライアントの計算コストを$o(K)$に制限した場合、$K$は仮説空間の候補数である。
副産物として,分散オンラインマルチカーネル学習におけるアルゴリズムの残差を,より少ない計算・通信コストで改善する。
我々のアルゴリズムは、マーチンゲールに対するバーンスタインの不等式の改善、フェデレートされたアルゴリズムフレームワークFOMD-No-LU、モデル選択と予測の分離という3つの新しい手法に依存している。
関連論文リスト
- An Incentive Mechanism for Federated Learning Based on Multiple Resource
Exchange [5.385462087305977]
Federated Learning(FL)は、機械学習におけるプライバシー問題に対処する分散機械学習パラダイムである。
ユーザをモデルオーナ(MO)とデータオーナ(DO)の2つの役割に分類する。
提案した協調計算フレームワークは、FLタスクの完了までの全体の時間を最小化しつつ、95%以上の精度を達成可能であることを示す。
論文 参考訳(メタデータ) (2023-12-13T12:28:37Z) - Optimal Multi-Distribution Learning [94.73322179348332]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では,$(d+k)/varepsilon2$の順に,サンプルの複雑さを伴って,$varepsilon$-optimal randomized hypothesisを生成するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Serverless Federated AUPRC Optimization for Multi-Party Collaborative
Imbalanced Data Mining [119.89373423433804]
有効指標としてAUPRC(Area Under Precision-Recall)を導入した。
サーバーレスのマルチパーティ共同トレーニングは、サーバーノードのボトルネックを避けることで通信コストを削減できる。
本稿では,AUPRCを直接最適化する ServerLess biAsed sTochastic gradiEnt (SLATE) アルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-08-06T06:51:32Z) - Settling the Sample Complexity of Online Reinforcement Learning [100.52613756483589]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳(メタデータ) (2023-07-25T15:42:11Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳(メタデータ) (2022-10-14T01:42:05Z) - Settling the Communication Complexity for Distributed Offline
Reinforcement Learning [10.315054389907031]
オフライン強化学習(RL)において,複数の分散マシンが協調して問題解決を行う新たな環境について検討する。
各マシンが送信できる情報の総数(ビット数)には予算の制約がある。
文脈的包帯における値関数の予測と, エピソード的および非エピソード的MDPの双方に対して, ミニマックスリスクに対する情報理論的下限を確立する。
論文 参考訳(メタデータ) (2022-02-10T06:27:07Z) - GT-STORM: Taming Sample, Communication, and Memory Complexities in
Decentralized Non-Convex Learning [11.129095449532283]
近年,分散1/2非堅牢性最適化が注目されている。
分散最適化アルゴリズムの設計における3つの基本的な課題は、サンプルコスト、通信、メモリ複雑さの削減である。
論文 参考訳(メタデータ) (2021-05-04T00:44:48Z) - Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。
目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。
ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文 参考訳(メタデータ) (2021-02-13T12:57:51Z) - An Efficient Algorithm for Cooperative Semi-Bandits [0.0]
本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。
T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
論文 参考訳(メタデータ) (2020-10-05T07:08:26Z) - Exact Support Recovery in Federated Regression with One-shot
Communication [31.061339148448006]
フェデレーション学習は、分散コンピューティング、データオーナシップ、プライバシといった課題に対処するためのフレームワークを提供する。
正確なサポートを計算するために,集中型サーバとのワンショット通信しか必要としない単純な通信アルゴリズムを提供する。
本手法では,クライアントが任意の最適化問題を解く必要はなく,計算能力の低いデバイスでも実行可能である。
論文 参考訳(メタデータ) (2020-06-22T19:48:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。