論文の概要: The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications

• arxiv url: http://arxiv.org/abs/2502.02002v1
• Date: Tue, 04 Feb 2025 04:30:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 15:01:56.702711
• Title: The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications
• Title（参考訳）: Ball-proximal (="Broximal") Point Method: a new algorithm, Convergence Theory, and Applications
• Authors: Kaja Gruntkowska, Hanmin Li, Aadi Rane, Peter Richtárik,
• Abstract要約: 非滑らかな制約と非グローバルな最適化は、様々なアプリケーションに重大な課題をもたらす。 我々は,BallProximal Point, Broximal Method (BPM) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel) (Rock Wafel)を提案する。
• 参考スコア（独自算出の注目度）: 44.99833362998488
• License:
• Abstract: Non-smooth and non-convex global optimization poses significant challenges across various applications, where standard gradient-based methods often struggle. We propose the Ball-Proximal Point Method, Broximal Point Method, or Ball Point Method (BPM) for short - a novel algorithmic framework inspired by the classical Proximal Point Method (PPM) (Rockafellar, 1976), which, as we show, sheds new light on several foundational optimization paradigms and phenomena, including non-convex and non-smooth optimization, acceleration, smoothing, adaptive stepsize selection, and trust-region methods. At the core of BPM lies the ball-proximal ("broximal") operator, which arises from the classical proximal operator by replacing the quadratic distance penalty by a ball constraint. Surprisingly, and in sharp contrast with the sublinear rate of PPM in the nonsmooth convex regime, we prove that BPM converges linearly and in a finite number of steps in the same regime. Furthermore, by introducing the concept of ball-convexity, we prove that BPM retains the same global convergence guarantees under weaker assumptions, making it a powerful tool for a broader class of potentially non-convex optimization problems. Just like PPM plays the role of a conceptual method inspiring the development of practically efficient algorithms and algorithmic elements, e.g., gradient descent, adaptive step sizes, acceleration (Ahn & Sra, 2020), and "W" in AdamW (Zhuang et al., 2022), we believe that BPM should be understood in the same manner: as a blueprint and inspiration for further development.
• Abstract（参考訳）: 非滑らかで非凸なグローバル最適化は、標準勾配法がしばしば苦労する様々なアプリケーションに重大な課題をもたらす。 本稿では,従来のPPM (Rockafellar, 1976) にインスパイアされた新しいアルゴリズムフレームワークであるBall-Proximal Point Method, Broximal Point Method, Ball Point Method (BPM) を提案する。 BPMの中核にボール近位作用素があり、これは古典的近位作用素からボール制約によって二次距離ペナルティを置き換えることによって生じる。 意外なことに、非滑らか凸系におけるPPMのサブ線形速度とは対照的に、BPMが線形に収束し、同じ状態において有限ステップで収束することが証明される。 さらに、ボール凸の概念を導入することで、BPMが弱い仮定の下で同じグローバル収束を保証することを証明し、潜在的に非凸最適化問題のより広範なクラスのための強力なツールとなる。 例えば、勾配降下、適応ステップサイズ、加速(Ahn & Sra, 2020)、AdamWの"W"(Zhuang et al , 2022)のように、PPMが実用的なアルゴリズムとアルゴリズム要素の開発を促す概念的手法の役割を担っているように、BPMは、さらなる開発のための青写真とインスピレーションとして、同じ方法で理解されるべきであると考えています。

関連論文リスト

• Towards Extremely Fast Bilevel Optimization with Self-governed Convergence Guarantees [42.514612465664605]
  既存の明示的かつ暗黙的なグラディエントベースのBLOを均一に理解するための単一レベル定式化を提案する。 我々の収束結果の顕著な特徴は、元の非加速GBLOバージョンと比較して、高速なBAGDCは定常性に対する非漸近収束理論を統一的に認めることである。
  論文  参考訳（メタデータ） (2022-05-20T09:46:10Z)
• Block Alternating Bregman Majorization Minimization with Extrapolation [16.04690575393738]
  ブロック相対滑らか関数と適切な分離関数の和を目的とする非滑らかな非最適化問題のクラスを考える。 外部補間(BMME)を用いたBregmanMajorization-Minimizationフレームワークを交互に提案する。 より強い条件下でのペナル化非負行列に対するBMMEの有効性を実証した。
  論文  参考訳（メタデータ） (2021-07-09T12:47:00Z)
• Bregman Gradient Policy Optimization [97.73041344738117]
  本稿では,Bregmanの発散と運動量に基づく強化学習のためのBregmanグラデーションポリシーの最適化を設計する。 VR-BGPOは、各イテレーションで1つの軌道のみを必要とする$epsilon$stationaryポイントを見つけるために、$tilde(epsilon-3)$で最高の複雑性に達する。
  論文  参考訳（メタデータ） (2021-06-23T01:08:54Z)
• Acceleration Methods [57.202881673406324]
  まず2次最適化問題を用いて加速法を2つ導入する。 我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。 我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
  論文  参考訳（メタデータ） (2021-01-23T17:58:25Z)
• SMG: A Shuffling Gradient-Based Method with Momentum [25.389545522794172]
  機械学習の最適化に広く使われている2つの先進的なアイデアを組み合わせる。 我々はシャッフルに基づく新しいモーメント技術を開発した。 私たちのテストでは、新しいアルゴリズムの性能が向上しました。
  論文  参考訳（メタデータ） (2020-11-24T04:12:35Z)
• Fast Gravitational Approach for Rigid Point Set Registration with Ordinary Differential Equations [79.71184760864507]
  本稿では,FGA(Fast Gravitational Approach)と呼ばれる厳密な点集合アライメントのための物理に基づく新しい手法を紹介する。 FGAでは、ソースとターゲットの点集合は、シミュレーションされた重力場内を移動しながら、世界規模で多重リンクされた方法で相互作用する質量を持つ剛体粒子群として解釈される。 従来のアライメント手法では,新しいメソッドクラスには特徴がないことを示す。
  論文  参考訳（メタデータ） (2020-09-28T15:05:39Z)
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints [10.578409461429626]
  本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。 我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。 一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
  論文  参考訳（メタデータ） (2020-09-23T20:02:00Z)
• Momentum-Based Policy Gradient Methods [133.53164856723782]
  モデルフリー強化学習のための効率的なモーメントに基づくポリシー勾配手法のクラスを提案する。 特に,IS-MBPG法の適応的でないバージョンを提示するが,これは大きなバッチを伴わずに$O(epsilon-3)$と最もよく知られたサンプルの複雑さに達する。
  論文  参考訳（メタデータ） (2020-07-13T20:44:15Z)
• IDEAL: Inexact DEcentralized Accelerated Augmented Lagrangian Method [64.15649345392822]
  本稿では,局所関数が滑らかで凸な分散最適化環境下での原始的手法設計のためのフレームワークを提案する。 提案手法は,加速ラグランジアン法により誘導されるサブプロブレム列を概ね解いたものである。 加速度勾配降下と組み合わせることで,収束速度が最適で,最近導出された下界と一致した新しい原始アルゴリズムが得られる。
  論文  参考訳（メタデータ） (2020-06-11T18:49:06Z)

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

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