論文の概要: Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms

• arxiv url: http://arxiv.org/abs/2404.08073v2
• Date: Mon, 14 Jul 2025 00:46:09 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-15 18:48:20.968755
• Title: Spurious Stationarity and Hardness Results for Bregman Proximal-Type Algorithms
• Title（参考訳）: Bregman近位型アルゴリズムの純粋定常性と硬度結果
• Authors: He Chen, Jiajin Li, Anthony Man-Cho So,
• Abstract要約: 本稿では,Bregman proximal-type algorithm (BPs) が非定常点の類に近づきやすいことを示す。 根本原因は、ユークリッド測地とブレグマン測地との間の降下挙動の基本的なコントラストにある。
• 参考スコア（独自算出の注目度）: 28.89573559893313
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bregman proximal-type algorithms (BPs), such as mirror descent, have become popular tools in machine learning and data science for exploiting problem structures through non-Euclidean geometries. In this paper, we show that BPs can get trapped near a class of non-stationary points, which we term spurious stationary points. Such stagnation can persist for any finite number of iterations if the gradient of the Bregman kernel is not Lipschitz continuous, even in convex problems. The root cause lies in a fundamental contrast in descent behavior between Euclidean and Bregman geometries: While Euclidean gradient descent ensures sufficient decrease near any non-stationary point, BPs may exhibit arbitrarily slow decrease around spurious stationary points. As a result, commonly used Bregman-based stationarity measure, such as relative change in terms of Bregman divergence, can vanish near spurious stationary points. This may misleadingly suggest convergence, even when the iterates remain far from any true stationary point. Our analysis further reveals that spurious stationary points are not pathological, but rather occur generically in a broad class of nonconvex problems with polyhedral constraints. Taken together, our findings reveal a serious blind spot in Bregman-based optimization methods and calls for new theoretical tools and algorithmic safeguards to ensure reliable convergence.
• Abstract（参考訳）: ミラー降下のようなブレグマン近位型アルゴリズム(BP)は、非ユークリッド幾何学を通して問題構造を利用する機械学習やデータサイエンスにおいて人気がある。 本稿では, BPが定常点の類に近づき, 急激な定常点を言う。 そのような停滞は、ブレグマン核の勾配がリプシッツ連続でなくても、凸問題においても有限個の反復に対して持続することができる。 ユークリッド勾配降下は任意の非定常点付近で十分な減少を保証しているが、BPは急激な定常点周辺で任意に緩やかに減少する可能性がある。 結果として、ブレグマンの発散の相対的な変化のような一般的なブレグマンに基づく定常度測度は、急激な定常点の近くで消滅する。 これは、繰り返しが真の定常点から遠く離れている場合でも、誤って収束を示唆するかもしれない。 解析の結果、急激な定常点は病理学的なものではなく、多面体制約を伴う幅広い非凸問題に一般的に発生することが明らかとなった。 この結果から,Bregmanに基づく最適化手法における重大な盲点が明らかとなり,信頼性の高い収束を保証するため,新たな理論ツールとアルゴリズムセーフガードが求められた。

関連論文リスト

• The Performance Of The Unadjusted Langevin Algorithm Without Smoothness Assumptions [0.0]
  本稿では,Langevinをベースとしたアルゴリズムを提案する。 ULAのようなサンプリング器の性能は、必ずしも低規則性で任意に劣化しないことを示す。
  論文  参考訳（メタデータ） (2025-02-05T18:55:54Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  近点法はその数値的安定性と不完全なチューニングに対する頑健性からかなりの関心を集めている。 本稿では,近位点法(SPPM)の幅広いバリエーションの包括的解析について述べる。
  論文  参考訳（メタデータ） (2024-05-24T21:09:19Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Convergent Bregman Plug-and-Play Image Restoration for Poisson Inverse Problems [8.673558396669806]
  Plug-noise-and-Play (Play) 法は画像逆問題に対する効率的な反復アルゴリズムである。 2つ提案する。 Bregman Score gradient Denoise 逆問題に基づくアルゴリズム。
  論文  参考訳（メタデータ） (2023-06-06T07:36:47Z)
• Optimal and exact recovery on general non-uniform Hypergraph Stochastic Block Model [0.0]
  非一様ハイパーグラフ化ブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 文献ではじめて、この一様でないケース下での正確な回復のための鋭いしきい値が、小さな制約の下で確立された。 しきい値を超えると正確な回復を達成でき、正確な回復が不可能な場合には最小の確率で達成できる2つの効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2023-04-25T20:30:33Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。 演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
  論文  参考訳（メタデータ） (2022-01-21T02:46:57Z)
• A Stochastic Bregman Primal-Dual Splitting Algorithm for Composite Optimization [2.9112649816695204]
  実バナッハ空間上の凸凹サドル点問題の第一次原始双対解法について検討する。 我々のフレームワークは一般であり、アルゴリズムにおいてブレグマンの発散を誘導するエントロピーの強い凸性を必要としない。 数値的な応用としては、エントロピー的正則化ワッサーシュタイン・バリセンタ問題や、単純体上の正則化逆問題などが挙げられる。
  論文  参考訳（メタデータ） (2021-12-22T14:47:44Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses [43.01811529439942]
  本研究は、非ユークリッド損失関数のクラスの下で低位正準多進分解(cpd)を考える。 この研究は、様々な非ユークリッド損失関数の下で大規模なCPD分解のための統一アルゴリズムフレームワークを提供する。
  論文  参考訳（メタデータ） (2021-04-29T14:58:25Z)
• Stochastic optimization with momentum: convergence, fluctuations, and traps avoidance [0.0]
  本稿では,重球法,ネステロフ加速勾配法(S-NAG),広く使用されているアダム法など,勾配勾配勾配のいくつかの変種を統一する一般最適化手法について検討する。 この回避は、非自明な常微分方程式のノイズ離散化として研究される。
  論文  参考訳（メタデータ） (2020-12-07T19:14:49Z)
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias [17.199063087458907]
  臨界点が好ましい統計特性を持つ構造化された非学習問題は、統計機械学習において頻繁に発生する。 我々は,SGDアルゴリズムが実際に広く利用されていることを示す。
  論文  参考訳（メタデータ） (2020-06-14T13:58:44Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• Debiased Sinkhorn barycenters [110.79706180350507]
  最適輸送(OT)におけるエントロピー正則化(Entropy regularization)は、機械学習におけるWassersteinメトリクスやバリセンタに対する近年の関心の原動力となっている。 このバイアスがエントロピー正則化器を定義する基準測度とどのように密接に関連しているかを示す。 両世界の長所を保ち、エントロピーを滑らかにしないシンクホーン様の高速な反復をデバイアスド・ワッサースタインのバリセンタとして提案する。
  論文  参考訳（メタデータ） (2020-06-03T23:06:02Z)

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

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