論文の概要、ライセンス

# (参考訳) 適応計算と電力制御を併用したオーバーザ・エアフェデレーション学習 [全文訳有]

Over-the-Air Federated Learning with Joint Adaptive Computation and Power Control ( http://arxiv.org/abs/2205.05867v1 )

ライセンス: CC BY 4.0
Haibo Yang, Peiwen Qiu, Jia Liu and Aylin Yener(参考訳) 本稿では,ota-fl(over-the-air federated learning)について述べる。 OTA-FLは、無線媒体の重ね合わせ特性を利用して、空気上のモデルアグリゲーションを無料で行う。 これにより、エッジデバイスからの通信モデル更新で発生する通信コストを大幅に削減することができる。 この利点を最大限に活用し、ノイズのないチャネルによるモデルアグリゲーションを想定した従来型のフェデレーション学習に匹敵する学習性能を提供しながら、各エッジデバイスにおける電力制約を考慮した伝送スケーリングと各ラウンドの局所イテレーション数について考察する。 我々はまず,リプシッツ連続勾配を持つ一般関数の基本下界を確立することにより,OTA-FLのチャネルノイズによるトレーニング誤差を特徴づける。 次に,適応的トランシーバパワースケーリングスキームを導入することで,協調適応計算と電力制御(acpc-ota-fl)を備えた,空気上フェデレート学習アルゴリズムを提案する。 非凸目的関数と異種データを用いたトレーニングにおけるACPC-OTA-FLの収束解析について述べる。 本稿では,ACPC-OTA-FLの収束速度がFLのノイズフリー通信と一致することを示す。

This paper considers over-the-air federated learning (OTA-FL). OTA-FL exploits the superposition property of the wireless medium, and performs model aggregation over the air for free. Thus, it can greatly reduce the communication cost incurred in communicating model updates from the edge devices. In order to fully utilize this advantage while providing comparable learning performance to conventional federated learning that presumes model aggregation via noiseless channels, we consider the joint design of transmission scaling and the number of local iterations at each round, given the power constraint at each edge device. We first characterize the training error due to such channel noise in OTA-FL by establishing a fundamental lower bound for general functions with Lipschitz-continuous gradients. Then, by introducing an adaptive transceiver power scaling scheme, we propose an over-the-air federated learning algorithm with joint adaptive computation and power control (ACPC-OTA-FL). We provide the convergence analysis for ACPC-OTA-FL in training with non-convex objective functions and heterogeneous data. We show that the convergence rate of ACPC-OTA-FL matches that of FL with noise-free communications.
公開日: Thu, 12 May 2022 03:28:03 GMT

※ 翻訳結果を表に示しています。PDFがオリジナルの論文です。翻訳結果のライセンスはCC BY-SA 4.0です。詳細はトップページをご参照ください。

翻訳結果

    Page: /      
英語(論文から抽出)日本語訳スコア
Over-the-Air Federated Learning with Joint Adaptive Computation and Power Control 適応計算と電力制御を併用したオーバーザ・エアフェデレーション学習 0.69
Haibo Yang, Peiwen Qiu, Jia Liu and Aylin Yener ハイボ・ヤン、ピーウェン・キウ、ジア・リュー、アリン・イェナー 0.46
Dept. of Electrical and Computer Engineering, The Ohio State University オハイオ州立大学電気・計算機工学専攻 0.56
{yang.9292, qiu.617}@osu.edu, liu@ece.osu.edu, yener@ece.osu.edu {yang.9292, qiu.617}@osu.edu, liu@ece.osu.edu, yener@ece.osu.edu 0.31
2 2 0 2 y a M 2 1 2 2 0 2 y a m 2 1 である。 0.52
] G L . s c [ ] G L。 sc [ 0.47
1 v 7 6 8 5 0 1 v 7 6 8 5 0 0.43
. 5 0 2 2 : v i X r a . 5 0 2 2 : v i X r a 0.42
Abstract—This paper considers over-the-air federated learning (OTA-FL). abstract — 本論文では,ota-fl(over-the-air federated learning)について述べる。 0.37
OTA-FL exploits the superposition property of the wireless medium, and performs model aggregation over the air for free. OTA-FLは、無線媒体の重ね合わせ特性を利用して、空気上のモデルアグリゲーションを無料で行う。 0.69
Thus, it can greatly reduce the communication cost incurred in communicating model updates from the edge devices. これにより、エッジデバイスからの通信モデル更新で発生する通信コストを大幅に削減することができる。 0.76
In order to fully utilize this advantage while providing comparable learning performance to conventional federated learning that presumes model aggregation via noiseless channels, we consider the joint design of transmission scaling and the number of local iterations at each round, given the power constraint at each edge device. この利点を最大限に活用し、ノイズのないチャネルによるモデルアグリゲーションを想定した従来型のフェデレーション学習に匹敵する学習性能を提供しながら、各エッジデバイスにおける電力制約を考慮した伝送スケーリングと各ラウンドの局所イテレーション数について考察する。 0.75
We first characterize the training error due to such channel noise in OTA-FL by establishing a fundamental lower bound for general functions with Lipschitz-continuous gradients. 我々はまず,リプシッツ連続勾配を持つ一般関数の基本下界を確立することにより,OTA-FLのチャネルノイズによるトレーニング誤差を特徴づける。 0.73
Then, by introducing an adaptive transceiver power scaling scheme, we propose an over-the-air federated learning algorithm with joint adaptive computation and power control (ACPC-OTAFL). 次に,適応的トランシーバパワースケーリングスキームを導入することで,協調適応計算と電力制御(acpc-otafl)を備えた,空気上フェデレート学習アルゴリズムを提案する。 0.82
We provide the convergence analysis for ACPC-OTA-FL in training with non-convex objective functions and heterogeneous data. 非凸目的関数と異種データを用いたトレーニングにおけるACPC-OTA-FLの収束解析について述べる。 0.57
We show that the convergence rate of ACPC-OTA-FL matches that of FL with noise-free communications. 本稿では,ACPC-OTA-FLの収束速度がFLのノイズフリー通信と一致することを示す。 0.60
I. INTRODUCTION I. イントロダクション 0.64
In recent years, advances in machine learning (ML) have achieved astonishing successes in many applications that transform our society, e g , in computer vision, natural language processing, and robotics. 近年、機械学習(ML)の進歩は、コンピュータビジョン、自然言語処理、ロボット工学などの社会を変える多くのアプリケーションで驚くべき成功を収めている。 0.67
Traditionally, ML training tasks often reside in cloud-based large data-centers that process training data in a centralized fashion. 従来、MLトレーニングタスクは、トレーニングデータを集中的な方法で処理するクラウドベースの大規模データセンタに常駐する。 0.64
However, due to the rapidly increasing demands for training data, high latency and costs of data transmissions, as well as data privacy/security concerns, aggregating all data to the cloud for ML training is unlikely to remain feasible. しかし、データトレーニングの需要が急速に増加し、データ送信のレイテンシが高くなり、データプライバシやセキュリティに関する懸念も高まっているため、MLトレーニングのためにすべてのデータをクラウドに集約することは不可能である。 0.66
To address these challenges, federated learning (FL) [1] has recently emerged as a prevailing distributed ML paradigm. これらの課題に対処するため、フェデレーション・ラーニング(FL)[1]は、最近分散MLパラダイムとして普及した。 0.59
FL employs multiple clients, typically deployed over wireless edge networks, to locally train a learning model and exchange only intermediate updates between the server and clients. FLは、通常、無線エッジネットワーク上にデプロイされる複数のクライアントを使用して、学習モデルをローカルにトレーニングし、サーバとクライアントの間の中間更新のみを交換する。 0.64
FL provides better avenues for privacy protection by avoiding the transmission of local data, while also being able to leverage parallel clients computation for training speedup. FLは、ローカルデータの送信を回避すると同時に、並列クライアント計算をトレーニングスピードアップに活用することで、プライバシー保護のためのより良い方法を提供する。 0.69
However, FL also inherits many design challenges of distributed ML. しかし、FLは分散MLの多くの設計課題を継承している。 0.57
One of the main challenges of FL stems from the communication constraint in the iterative FL learning process, particularly in resource (bandwidth and power)-limited wireless FL systems [2]–[4]. FLの主な課題の1つは、反復的なFL学習過程における通信制約、特にリソース(帯域と電力)に制限された無線FLシステム [2]–[4] に起因している。 0.78
To receive the update information from multiple clients in each round, the conventional wisdom 各ラウンドの複数のクライアントから更新情報を受信するには、従来の知恵 0.82
This work is supported in part by NSF-2112471 (AI-EDGE). NSF-2112471(AI-EDGE) によって部分的にサポートされている。 0.55
is to use orthogonal spectral or temporal channels for each client and avoid interference among the clients. 各クライアントに直交スペクトルまたは時間的チャネルを使用し、クライアント間の干渉を避けること。 0.79
However, this is neither desirable (since as the number of clients increases, the available rate per edge device decreases, lengthening the communication duration), nor necessary (since only the aggregated model updates is needed at the server) in FL. しかし、これは望ましくない(クライアント数が増加するにつれて、エッジデバイス当たりの使用率が減少し、通信期間が長くなる)し、必要(サーバで集約されたモデル更新が必要なため)でもない。 0.68
Over-the-air FL (OTA-FL) has recently emerged as an effective approach in that it exploits the superposition property of the wireless medium to perform model aggregation “for free” by allowing simultaneous transmission of all clients’ updates [5]–[7]. オーバー・ザ・エアfl(ota-fl)は、無線媒体の重畳特性を利用して、全クライアントの[5]–[7]の同時送信を可能にすることで、モデル集約を「無料で」実行する効果的なアプローチとして最近登場した。 0.63
Specifically, under OTA-FL, the server directly recovers a noisy aggregation of the clients’ model updates that transmit in the same spectral-temporal channel, rather than trying to decode each client’s model update first in orthogonal spectral or temporal channels. 特に、ota-flでは、サーバは、各クライアントのモデル更新をまず直交するスペクトルまたは時間的チャネルでデコードするのではなく、同じスペクトル-時間的チャネルで送信されるクライアントのモデル更新のノイズのアグリゲーションを直接リカバリする。 0.70
As a result, OTA-FL dramatically reduces the communication costs and overheads from collecting the update from each client, and accordingly enjoys better communication parallelism regardless of the number of clients. その結果、OTA-FLは各クライアントから更新を収集する際の通信コストとオーバーヘッドを劇的に削減し、クライアント数に関係なく通信並列性を向上する。 0.80
However, despite of the aforementioned salient features in terms of communication efficiency, several issues remain in OTA-FL. しかし、通信効率の面では上述の健全な特徴にもかかわらず、OTA-FLにはいくつかの問題が残っている。 0.50
First, the convergence analysis of OTA-FL often assumes noise-free communications (see Section II for more in-depth discussions). 第一に、OTA-FLの収束解析はしばしばノイズのない通信を前提としている(詳細はセクションIIを参照)。 0.64
Moreover, existing works on OTA-FL have not considered data heterogeneity, (i.e., datasets among clients are non-i.i.d. and with unbalanced sizes) and system heterogeneity (i.e., the computation and communication capacities varies among clients and could be time-varying [2], [3] simultaneously). さらに、OTA-FLの既存の研究は、データ不均一性(すなわち、クライアント間のデータセットは非i.d.、不均衡サイズ)とシステム不均一性(すなわち、計算能力と通信能力はクライアントによって異なり、同時に[2],[3]が変化する可能性がある)を考慮していない。 0.65
Therefore, a fundamental question in OTAFL system design is: how to develop an efficient OTA-FL training algorithm that can handle both data and system heterogeneity under noisy channels. したがって、otaflシステム設計における基本的な問題は次のとおりである: ノイズチャネル下でデータとシステムの不均一性を処理する効率的なota-flトレーニングアルゴリズムの開発方法。 0.64
In this paper, we answer this question by studying the impact of channel noise on OTA-FL and proposing an overthe-air federated learning algorithm with joint adaptive computation and power control (ACPC-OTA-FL) for edge devices with heterogeneous capabilities. 本稿では,OTA-FLにおけるチャネルノイズの影響について検討し,異種機能を持つエッジデバイスを対象とした協調適応計算と電力制御(ACPC-OTA-FL)を用いたオーバーエア・フェデレーション学習アルゴリズムを提案する。 0.77
Our main contributions are summarized as follows: • We first characterize the training error of the conventional OTA-based FedAvg algorithm [1] by establishing a lower bound of the convergence error under Gaussian multiple access channels (MAC) for general functions with Lipschitz continuous gradients. 我々はまず, ガウス多重アクセスチャネル(MAC)の下で, リプシッツ連続勾配を持つ一般関数に対する収束誤差の下位境界を確立することにより, 従来のOTAベースのFedAvgアルゴリズムのトレーニング誤差を特徴付ける。 0.75
Our lower bound indicates that there is a non-vanishing convergence error due to channel noise compared with those convergence results of OTA-FL under 我々の下限は,ota-flの収束結果と比較して,チャネルノイズによる非バニッシブ収束誤差があることを示唆する。 0.70
英語(論文から抽出)日本語訳スコア
the noise-free assumption. This insight motivates us to propose our ACPC-OTA-FL algorithm that considers local computation and power control co-design to best utilize the power resources at the edge devices. ノイズのない仮定。 この知見は,エッジデバイスの電力資源を最大限活用するために,局所計算と電力制御の共同設計を考慮したacpc-ota-flアルゴリズムを提案する動機付けである。 0.67
• Our ACPC-OTA-FL algorithm allows each client to (in a distributed manner) adaptively determine its transmission power level and number of local update steps to fully utilize the computation and communication resources. • 我々のACPC-OTA-FLアルゴリズムにより,各クライアントが(分散的に)送信電力レベルとローカル更新の回数を適応的に決定し,計算および通信資源を十分に活用することができる。 0.79
We show that, even with non-i.i.d. and unbalanced datasets, ACPC-OTA-FL converges to a stationary point with an 非i.d.とアンバランスなデータセットであっても、ACPC-OTA-FLは静止点に収束することを示す。 0.57
O(1/√mT ) convergence rate for nonconvex objective func- 非凸目的菌類のO(1/>mT )収束速度- 0.26
tions in training, where m is the number of clients and T is the total number of training iterations. mはクライアントの数、tはトレーニングイテレーションの総数である。 0.43
This result further implies a linear speedup in the number of clients and matches that of the noise-free FedAvg algorithm. この結果はさらにクライアント数を線形に高速化し、ノイズフリーfedavgアルゴリズムのそれと一致する。 0.71
II. RELATED WORK OTA-FL utilizes over-the-air computation through analog transmission in wireless MAC [5], [6], [8]–[13]. II。 関連作業 ota-fl は無線mac [5], [6], [8]–[13] のアナログ伝送による空中計算を利用する。 0.68
Despite the advantage of high scalability for large amount of clients, existing works on OTA-FL [9]–[13] have empirically shown that the channel noise substantially degrades the learning performance. OTA-FL [9]–[13]の既存の研究は、大量のクライアントに対して高いスケーラビリティの利点があるにもかかわらず、チャネルノイズが学習性能を著しく低下させることを示した。 0.68
Therefore, theoretically quantifying the impact of channel noise on convergence needs more in-depth investigation (See Section IV). したがって、チャネルノイズが収束に与える影響を理論的に定量化するには、より深い調査が必要である(第4節参照)。 0.58
To mitigate the impacts of channel noise under limited transmission power constraints, one popular approach is to utilize uniform transceiver scaling for all clients. 送信電力制限下でのチャネルノイズの影響を軽減するため,全クライアントに対して均一なトランシーバスケーリングを利用する方法が一般的である。 0.75
For example, references [11], [12], [14] have considered an identical sparsity pattern to reduce communication overhead. 例えば、参照 [11], [12], [14] は通信のオーバーヘッドを減らすために同じスパーシティパターンを検討してきた。 0.76
Reference [15] has proposed a new learning rate scheme that considers the quality of the gradient estimation; Reference [16] has developed a uniform-forcing transceiver scaling for OTA function computation, while the work in [17] has studied the optimal power control problem by taking gradient statistics into account. 参照[15]は、勾配推定の品質を考慮した新しい学習率スキームを提案し、参照[16]は、OTA関数計算のための均一な強制的トランシーバスケーリングを開発し、[17]では、勾配統計を考慮した最適電力制御問題を研究している。 0.77
Reference [18] has proposed an uniform transceiver scaling by considering data heterogeneity. 参照 [18] はデータの均一性を考慮した一様トランシーバスケーリングを提案している。 0.48
A common approach of these existing works above is to formulate the power control problem separately to satisfy the power constraints after the local computation at clients. これらの既存の作業の一般的なアプローチは、クライアントでの局所計算後の電力制約を満たすために、電力制御問題を別々に定式化することである。
訳抜け防止モード: これらの既存の作品の一般的なアプローチは クライアントでの局所計算後の電力制約を満たすために、電力制御問題を別々に定式化する。
0.77
Moreover, data and system heterogeneity and adapting the power resources for computation is not tied to transmission power control, despite the fact that each edge device is constrained in total power that is needed for both computation and communication. さらに、各エッジデバイスが計算と通信の両方に必要な全電力に制約されているにもかかわらず、計算のためのデータとシステムの不均一性と電力資源の適応は送信電力制御とは結びついていない。 0.83
Due to the coupling of computation and communication processes, a joint adaptive computation and power control for OTA-FL is necessary in order to better mitigate the combined impacts of channel noise, power constraints, as well as data and system heterogeneity, which constitutes the main goal of this paper. 計算処理と通信プロセスの結合により,ota-flの協調適応計算と電力制御が必要となり,チャネルノイズや電力制約,データやシステムの不均一性の影響を緩和し,本論文の主目的とする。 0.71
III. SYSTEM MODEL III。 システムモデル 0.74
In this section, we first introduce our OTA-FL model in Section III-A and then the communication model in Section III-B. 本稿では,まずOTA-FLモデルをIII-A節で,次いでIII-B節で通信モデルについて紹介する。 0.72
A. Over-the-Air Federated Learning Model a. オーバーザ・エアフェデレーション学習モデル 0.67
We consider a FL system with one server and m clients in total. 1つのサーバとmクライアントを持つFLシステムについて検討する。 0.63
Each client i ∈ [m] contains a private local dataset Di. 各クライアント i ∈ [m] はプライベートなローカルデータセット di を含む。 0.85
Each local dataset Di is i.i.d. sampled from a distribution Xi. 各ローカルデータセットDiは、分布Xiからサンプリングされたi.d.d.である。 0.57
In this paper, we consider non-i.i.d. datasests across users, i.e., Xi 6= Xj if i 6= j,∀i, j ∈ [m]. 本稿では、ユーザ間での非i.d.データセスト、すなわち、i 6= j, i, j ∈ [m] であれば Xi 6= Xj を考える。 0.78
The goal of FL is to collaboratively train a global learning model by solving an optimization problem in the form of: flの目標は、次の形式で最適化問題を解決することで、グローバルな学習モデルを協調的にトレーニングすることである。
訳抜け防止モード: FLのゴールは 最適化問題の解決を図って,グローバルな学習モデルを協調的に訓練すること
0.80
min x∈Rd min (複数形 mins) 0.31
F (x) , min F (x) , min 0.42
x∈Rd Xi∈[m] x・RdXi・[m] 0.25
αiFi(x, Di), αiFi(x, Di) 0.41
(1) where x ∈ Rd is the model parameter, αi = denotes the proportion of client i’s dataset size in the entire population. (1) x ∈ Rd がモデルパラメータである場合、αi = は人口全体のクライアント i のデータセットサイズの割合を表す。 0.62
In this paper, we consider the unbalanced data setting: αi 6= αj if i 6= j. 本稿では,不均衡なデータ集合である αi 6= αj を考える。 0.77
In (1), Fi(x, Di) , 1 F (x, ξi j ) is the local objective function, where ξi j is the j-th sample in Di. (1)において、fi(x, di) , 1 f (x, si j ) は局所目的函数であり、ここで si j は di の j-番目のサンプルである。 0.78
In FL, Fi(x, Di) is assumed to be non-convex in general. FL において、Fi(x, Di) は一般に非凸であると仮定される。 0.68
In each communication round t, the server broadcasts the latest global model parameter xt to each client. 各通信ラウンドtでは、サーバは各クライアントに最新のグローバルモデルパラメータxtをブロードキャストする。 0.76
Upon receiving xt, client i performs local computations with xi xt を受信すると、クライアント i は xi で局所計算を行う 0.73
|Di|Pξi Pi∈[m] |Di| |Di|P'i ピアル[m] |Di| 0.39
j∈Di |Di| t,0 = xt: t − 1, jjdi 〔di〕 t,0 = xt: t − 1 0.31
xi t,k+1 = xi xi t,k+1 = xi 0.46
t,k − η∇F (xi t,k − η\f (xi) である。 0.57
t,k, ξi t,k), t,k,i t,k)。 0.37
k = 0, . . . , τ i k = 0, . . , τ i 0.38
(2) where τ i t denotes the total number of local steps at client i in round t and ξi t,k is a random data sample used by client i in step k in round t. (2) τ i t は、ラウンド t のクライアント i における局所的なステップの総数、そして τi t,k は、ラウンド t のステップ k においてクライアント i が使うランダムなデータサンプルである。 0.63
We note that one key feature of the OTA-FL model in this paper is that we allow τ i t to be time-varying and device-dependent. 本稿では,OTA-FLモデルの重要な特徴の一つとして,τ i t の時間変化とデバイス依存を許容する点に留意する。 0.71
While this makes the OTA-FL model more practical and flexible, it also introduces an extra dimension of challenges in algorithmic design and convergence analysis. これにより、OTA-FLモデルはより実用的で柔軟なものとなるが、アルゴリズム設計と収束解析における課題の余分な次元も導入される。 0.69
After finishing the local iterations, each client returns the update of model parameters back to server. ローカルイテレーションを完了した後、各クライアントはモデルパラメータの更新をサーバに返します。 0.78
Upon the reception of returned updates from all clients, the server aggregates and updates the global model xt. すべてのクライアントから返される更新を受信すると、サーバはグローバルモデルxtを集約し、更新する。 0.75
In OTA-FL, the aggregation process on the server side happens automatically over-the-air thanks to the superposition property of the wireless medium. OTA-FLでは、無線媒体の重ね合わせ特性により、サーバ側のアグリゲーションプロセスが自動的にオンザエアされる。 0.70
The specific communication model will be described in Section III-B. 具体的な通信モデルは第III-B節で記述する。 0.70
B. Communication Model We consider an OTA-FL system in which the server broadcasts to all clients in a downlink channel and the clients transmit to the server through a common uplink channel synchronously. B.通信モデル 我々は、サーバがダウンリンクチャネルで全クライアントにブロードキャストし、クライアントが共通のアップリンクチャネルを介してサーバに同期的に送信するOTA-FLシステムを考える。 0.84
We assume an error-free downlink when broadcasting the global model. グローバルモデルをブロードキャストする場合,エラーのないダウンリンクを仮定する。 0.60
This is a reasonable assumption when the server has access to more power and bandwidth resources compared to edge devices. これはサーバがエッジデバイスよりも多くの電力と帯域のリソースにアクセスできるという合理的な仮定である。 0.77
As a result, each client receives an error-free global model parameter xt for its local computation in the beginning of each round t, i.e., xi t,0 = xt. その結果、各クライアントは、各ラウンドt、すなわちxi t,0 = xtの開始時に、ローカル計算のためのエラーのないグローバルモデルパラメータxtを受信する。 0.79
For the uplink, we consider a Gaussian MAC, where the output the channel in each communication round t is: アップリンクについては、各通信ラウンド t におけるチャネルの出力が次のようになるガウスmacを考える。 0.67
yt = Xi∈[m] yt = Xi∂[m] 0.35
hi tzi t + wt. こんにちは tzi t + wt である。 0.71
(3) In (3), zi gain of client i, and wt ∼ N (0, σ2 (3) (3)では、クライアント i の zi ゲインと wt > N (0, σ2) 0.62
t ∈ Rd is the input from client i, hi t ∈ Rd はクライアント i, hi からの入力である 0.88
t is the channel c Id) is an additive Gaussian t はチャネル c Id) は加法ガウスである 0.63
channel noise. チャンネルノイズ。 0.73
英語(論文から抽出)日本語訳スコア
We also consider an instantaneous power constraint at each それぞれに瞬間的な電力制約も考慮する。 0.75
client in each communication round: 各通信ラウンドのクライアント: 0.75
kzi tk2 ≤ P i t , キジ tk2 ≤ P i t , 0.46
∀i ∈ [m],∀t, i ∈ [m], t である。 0.56
(4) where P i i in communication round t. (4) p i は t で通信する。 0.48
t is the maximum transmission power limit for client tはクライアントの送信電力制限の最大値です 0.89
IV. IMPACTS OF CHANNEL NOISE AND SYSTEM-DATA IV。 チャネルノイズとシステムデータの影響 0.48
HETEROGENEITY ON OTA-FL OTA-FLのヘテロジェネティ 0.61
In Section IV-A, we first characterize the impact of the channel noise on OTA-FL when directly applying the standard FedAvg framework with SGD local updates without considering power control at each client. 第IV節-A節では、各クライアントの電力制御を考慮せずに、SGDローカル更新で標準のFedAvgフレームワークを直接適用する場合、チャネルノイズがOTA-FLに与える影響を最初に特徴付ける。 0.62
Then, in Section IV-B, we provide a concrete example to further illustrate the impact of channel noise coupled with heterogeneous numbers of local updates, i.e., system heterogeneity, on OTA-FL performance. そして,第IV節-B節において,チャネルノイズと局部更新の異種数,すなわちシステムの異種度がOTA-FL性能に与える影響を更に示す具体例を示す。 0.77
A. Impact of Channel Noise on OTA-FL A. OTA-FLにおけるチャネルノイズの影響 0.75
To study the impact of channel noise, we first consider a general L-smooth objective function (i.e., having L-Lipschitz continuous gradients) with a single local step, i.e., τ i t = 1,∀i ∈ [m], t ∈ [T ]. チャネルノイズの影響を研究するために、まず1つの局所ステップ、すなわちτ i t = 1, i ∈ [m], t ∈ [T ] を持つ一般L-スムース目的関数(すなわち、L-リプシッツ連続勾配を持つ)を考える。 0.74
We note that we consider the original FedAvg where model parameters {xi t, i ∈ [m]} are aggregated overthe-air without any further scaling. ここでは、モデルパラメータ {xi t, i ∈ [m]} がそれ以上のスケーリングを行わずに空気上に集約されるオリジナルのFedAvgを考える。 0.70
Consequently, the channel output could be simplified as xt+1 = xt − η∇F (xt, ξt) + wt, where ξt , {ξi t,∀i ∈ [m]} represents one collective data batch composed of random samples {ξi t,∀i} from all clients. したがって、チャネル出力は xt+1 = xt − η\f (xt, \t) + wt として単純化できる(ここで st , {i t, \i ∈ [m]} はすべてのクライアントからランダムなサンプル {i t,\i} からなる1つの集合データバッチを表す)。 0.76
Then, we have the following theorem to characterize the impact of the channel noise on the OTA version of the FedAvg algorithm: 次に、fedavgアルゴリズムのota版におけるチャネルノイズの影響を特徴付ける次の定理を示す。 0.65
Theorem 1 (Lower Bound for Gaussian Channel). 定理1(ガウスチャネルのより下界)。 0.52
Consider an OTA-FL system for training an L-smooth objective function F (x) with an optimal solution x∗. 最適解 x∗ で l-smooth objective function f (x) を訓練するための ota-fl システムを考える。 0.75
Supposed that each client uses local SGD updates that are subject to additive white Gaussian noise (AWGN), i.e., xt+1 = xt − η∇F (xt, ξt) + wt, where η < 1 c Id). 各クライアントは、付加的な白色ガウスノイズ(AWGN)、すなわち xt+1 = xt − η\F(xt, tt) + wt(η < 1 c Id)の対象となる局所的なSGD更新を使用する。 0.86
Then, the sequence {xt} satisfies the following recursive relationship: 次に、列 {xt} は次の再帰関係を満たす。 0.72
L and wt ∼ N (0, σ2 L と wt は N (0, σ2) である。 0.70
E(cid:2)kxt+1 − x∗k2(cid:3) ≥ Eh(1 − ηL)2 kxt − x∗k2i + η2σ2 + σ2 E(cid:2)kxt+1 − x∗k2(cid:3) ≥ Eh(1 − ηL)2 kxt − x∗k2i + η2σ2 + σ2 0.35
which further implies the following lower bound for the training convergence: これはさらに、トレーニング収束の以下の下限を意味する。 0.65
c , lim t→∞ c」。 lim t→∞ 0.33
E(cid:2)kxt − x∗k2(cid:3) ≥ E(cid:2)kxt − x∗k2(cid:3) ≥ 0.37
η2σ2 + σ2 c η2σ2 + σ2 c 0.33
1 − (1 − ηL)2 , 1 − (1 − ηL)2 , 0.47
where the stochastic gradient noise is assumed to be Gaussian, 確率的勾配ノイズがガウス的であると仮定される。 0.61
i.e., ∇F (xt, ξt) − ∇F (xt) ∼ N (0, σ2Id). すなわち、n (0, σ2Id) − σF (xt, σ2Id) である。 0.67
Proof Sketch. By assuming independent stochastic gradient noise and channel noise, we could decouple these noise terms and thus producing an iteration relation of kxt − x∗k by Lsmoothness with proper learning rate η < 1 L . スケッチの証明。 独立確率勾配雑音とチャネル雑音を仮定することにより、これらの雑音項を分離し、Lsmoothness による kxt − x∗k の反復関係を適切な学習率 η < 1 L で生成することができる。 0.69
As the channel noise exists in every round, such noise variance term σ2 c is non-vanishing even for infinitely many rounds. チャネルノイズはすべてのラウンドに存在するので、このようなノイズ分散項 σ2 c は無限に多くのラウンドに対しても消滅しない。 0.56
Due to space limitation, we refer readers to Appendix VIII for the complete proof. 空間制限のため、読者は完全な証明のために appendix viii を参照する。 0.63
standard SGD updates are used locally at each client. 標準のsgdアップデートは各クライアントでローカルに使用される。 0.69
This motivates us to develop joint adaptive computation and power control for OTA-FL to mitigate the MAC noise effect. これにより、MACノイズ効果を軽減するために、OTA-FLの協調適応計算と電力制御を開発することができる。 0.64
B. Impacts of System-Data Heterogeneity on OTA-FL B. OTA-FLにおける系統データ不均一性の影響 0.49
As discussed in above Section III-A, the FL optimization problem considered in this paper contains non-convex objective function, heterogeneous (non-i.i.d.) data, and different number of local updates τ i t at each client. 上述のセクションIII-Aで論じられたように、この論文で考慮されたFL最適化問題は、非凸目的関数、不均一(非i.d.)データ、各クライアントにおけるローカル更新 τ i t の異なる数を含む。 0.65
As shown in previous work [19], different number of local steps (or optimization processes) among clients introduce objective inconsistency, rendering potentially arbitrary deviation from optimal solutions in conventional FL. 以前の研究[19]で示されているように、クライアント間の異なるローカルステップ(あるいは最適化プロセス)が客観的な矛盾を導入し、従来のFLの最適解から潜在的に逸脱する可能性がある。
訳抜け防止モード: 以前の作業 [19 ] で示されているように、クライアント間で異なるローカルステップ(あるいは最適化プロセス)が客観的な矛盾を導入します。 従来のFLにおける最適解からの潜在的任意の偏差のレンダリング。
0.60
Next, we show that similar negative impacts of data heterogeneity and different number of local steps also affect the OTA-FL performance even under proper power control. 次に,データの不均一性と異なる局所ステップ数による同様の負の影響が,適切な電力制御下でもota-fl性能に与える影響を示す。 0.69
This insight further motivates the need for a joint adaptive computation and power control. この洞察は、協調適応計算と電力制御の必要性をさらに動機付ける。 0.75
Here, we use the GD method for each client’s local update and omit the channel noise for now to clearly characterize the above factors in FL. ここで、各クライアントのローカル更新にgdメソッドを使用し、今のところチャネルノイズを省略し、上記のflの要因を明確に特徴付ける。 0.67
That is, each client i ∈ [m] takes local steps as follows: すなわち、各クライアント i ∈ [m] は以下のローカルステップを取る。 0.76
xi t,k+1 = xi xi t,k+1 = xi 0.46
Then, a power control factor at client i is applied as follows: zi factor β on the server side can be written as 次に、クライアントiの電力制御係数を次のように適用する。 サーバ側のzi因子βは、次のように書ける。 0.73
t,k − η∇Fi(xi t,0(cid:1). t,k − η\fi(xi t,0(cid:1) である。 0.62
The aggregation with power control パワーコントロールによるアグリゲーション 0.64
t = βi(cid:0)xi t = βi(cid:0)xi 0.43
∀k ∈ [τi]. k ∈ [τi] である。 0.56
t,τi − xi t,k), t,τi − xi t,k)。 0.42
(6) xt+1 − xt = (6) xt+1 − xt = 0.42
m Xi=1 βi β (cid:0)xi M Xi=1 βi β (cid:0)xi 0.38
t,0(cid:1) . t,0(cid:1)。 0.59
t,τi − xi We now consider the following OTA-FL example: t,τi − xi 以下はOTA-FLの例である。 0.62
(7) Example 1 (Deviation of Objective Value under Disjoint Power Control and System-Data Heterogeneity). (7) 例1(解離電力制御とシステム-データ不均一性の下での客観値の決定)。 0.50
Consider quadratic objective functions: 二次目的関数を考える。 0.59
Fi(x) = F (x) = Fi(x) = F(x) = 0.42
1 2 m xtHix − eT Xi=1 αiFi(x) = 1-2m xtHix − eT Xi=1 αiFi(x) = 0.40
i x + i H−1 eT i x + i H−1 eT 0.41
1 2 xt ¯Hx − ¯ei 1 2 xt shx − sei である。 0.58
1 2 i ei,∀i ∈ [m], and αieT 1 2 i ei, i ∈ [m], αiet 0.38
T x + m 1 2 T x + M 1 2 0.41
Xi=1 i H−1 Xi=1 i H−1 0.32
i ei, where Hi ∈ Rd×d is invertible, ¯H ,Pm an arbitrary vector, and ¯e , Pm τi GD steps. 私は... ここで、Hi ∈ Rd×d は可逆であり、Pm は任意のベクトルであり、Pm τi GD の段階である。 0.45
Then, the generated sequence {xt} satisfies: そして、生成されたシーケンス {xt} が満足する。 0.64
i=1 αiHi, ei ∈ Rd is i=1 αiei. i=1 αiHi, ei ∈ Rd は i=1 αiei である。 0.67
Let each client take 各クライアントを離す 0.74
(5) lim t→∞ (5) lim t→∞ 0.39
xt = ˆx, xt = sx である。 0.75
where the limit point ˆx can be computed as: β [I − (I − ηHi)τi] H−1 β [I − (I − ηHi)τi] H−1 β [i − (i − ηhi)τi] h−1 β [i − (i − ηhi)τi] h−1 と計算できる。 0.76
ˆx =hPm hPm x =hPm hPm 0.40
i Hii−1 i eii . I Hii−1 i eii である。 0.57
i=1 i=1 i=1 である。 i=1 である。 0.31
βi βi For the quadratic objective function F (x), the closed-form solution is x∗ = ¯H−1¯e. βi βi 二次目的函数 f(x) に対して、閉形式解は x∗ = sh−1 である。 0.49
Comparing x∗ and ˆx, we can see a deviation that depends on problem hyper-parameter H, learning rate η, local step numbers τi, factor βi and β. x∗ と x を比較すると、問題の超パラメータ H, 学習率 η, 局所ステップ数 τi, 因子 βi, β に依存する偏差が見られる。 0.80
(8) (9) × Theorem 1 suggests that (8) (9) × 定理1はそれを示唆する 0.46
there is a non-vanishing convergence error due to the Gaussian MAC noise when only ガウスMACノイズによる非消滅収束誤差があるときのみ 0.58
Due to space limitation, we provide the proof details of this example in Appendix VIII. 空間制限のため、この例の証明の詳細を Appendix VIII で提供する。 0.74
It can be seen from this example この例から見ることができる。 0.84
英語(論文から抽出)日本語訳スコア
Algorithm 1 Adaptive Over-the-Air Federated Learning. アルゴリズム1 適応的オーバーザエアフェデレーション学習 0.62
1: Init: global mode x0. 1: インイット: グローバルモード x0。 0.87
2: for t = 0, . . . , T − 1 do 2: t = 0, . . , t − 1 に対して 0.81
3: 4: 5: 6: 3: 4: 5: 6: 0.43
7: Server broadcasts latest global model xt to each device. 7: サーバは各デバイスに最新のグローバルモデルxtをブロードキャストする。 0.53
for each client i ∈ [m] do 各クライアント i ∈ [m] do に対して 0.87
Each client locally and adaptively trains model via SGD (10) under power constraints and transmits δi t by transmission scaling as in (11). 各クライアントは、電力制約下でSGD (10)を介して局所的かつ適応的にモデルを訓練し、(11)のように送信スケーリングによりδi tを送信する。 0.58
end for The server aggregates and updates global model by receiver rescaling (12). サーバは、レシーバ再スケーリングによってグローバルモデルを集約し、更新する(12)。 0.65
8: end for that the complex coupling between power control and systemdata heterogeneity renders a highly non-trivial OTA-FL power control and algorithmic design to guarantee convergence to an optimal solution. 8: 終了。 電力制御とシステムデータの不均一性の複雑な結合は、最適解への収束を保証するために非常に非自明なota-fl電力制御とアルゴリズム設計をもたらす。 0.70
This further motivates our OTA-FL algorithm design with joint adaptive computation and power control in Section V. このことはOTA-FLアルゴリズムの設計を第V節の適応計算と電力制御で動機付けている。 0.67
V. ALGORITHM DESIGN V.アルゴリトム設計 0.73
To address the negative impacts of channel noise and system-data heterogeneity in Section IV, we propose an overthe-air federated learning algorithm with joint adaptive computation and power control (ACPC-OTA-FL) as shown in Algorithm 1. 第4節では、チャネルノイズとシステムデータの不均一性による負の影響に対処するため、アルゴリズム1に示すように、協調適応計算と電力制御(ACPC-OTA-FL)を用いたオーバーエア・フェデレーション学習アルゴリズムを提案する。 0.68
The basic idea of our ACPC-OTA-FL algorithm is to utilize a time-varying dynamic number of local SGD steps at each client under the instantaneous power constraint at this particular client. acpc-ota-flアルゴリズムの基本的な考え方は、特定のクライアントの瞬時パワー制約の下で各クライアントのローカルsgdステップの時変動的数を利用することです。 0.72
Specifically, given a server-side power control scaling factor βt, each client i chooses to perform τ i t local SGD steps as follows: 具体的には、サーバ側の電力制御スケーリング係数 βt が与えられた場合、各クライアント i は τ i t ローカル SGD ステップを実行することを選択します。 0.63
xi t,k+1 = xi xi t,k+1 = xi 0.46
t,k − η∇F (xi t,k − η\f (xi) である。 0.57
t,k, ξi t,k), t,k,i t,k)。 0.37
k = 1, . . . , τ i t , k = 1 , τ i t である。 0.63
(10) under the time-varying and client-dependent power constraints t such that kδi P i (10) kδi P i のような時間変化およびクライアント依存の電力制約 t の下で 0.54
tk2 ≤ P i t , where δi tk2 ≤ p i t, ここでδi 0.61
t − xi t,0) and t − xi t,0) および 0.58
t = βi t(xi t = βi t(xi) 0.46
t,τ i βi t = t,τi βi t = 0.43
βtαi τ i t βtαi τ i t 0.37
. (11) Given power constraints P and β, we can choose τ i t based on trail-and-error or greedy approach whenever the power constraints are satisfied. . (11) パワー制約 p と β が与えられると、パワー制約が満たされるたびに、trail-and-error や greedy アプローチに基づいて τ i t を選択できる。 0.49
For simplicity, we ignore fading for t + wt. 単純さのため、t + wt のフェーディングは無視する。 0.57
With power is now. The uplink channel output isPm 力があれば 今だ uplink channel output isPm 0.54
control rescaling on the server side, aggregated and updated as: サーバ側のコントロール再スケーリングを集約し、次のように更新する。 0.58
the global model グローバルモデルでは 0.78
i=1 δi xt+1 = xt + i=1δi xt+1 = xt + 0.35
m Xi=1 δi t βt M Xi=1 δi t βt 0.35
+ ˜wt. (12) + swt。 (12) 0.39
wt ∼ N (0, σ2 wt n (0, σ2) である。 0.65
As mentioned earlier, we assume a Gaussian channel noise Id). 先に述べたように、ガウスチャネルノイズidを仮定する)。 0.64
The novelty of our algorithm lies in utilizing a time-varying dynamic local steps to fully exploit the computation and communication power resources. 我々のアルゴリズムの新規性は、時間変化の動的局所的なステップを利用して計算と通信の電力資源を完全に活用することにある。 0.67
c Id) and thus ˜wt ∼ N (0, σ2 c Id) で、したがって、n (0, σ2) である。 0.67
c β2 t There are two advantages in our algorithm compared to previous works. c β2 t 我々のアルゴリズムには以前のものに比べて2つの利点がある。 0.78
First, we jointly consider the computationcommunica tion co-design due to their complex coupling relationship as shown in Section IV-B. まず,第IV-B節に示すような複雑な結合関係による計算通信の協調設計について考察する。 0.72
As a result, more powerful clients with more computation capacities and transmission power will execute more local update steps and have a large fraction in the server-side aggregation. その結果、より強力な計算能力と送信パワーを持つクライアントは、よりローカルな更新ステップを実行し、サーバ側のアグリゲーションに大きな割合を持つことになる。 0.65
This adaptive and client-dependent design is different from previous works [11], [12], [14]–[18], which considered the communication problem separately after finishing local update computation and used an uniform power control scaling factor without considering the heterogeneity among the clients. この適応性とクライアント依存の設計は、ローカル更新処理を終えて通信問題を別々に考慮し、クライアント間の不均一性を考慮せずに一様電力制御スケーリング係数を使用した以前の[11], [12], [14]–[18]と異なる。 0.87
Second, our ACPC-OTA-FL algorithm alleviates the straggler (i.e., slow client) problem by allowing different local step numbers across clients in each communication round. 第2に、ACPC-OTA-FLアルゴリズムは、各通信ラウンドにおけるクライアント間の異なるローカルステップ番号を許容することにより、ストラグラー(すなわち遅いクライアント)問題を緩和する。 0.62
Before providing the theoretical convergence result, we first state our assumptions: 理論的な収束結果を提供する前に、まず仮定を述べる。 0.69
Assumption 1. (L-Lipschitz Continuous Gradient) 仮定1。 (l-リプシッツ連続勾配) 0.58
There exists a constant L > 0, such that k∇Fi 定数 L > 0 が存在して k が成り立つ。 0.69
(x) − ∇Fi (y)k ≤ Lkx − yk, ∀x, y ∈ Rd, and i ∈ [m]. (x) − ジフィ (y)k ≤ lkx − yk, (y)x, y ∈ rd, i ∈ [m] である。 0.88
Assumption 2. (Unbiased Local Stochastic Gradients and Their Bounded Variance) Let ξi be a random local data sample at client i. 推定 2. (Unbiased Local Stochastic Gradients and Their Bounded Variance) .i をクライアント i におけるランダムなローカルデータサンプルとする。 0.71
The local stochastic gradient is unbiased and has a bounded variance, i.e., E[∇Fi(x, ξi)] = ∇Fi(x), ∀i ∈ [m], and E[k∇Fi(x, ξi) − ∇Fi(x)k2] ≤ σ2, where the expectation is taken over the local data distribution Xi. 局所確率勾配(英語版)は偏りがなく、有界な分散(英語版)(bounded variance)を持つ、すなわち、局所データ分布 xi に対して期待値が取られる e[\fi(x, \\fi(x), e[k\fi(x, \fi(x)-\fi(x)k2} ≤ σ2 である。 0.75
Assumption 3. (Bounded Stochastic Gradient) There exist a constant G ≥ 0, such that the norm of each local stochastic gradient is bounded: E[k∇Fi(x, ξi)k2] ≤ G2, ∀i ∈ [m]. 推定 3. (境界確率勾配) 定数 G ≥ 0 が存在し、各局所確率勾配のノルムは有界である: E[k)Fi(x, .i)k2] ≤ G2, .i ∈ [m] 。 0.61
Assumptions 1–2 are common in the analysis of SGD-based algorithms. 仮定 1-2 は SGD ベースのアルゴリズムの解析において一般的である。 0.58
Assumption 3 is also widely used in OTA-FL with non-i.i.d. datasets (e g , [12], [18], [20]). 推定3は、非i.d.データセット(eg , [12], [18], [20])を持つOTA-FLでも広く使われている。 0.79
With these three assumptions, we have the following convergence result: Theorem 2 (Convergence Rate). これら3つの仮定により、次の収束結果が得られる:定理2(収束率)。 0.68
Let {xt} be the global model generated by Algorithm 1. xt} をアルゴリズム1で生成される大域的モデルとする。 0.71
Under Assumptions 1- 3 and a constant learning rate ηt = η,∀t ∈ [T ], it holds that: Xi=1 {z |{z} 仮定 1-3 と一定学習率 ηt = η,\t ∈ [T ] では、Xi=1 {z |{z} となる。 0.80
2 (F (x0) − F (x∗)) | } 2 (F (x0) − F (x∗)) | } 0.43
Ek∇F (xt)k2 ≤ xt)k2 ≤ である。 0.59
{z Xi=1 {z z xi=1 {z である。 0.47
+ mL2η2G2 (αi)2 (τi)2 + mL2η2G2 (αi)2(τi)2 0.34
optimization error Lσ2 c ηβ2 最適化エラー Lσ2 c ηβ2 0.51
local update error min t∈[T ] ローカル更新エラー min (複数形 mins) 0.61
+ Lησ2 statistical error +Lησ2 統計誤差 0.51
channel noise } | チャネルノイズ } | 0.54
| α2 i T η error | α2i Tη 誤り 0.49
+ where (τi)2 = + ここで (τi)2 = 0.61
t=0 (τ i PT −1 T t=0(τi) PT −1 T 0.59
t )2 and 1 t)2。 そして 1 0.81
¯β2 = 1 m m ¯β2 = 1 M M 0.38
, } T PT−1 t=0 , T PT−1 t=0 0.38
1 β2 t . Proof Sketch. 1 β2 t . スケッチの証明。 0.66
In each round, the average global model update is the same as noise-free FedAvg since the channel noise is independent Gaussian with zero mean. 各ラウンドでは、平均的なグローバルモデル更新はノイズフリーのFedAvgと同じであり、チャンネルノイズは平均ゼロの独立ガウスである。 0.73
Thus, we can decouple the channel noise term as an extra error scaled by σ2 c when β2 t calculating the function descent (F (xt+1) − F (xt)) in each round by the L-smoothness. したがって、各ラウンドの関数降下 (f (xt+1) − f (xt)) をl-スムースネスで計算したとき、チャネルノイズ項をσ2 c でスケールする余分な誤差として分離することができる。 0.69
Then, the technical challenge lies in heterogeneous local steps across clients. 技術的な課題は、クライアント間の異種なローカルステップにある。 0.55
By simulating シミュレーションすることで 0.57
英語(論文から抽出)日本語訳スコア
i=1 αi τ i i=1 である。 αi τ i 0.39
2 ηtEt[kPm t mL2Pm 2 ηtEt[kPm t mL2Pm 0.41
mini-batch SGD method, we could further bound the differt Pτ i t−1 ence 1 t,k))k2] ≤ k=0 (∇Fi(xt) − ∇Fi(xi i=1(αi)2(cid:0)τ i t(cid:1)2 1 2 η3 G2, which accounts for the size of dataset, data heterogeneity and different local steps. Pτ i t−1 ence 1 t,k))k2] ≤ k=0 (\Fi(xt) − >Fi(xi i=1(αi)2(cid:0)τ i t(cid:1)2 1 2 η3 G2 はデータセットのサイズ、データの異質性、局所的なステップが異なる。 0.78
The above two terms correspond to channel noise error and local update error, respectively. 上記の2つの用語はそれぞれチャンネルノイズエラーとローカル更新エラーに対応している。 0.77
Following the classic analysis for SGDbased methods, the optimization error and statistical error could be similarly derived, and the final convergence result naturally follows. SGD法における古典的な解析の後、最適化誤差と統計的誤差も同様に導出することができ、最終的な収束結果は自然に従う。
訳抜け防止モード: SGD法における古典的解析の後、最適化誤差と統計誤差も同様に導出できる。 最終的な収束結果は自然に続きます
0.79
Due to space limitation, we relegate the full proof to Appendix VIII. 空間制限のため、我々は Appendix VIII に完全証明を再帰する。 0.77
Theorem 2 characterizes four sources of errors that affect the convergence rate: 定理2は収束率に影響を与える4つの誤差源を特徴づける。 0.66
1) the optimization error dependent on the distance between the initial guess and optimal objective value; 1) 最適化誤差は,初期推定値と最適目標値との距離に依存する。 0.85
2) the statistical error due to the use of stochastic gradients rather than full gradients; 2) 完全勾配よりも確率勾配を用いることによる統計的誤差 0.62
3) local update error from local update steps coupled with data heterogeneity; and 3) ローカル更新ステップからのローカル更新エラーとデータの不均一性 0.77
4) channel noise error from over-the-air transmissions. 4) 送風機からの流路騒音誤差 0.65
Among these four errors, only the optimization error (first term) vanishes as the total number of iterations T gets large, while other three terms are independent of T . これら4つの誤りのうち、最適化誤差(第一項)だけが、T の総イテレーション数が大きくなるにつれて消え、他の3つの項は T とは独立である。 0.69
Similar to classic SGD or FedAvg convergence analysis, diminishing learning rates O( 1√T ) can be used to remove the statistical and local update errors and obtain a convergence error bound mint∈[T ] Ek∇F (xt)k2 = O( 1√T ). 古典的なSGDやFedAvg収束解析と同様に、統計的および局所的な更新誤差を除去し、収束誤差境界 mint・[T ] Ek-F (xt)k2 = O(1\T ) を得ることができる。 0.71
To mitigate the channel noise error, the parameter β needs to be chosen judiciously. チャネルノイズを緩和するには、パラメータβを適切に選択する必要がある。 0.81
Given δi t in communication round t, we can set t (τ i t )2 t = mini∈[m]{ P i β2 i }. 通信円 t における δi t が与えられたとき、t (τ i t )2 t = mini∂[m]{ P i β2 i } を設定できる。 0.78
If the δi t-information is unavailable, kδi tk2α2 t )2G2 by its upper bound, and tk2 ≤ η2 we can choose kδi t = Pt thus β2 t G2 , where Pt = mini∈[m] P i t . δi t-情報が利用できない場合、kδi tk2α2 t )2g2 はその上界で、tk2 ≤ η2 は kδi t = pt から β2 t g2 を選ぶことができる。 0.81
For the special i η2 t ,∀i, t, αi = 1 case with P = P i m (balanced datasets), and identical local steps τ i t = τ,∀i, t, the channel noise error c G2 (the fourth term) becomes ησ2 P m2 , and the following result immediately follows from Theorem 2: p = p i m (バランスデータセット) と同一の局所ステップ τ i t = τ,i, t を持つ特別な i η2 t ,i, t, αi = 1 の場合、チャネルノイズエラー c g2 (第4項) は ησ2 p m2 となり、次の結果は定理 2 からすぐ続く。 0.84
t (τ i t (複数形 ts) 0.58
α2 , β2 = m α2 , β2 = m 0.44
m , τi = τ, η = η2 , the convergence rate of ACPC-OTA-FL under ). m , τi = τ, η = η2, ACPC-OTA-FL の収束速度。 0.68
Corollary 1 (Convergence Rate). Let αi = 1 √m√T the special case above is O( σ2+1√mT Corollary 1 implies that, if τ ≤ T 1/4 m3/4 , a linear speedup in terms of the number of clients (i.e., O( )) can be achieved, which shows the benefits of parallelism and matches the convergence rate of FedAvg in noise-free communication environment [21], [22]. 第1回(収束率)。 上の特別な場合を o( σ2+1,mt corollary 1) とすると、τ ≤ t 1/4 m3/4 のとき、クライアント数(すなわち o( ) )の項による線形速度アップは、並列性(parallelism)の利点を示し、ノイズのない通信環境 [21], [22] におけるfedavgの収束率と一致する。 0.70
) + O( mτ 2G2 ) + O(mτ 2G2 0.81
) + O( σ2 c√mT ) + o( σ2 ) である。 0.58
1√mT T Lastly, we note that it is straightforward to extend our results to fading channels with known CSI. 1/mT T 最後に、結果を既知のcsiでフェージングチャネルに拡張するのは簡単なことです。 0.42
Specifically, the adaptive computation and power control strategy for fading channels tk2 ≤ P i is to choose local steps τ i t , where δi t = βi t > 0 represents the maximum transmission power for client i in round t. 具体的には、フェーディングチャネル tk2 ≤ P i に対する適応計算および電力制御戦略は、δi t = βi t > 0 が t のクライアント i の最大送信電力を表すような局所ステップ τi t を選択することである。 0.85
Under this joint computation and power control, the received signal remains the same as that in the non-fading OTA-FL setting. この共同計算と電力制御の下では、受信信号は非フェーディングOTA-FL設定と同じである。 0.73
Thus, the same convergence results in Theorem 2 and Corollary 1 continue to hold. したがって、定理 2 と補題 1 における同じ収束結果が保たれている。 0.71
t such that kδi t = βtαi , and P i τ i t hi t t を kδi t = βtαi とし、p i τi t hi t とする。 0.64
t(cid:0)xi t,τi − xi t(cid:0)xi t,τi − xi 0.46
t,0(cid:1) , βi t,0(cid:1),βi 0.37
LOGISTIC REGRESSION TEST ACCURACY (%) FOR ACPC-OTA-FL COMPARED WITH COTAF AND FEDAVG ON THE MNIST DATASET. コタフとFedAVGとを併用したACPC-OTA-FLのロジスティック回帰試験精度(%)。 0.61
TABLE I Non-IID Level テーブルI 非IIDレベル 0.66
Algorithm p = 1 アルゴリズム p = 1 0.57
p = 2 p = 5 p = 2 p = 5 0.43
p = 10 ACPC-OTA-FL p = 10 ACPC-OTA-FL 0.31
COTAF FedAvg COTAF FedAvg 0.43
ACPC-OTA-FL ACPC-OTA-FL 0.20
COTAF FedAvg COTAF FedAvg 0.43
ACPC-OTA-FL ACPC-OTA-FL 0.20
COTAF FedAvg COTAF FedAvg 0.43
ACPC-OTA-FL ACPC-OTA-FL 0.20
COTAF FedAvg COTAF FedAvg 0.43
Signal-to-Noise Ratio -1 dB 78.22 46.55 67.49 81.89 63.59 71.55 86.48 79.64 74.76 86.21 86.43 76.26 信号対雑音比 -1 dB 78.22 46.55 67.49 81.89 63.59 71.55 86.48 79.64 74.76 86.21 86.43 76.26 0.23
10 dB 89.08 65.54 68.08 89.58 78.80 78.03 90.64 86.52 82.84 90.75 91.08 84.94 10 dB 89.08 65.54 68.08 89.58 78.80 78.03 90.64 86.52 82.84 90.75 91.08 84.94 0.23
20 dB 89.54 85.92 67.65 90.43 86.57 79.86 91.20 90.82 85.40 91.08 92.63 88.11 20 dB 89.54 85.92 67.65 90.43 86.57 79.86 91.20 90.82 85.40 91.08 92.63 88.11 0.23
VI. NUMERICAL RESULTS In this section, we conduct numerical experiments to verify our theoretical results using logistic regression on the MNIST dataset [23]. VI。 数値結果 本稿では,MNISTデータセット[23]上のロジスティック回帰を用いて理論的結果を検証する数値実験を行う。 0.62
Following the same procedure as in existing works [1], [20], [22], we distribute the data evenly to m = 10 clients in a label-based partition to impose data heterogeneity across the clients, where the heterogeneity level can be characterized by a parameter p. 既存の作業 [1], [20], [22] と同じ手順に従って、データをラベルベースのパーティションで m = 10 のクライアントに均等に分散し、クライアントに不均一性を課し、不均一度レベルをパラメータ p で特徴づける。 0.67
As the MNIST dataset contains 10 classes of labels in total, p = 10 represents the i.i.d. case. MNISTデータセットには10のラベルのクラスが含まれており、p = 10はi.i.d.の場合を表す。 0.70
The smaller the p-value, the more heterogeneous the data across clients. p-値が小さくなればなるほど、クライアント間のデータの均一性が増す。 0.59
We simulate Gaussian MAC with signal-to-noise ratios (SNRs) of −1 dB, 10 dB and 20 dB. ガウスMACを1dB,10dB,20dBの信号-雑音比(SNR)でシミュレートする。 0.77
We illustrate the test accuracy of ACPC-OTA-FL compared with COTAF [18] and FedAvg [1] in Table I. Two key observations are in order: 表Iにおける COTAF [18] および FedAvg [1] と比較した ACPC-OTA-FL の試験精度について述べる。 0.73
1) Test accuracy drops significantly by directly applying FedAvg algorithm to wireless OTA-FL (up to 20% accuracy drop) under large channel noise, which validates our Theorem 1 and is consistent with existing works [9]–[11]; and 1) 大チャネル雑音下で無線ota-fl(最大20%の精度低下)にfedavgアルゴリズムを直接適用することにより,テスト精度は大幅に低下する。
訳抜け防止モード: 1)fedavgアルゴリズムをワイヤレスota - flに直接適用することで、テスト精度が大幅に低下する (最大20%精度低下) 大きなチャンネルノイズで 私たちの定理1を検証し、既存の作品[9]–[11 ]と一致します。
0.77
2) Under power control, both ACPC-OTA-FL and COTAF could alleviate the channel noise impacts in the i.i.d. data setting (p = 10). 2) 電力制御では, acpc-ota-flとcotafは, i.i.d.データ設定(p = 10)におけるチャネルノイズの影響を軽減することができた。 0.64
But in the highly heterogeneous data (p = 1, しかし、高度に異質なデータ(p = 1)では 0.77
2) and/or low SNR settings, our ACPC-OTAFL algorithm outperforms COTAF by a large margin. 2) および/または低SNR設定では, 当社のACPC-OTAFLアルゴリズムはCOTAFよりも大きなマージンで優れている。 0.62
For example, when SNR = −1 dB and p = 1, ACPC-OTA-FL improves the test accuracy by 31.76% and 10.73% compared to COTAF and FedAvg, respectively. 例えば、SNR = −1 dB と p = 1 のとき、ACPC-OTA-FL は COTAF と FedAvg と比較してテスト精度を 31.76% と 10.73% 改善する。 0.74
The intuition is that the gradient returned from the clients vary dramatically in highly heterogeneous data settings, and thus utilizing an adaptive local steps under limited power constraints allows each client to fully exploit both computation and communication resources. 直感的には、クライアントから返される勾配は、非常に異種なデータ設定で劇的に変化するため、限られた電力制約の下で適応的なローカルステップを利用することで、各クライアントは計算と通信リソースの両方を完全に活用できる。 0.56
VII. CONCLUSION In this paper, we considered the joint adaptive local computation (number of local steps) and power control for OTAFL. VII。 結論 本稿では,otaflにおける協調適応局所計算(局所ステップ数)と電力制御について検討した。 0.68
We first characterized the training error due to channel noise for conventional OTA-FL by establishing a fundamental lower bound for general objective functions with Lipschitzcontinuous gradients. 我々はまず,従来のOTA-FLのチャネルノイズによるトレーニング誤差を,リプシッツ連続勾配を持つ汎用関数の基本的な下限を確立することで特徴づけた。 0.70
This motivated us to propose an overthe-air federated learning algorithm with joint adaptive computation and power control (ACPC-OTA-FL) to mitigate the impacts of channel noise on the learning performance, while これにより,協調適応計算と電力制御(ACPC-OTA-FL)を併用したオーバーエア・フェデレーション学習アルゴリズムを提案し,チャネルノイズが学習性能に与える影響を緩和する。 0.83
英語(論文から抽出)日本語訳スコア
[21] H. Yu, S. Yang, and S. Zhu, “Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. H. Yu, S. Yang, S. Zhuは、AAAI Conference on Artificial Intelligence, vol.の中で、“Parallelは、より早く収束し、コミュニケーションの少ないsgdを再開した。
訳抜け防止モード: [21]H.Yu、S.Yang、S.Zhu 並列再起動型sgdの高速化とコミュニケーションの低減 : なぜデミスティフィケーション モデル平均化はディープラーニングに役立ちます。 人工知能国際会議(AAAI)に参加して
0.65
33, no. 01, 2019, pp. 5693–5700. 33, no. 01, 2019, pp. 5693-5700。 0.90
[22] H. Yang, M. Fang, and J. Liu, “Achieving linear speedup with partial worker participation in non-IID federated learning,” in International Conference on Learning Representations, 2021. 22] h. yang, m. fang, j. liu, “achieving linear speedup with partial workers participation in non-iid federated learning” in international conference on learning representations, 2021” (英語)
訳抜け防止モード: [22 ]H. Yang, M. Fang, J. Liu 「非IDフェデレーション学習における部分的労働者参加による線形スピードアップの実現」 国際学習表現会議(2021年)に参加。
0.81
[Online]. Available: https://openreview.n et/forum? [オンライン]。 https://openreview.n et/forum? 0.50
id=jDdzh5ul-d id=jDdzh5ul-d 0.15
[23] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” Proceedings of the IEEE, vol. Y. LeCun, L. Bottou, Y. Bengio, P. Haffner, “Gradient-based learning applied to document recognition”, Proceedings of the IEEE, vol。
訳抜け防止モード: [23 ]Y.LeCun,L.Bottou,Y.B engio, そしてP. Haffner氏は,“ドキュメント認識に適用されたグラディエントベースの学習”だ。 IEEE , vol の成果。
0.71
86, no. 11, pp. 2278–2324, 1998. 86, No. 11, pp. 2278–2324, 1998。 0.45
taking the device heterogeneity into consideration. 装置の不均一性を考慮に入れます 0.60
We analyzed the convergence of ACPC-OTA-FL with non-convex objective functions and heterogeneous data, and shown that the convergence rate of ACPC-OTA-FL matches that of FedAvg with noise-free communications. 非凸目的関数と異種データとのACPC-OTA-FLの収束速度を解析し、ACPC-OTA-FLの収束速度がFedAvgとノイズフリー通信と一致することを示した。 0.64
REFERENCES [1] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-efficient learning of deep networks from decentralized data,” in Artificial intelligence and statistics. 参考 B. McMahan氏、E. Moore氏、D. Ramage氏、S. Hampson氏、B. A. y Arcas氏は人工知能と統計学で「分散データから深層ネットワークをコミュニケーション効率よく学習する」と語っています。
訳抜け防止モード: 参考 B. McMahan, E. Moore, D. Ramage, S. Hampson, B. A. y Arcas, “コミュニケーション - 分散データからのディープネットワークの効率的な学習”。 人工知能と統計学の分野です
0.66
PMLR, 2017, pp. 1273– 1282. pmlr、2017年、p.1273-1282。 0.55
[2] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” ACM Transactions on Intelligent Systems and Technology (TIST), vol. [2] Q. Yang, Y. Liu, T. Chen, Y. Tong, “Federated Machine Learning: Concept and Applications”, ACM Transactions on Intelligent Systems and Technology (TIST), vol. 0.43
10, no. 2, pp. 1–19, 2019. 第10巻、第2巻、第1-19頁、2019年。 0.41
[3] H. B. McMahan et al , “Advances and open problems in federated learning,” Foundations and Trends® in Machine Learning, vol. H.B. McMahan氏らによると,“フェデレートラーニングにおけるアドバンスとオープンな問題”は,機械学習のファウンデーションとトレンド®です。 0.65
14, no. 1, 2021. 14・1・2021。 0.46
[4] S. Niknam, H. S. Dhillon, and J. H. Reed, “Federated learning for wireless communications: Motivation, opportunities, and challenges,” IEEE Communications Magazine, vol. 4]s. niknam, h. s. dhillon, j. h. reed, “federated learning for wireless communications: motivation, opportunity, and challenges”. ieee communications magazine, vol. (英語)
訳抜け防止モード: [4 ]S.Niknam、H.S.Dhillon、J.H. Reed 「無線通信のためのフェデレーションラーニング : モチベーション、機会、課題」 IEEE Communications Magazine, vol。
0.71
58, no. 6, pp. 46–51, 2020. 58, No. 6, pp. 46-51, 2020。 0.46
[5] O. Abari, H. Rahul, and D. Katabi, “Over-the-air function computation [5]O. Abari, H. Rahul, D. Katabi, “Over-the-air function computing” 0.39
in sensor networks,” arXiv preprint arXiv:1612.02307, 2016. arxivは2016年にarxiv:1612.02307をプレプリントした。 0.36
[6] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via overthe-air computation,” IEEE Transactions on Wireless Communications, vol. 6] k. yang, t. jiang, y. shi, z. ding, “federated learning via over the-air computation”, ieee transactions on wireless communications, vol. 。
訳抜け防止モード: [6]王陽、T.江、Y.シー、 とZ.Ding氏は語る。「空気計算によるフェデレーション学習」。 IEEE Transactions on Wireless Communications, vol。
0.71
19, no. 3, pp. 2022–2035, 2020. 19, 3, pp. 2022-2035, 2020。 0.80
[7] G. Zhu, J. Xu, K. Huang, and S. Cui, “Over-the-air computing for wireless data aggregation in massive iot,” IEEE Wireless Communications, vol. ieee wireless communications, vol.7] g. zhu, j. xu, k. huang, s. cui, “大規模iotにおけるワイヤレスデータ集約のための無線コンピューティング”。 0.77
28, no. 4, pp. 57–65, 2021. 28,4,p.57-65,2021。 0.61
[8] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning based on over-the-air computation,” in ICC 2019-2019 IEEE international conference on communications (ICC). 9] K. Yang, T. Jiang, Y. Shi, Z. Ding, “Federated Learning based on over-the-air calculation” in ICC 2019-2019 IEEE international conference on Communication (ICC)。
訳抜け防止モード: [8]王陽、T.江、Y.シー、 そしてZ.Ding氏は,“オーバー - 空気計算に基づくフェデレートラーニング”について語る。 ICC 2019 - 2019 IEEE International Conference on Communications (ICC) に参加。
0.61
IEEE, 2019, pp. 1–6. IEEE, 2019, pp. 1-6。 0.44
[9] G. Zhu, Y. Wang, and K. Huang, “Broadband analog aggregation for low-latency federated edge learning,” IEEE Transactions on Wireless Communications, vol. G. Zhu, Y. Wang, K. Huang, “Broadband analog aggregate for low-latency federated edge learning”, IEEE Transactions on Wireless Communications, vol.[9] G. Zhu, Y. Wang, K. Huang。
訳抜け防止モード: 9 ] g. zhu, y. wang, k. huang. 低遅延フェデレートエッジラーニングのためのブロードバンドアナログアグリゲーション” ieee transactions on wireless communications, vol. を参照。
0.60
19, no. 1, pp. 491–506, 2019. 19, 1, pp. 491-506, 2019。 0.77
[10] T. Sery and K. Cohen, “On analog gradient descent learning over multiple access fading channels,” IEEE Transactions on Signal Processing, vol. 10] t. sery氏とk. cohen氏は、"複数のアクセスフェージングチャネル上でのアナログ勾配降下学習について"、ieee transactions on signal processing, vol。 0.66
68, pp. 2897–2911, 2020. 68, pp. 2897-2911, 2020。 0.90
[11] M. M. Amiri and D. G ¨und¨uz, “Federated learning over wireless fading channels,” IEEE Transactions on Wireless Communications, vol. IEEE Transactions on Wireless Communications, vol..[11] M.M. AmiriとD.G.シュンド・ジュズ, “Federated Learning over Wireless fading channel”. IEEE Transactions on Wireless Communications. 0.41
19, no. 5, pp. 3546–3557, 2020. 19,5,p.3546-3557,202 0。 0.64
[12] ——, “Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air,” IEEE Transactions on Signal Processing, vol. IEEE Transactions on Signal Processing, vol.[12] ——— “ワイヤレスエッジでのマシーン学習:分散確率勾配降下”。 0.71
68, pp. 2155–2169, 2020. 68, pp. 2155–2169, 2020。 0.93
[13] ——, “Over-the-air machine learning at the wireless edge,” in 2019 IEEE 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC). 2019年にはIEEE 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)が開催された。
訳抜け防止モード: ワイヤレスのエッジでエアマシーンを学習する”。 2019年、IEEE 20th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC) に参加。
0.62
IEEE, 2019, pp. 1–5. IEEE, 2019, pp. 1-5。 0.87
[14] G. Zhu, Y. Du, D. G ¨und¨uz, and K. Huang, “One-bit over-the-air aggregation for communication-efficient federated edge learning: Design and convergence analysis,” IEEE Transactions on Wireless Communications, vol. IEEE Transactions on Wireless Communications, vol.[14] G. Zhu, Y. Du, D. G シュンド・シュウズ, K. Huang, “通信効率のよいエッジ学習のための一ビットオーバーザエアアグリゲーション:設計と収束分析”。 0.84
20, no. 3, pp. 2120–2135, 2020. 20, 3, pp. 2120-2135, 2020。 0.79
[15] H. Guo, A. Liu, and V. K. Lau, “Analog gradient aggregation for federated learning over wireless networks: Customized design and convergence analysis,” IEEE Internet of Things Journal, vol. IEEE Internet of Things Journal, vol.[15] H. Guo, A. Liu, V. K. Lau, “Analog gradient aggregate for federated learning over Wireless network: Customized design and convergence analysis”. IEEE Internet of Things Journal.com
訳抜け防止モード: [15]H.Guo、A.Liu、V.K. Lau 「無線ネットワーク上での連合学習のためのアナログ勾配集約 : カスタマイズ設計と収束解析」 IEEE Internet of Things Journal(英語)
0.78
8, no. 1, pp. 197–210, 2020. 8巻1頁、p.197-210、2020年。 0.57
[16] L. Chen, X. Qin, and G. Wei, “A uniform-forcing transceiver design for over-the-air function computation,” IEEE Wireless Communications Letters, vol. ieee wireless communications letters, vol. “a uniform-forcing transceiver design for over-the-air function computation”[16] l. chen, x. qin, g. wei。
訳抜け防止モード: [16 ]l. chen, x. qin, g. wei, 「制服」 オーバーのためのトランシーバ設計を強制する --air function computation, ”ieee wireless communications letters, vol. の略。
0.61
7, no. 6, pp. 942–945, 2018. 7、no. 6、p. 942-945、2018。 0.80
[17] N. Zhang and M. Tao, “Gradient statistics aware power control for over-the-air federated learning in fading channels,” in 2020 IEEE International Conference on Communications Workshops (ICC Workshops). [17] n. zhang と m. tao は,2020 ieee international conference on communications workshops (icc workshops) において,“フェージングチャネルにおけるオーバー・ザ・エア・フェデレート・ラーニングのための段階的統計認識電力制御”を発表した。 0.71
IEEE, 2020, pp. 1–6. 橋本、2020年、p.1-6。 0.37
[18] T. Sery, N. Shlezinger, K. Cohen, and Y. C. Eldar, “Over-the-air federated learning from heterogeneous data,” IEEE Transactions on Signal Processing, 2021. T.Sery, N. Shlezinger, K. Cohen, Y. C. Eldar, “Over-the-air federated learning from heterogeneous data”, IEEE Transactions on Signal Processing, 2021。
訳抜け防止モード: [18 ]T.Sery,N.Shlezinger, K.Cohen, そしてY・C・エルダーは、"Over - the - the- air federated learning from heterogeneous data"と述べた。 IEEE Transactions on Signal Processing , 2021
0.68
[19] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the objective inconsistency problem in heterogeneous federated optimization,” Advances in Neural Information Processing Systems, vol. 19] j. wang, q. liu, h. liang, g. joshi, h. v. poor, “ヘテロジニアスフェデレーション最適化における客観的不整合問題に取り組むこと” ニューラル情報処理システムの進歩, vol.
訳抜け防止モード: [19 ]J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “異種フェデレーション最適化における目的的不整合問題に取り組む”。 ニューラル情報処理システムの進歩
0.86
33, 2020. [20] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, 33, 2020. [20]X.Li、K.Huang、W.Yang、S.Wang、Z.Zhang 0.37
“On the in International Conference on Learning Representations, 2020. 平成20年(2020年)、学習表現に関する国際会議。 0.64
[Online]. Available: https://openreview.n et/forum? [オンライン]。 https://openreview.n et/forum? 0.50
id=HJxNAnVtDS id=HJxNAnVtDS 0.29
convergence of fedavg on non-iid data,” 収束 非idデータに関するFeedavg”。 0.60
英語(論文から抽出)日本語訳スコア
Theorem 1 (Lower Bound for Gaussian Channel). 定理1(ガウスチャネルのより下界)。 0.52
Consider an OTA-FL system for training an L-smooth objective function F (x) with an optimal solution x∗. 最適解 x∗ で l-smooth objective function f (x) を訓練するための ota-fl システムを考える。 0.75
Supposed that each client uses local SGD updates that are subject to additive white Gaussian noise (AWGN), i.e., xt+1 = xt − η∇F (xt, ξt) + wt, where η < 1 c Id). 各クライアントは、付加的な白色ガウスノイズ(AWGN)、すなわち xt+1 = xt − η\F(xt, tt) + wt(η < 1 c Id)の対象となる局所的なSGD更新を使用する。 0.86
Then, the sequence {xt} satisfies そして、シーケンス {xt} が満たされる 0.79
L and wt ∼ N (0, σ2 L と wt は N (0, σ2) である。 0.70
the following recursive relationship: VIII. 次の再帰的な関係は VIII。 0.74
PROOF which further implies the following lower bound for the training convergence: 証明 これはさらに、トレーニング収束の以下の下限を意味する。 0.60
E(cid:2)kxt+1 − x∗k2(cid:3) ≥ Eh(1 − ηL)2 kxt − x∗k2i + η2σ2 + σ2 E(cid:2)kxt+1 − x∗k2(cid:3) ≥ Eh(1 − ηL)2 kxt − x∗k2i + η2σ2 + σ2 0.35
c , where the stochastic gradient noise is assumed to be Gaussian, i.e., ∇F (xt, ξt) − ∇F (xt) ∼ N (0, σ2Id). c」。 確率的勾配ノイズがガウス的(英語版)(gaussian)であると仮定される場合、すなわち f ( xt, σ2id) は n (0, σ2id) である。 0.49
lim t→∞ E(cid:2)kxt − x∗k2(cid:3) ≥ lim t→∞ E(cid:2)kxt − x∗k2(cid:3) ≥ 0.36
η2σ2 + σ2 c η2σ2 + σ2 c 0.33
1 − (1 − ηL)2 , 1 − (1 − ηL)2 , 0.47
Proof. E(cid:2)kxt+1 − x∗k2(cid:3) = E(cid:2)kxt − η∇F (xt, ξt) + wt − x∗k2(cid:3) 証明。 E(cid:2)kxt+1 − x∗k2(cid:3) = E(cid:3)kxt − η\F(xt, t) + wt − x∗k2(cid:3) 0.49
= E(cid:2)kxt − x∗ − η∇F (xt)k2(cid:3) + E(cid:2)kη∇F (xt, ξt) − η∇F (xt)k2(cid:3) + E(cid:2)kwtk2(cid:3) = E(cid:2)kxt − x∗ − η (∇F (xt) − ∇F (x∗)) k2(cid:3) + η2σ2 + σ2 ≥ Eh(kxt − x∗k − ηk∇F (xt) − ∇F (x∗)k)2i + η2σ2 + σ2 ≥ Eh(1 − ηL)2 kxt − x∗k2i + η2σ2 + σ2 E(cid:2)kxt − x∗ − ηnF (xt)k2(cid:3) + E(cid:2)kηnF (xt, sht) − ηnF (xt)k2(cid:3) + E(cid:2)kwtk2(cid:3) = E(cid:2)kxt − x∗ − η(shF (xt)) k2(cid:3) + η2σ2 + σ2 ≥ Eh(kxt − x∗k − ηknF (xt) − shF (x∗)k)2 + η2σ2 ≥ Eh(kxt − x∗)k2 + η2σ2 ≥ Eh(kxt − x∗)k2(cid:3) + η2σ2+ 0.40
c c c Example 1 Consider quadratic objective functions: c c c 例1 二次目的関数を考える。 0.49
(5) (13) (14) (5) (13) (14) 0.43
(15) (16) (17) (15) (16) (17) 0.43
Fi(x) = xtHix − eT Xi=1 αiFi(x) = i=1 αiHi, ei ∈ Rd is an arbitrary vector, and ¯e ,Pm where Hi ∈ Rd×d is invertible, ¯H ,Pm GD steps. Fi(x) = xtHix − eT Xi=1 αiFi(x) = i=1 αiHi, ei ∈ Rd は任意のベクトルであり、Hi ∈ Rd×d が可逆であるとき、Hi ∈ Rd×d は可逆である。 0.63
Then, the generated sequence {xt} satisfies: そして、生成されたシーケンス {xt} が満足する。 0.64
i ei,∀i ∈ [m], and αieT i ei, i ∈ [m], αiet 0.34
Xi=1 i H−1 Xi=1 i H−1 0.32
F (x) = i H−1 eT F(x) = i H−1 eT 0.41
1 2 xt ¯Hx − ¯ei 1 2 xt shx − sei である。 0.58
1 2 m i ei, 1-2m 私は... 0.30
T x + i x + T x + i x + 0.43
1 2 1 2 m i=1 αiei. 1 2 1 2 M i=1αiei。 0.46
Let each client take τi 各クライアントにτiを 0.80
where the limit point ˆx can be computed as: 極限点は次のように計算できる。 0.59
lim t→∞ xt = ˆx, lim t→∞ xt = sx である。 0.55
× (18) (19) × (18) (19) 0.42
i=1 ˆx =hPm hPm i=1 である。 x =hPm hPm 0.36
i=1 βi i=1 である。 βi 0.35
β [I − (I − ηHi)τi] H−1 β [I − (I − ηHi)τi] H−1 β [I − (I − ηHi)τi] H−1 β [I − (I − ηHi)τi] H−1 0.45
βi i Hii−1 i eii . βi I Hii−1 i eii である。 0.48
For the quadratic objective function F (x), the closed-form solution is x∗ = ¯H−1¯e. 二次目的函数 f(x) に対して、閉形式解は x∗ = sh−1 である。 0.68
Comparing x∗ and ˆx, we can see a deviation that depends on problem hyper-parameter H, learning rate η, local step numbers τi, factor βi and β. x∗ と x を比較すると、問題の超パラメータ H, 学習率 η, 局所ステップ数 τi, 因子 βi, β に依存する偏差が見られる。 0.80
Proof. Consider quadratic objective functions: 証明。 二次目的関数を考える。 0.60
Fi(x) = F (x) = Fi(x) = F(x) = 0.42
1 2 m xtHix − eT Xi=1 αiFi(x) = 1-2m xtHix − eT Xi=1 αiFi(x) = 0.40
i x + i H−1 eT i x + i H−1 eT 0.41
1 2 xt ¯Hx − ¯ei 1 2 xt shx − sei である。 0.58
1 2 i ei, T x + 1 2 私は... T x + 0.36
1 2 m Xi=1 1 2 M Xi=1 0.36
αiet iH−1 エイエット iH−1 0.40
i ei, (20) 私は... (20) 0.33
(21) i=1 αiei. (21) i=1αiei。 0.52
It is easy to show the optimum for each local and global objective function are x∗i = H−1 見せるのは簡単です 局所的および大域的目的関数の最適化は x∗i = H−1 である 0.66
where Hi ∈ Rd×d is invertible matrix, ¯H =Pm The local update for each client i ∈ [m] is as follows: xi t,k+1 = xi hi ∈ rd×d が可逆行列であるとき、各クライアント i ∈ [m] に対する局所更新は次のようになる: xi t,k+1 = xi。 0.81
i=1 αiHi, ei ∈ Rd is arbitrary vector, and ¯e =Pm i ei,∀i ∈ [m] and x∗ = ¯H−1¯e. i=1 αihi, ei ∈ rd は任意のベクトルであり、 s e = pm i ei, s i ∈ [m] と x∗ = sh−1 である。 0.70
t,k − ei(cid:3) t,k − ei(cid:3) 0.48
t,k − η(cid:2)Hixi = (I − ηHi) xi t,k − η(cid:2)hixi = (i − ηhi) xi 0.49
t,k + ηei (22) t,k + ηei (22) 0.46
(23) (23) 0.43
英語(論文から抽出)日本語訳スコア
Then we have the recursive equation for one local step by rearranging 23: そして、23:を並べ替えることで、ある局所的なステップに対する再帰方程式を得る。 0.56
where ci t = H−1 どこで t = H−1 0.57
i ei. xi t,k+1 − ci 私は... xi t,k+1 − ci 0.38
t = (I − ηHi)(cid:0)xi t = (I − ηHi)(cid:0)xi 0.47
t(cid:1) , t,k − ci t(cid:1) , t,k − ci 0.50
t,τi − ci xi t,τi − xi xi t,τi − ci xi t,τi − xi xi 0.49
t(cid:1) , t = (I − ηHi)τi(cid:0)xi t,0 − ci t,0(cid:1) (cid:0)ei − Hixi t,0 = [(I − ηHi)τi − I] H−1 = Ki(η)(cid:0)ei − Hixi t,0(cid:1) , t(cid:1) , t = (I − ηHi)τi(cid:0)xi t,0 − ci t,0(cid:1) (cid:0)ei − Hixi t,0 = [(I − ηHi)τi − I] H−1 = Ki(η)(cid:0)ei − Hixi t,0(cid:1) 0.41
i . i m βi 私は . 私は M βi 0.45
Aggregation: xt+1 − xt = アグリゲーション: xt+1 − xt = 0.49
where we define Ki(η) = [I − (I − ηHi)τi] H−1 Xi=1 Xi=1 xt+1 ="I − xt+1 − ˆx ="I − xt ="I − β Ki(η)eii =hPm ここで、Ki(η) = [I − (I − ηHi)τi] H−1 Xi=1 xt+1 ="I − xt+1 − sx ="I − xt ="I − β Ki(η)eii =hPm を定義する。 0.91
β Ki(η)Hii−1hPm β Ki(η)Hii−1hPm 0.41
i=1 As t goes to sufficiently large, we have i=1 t が十分に大きくなったら、 0.78
where ˆx :=hPm ここで-x :=hPm 0.48
βi β βi β t,0(cid:1) β (cid:0)xi t,τi − xi Ki(η)(cid:0)ei − Hixi t,0(cid:1) , Ki(η)Hi# xt + Xi=1 Xi=1 Ki(η)Hi# (xt − ˆx) , Xi=1 Ki(η)Hi#t Xi=1 βiβ βiβ t,0(cid:1) β (cid:0)xi t,τi − xi Ki(η)(cid:0)ei − Hixi t,0(cid:1) , Ki(η)Hi# xt + Xi=1 Xi=1 Ki(η)Hi# (xt − shx) , Xi=1 Ki(η)Hi#t Xi=1
訳抜け防止モード: βiβ βiβ t,0(cid:1 ) β (cid:0)xi t, τi − xi ki(η)(cid:0)ei − hixi t,0(cid:1 ) ki(η)hi # xt + xi=1 xi=1 ki(η)hi # ( xt − sx ) である。 xi=1 ki(η)hi#t xi=1
0.54
βi β βi β i=1 βiβ βiβ i=1 である。 0.39
i=1 = i=1 である。 = 0.37
βi βi βi m βi βi βi M 0.39
m m m m lim t→∞ M M M M lim t→∞ 0.37
xt = ˆx. xt = x である。 0.77
βi β Ki(η)ei, βiβ Ki(η)ei 0.37
(x0 − ˆx) + ˆx, (x0 − >x) + >x。 0.39
β [I − (I − ηHi)τi] H−1 β [I − (I − ηHi)τi] H−1 0.45
i Hii−1hPm i Hii−1hPm 0.29
i=1 (24) i=1 である。 (24) 0.37
(25) (26) (27) (25) (26) (27) 0.43
(28) (29) (30) (28) (29) (30) 0.43
(31) (32) βi (31) (32) βi 0.41
i eii. β [I − (I − ηHi)τi] H−1 I eii. β [I − (I − ηHi)τi] H−1 0.41
Theorem 2 (Convergence Rate). Let {xt} be the global model generated by Algorithm 1. 理論2(収束率)。 xt} をアルゴリズム1で生成される大域的モデルとする。 0.50
Under Assumptions 1- 3 and a 1- 3 と a の仮定の下で 0.59
constant learning rate ηt = η,∀t ∈ [T ], it holds that: 一定の学習率 ηt = η,\t ∈ [t ] では、次のようになる。 0.64
min t∈[T ] min (複数形 mins) 0.46
Ek∇F (xt)k2 エケシュフ(xt)k2 0.71
≤ where (τi)2 = ≤ ここで (τi)2 = 0.61
Proof. t=0 (τ i 証明。 t=0(τi) 0.66
PT −1 T t )2 PT −1 T t)2。 0.65
and 1 ¯β2 = 1 そして 1 ¯β2 = 1 0.59
+ Lησ2 α2 i + mL2η2G2 +Lησ2 α2i + mL2η2G2 0.30
m Xi=1 {z M xi=1 {z である 0.40
} | | m Xi=1 {z } | | M xi=1 {z である 0.42
statistical error local update error 統計誤差 ローカル更新エラー 0.75
(αi)2 (τi)2 (αi)2(τi)2 0.45
+ Lσ2 c ηβ2 + Lσ2 c ηβ2 0.36
, (33) T η optimization error , (33) Tη 最適化エラー 0.50
2 (F (x0) − F (x∗)) | } T PT−1 2 (F (x0) − F (x∗)) | } T PT−1 0.48
{z 1 β2 t t=0 {z 1 β2 t t=0 0.55
. xt+1 − xt = . xt+1 − xt = 0.42
= = m m Xi=1 Xi=1 Xi=1 = = M M Xi=1 Xi=1 Xi=1 0.37
m βi β (cid:16)xi t (cid:16)xi M βi β(cid:16)xit(cid:16)x i 0.40
αi τ i αi τ i t αi τ i αi τ i t 0.48
ηt t,0(cid:17) + ˜wt t,0(cid:17) + ˜wt ηt t,0(cid:17) + swt t,0(cid:17) + swt 0.36
t,τ i t − xi t,τi t − xi 0.41
t,τ i t − xi τ i t−1 Xk=0 (cid:0)∇Fi(xi t,τi t − xi τ i t−1 Xk=0 (cid:0) =Fi(xi) 0.38
t,k, ξi t,k)(cid:1) + ˜wt t,k,i t,k)(cid:1) + swt である。 0.52
} channel noise |{z} } チャネルノイズ |{z} 0.68
error (34) (35) 誤り (34) (35) 0.52
(36) (37) Due to L-smoothness, we have one step descent in expectation conditioned on xt, (36) (37) L-smoothness により、xt に条件付き期待値が 1 段階降下する。 0.49
Et[F (xt+1)] − F (xt) ≤ h∇F (xt), Et [xt+1 − xt]i + Et[F (xt+1)] − F (xt) ≤ h\F (xt), Et[xt+1 − xt]i + 0.49
L 2 Et(cid:2)kxt+1 − xtk2(cid:3) L2 Et(cid:2)kxt+1 − xtk2(cid:3) 0.37
英語(論文から抽出)日本語訳スコア
err 翻訳エラー 0.00
英語(論文から抽出)日本語訳スコア
1 2 ≤ η3 t mL2 1 2 ≤ η3 t mL2 0.41
m Xi=1 t(cid:1)2 (αi)2(cid:0)τ i M Xi=1 t(cid:1)2(αi)2(cid:0)τi 0.37
G2 Plugging inequality (55) into (49), we have G2 不平等(55)を(49)にプラグインすること 0.59
Et[F (xt+1)] − F (xt) ≤ h∇F (xt), Et [xt+1 − xt]i + G2 + Et[F (xt+1)] − F (xt) ≤ h*F (xt), Et[xt+1 − xt]i + G2 + 0.50
η3 t mL2 m η3 t mL2 M 0.38
ηtk∇F (xt)k2 + ηtknF (xt)k2 + 0.41
≤ − 1 2 1 2 ≤ − 1 2 1 2 0.43
Xi=1 t(cid:1)2 (αi)2(cid:0)τ i Xi=1 t(cid:1)2(αi)2(cid:0)τi 0.36
L 2 Lη2 t 2 L2 Lη2 t 2 0.42
Et(cid:2)kxt+1 − xtk2(cid:3) Xi=1 Et(cid:2)kxt+1 − xtk2(cid:3) Xi=1 0.34
α2 i σ2 + m α2 i σ2 + M 0.40
Lσ2 c 2β2 t lσ2 c 2β2 t 0.62
Rearranging and telescoping: 再配置とテレスコップ: 0.80
(55) (56) (57) (55) (56) (57) 0.43
1 T T−1 Xt=0 1T T−1 Xt=0 0.32
ηtEtk∇F (xt)k2 ≤ ηtEtknF(xt)k2 ≤ 0.43
2 (F (x0) − F (xT )) 2 (F (x0) − F (xT )) 0.46
T + mL2 1 T T + mL2 1 T 0.46
T−1 Xt=0 η3 t T−1 Xt=0 η3 t 0.34
m Xi=1 t(cid:1)2 (αi)2(cid:0)τ i M Xi=1 t(cid:1)2(αi)2(cid:0)τi 0.37
G2 + Lσ2 m G2 + Lσ2 M 0.36
Xi=1 α2 i 1 T Xi=1 α2i 1T 0.36
T−1 Xt=0 η2 t + Lσ2 T−1 Xt=0 η2 t + Lσ2 0.32
c 1 T T−1 Xt=0 c 1T T−1 Xt=0 0.35
1 β2 t (58) 1 β2 t (58) 0.49
Let ηt = η be constant learning rate, (τi)2 = ηt = η を一定学習率 (τi)2 = とする。 0.86
t=0 (τ i PT −1 T t=0(τi) PT −1 T 0.59
t )2 then we have: t)2。 するとこうなるのです 0.57
where 1 ¯β2 = 1 場所1 ¯β2 = 1 0.50
T−1 1 T Xt=0 T PT−1 T−1 1T Xt=0 T PT−1 0.32
t=0 Ek∇F (xt)k2 ≤ t=0 xt)k2 ≤ である。 0.44
2 (F (x0) − F (xT )) 2 (F (x0) − F (xT )) 0.46
T η + mL2η2G2 Tη + mL2η2G2 0.31
1 β2 t . (αi)2 (τi)2 + Lησ2 1 β2 t . (αi)2 (τi)2 + lησ2 0.59
m Xi=1 α2 i + M Xi=1 α2 i + 0.37
Lσ2 c ηβ2 , Lσ2 c ηβ2 , 0.33
m Xi=1 (59) M Xi=1 (59) 0.36
                     ページの最初に戻る

翻訳にはFugu-Machine Translatorを利用しています。