論文の概要: Projection-free Online Learning with Arbitrary Delays
- arxiv url: http://arxiv.org/abs/2204.04964v2
- Date: Sat, 20 May 2023 08:14:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-24 06:25:37.163715
- Title: Projection-free Online Learning with Arbitrary Delays
- Title(参考訳): 任意遅延によるプロジェクションフリーオンライン学習
- Authors: Yuanyu Wan and Yibo Wang and Chang Yao and Wei-Wei Tu and Lijun Zhang
- Abstract要約: 我々は、オンラインFrank-Wolfe (OFW)アルゴリズムとオンラインスムーズプロジェクションフリー (OSPF) アルゴリズムを遅延設定に一般化する。
新たな解析により,OW と OSPF は非遅延環境ではOW と OSPF と同じ後悔を味わうことが明らかとなった。
- 参考スコア(独自算出の注目度): 38.13351554274417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Projection-free online learning, which eschews the projection operation via
less expensive computations such as linear optimization (LO), has received much
interest recently due to its efficiency in handling high-dimensional problems
with complex constraints. However, previous studies assume that any queried
gradient is revealed immediately, which may not hold in practice and limits
their applications. To address this limitation, we generalize the online
Frank-Wolfe (OFW) algorithm and the online smooth projection-free (OSPF)
algorithm, which are state-of-the-art LO-based projection-free online
algorithms for non-smooth and smooth functions respectively, into a delayed
setting where queried gradients can be delayed by arbitrary rounds.
Specifically, the main idea of our generalized OFW is to perform an update
similar to the original OFW after receiving any delayed gradient, and play the
latest decision for each round. Moreover, the essential change on OSPF is to
replace the sum of queried gradients, which is originally utilized in each
update, with the sum of available gradients. Despite their simplicities, our
novel analysis shows that under a relatively large amount of delay, the
generalized OFW and OSPF enjoy the same regret bound as OFW and OSPF in the
non-delayed setting, respectively.
- Abstract(参考訳): 線形最適化 (LO) のようなより安価な計算によって投影操作を誘発するプロジェクションフリーオンライン学習は, 複雑な制約を伴って高次元問題を扱うことの効率性から, 最近注目されている。
しかし、以前の研究では、クエリされた勾配は直ちに明らかにされるが、実際には保持されず、適用範囲が制限される可能性がある。
この制限に対処するために、オンラインのFrank-Wolfe (OFW) アルゴリズムとオンラインのスムーズなプロジェクションフリー (OSPF) アルゴリズムを一般化する。
具体的には,遅延勾配を受けた後,元のofwと同じような更新を行い,ラウンド毎に最新の決定を行うという,一般的なofwの主な考え方です。
さらに、OSPFの基本的な変更は、クエリされた勾配の総和を、本来は各更新で使用されるもので、利用可能な勾配の総和に置き換えることである。
その単純化にもかかわらず, 比較的大きな遅延下では, 一般化されたofw と ospf はofw と ospf が非遅延設定でそれぞれofw と ospf に拘束されるのと同じ後悔を味わうことを示した。
関連論文リスト
- 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) - Convergence under Lipschitz smoothness of ease-controlled Random
Reshuffling gradient Algorithms [0.0]
非常に多くの滑らかで非単調な勾配関数の平均を最小化することを検討する。
我々は、IG/RR反復をウォッチドッグルールと、収束を保証するために散発的にのみ活性化するラインサーチの導関数を用いて制御する、モノトーンまたはノンモノトーンの2つの弱いスキームを定義する。
論文 参考訳(メタデータ) (2022-12-04T15:26:36Z) - Scaling Forward Gradient With Local Losses [117.22685584919756]
フォワード学習は、ディープニューラルネットワークを学ぶためのバックプロップに代わる生物学的に妥当な代替手段である。
重みよりも活性化に摂動を適用することにより、前方勾配のばらつきを著しく低減できることを示す。
提案手法はMNIST と CIFAR-10 のバックプロップと一致し,ImageNet 上で提案したバックプロップフリーアルゴリズムよりも大幅に優れていた。
論文 参考訳(メタデータ) (2022-10-07T03:52:27Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳(メタデータ) (2021-10-24T22:43:15Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。