論文の概要: Decentralized Online Regularized Learning Over Random Time-Varying Graphs
- arxiv url: http://arxiv.org/abs/2206.03861v5
- Date: Fri, 01 Nov 2024 01:50:40 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-05 14:41:56.983984
- Title: Decentralized Online Regularized Learning Over Random Time-Varying Graphs
- Title（参考訳）: ランダムな時間変化グラフによる分散オンライン正規化学習
- Authors: Xiwei Zhang, Tao Li, Xiaozheng Fu,
- Abstract要約: ランダムな時間変化グラフを用いたオンライン正規化線形回帰アルゴリズムを開発した。
後悔の上限は$O(T1-tauln T)$であり、$tauin (0.5,1)$はアルゴリズムのゲインに依存する定数である。
さらに、後悔の上限は$O(T1-tauln T)$であり、$tauin (0.5,1)$はアルゴリズムのゲインに依存する定数であることを示す。
- 参考スコア（独自算出の注目度）: 4.065547532041163
- License:
- Abstract: We study the decentralized online regularized linear regression algorithm over random time-varying graphs. At each time step, every node runs an online estimation algorithm consisting of an innovation term processing its own new measurement, a consensus term taking a weighted sum of estimations of its own and its neighbors with additive and multiplicative communication noises and a regularization term preventing over-fitting. It is not required that the regression matrices and graphs satisfy special statistical assumptions such as mutual independence, spatio-temporal independence or stationarity. We develop the nonnegative supermartingale inequality of the estimation error, and prove that the estimations of all nodes converge to the unknown true parameter vector almost surely if the algorithm gains, graphs and regression matrices jointly satisfy the sample path spatio-temporal persistence of excitation condition. Especially, this condition holds by choosing appropriate algorithm gains if the graphs are uniformly conditionally jointly connected and conditionally balanced, and the regression models of all nodes are uniformly conditionally spatio-temporally jointly observable, under which the algorithm converges in mean square and almost surely. In addition, we prove that the regret upper bound is $O(T^{1-\tau}\ln T)$, where $\tau\in (0.5,1)$ is a constant depending on the algorithm gains.
- Abstract（参考訳）: ランダムな時間変化グラフ上の分散オンライン正規化線形回帰アルゴリズムについて検討する。
各時点において、各ノードは、独自の新しい測定値を処理する革新項と、追加的かつ乗算的な通信ノイズを伴って、それ自身とその隣人の推定量の重み付けされた和をとるコンセンサス項と、過度な適合を防止する正規化項からなるオンライン推定アルゴリズムを実行する。
回帰行列とグラフは、相互独立、時空間独立、定常といった特別な統計的仮定を満たす必要はない。
推定誤差の非負スーパーマーチンゲール不等式を開発し、アルゴリズムが励起条件のサンプルパス時空間的持続性を共に満たすと、全てのノードの推定が未知の真のパラメータベクトルにほぼ確実に収束することを証明した。
特に、この条件は、グラフが一様連接で条件バランスが取れている場合、適切なアルゴリズムゲインを選択し、全てのノードの回帰モデルが一様連接可能で、アルゴリズムが平均二乗に収束し、ほぼ確実に収束する。
さらに、後悔の上界が$O(T^{1-\tau}\ln T)$であることを証明する。
関連論文リスト
- Graphon Particle Systems, Part II: Dynamics of Distributed Stochastic Continuum Optimization [5.685037987395183]
ノード連続体を持つグラフオン上での分散最適化問題について検討する。
グラノン上での勾配降下と勾配追従アルゴリズムを提案する。
時間変化アルゴリズムを適切に選択することにより、すべてのノードの状態が接続されたグラフに対して$mathcalLinfty$-consensusを達成することを示す。
論文 参考訳（メタデータ） (2024-07-03T02:47:39Z) - A Statistical Theory of Regularization-Based Continual Learning [10.899175512941053]
線形回帰タスクの順序に基づく正規化に基づく連続学習の統計的解析を行う。
まず、全てのデータが同時に利用可能であるかのように得られたオラクル推定器の収束率を導出する。
理論解析の副産物は、早期停止と一般化された$ell$-regularizationの等価性である。
論文 参考訳（メタデータ） (2024-06-10T12:25:13Z) - Convergence Conditions of Online Regularized Statistical Learning in Reproducing Kernel Hilbert Space With Non-Stationary Data [4.5692679976952215]
本研究では,HilbertRKHSにおける正規化学習アルゴリズムの収束性について検討した。
独立および非独立に分散したデータストリームに対して、アルゴリズムは平均二乗一貫性を達成する。
論文 参考訳（メタデータ） (2024-04-04T05:35:59Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - Decentralized Online Learning for Random Inverse Problems Over Graphs [6.423798607256407]
ヒルベルト空間におけるアルゴリズムの安定性の収束性は、$_$-bounded martingale difference 項で表される。
ネットワークグラフが連結され、フォワード演算子の列が励起条件の無限次元時間持続性を満たすなら、全てのノードの推定は平均平方である。
非定常オンラインデータに基づく分散オンライン学習アルゴリズムをRKHSで提案する。
論文 参考訳（メタデータ） (2023-03-20T08:37:08Z) - On the Convergence of Stochastic Extragradient for Bilinear Games with
Restarted Iteration Averaging [96.13485146617322]
本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。
平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
論文 参考訳（メタデータ） (2021-06-30T17:51:36Z) - Spectral clustering under degree heterogeneity: a case for the random
walk Laplacian [83.79286663107845]
本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。
次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
論文 参考訳（メタデータ） (2021-05-03T16:36:27Z) - Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
帰納バイアスは 経験的に過剰フィットを防げる中心的存在です
この研究は、この問題を最も基本的な設定として考慮している: 線形回帰に対する定数ステップサイズ SGD。
我々は、(正規化されていない)SGDで得られるアルゴリズム正則化と、通常の最小二乗よりも多くの顕著な違いを反映する。
論文 参考訳（メタデータ） (2021-03-23T17:15:53Z) - The Connection between Discrete- and Continuous-Time Descriptions of
Gaussian Continuous Processes [60.35125735474386]
我々は、一貫した推定子をもたらす離散化が粗粒化下での不変性を持つことを示す。
この結果は、導関数再構成のための微分スキームと局所時間推論アプローチの組み合わせが、2次または高次微分方程式の時系列解析に役立たない理由を説明する。
論文 参考訳（メタデータ） (2021-01-16T17:11:02Z) - Graph Gamma Process Generalized Linear Dynamical Systems [60.467040479276704]
実マルチ変数時系列をモデル化するために,グラフガンマ過程(GGP)線形力学系を導入する。
時間的パターン発見のために、モデルの下での潜在表現は、時系列を多変量部分列の同相集合に分解するために使用される。
非零次ノード数が有限であるランダムグラフを用いて、潜時状態遷移行列の空間パターンと次元の両方を定義する。
論文 参考訳（メタデータ） (2020-07-25T04:16:34Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
本稿では、収束保証付き非正則正規化器のためのワーキングセットアルゴリズムを提案する。
その結果,ブロックコーディネートや勾配ソルバの完全解法と比較して高い利得を示した。
論文 参考訳（メタデータ） (2020-06-24T07:40:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。