論文の概要: Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization

• arxiv url: http://arxiv.org/abs/2605.25255v1
• Date: Sun, 24 May 2026 21:04:26 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-26 19:50:19.046787
• Title: Boosted Stochastic Frank-Wolfe for Constrained Nonconvex Optimization
• Title（参考訳）: 制約付き非凸最適化のためのブースト確率フランクウルフ
• Authors: Navil Nandhan, Abbas Khademi, Antonio Silveti-Falls,
• Abstract要約: 我々は、強化されたフランク・ウルフアルゴリズムの新たなステップ定数を開発する。 このステップサイズ戦略の強化は多くの現代的な推定器と組み合わせることができることを実証する。
• 参考スコア（独自算出の注目度）: 0.4499833362998487
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The boosted Frank-Wolfe algorithm accelerates the classical Frank-Wolfe algorithm by better aligning the update direction with the negative gradient. Its analysis, however, has been limited to deterministic convex problems, with step sizes that require either line search or knowledge of the Lipschitz constant of the gradient. We develop a novel step size strategy that does not depend on the Lipschitz constant of the gradient, which allows us to extend the boosted Frank-Wolfe algorithm to the stochastic setting. We prove that boosting with this step size strategy can be combined with many modern gradient estimators, including SAGA, L-SVRG, SAG, Heavy Ball momentum, and zeroth-order estimators, among others, while retaining the worst-case convergence rates of ordinary stochastic Frank-Wolfe. Our analysis also yields the first convergence rates for boosted Frank-Wolfe on nonconvex and quasar-convex objectives, results which are new even for deterministic problems. Experiments on sparse logistic regression and quantum process tomography show that stochastic boosted Frank-Wolfe achieves faster convergence per gradient oracle call (and on wall-clock) compared to the non-boosted baseline.
• Abstract（参考訳）: 強化されたFrank-Wolfeアルゴリズムは、更新方向と負の勾配をより良く整合させることで、古典的なFrank-Wolfeアルゴリズムを加速する。 しかし、その解析は決定論的凸問題に限られており、勾配の直線探索やリプシッツ定数の知識を必要とするステップサイズがある。 我々は勾配のリプシッツ定数に依存しない新しいステップサイズ戦略を開発し、強化されたフランク=ウルフアルゴリズムを確率的設定に拡張することができる。 本研究では,SAGA, L-SVRG, SAG, ヘビーボール運動量, ゼロ次推定器など, 一般的な確率論的フランク=ウルフの最悪の収束率を維持しつつ, 最新の勾配推定器と組み合わせることができることを示す。 我々の分析は、非凸および準凸の目的に対するフランク=ウルフ強化に対する最初の収束率をもたらし、これは決定論的問題においても新しい結果である。 スパースロジスティック回帰法と量子プロセストモグラフィーの実験により、確率的に増強されたフランク=ウルフは、非ボオスト基底線に比べて勾配オラクル呼び出し(および壁面時計)あたりの収束が速くなることを示した。

関連論文リスト

• Beyond Short Steps in Frank-Wolfe Algorithms [25.808224336342683]
  本稿では,関数のスムーズさを従来のショートステップを超えて活用することで,フランク・ウルフアルゴリズムを強化する新しい手法を提案する。 楽観的なフレームワークを用いた新しいフランク・ウルフアルゴリズムを提案し、原始双対収束証明を提供する。
  論文  参考訳（メタデータ） (2025-01-30T21:52:45Z)
• Gradient-Variation Online Learning under Generalized Smoothness [56.38427425920781]
  勾配変分オンライン学習は、オンライン関数の勾配の変化とともにスケールする後悔の保証を達成することを目的としている。 ニューラルネットワーク最適化における最近の取り組みは、一般化された滑らかさ条件を示唆し、滑らかさは勾配ノルムと相関する。 ゲームにおける高速収束と拡張逆最適化への応用について述べる。
  論文  参考訳（メタデータ） (2024-08-17T02:22:08Z)
• Rethinking SIGN Training: Provable Nonconvex Acceleration without First- and Second-Order Gradient Lipschitz [66.22095739795068]
  符号ベースの手法は、パラメータ更新にのみ符号情報を使用するにもかかわらず、堅牢な性能を達成する能力によって注目されている。 符号に基づく手法の現在の収束解析は、一階加速度と二階加速度の強い仮定に依存する。 本稿では,より現実的な第1次および第2次加速度の仮定の下で,それらの収束を解析する。
  論文  参考訳（メタデータ） (2023-10-23T06:48:43Z)
• Sarah Frank-Wolfe: Methods for Constrained Optimization with Best Rates and Practical Features [65.64276393443346]
  Frank-Wolfe (FW) 法は、構造化制約による最適化問題の解法として一般的な手法である。 有限サム勾配の最小化のためのアルゴリズムの2つの新しい変種を示す。
  論文  参考訳（メタデータ） (2023-04-23T20:05:09Z)
• Reducing Discretization Error in the Frank-Wolfe Method [2.806911268410107]
  Frank-Wolfeアルゴリズムは、構造的に制約された機械学習アプリケーションで一般的な方法である。 この手法の1つの大きな制限は、不安定なジグザグングステップの方向のために加速が難しい収束速度の遅いことである。 最適化された高次離散化スキームを直接適用するマルチステップFrank-Wolfe法と、離散化誤差を低減したLMO-averagingスキームの2つの改善を提案する。
  論文  参考訳（メタデータ） (2023-04-04T00:43:05Z)
• A Multistep Frank-Wolfe Method [2.806911268410107]
  フランク=ウルフ法におけるジグザグ現象を離散化の成果物として検討した。 多重ステップのフランク・ウルフ変種は、トラニケート誤差が$O(Deltap)$として崩壊し、$p$はメソッドの順序である。
  論文  参考訳（メタデータ） (2022-10-14T21:12:01Z)
• Boosting Frank-Wolfe by Chasing Gradients [26.042029798821375]
  本稿では,降下方向をサブルーチンによる負勾配に整合させることにより,Frank-Wolfeアルゴリズムの高速化を提案する。 我々は、一連の計算実験において、反復時間とCPU時間の両方において、その競争上の優位性を実証する。
  論文  参考訳（メタデータ） (2020-03-13T16:29:02Z)
• Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets [71.05306664267832]
  適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。 本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。 実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
  論文  参考訳（メタデータ） (2019-12-26T22:10:10Z)

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

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