論文の概要: Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
- arxiv url: http://arxiv.org/abs/2607.21579v1
- Date: Thu, 23 Jul 2026 17:56:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-24 18:26:25.513539
- Title: Barzilai-Borwein Fails Superlinear Convergence on an Open Set of Quadratics for Every Dimension $n\geq 4$
- Title（参考訳）: Barzilai-Borwein はすべての次元 $n\geq 4$ に対する四面体の開集合上の超線型収束を損なう
- Abstract要約: Barzilai--Borwein (BB) 法は収束するが根上線上収束はできないことを示す。
この構成は、コンピュータ支援による非共振器の証明に基づく非自明なものである。
- 参考スコア（独自算出の注目度）: 12.018537165567055
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Barzilai--Borwein (BB) method has shown strong practical performance in continuous optimization, yet its convergence dynamics remains poorly understood. In particular, a central unresolved question is whether BB converges superlinearly for almost every strictly convex quadratic problem and initialization. We provide a negative answer to this question. Specifically, for every finite dimension $n\geq4$, we construct a nonempty open, hence positive-Lebesgue-measure, family of strictly convex quadratic problems and initial points for which the long Barzilai--Borwein method (BB1) converges but cannot converge root-superlinearly. More precisely, with the explicit constants $ρ_{\min}=10^{-6},ρ_{\max}=0.61$, every spectral component of the gradient is bounded above and below by the corresponding geometric sequence. Consequently, the gradient norm and the energy norm of the error satisfy two-sided geometric estimates with the same rates, while the objective gap satisfies the corresponding estimates with squared rates. In particular, all three quantities are bounded below by geometric sequences, ruling out superlinear convergence. The construction is highly nontrivial, based on a computer-assisted proof of a nonresonant, attracting seven-cycle of the projectivized BB dynamics in dimension four.
- Abstract（参考訳）: Barzilai--Borwein (BB) 法は連続最適化において高い実用的な性能を示したが、収束ダイナミクスはいまだに理解されていない。
特に、中心的未解決の問題は、BBがほぼすべての厳密な凸二次問題と初期化に対して超線型収束するかどうかである。
私たちはこの質問に対して否定的な答えを与える。
具体的には、すべての有限次元 $n\geq4$ に対して、非空開で、したがって正のリーベーグ測度、厳密な凸二次問題の族と、長いバルジライ=ボルワイン法 (BB1) が収束する初期点を構成する。
より正確には、明示定数 $ρ_{\min}=10^{-6},ρ_{\max}=0.61$ で、勾配の全てのスペクトル成分は対応する幾何列によって上下に有界である。
その結果、勾配ノルムと誤差のエネルギーノルムは同じ速度で2辺の幾何推定を満足し、目的ギャップは対応する推定を2乗率で満足する。
特に、3つの量はすべて幾何学的列によって下界され、超線型収束を除外する。
この構造は、コンピュータ支援による非共振子の証明に基づいて、次元4の射影BBダイナミクスの7サイクルを惹きつける非常に非自明なものである。
関連論文リスト
- Nonconvex Composite Functional Constraints via First-Order Augmented Lagrangian Methods under Local Regularity [10.643433352418915]
一次非バランス性非コンケーブ最小値再構成の条件境界を均一に拡張した。
双対正則化では、大域的局所論はバイアスとともに議論される。
KKT。
論文 参考訳（メタデータ） (2026-07-09T21:28:29Z) - Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
我々は高次元多角曲線の次元を減少させるためにランダムな射影を再考する。
我々は、既知の$O(varepsilon-2log(nm))$がランダム射影のターゲット次元に有界であることの簡単な証明を与える。
我々の証明はスパース・オブリビラスな部分空間埋め込みの概念に基づいている。
論文 参考訳（メタデータ） (2026-07-03T08:48:35Z) - Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
Scoreベースの生成モデルは高次元空間で訓練されていることを示す。
有限固有アンカーとガウス・ニュートンによる最も近い射影座標のReLU実装を用いる。
論文 参考訳（メタデータ） (2026-05-15T10:20:05Z) - Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence [0.764671395172401]
局所化幾何正則性に基づく線形収束のための軌道制限フレームワークを開発する。
古典的な収束保証は、これらの局所的な条件の下で拡張されることを示す。
我々の研究は、能動集合や多様体の同定後の高速局所収束のための幾何学的定量化を提供する。
論文 参考訳（メタデータ） (2026-04-18T17:02:06Z) - An Information-Minimal Geometry for Qubit-Efficient Optimization [0.0]
量子ビット効率の最適化を幾何学的問題として再検討する。
局所一貫性問題は、Sherali-Adams level-2 polytope $mathrmSA(2)$とちょうど一致する。
論文 参考訳（メタデータ） (2025-11-11T15:38:57Z) - Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias [55.72269695392027]
本稿では,線形系を解くためにエントロピックミラー降下を適用することに焦点を当てる。
収束解析の主な課題は、領域の非有界性に起因する。
制限的な仮定を課さずにこれを克服するために、Polyak型階段の変種を導入する。
論文 参考訳（メタデータ） (2025-05-05T12:33:18Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - Convergence of Adam Under Relaxed Assumptions [72.24779199744954]
我々は、アダムがより現実的な条件下で、$O(epsilon-4)$勾配複雑性で$epsilon$-定常点に収束することを示している。
また、Adamの分散還元版を$O(epsilon-3)$の加速勾配複雑性で提案する。
論文 参考訳（メタデータ） (2023-04-27T06:27:37Z) - SPIRAL: A superlinearly convergent incremental proximal algorithm for
nonconvex finite sum minimization [11.15617238382324]
SPIRAL は有限和問題に対する収束pRoximal algogomrithor である。
軽微な仮定の下では顕著な収束がある。
それは芸術の状況に競争力がある。
論文 参考訳（メタデータ） (2022-07-17T14:58:06Z) - Randomized Coordinate Subgradient Method for Nonsmooth Composite
Optimization [11.017632675093628]
非滑らかな問題に対処するコーディネート型劣階法は、リプシッツ型仮定の性質のセットのため、比較的過小評価されている。
論文 参考訳（メタデータ） (2022-06-30T02:17:11Z) - Last iterate convergence of SGD for Least-Squares in the Interpolation
regime [19.05750582096579]
基本最小二乗構成におけるノイズレスモデルについて検討する。
最適予測器が完全に入力に適合すると仮定し、$langletheta_*, phi(X) rangle = Y$, ここで$phi(X)$は無限次元の非線型特徴写像を表す。
論文 参考訳（メタデータ） (2021-02-05T14:02:20Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。