論文の概要: Projection-free Distributed Online Learning with Strongly Convex Losses
- arxiv url: http://arxiv.org/abs/2103.11102v1
- Date: Sat, 20 Mar 2021 05:38:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-23 14:54:34.098225
- Title: Projection-free Distributed Online Learning with Strongly Convex Losses
- Title（参考訳）: 凸損失の強いプロジェクションフリー分散オンライン学習
- Authors: Yuanyu Wan, Guanghui Wang, Lijun Zhang
- Abstract要約: 損失関数の強い凸性を利用して、後悔と通信の複雑さを改善する。
本アルゴリズムは多対数因子に縛られた$o(t2/3log t)$ regretを得るのにほぼ最適である。
- 参考スコア（独自算出の注目度）: 37.08975118221237
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: To efficiently solve distributed online learning problems with complicated
constraints, previous studies have proposed several distributed projection-free
algorithms. The state-of-the-art one achieves the $O({T}^{3/4})$ regret bound
with $O(\sqrt{T})$ communication complexity. In this paper, we further exploit
the strong convexity of loss functions to improve the regret bound and
communication complexity. Specifically, we first propose a distributed
projection-free algorithm for strongly convex loss functions, which enjoys a
better regret bound of $O(T^{2/3}\log T)$ with smaller communication complexity
of $O(T^{1/3})$. Furthermore, we demonstrate that the regret of distributed
online algorithms with $C$ communication rounds has a lower bound of
$\Omega(T/C)$, even when the loss functions are strongly convex. This lower
bound implies that the $O(T^{1/3})$ communication complexity of our algorithm
is nearly optimal for obtaining the $O(T^{2/3}\log T)$ regret bound up to
polylogarithmic factors. Finally, we extend our algorithm into the bandit
setting and obtain similar theoretical guarantees.
- Abstract（参考訳）: 複雑な制約で分散オンライン学習問題を効率的に解くため、従来の研究では、複数の分散プロジェクションフリーアルゴリズムが提案されている。
最先端のものは$O({T}^{3/4})$ regret bound with $O(\sqrt{T})$ communication complexityを達成する。
本稿では,損失関数の強い凸性を利用して,後悔の束縛とコミュニケーションの複雑さを改善する。
具体的には、まず、強い凸損失関数に対する分散プロジェクションフリーアルゴリズムを提案し、このアルゴリズムは、$O(T^{2/3}\log T)$と$O(T^{1/3})$の通信複雑性がより小さいことを後悔する。
さらに,損失関数が強い凸である場合でも,$c$通信ラウンドを持つ分散オンラインアルゴリズムの後悔は$\omega(t/c)$という低い限界を持つことを実証する。
この下限は、我々のアルゴリズムの$O(T^{1/3})$通信複雑性が、多対数因子に束縛された$O(T^{2/3}\log T)$後悔を得るのにほぼ最適であることを意味する。
最後に,アルゴリズムを帯域設定に拡張し,同様の理論的保証を得る。
関連論文リスト
- Nearly Optimal Regret for Decentralized Online Convex Optimization [53.433398074919]
分散オンライン凸最適化(D-OCO)は,局所計算と通信のみを用いて,グローバルな損失関数の列を最小化することを目的としている。
我々は凸関数と強い凸関数の残差をそれぞれ低減できる新しいD-OCOアルゴリズムを開発した。
我々のアルゴリズムは、$T$、$n$、$rho$の点でほぼ最適です。
論文 参考訳（メタデータ） (2024-02-14T13:44:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Nearly Optimal Algorithms with Sublinear Computational Complexity for
Online Kernel Regression [13.510889339096117]
後悔と計算コストのトレードオフは、オンラインカーネル回帰の根本的な問題である。
AOGD-ALDとNONS-ALDの2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-14T07:39:09Z) - Improved Projection-free Online Continuous Submodular Maximization [35.324719857218014]
単調かつ連続DR-サブモジュラー報酬関数を用いたオンライン学習の問題点について検討する。
従来の研究では、$O(T)$グラデーション評価を用いたMono-Frank-Wolfe (Mono-FW)と呼ばれる効率的なプロジェクションフリーアルゴリズムが提案されている。
同じ計算量を維持しつつ, 後悔を$O(T3/4)$に抑える改良されたプロジェクションフリーアルゴリズム(POBGA)を提案する。
論文 参考訳（メタデータ） (2023-05-29T02:54:31Z) - Projection-free Online Exp-concave Optimization [21.30065439295409]
LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。
我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
論文 参考訳（メタデータ） (2023-02-09T18:58:05Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Empirical Risk Minimization in the Non-interactive Local Model of
Differential Privacy [26.69391745812235]
本研究では,非対話型局所微分プライバシー(LDP)モデルにおける経験的リスク最小化(ERM)問題について検討する。
これまでの研究では、誤差$alphaを達成するためには、一般的な損失関数の次元$p$に依存する必要があることが示されている。
論文 参考訳（メタデータ） (2020-11-11T17:48:00Z) - Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。
一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
論文 参考訳（メタデータ） (2020-10-16T05:42:50Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。