論文の概要: Online Frank-Wolfe with Unknown Delays

• arxiv url: http://arxiv.org/abs/2204.04964v1
• Date: Mon, 11 Apr 2022 09:26:24 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-12 17:14:33.780375
• Title: Online Frank-Wolfe with Unknown Delays
• Title（参考訳）: 不明遅延を伴うオンラインFrank-Wolfe
• Authors: Yuanyu Wan and Wei-Wei Tu and Lijun Zhang
• Abstract要約: オンラインのFrank-Wolfe (OFW) 法は、プロジェクションフリーな性質のため、オンライン凸最適化において大いに人気を集めている。 我々は、勾配が任意の遅延と未知の遅延を伴って到着するより実践的な設定を検討し、この設定にOwを一般化する遅延 OFWを提案する。
• 参考スコア（独自算出の注目度）: 42.87484879029545
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The online Frank-Wolfe (OFW) method has gained much popularity for online convex optimization due to its projection-free property. Previous studies showed that for convex losses, OFW attains $O(T^{3/4})$ regret over general sets and $O(T^{2/3})$ regret over strongly convex sets, and if losses are strongly convex, these bounds can be improved to $O(T^{2/3})$ and $O(\sqrt{T})$, respectively. However, they assumed that each gradient queried by OFW is revealed immediately, which may not hold in practice. In this paper, we consider a more practical setting where gradients arrive with arbitrary and unknown delays, and propose delayed OFW which generalizes OFW to this setting. The main idea is to perform an update similar to OFW after receiving any gradient, and play the latest decision for each round. We first show that for convex losses, delayed OFW achieves $O(T^{3/4}+dT^{1/4})$ regret over general sets and $O(T^{2/3}+dT^{1/3})$ regret over strongly convex sets, where $d$ is the maximum delay. Furthermore, we prove that for strongly convex losses, delayed OFW attains $O(T^{2/3}+d\log T)$ regret over general sets and $O(\sqrt{T}+d\log T)$ regret over strongly convex sets. Compared with regret bounds in the non-delayed setting, our results imply that the proposed method is robust to a relatively large amount of delay.
• Abstract（参考訳）: オンラインのFrank-Wolfe(OFW)メソッドは、プロジェクションフリーな性質のため、オンライン凸最適化において非常に人気がある。 以前の研究では、凸損失に対して、OWは一般集合に対する後悔$O(T^{3/4})と強い凸集合に対する後悔$O(T^{2/3})を達成し、損失が強い凸であれば、これらの境界はそれぞれ$O(T^{2/3})$と$O(\sqrt{T})$に改善できることを示した。 しかし、OFWによってクエリされた各勾配は直ちに明らかになり、実際には保持されない可能性がある。 本稿では、勾配が任意かつ未知の遅延で到達するより実用的な設定を検討し、この設定を一般化する遅延 OFWを提案する。 主なアイデアは、グラデーションを受け取った後にOFWに似たアップデートを実行し、各ラウンドの最新の決定を実行することである。 まず、凸損失に対して、遅延 OFW は一般集合に対して$O(T^{3/4}+dT^{1/4}) および強い凸集合に対して$O(T^{2/3}+dT^{1/3}) の後悔を達成し、$d$ は最大遅延であることを示す。 さらに、強い凸損失に対して、遅延 OFW は一般集合に対する後悔$O(T^{2/3}+d\log T) と強凸集合に対する後悔$O(\sqrt{T}+d\log T) が得られることを証明している。 非遅延設定の後悔限界と比較すると,提案手法は比較的大きな遅延に対して頑健であることが示唆された。

関連論文リスト

• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。 ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。 ゲームにおける高速収束と拡張逆最適化への応用について述べる。
  論文  参考訳（メタデータ） (2024-08-17T02:22:08Z)
• Online Dynamic Submodular Optimization [0.0]
  オンラインバイナリ最適化のための証明可能な性能を持つ新しいアルゴリズムを提案する。 高速な需要応答とリアルタイム分散ネットワーク再構成という2つのパワーシステムアプリケーションでアルゴリズムを数値的にテストする。
  論文  参考訳（メタデータ） (2023-06-19T10:37:15Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Scaling Forward Gradient With Local Losses [117.22685584919756]
  フォワード学習は、ディープニューラルネットワークを学ぶためのバックプロップに代わる生物学的に妥当な代替手段である。 重みよりも活性化に摂動を適用することにより、前方勾配のばらつきを著しく低減できることを示す。 提案手法はMNIST と CIFAR-10 のバックプロップと一致し,ImageNet 上で提案したバックプロップフリーアルゴリズムよりも大幅に優れていた。
  論文  参考訳（メタデータ） (2022-10-07T03:52:27Z)
• Isotuning With Applications To Scale-Free Online Learning [19.52475623314373]
  私たちは、高速で適応性があり、いつでも、スケールフリーなオンライン学習アルゴリズムを設計するために、文学のいくつかのツールを拡張し、組み合わせています。 最初の、そして主要なツールであるisotuningは、後悔のトレードオフをバランスさせる適応的な学習率を設計するというアイデアの一般化です。 第2のツールはオンラインの修正であり、多くのアルゴリズムで中心となる境界を得ることができ、後悔する境界が空白にならないようにする。 最後のツールはnullアップデートであり、アルゴリズムが過度に大規模な更新を行うのを防ぐ。
  論文  参考訳（メタデータ） (2021-12-29T14:58:56Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Inertial Proximal Deep Learning Alternating Minimization for Efficient Neutral Network Training [16.165369437324266]
  この研究は、有名な慣性手法であるiPDLAMによって改良されたDLAMを開発し、電流と最後の繰り返しの線形化によって点を予測する。 実世界のデータセットの数値計算結果を報告し,提案アルゴリズムの有効性を実証した。
  論文  参考訳（メタデータ） (2021-01-30T16:40:08Z)
• Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
  BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。 LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。 既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
  論文  参考訳（メタデータ） (2020-11-27T16:42:12Z)
• Improving the Backpropagation Algorithm with Consequentialism Weight Updates over Mini-Batches [0.40611352512781856]
  適応フィルタのスタックとして多層ニューラルネットワークを考えることが可能であることを示す。 我々は,BPで発生した行動の悪影響を予測し,その発生前にも予測し,よりよいアルゴリズムを導入する。 我々の実験は、ディープニューラルネットワークのトレーニングにおけるアルゴリズムの有用性を示す。
  論文  参考訳（メタデータ） (2020-03-11T08:45:36Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。