論文の概要: 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))$で計算するランタイムを改善する。 理論的には,予備計算実験における実行時の規模削減の順序を示す。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Differential Private Stochastic Optimization with Heavy-tailed Data: Towards Optimal Rates [15.27596975662702]
  重み付き勾配を用いたDP最適化の最適速度を達成するアルゴリズムについて検討する。 その結果,DP下での凸最適化の理論的限界が達成可能であることを示す。
  論文  参考訳（メタデータ） (2024-08-19T11:07:05Z)
• Uncertainty quantification for iterative algorithms in linear models with application to early stopping [4.150180443030652]
  本稿では,高次元線形回帰問題における反復アルゴリズムから得られた繰り返し$hbb1,dots,hbbT$について検討する。 解析および提案した推定器は、GD(Gradient Descent)、GD(GD)およびFast Iterative Soft-Thresholding(FISTA)などの加速変種に適用できる。
  論文  参考訳（メタデータ） (2024-04-27T10:20:41Z)
• 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)
• 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)
• Planning and Learning with Adaptive Lookahead [74.39132848733847]
  ポリシーイテレーション(PI)アルゴリズムは、欲求の一段階の改善と政策評価を交互に行う。 近年の文献では、複数段階のルックアヘッドポリシーの改善が、イテレーション毎の複雑さの増加を犠牲にして、よりコンバージェンス率の向上につながることが示されている。 本研究では,多段階の地平線を状態と推定値の関数として動的に適応する手法を初めて提案する。
  論文  参考訳（メタデータ） (2022-01-28T20:26:55Z)
• 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)

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

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