論文の概要: Nearly Optimal Regret for Decentralized Online Convex Optimization
- arxiv url: http://arxiv.org/abs/2402.09173v1
- Date: Wed, 14 Feb 2024 13:44:16 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 15:19:52.560616
- Title: Nearly Optimal Regret for Decentralized Online Convex Optimization
- Title（参考訳）: 分散オンライン凸最適化における最善の後悔
- Authors: Yuanyu Wan and Tong Wei and Mingli Song and Lijun Zhang
- Abstract要約: 分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
- 参考スコア（独自算出の注目度）: 58.372148767703955
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 novel D-OCO algorithms 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 the 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})$, respectively. These
lower bounds suggest that our algorithms are nearly optimal in terms of $T$,
$n$, and $\rho$.
- Abstract（参考訳）: 本研究では,局所的な計算と通信のみを用いてグローバル損失関数列を最小化するために,局所学習者の一組が必要となる分散型オンライン凸最適化(d-oco)について検討する。
これまでの研究では、それぞれ凸関数と強い凸関数に対する後悔境界を$o(n^{5/4}\rho^{-1/2}\sqrt{t})$と${o}(n^{3/2}\rho^{-1}\log t)$が確立されており、ここでは$n$は局所学習者の数、$\rho<1$は通信行列のスペクトルギャップ、$t$は時間軸である。
しかし、既存の下限、すなわち凸函数に対して$\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})$に拡張する。
これらの下限は、我々のアルゴリズムが$T$, $n$, $\rho$の点でほぼ最適であることを示している。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - Fast Rates in Online Convex Optimization by Exploiting the Curvature of
Feasible Sets [42.37773914630974]
オンライン線形最適化では、損失関数の平均勾配が特定の値よりも大きい場合、実現可能な集合の曲率を利用することができる。
本稿では、損失関数の曲率に適応したアルゴリズムが、実現可能な集合の曲率を活用できることを明らかにする。
論文 参考訳（メタデータ） (2024-02-20T09:59:33Z) - On the Complexity of Finite-Sum Smooth Optimization under the
Polyak-{\L}ojasiewicz Condition [14.781921087738967]
本稿では、$min_bf xinmathbb Rd f(bf x)triangleq frac1nsum_i=1n f_i(bf x)$, ここで、$f(cdot)$はパラメータ$mu$と$f_i(cdot)_i=1n$は$L$-mean-squared smoothである。
論文 参考訳（メタデータ） (2024-02-04T17:14:53Z) - An Optimal Stochastic Algorithm for Decentralized Nonconvex Finite-sum
Optimization [25.21457349137344]
私たちは、DEARESTが少なくとも$mathcal O(+sqrtmnLvarepsilon-2)$ 1次オラクル(IFO)コールと$mathcal O(Lvarepsilon-2/sqrt1-lambda_W)$通信ラウンドを必要とすることを示す証拠を示します。
論文 参考訳（メタデータ） (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) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。