論文の概要: Non-KKT Accumulation in Entropic Mirror Descent
- arxiv url: http://arxiv.org/abs/2608.01658v1
- Date: Mon, 03 Aug 2026 03:47:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.316971
- Title: Non-KKT Accumulation in Entropic Mirror Descent
- Title（参考訳）: エントロピックミラーにおける非KKT蓄積
- Abstract要約: ルジャンドル核が生成するミラー降下に対して、すべての累積点は適切なステップサイズの下でカルーシュ-クーン-タッカー定常でなければならないか?
私たちはその答えがノーであることを示す。
我々は、シャノン-エントロピックミラー降下によって生成される目的と有界列を、非負のorthant$R_+n$に対して、すべての$ngeq 3$に対して、確率単純度$_n$で、各$ngeq 4$に対して、それぞれの場合において、累積点の集合は、比較的空でない円を含む滑らかな境界円であるように構成する。
- 参考スコア（独自算出の注目度）: 6.110024414173389
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: For mirror descent generated by a Legendre kernel, perhaps one of the most basic question in optimization is this: must every accumulation point of a bounded mirror descent sequence be Karush--Kuhn--Tucker (KKT) stationary under proper stepsizes? We show that the answer is no. A longstanding obstacle to resolving this question is the boundary blow-up of the Legendre gradient: it keeps every mirror step in the interior, while at a boundary limit, the inverse entropy metric vanishes on active coordinates and can erase the dual-feasibility in the KKT system. We construct $C^\infty$ objectives and bounded sequences generated by the Shannon-entropic mirror descent on the nonnegative orthant $\R_+^n$, for every $n\geq 3$, and on the probability simplex $Δ_n$, for every $n\geq 4$, such that, in each case, the set of accumulation points is a smooth boundary circle containing a nonempty relatively open arc of non-KKT points. The steps satisfy $α_k\asymp k^{-β}$ with $β\in(1/2,1)$, the objective values are nonincreasing, and the objectives are entropy-relatively smooth. Hence the pathology stems from the degeneracy of the Bregman geometry at the boundary, rather than from failure of descent, or improper stepsizes. To the best of our knowledge, these provide the first counterexamples to KKT accumulation for bounded mirror descent sequences with nonincreasing objective values.
- Abstract（参考訳）: ルジャンドル核が生成するミラー降下については、おそらく最適化において最も基本的な問題の一つがこれである: 有界ミラー降下列のすべての蓄積点は、適切なステップサイズの下でカルーシュ-クーン-タッカー(KKT)定常でなければならないか?
私たちはその答えがノーであることを示す。
この問題を解くための長年の障害は、ルジャンドル勾配の境界の爆破である:すべてのミラーステップを内部に保持するが、境界極限では、逆エントロピー計量は活性座標上で消滅し、KKT系の二重実現可能性を削除することができる。
C^\infty$ の目的と、非負のorthant $\R_+^n$ 上のシャノン-エントロピックミラー降下によって生成される有界列を、すべての$n\geq 3$ に対して確率単純度 $Δ_n$ に対して構成し、それぞれの場合において、累積点の集合は非KKT点の空でない比較的オープンな弧を含む滑らかな境界円である。
ステップは$α_k\asymp k^{-β}$と$β\in(1/2,1)$を満たす。
したがって、病理学は、降下の失敗や不適切なステップ化ではなく、境界におけるブレグマン幾何学の退化に由来する。
我々の知る限り、これらは増加しない目的値を持つ有界ミラー降下系列に対するKKT蓄積に対する最初の逆例を提供する。
関連論文リスト
- The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives [26.189892200366895]
本研究では、非拘束な滑らかな凸対象に対する標準降下勾配(SGD)の原繰り返しの時間一様収束について検討する。
標準的な雑音仮定の下では、時間一様収束速度が$sqrtlog n / n$に任意に近づくが、それに到達することはないことを証明している。
論文 参考訳（メタデータ） (2026-09-08T10:24:19Z) - Establishing Boundary KKT Convergence of Mirror Descent through Reparameterization [6.110024414173389]
Karush--Kuhn-Tucker (KKT) 点への収束は、ルジャンドル核を持つ非ミラー降下に対して、長い間不明なままである。
最近の研究は、KKT(Karush--Kuhn-Tucker)点でミラー降下が非励起点を蓄積できることを示している。
論文 参考訳（メタデータ） (2026-08-07T14:06:54Z) - Entropy-Smooth Convex Optimization Cannot Be Accelerated [0.0]
負のエントロピーに対する凸函数のクラスにおける最小化の収束率に対して、$(L/T)$低い境界を証明します。
このことは、ミラー降下がこのクラスの対数係数に最適であることを示している。
論文 参考訳（メタデータ） (2026-07-29T21:34:12Z) - Optimal Dimension-Free Sampling for Regularized Classification [56.72526267755301]
我々は、リプシッツ連続分類損失関数の幅広いクラスに対して、$(1pmvarepsilon)$-relativeエラーを達成する最適サンプリング境界を証明した。
これにはロジスティックやシグモイドの損失、ヒンジの損失、ReLUの損失といった重要な機能が含まれており、顕著で一般的な例である。
論文 参考訳（メタデータ） (2026-05-22T15:05:33Z) - Complexity Bounds for Smooth Convex Multiobjective Optimization [0.0]
目的値$m$の滑らかな多目的最適化において,$varepsilon$-Pareto定常点を求める際のオラクルの複雑さについて検討する。
強い凸目的に対して、任意の一階法は、$exp(-Theta(T/sqrtkappa)$ after $T$ oracle call よりも早く線形収束を示す。
適応スカラー化を伴う凸問題や一般スパン法に対して、最終イテレートの勾配ノルムに1/T2$の普遍的下界を確立する。
論文 参考訳（メタデータ） (2025-09-16T21:33:11Z) - Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Global convergence of gradient descent for phase retrieval [3.7873341907492923]
位相探索におけるベニグアランドスケープのテンソルに基づく基準を提案し,勾配軌道の有界性を確立する。
これは、勾配降下がほとんどすべての初期点に対して大域最小値に収束することを意味する。
論文 参考訳（メタデータ） (2024-10-13T20:12:34Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Convergence of Gradient Descent with Small Initialization for
Unregularized Matrix Completion [21.846732043706318]
バニラ勾配降下は、明示的な正則化を必要とせず、必ず基底真理$rmXstar$に収束することを示す。
驚くべきことに、収束率も最終的な精度もオーバーパラメータ化された検索ランク$r'$に依存しておらず、それらは真のランク$r$によってのみ支配される。
論文 参考訳（メタデータ） (2024-02-09T19:39:23Z) - ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。
我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-01-01T18:51:29Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - A Simple Convergence Proof of Adam and Adagrad [74.24716715922759]
我々はAdam Adagradと$O(d(N)/st)$アルゴリズムの収束の証明を示す。
Adamはデフォルトパラメータで使用する場合と同じ収束$O(d(N)/st)$で収束する。
論文 参考訳（メタデータ） (2020-03-05T01:56:17Z) - Randomized Bregman Coordinate Descent Methods for Non-Lipschitz
Optimization [31.474280642125734]
そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。
提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
論文 参考訳（メタデータ） (2020-01-15T09:57:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。