論文の概要: Reusing Combinatorial Structure: Faster Iterative Projections over
Submodular Base Polytopes
- arxiv url: http://arxiv.org/abs/2106.11943v1
- Date: Tue, 22 Jun 2021 17:29:24 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-23 14:41:28.145653
- Title: Reusing Combinatorial Structure: Faster Iterative Projections over
Submodular Base Polytopes
- Title(参考訳): reusing combinatorial structure:submodular base polytopes上の高速な反復射影
- Authors: Jai Moondra, Hassan Mortagy, Swati Gupta
- Abstract要約: 離散的視点と連続的な視点の両方を用いて投影の計算を高速化するツールキットを開発した。
基数に基づく部分モジュラーポリトープの特別の場合、あるブレグマン射影の計算ランタイムを$Omega(n/log(n))$の係数で改善する。
- 参考スコア(独自算出の注目度): 7.734726150561089
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Optimization algorithms such as projected Newton's method, FISTA, mirror
descent and its variants enjoy near-optimal regret bounds and convergence
rates, but suffer from a computational bottleneck of computing "projections''
in potentially each iteration (e.g., $O(T^{1/2})$ regret of online mirror
descent). On the other hand, conditional gradient variants solve a linear
optimization in each iteration, but result in suboptimal rates (e.g.,
$O(T^{3/4})$ regret of online Frank-Wolfe). Motivated by this trade-off in
runtime v/s convergence rates, we consider iterative projections of close-by
points over widely-prevalent submodular base polytopes $B(f)$. We develop a
toolkit to speed up the computation of projections using both discrete and
continuous perspectives. We subsequently adapt the away-step Frank-Wolfe
algorithm to use this information and enable early termination. For the special
case of cardinality based submodular polytopes, we improve the runtime of
computing certain Bregman projections by a factor of $\Omega(n/\log(n))$. Our
theoretical results show orders of magnitude reduction in runtime in
preliminary computational experiments.
- Abstract(参考訳): projected newton's method, fista, mirror descent, and its variantsのような最適化アルゴリズムは、ほぼ最適の後悔の限界と収束率を享受するが、各イテレーションにおける「プロジェクション」計算の計算ボトルネック(例えば、$o(t^{1/2})$ regret of online mirror descent)に悩まされている。
一方、条件付き勾配変種は各イテレーションで線形最適化を解くが、結果として準最適レートとなる(例えば、$o(t^{3/4})$ regret of online frank-wolfe)。
実行時v/s収束率のこのトレードオフに動機づけられ、広く普及しているサブモジュラーベースポリトープに対して、近接点の反復射影を考える。
我々は離散的視点と連続的視点の両方を用いて投影の計算を高速化するツールキットを開発した。
後述のFrank-Wolfeアルゴリズムを用いて,この情報を用いて早期終了を可能にする。
基数性に基づく部分モジュラーポリトープの特別な場合、特定のブレグマン射影を$\omega(n/\log(n))$で計算するランタイムを改善する。
理論的には,予備計算実験における実行時の規模削減の順序を示す。
関連論文リスト
- Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳(メタデータ) (2023-12-19T01:52:13Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Online Dynamic Submodular Optimization [0.0]
オンラインバイナリ最適化のための証明可能な性能を持つ新しいアルゴリズムを提案する。
高速な需要応答とリアルタイム分散ネットワーク再構成という2つのパワーシステムアプリケーションでアルゴリズムを数値的にテストする。
論文 参考訳(メタデータ) (2023-06-19T10:37:15Z) - 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 Adaptive Regret with Membership Oracles [31.422532403048738]
ほとんどの反復アルゴリズムは凸集合への射影の計算を必要とし、計算コストがかかる。
GK22による最近の研究は、フランク・ウルフのアプローチに基づく射影自由アルゴリズムによる準線形適応的後悔の保証を与えた。
我々はMhammedi22にインスパイアされた異なる手法に基づくプロジェクションフリーなアルゴリズムを提案し、プロジェクションをセットメンバーシップ計算で置き換える。
論文 参考訳(メタデータ) (2022-11-22T23:53:06Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。
本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
論文 参考訳(メタデータ) (2022-07-18T12:03:26Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Planning and Learning with Adaptive Lookahead [74.39132848733847]
ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。
近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。
本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
論文 参考訳(メタデータ) (2022-01-28T20:26:55Z) - SHINE: SHaring the INverse Estimate from the forward pass for bi-level
optimization and implicit models [15.541264326378366]
近年,深層ニューラルネットワークの深度を高める手法として暗黙の深度学習が登場している。
トレーニングは双レベル問題として実行され、その計算複雑性は巨大なヤコビ行列の反復反転によって部分的に駆動される。
本稿では,この計算ボトルネックに対処する新たな手法を提案する。
論文 参考訳(メタデータ) (2021-06-01T15:07:34Z) - Global Optimization of Gaussian processes [52.77024349608834]
少数のデータポイントで学習したガウス過程を訓練した空間定式化を提案する。
このアプローチはまた、より小さく、計算的にもより安価なサブソルバを低いバウンディングに導く。
提案手法の順序の順序による時間収束を,総じて低減する。
論文 参考訳(メタデータ) (2020-05-21T20:59:11Z) - Boosting Frank-Wolfe by Chasing Gradients [26.042029798821375]
本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。
我々は、一連の計算実験において、反復時間とCPU時間の両方において、その競争上の優位性を実証する。
論文 参考訳(メタデータ) (2020-03-13T16:29:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。