論文の概要: Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
- arxiv url: http://arxiv.org/abs/2610.15241v1
- Date: Sun, 11 Oct 2026 00:22:58 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-20 02:00:08.226886
- Title: Explicit Bounds on Hoffman Constants for Sparse Polyhedral Regularizers
- Title（参考訳）: スパース多面体正規化器におけるホフマン定数の明示的境界
- Abstract要約: スパース正規化で生じる構造化多面体系のクラスに対するホフマン定数の明示的境界を導出する。
これらの定数はスペクトル,幾何,相互作用成分の分解を許容し,それらのスケーリング挙動を決定する。
我々の理論的結果は、ホフマン定数が構造化回帰設定において明示的で解釈可能な形式を認めることを示している。
- 参考スコア（独自算出の注目度）: 0.764671395172401
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Hoffman constants quantify the distance to the solution set of a polyhedral system in terms of its residual; they control error bounds, geometric conditioning, the convergence rate of first-order iterative algorithms, and the stability of regression estimators to target perturbations. Despite their importance, explicit values of Hoffman constants are rarely available due to their computational complexity. In this paper, we derive explicit bounds on the Hoffman constant for a class of structured polyhedral systems arising in sparse regularization. We show that the constants admit a decomposition into spectral, geometric, and interaction components, which together determine their scaling behavior. This framework explains the gap between worst-case dimension-dependent bounds and the favorable conditioning observed empirically in structured problems. As a primary application, we analyze $\ell_1$-regularized least squares, demonstrating that the effective constants depend on low-dimensional active subspaces rather than the ambient dimension. We then extend to the elastic net and adaptive $\ell_1$-regularized formulations, demonstrating how the underlying optimization geometry is altered by the $\ell_2$ penalty and reweighting scheme. Furthermore, we relate our results to classical statistical assumptions and show that the restricted eigenvalue condition bounds only the primal curvature of the active set, leaving the dual interaction geometry unconstrained and is thus insufficient alone for fast theoretical convergence rates. We further show standard $\ell_\infty$ coherence conditions do not yield dimension-independent Euclidean bounds to close this gap. Our theoretical results show that Hoffman constants admit explicit, interpretable forms in structured regression settings and, in practice, provide actionable tools for post-hoc feature pruning and a priori optimal hyperparameter selection.
- Abstract（参考訳）: ホフマン定数はその残差の観点から多面体系の解集合への距離を定量化し、誤差境界、幾何学的条件付け、一階反復アルゴリズムの収束率、摂動を目標とする回帰推定器の安定性を制御する。
その重要性にも拘わらず、ホフマン定数の明示的な値は計算複雑性のためにほとんど利用できない。
本稿では,スパース正規化に伴う構造化多面体系のクラスに対するホフマン定数の明示的境界を導出する。
これらの定数はスペクトル,幾何,相互作用成分の分解を許容し,それらのスケーリング挙動を決定する。
この枠組みは、最悪のケースの次元依存境界と、構造化された問題において経験的に観察された好ましい条件付けとのギャップを説明する。
第一の応用として、$\ell_1$-regularized least squares を解析し、実効定数が周囲次元よりも低次元の活性部分空間に依存することを示した。
次に、弾性ネットに拡張して、$\ell_1$-regularized formulations を適応させ、基礎となる最適化幾何が $\ell_2$ ペナルティと再重み付けスキームによってどのように変化するかを示す。
さらに、我々の結果は古典的な統計的仮定と関係し、制限された固有値条件が活性集合の原始曲率のみに制限され、双対相互作用の幾何学は制約されず、高速な理論収束速度には不十分であることを示す。
さらに、標準的な$\ell_\infty$コヒーレンス条件は、このギャップを閉じるために次元に依存しないユークリッド境界を生じさせないことを示す。
理論的には, ホフマン定数は構造的回帰設定において明示的かつ解釈可能な形式を認めており, 実際には, ポストホックな特徴プレーニングのための実行可能なツールと, 最優先の最適ハイパーパラメータ選択を提供する。
関連論文リスト
- Geometry-Aware Multi-Objective Optimization: Norm-Constrained Oracles with Entropic Weight Updates [38.97446792838266]
多重勾配降下は典型的にはユークリッド幾何学で定式化されるが、行列対応のオラクルは他のノルムによって誘導される方向を使用する。
基準制約付き線形最小化とタスク重みのエントロピー更新を組み合わせた単一ループ多目的法を解析する。
実験では、この手法を既存のマルチタスクと比較し、ジオメトリ、重み付け、運動量選択を検討した。
論文 参考訳（メタデータ） (2026-10-09T15:55:53Z) - Phasor Attention: Mean Root Square Normalization for Phase Manifold Preservation [3.0459410574367314]
平均根角正規化(MRSNorm)について紹介する。
MRSNormは数学的に従来のスケーリングパラダイムを反転させる。
我々は、この制約がピタゴラスのアイデンティティによって支配される組込み三角勾配クリッパーをもたらすことを解析的に実証した。
論文 参考訳（メタデータ） (2026-07-20T11:10:51Z) - Residual-Based Time Discretization on Nonlinear Approximation Manifolds: Analysis and Gaussian Applications [0.0]
ヒルベルト空間における進化方程式の時間離散パラメトリック近似を残留最小化に基づいて検討する。
離散化と進化方程式のパラメトリゼーション、パラメータ力学を規定するディラック-フランケル変分原理の離散化である。
論文 参考訳（メタデータ） (2026-07-16T14:57:44Z) - Optimization Geometrodynamics: Variational Reduction and Interaction Curvature [0.0]
我々は、この隠れ行列式プッシュフォワードの変分理論として、測地力学を発展させる。
アフィン事前還元の場合、誘導的相互作用曲率(英語版)は負半有限作用素 $-G*H-1G$ である。
閉全測地線ファイバーを持つ大域的解析バンドルと、特異な解析的近接制御器部とを証明した。
論文 参考訳（メタデータ） (2026-07-07T18:42:00Z) - Generalized nonparametric regression in reproducing kernel Hilbert spaces: Consistency and rates of convergence [0.0]
我々は再生空間におけるM-levの包括的理論を開発する。
ソボ空間に対しては、混合滑らか性関数を持つ滑らか性空間に接続する新たなレートを得る。
論文 参考訳（メタデータ） (2026-06-22T08:12:31Z) - Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
プッシュベースの分散通信は、情報交換が非対称である可能性のある通信ネットワークの最適化を可能にする。
我々は、グラディエント・プッシュ(SGP)アルゴリズムのための統一的な一様安定性フレームワークを開発する。
重要な技術的要素は、2つの量に束縛された不均衡認識の一般化である。
論文 参考訳（メタデータ） (2026-02-24T05:32:03Z) - Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
乱摂動の分布は, 摂動段差がゼロになる傾向にあるため, 推定子の分散を最小限に抑える。
以上の結果から, 一定の長さを維持するのではなく, 真の勾配に方向を合わせることが可能であることが示唆された。
論文 参考訳（メタデータ） (2025-10-22T19:06:39Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
本稿では,テクスト幾何学的強単調ゲームに対する新たな収束結果を確立する。
我々のキーとなる結果は、RGDがテクスト幾何学的手法で最終定位線形収束を実現することを示しています。
全体として、ユークリッド設定を超えるゲームに対して、幾何学的に非依存な最終点収束解析を初めて提示する。
論文 参考訳（メタデータ） (2023-06-29T01:20:44Z) - Kernel-based off-policy estimation without overlap: Instance optimality
beyond semiparametric efficiency [53.90687548731265]
本研究では,観測データに基づいて線形関数を推定するための最適手順について検討する。
任意の凸および対称函数クラス $mathcalF$ に対して、平均二乗誤差で有界な非漸近局所ミニマックスを導出する。
論文 参考訳（メタデータ） (2023-01-16T02:57:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。