論文の概要: Optimal and Efficient Algorithms for Decentralized Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2402.09173v3
- Date: Wed, 11 Dec 2024 06:07:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-12 13:58:52.525548
- Title: Optimal and Efficient Algorithms for Decentralized Online Convex Optimization
- Title(参考訳): 分散オンライン凸最適化のための最適・効率的なアルゴリズム
- Authors: Yuanyu Wan, Tong Wei, Bo Xue, Mingli Song, Lijun Zhang,
- Abstract要約: 分散オンライン凸最適化(D-OCO)は、局所計算と通信のみを用いて、グローバルな損失関数の列を最小化するように設計されている。
我々は,凸関数と強凸関数の残差を$tildeO(nrho-1/4sqrtT)$と$tildeO(nrho-1/2log T)$に削減できる新しいD-OCOアルゴリズムを開発した。
我々の分析によると、射影自由多様体は$O(nT3/4)$と$O(n)を達成できる。
- 参考スコア(独自算出の注目度): 51.00357162913229
- License:
- Abstract: We investigate decentralized online convex optimization (D-OCO), in which a set of local learners are required to minimize a sequence of global loss functions using only local computations and communications. Previous studies have established $O(n^{5/4}\rho^{-1/2}\sqrt{T})$ and ${O}(n^{3/2}\rho^{-1}\log T)$ regret bounds for convex and strongly convex functions respectively, where $n$ is the number of local learners, $\rho<1$ is the spectral gap of the communication matrix, and $T$ is the time horizon. However, there exist large gaps from the existing lower bounds, i.e., $\Omega(n\sqrt{T})$ for convex functions and $\Omega(n)$ for strongly convex functions. To fill these gaps, in this paper, we first develop a novel D-OCO algorithm that can respectively reduce the regret bounds for convex and strongly convex functions to $\tilde{O}(n\rho^{-1/4}\sqrt{T})$ and $\tilde{O}(n\rho^{-1/2}\log T)$. The primary technique is to design an online accelerated gossip strategy that enjoys a faster average consensus among local learners. Furthermore, by carefully exploiting spectral properties of a specific network topology, we enhance the lower bounds for convex and strongly convex functions to $\Omega(n\rho^{-1/4}\sqrt{T})$ and $\Omega(n\rho^{-1/2}\log T)$, respectively. These results suggest that the regret of our algorithm is nearly optimal in terms of $T$, $n$, and $\rho$ for both convex and strongly convex functions. Finally, we propose a projection-free variant of our algorithm to efficiently handle practical applications with complex constraints. Our analysis reveals that the projection-free variant can achieve ${O}(nT^{3/4})$ and ${O}(nT^{2/3}(\log T)^{1/3})$ regret bounds for convex and strongly convex functions with nearly optimal $\tilde{O}(\rho^{-1/2}\sqrt{T})$ and $\tilde{O}(\rho^{-1/2}T^{1/3}(\log T)^{2/3})$ communication rounds, respectively.
- Abstract(参考訳): 分散オンライン凸最適化(D-OCO)について検討し、局所的な計算と通信のみを用いて、グローバルな損失関数の列を最小化するために、一組のローカル学習者が要求される。
これまでの研究では、$O(n^{5/4}\rho^{-1/2}\sqrt{T})$および${O}(n^{3/2}\rho^{-1}\log T)$ regret bounds for convex and strong convex function, where $n$ is the number of local learners, $\rho<1$ is the gap of the communication matrix, $T$ is the time horizon。
しかし、既存の下界からの大きなギャップ、すなわち凸函数の$Omega(n\sqrt{T})$、強凸函数の$Omega(n)$がある。
これらのギャップを埋めるために、まず、凸関数と強凸関数の後悔境界をそれぞれ$\tilde{O}(n\rho^{-1/4}\sqrt{T})$と$\tilde{O}(n\rho^{-1/2}\log T)$に還元できる新しいD-OCOアルゴリズムを開発する。
主な手法は,地域学習者の平均コンセンサスを向上するオンライン・アクセラレーション・ゴシップ・ストラテジーを設計することである。
さらに、特定のネットワークトポロジーのスペクトル特性を慎重に活用することにより、凸関数と強凸関数の下位境界を、それぞれ$\Omega(n\rho^{-1/4}\sqrt{T})$と$\Omega(n\rho^{-1/2}\log T)$に拡張する。
これらの結果から,我々のアルゴリズムの後悔は凸関数と凸関数の両方に対して$T$,$n$,および$\rho$の点でほぼ最適であることが示唆された。
最後に,複雑な制約を伴って現実的なアプリケーションを効率的に扱うために,提案アルゴリズムのプロジェクションフリー変種を提案する。
我々の分析は、射影自由多様体が${O}(nT^{3/4})$と${O}(nT^{2/3)(\log T)^{1/3})$、ほぼ最適な$\tilde{O}(\rho^{-1/2}\sqrt{T})$と$\tilde{O}(\rho^{-1/2}T^{1/3}(\log T)^{2/3})$通信ラウンドで、凸関数と強凸関数に対する後悔境界をそれぞれ達成できることを明らかにする。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳(メタデータ) (2024-08-21T20:14:54Z) - Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。
逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。
設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
論文 参考訳(メタデータ) (2024-06-10T17:44:11Z) - Fast Rates in Stochastic Online Convex Optimization by Exploiting the Curvature of Feasible Sets [35.8717656676532]
オンライン線形最適化では、損失関数の平均勾配が一定の閾値を超えると、実現可能な集合の曲率を利用することができることが知られている。
本研究では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
論文 参考訳(メタデータ) (2024-02-20T09:59:33Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳(メタデータ) (2023-01-01T18:51:29Z) - On the Complexity of Decentralized Smooth Nonconvex Finite-Sum Optimization [21.334985032433778]
分散最適化問題 $min_bf xinmathbb Rd f(bf x)triq frac1msum_i=1m f_i(bf x)triq frac1nsum_j=1n。
論文 参考訳(メタデータ) (2022-10-25T11:37:11Z) - Decentralized Stochastic Variance Reduced Extragradient Method [25.21457349137344]
本稿では,$min_xmax_y fx,y triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumi=1m f_i triqfrac1msumiの分散凸-凹極小最適化問題を考察する。
論文 参考訳(メタデータ) (2022-02-01T16:06:20Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳(メタデータ) (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳(メタデータ) (2021-02-15T08:16:51Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。