論文の概要: Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling

• arxiv url: http://arxiv.org/abs/2606.23867v1
• Date: Mon, 22 Jun 2026 19:09:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:16:48.639724
• Title: Exact Schur-Sylvester Dimensionality Reductions for Non-Smooth Stochastic Complexity and Manifold Sampling
• Title（参考訳）: 非滑らかな確率複雑性とマニフォールドサンプリングのための厳密なシュル・シルヴェスター次元化
• Authors: Trenton Lau, Gary P. T. Choi,
• Abstract要約: 本稿では、シュア補数ブロックとシルヴェスターの同一性を利用してボトルネックを回避した、正確に数学的に等価な定式化を提案する。 高次元データセットのベンチマークでは,2倍精度の数値等価性を保ちながら,14,100Times$を超える一定のスピードアップを確認した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The exact computation of the Normalized Maximum Likelihood (NML) codelength for regular non-smooth estimators (e.g., Lasso) has been historically limited by the cubic scaling walls of manifold-constrained projection and volume integration. At each step of the geometric Propose-and-Project Metropolis--Hastings (PPMH) sampler, evaluating the projection operator requires inverting an $(N+k) \times (N+k)$ generalized KKT matrix, while calculating the volume factor requires the determinant of an $(N-k) \times (N-k)$ Gram matrix. This paper presents an exact, mathematically equivalent formulation that bypasses both bottlenecks by utilizing the block Schur complement and Sylvester's determinant identity. We prove that the computational complexity of both operations collapses from $\mathcal{O}(N^3)$ to $\mathcal{O}(k^3 + N^2 k)$ per step. We generalize this reduction to Sparse Support Vector Machines (SVMs), Elastic Net, and Group Lasso. Finally, we provide a rigorous numerical stability analysis and evaluate the sampler's efficiency using the Effective Sample Size (ESS) per second. Our empirical benchmarks on high-dimensional datasets confirm a constant speedup exceeding $14{,}100\times$ while maintaining double-precision numerical equivalence, rendering exact non-smooth NML estimation highly tractable for large-scale statistical inference.
• Abstract（参考訳）: 正規化最大同値 (NML) 符号長の正規化非滑らかな推定器 (eg , Lasso) の正確な計算は、多様体に制約された射影と体積積分の立方体スケーリング壁によって歴史的に制限されてきた。 幾何学的プロポーション・アンド・プロジェクト・メトロポリス・ハスティングス(PPMH)サンプリング器の各ステップにおいて、射影作用素を評価するには、$(N+k) \times (N+k)$ generalized KKT matrix を反転させる必要があるが、体積係数を計算するには$(N-k) \times (N-k)$ Gram matrix の行列式が必要となる。 本稿では,シュア補数ブロックとシルヴェスターの行列式を利用して,両方のボトルネックを回避した,数学的に等価な正確な定式化を提案する。 両演算の計算複雑性は、ステップ毎に$\mathcal{O}(N^3)$から$\mathcal{O}(k^3 + N^2 k)$に崩壊することを示す。 この削減をSVM(Sparse Support Vector Machines)、Elastic Net、Group Lassoに一般化する。 最後に、厳密な数値安定性解析を行い、1秒あたりの有効サンプルサイズ(ESS)を用いてサンプルの効率を評価する。 高次元データセットに対する実験的なベンチマークでは,2倍精度の数値等価性を保ちながら,14{,}100\times$を超える一定のスピードアップを確認した。

関連論文リスト

• Efficient Mean Curvature Computation on High-Dimensional Data Manifolds [52.452902154360565]
  高次元データセットの各点における局所的な平均曲率の推定は、機械学習アルゴリズムの重要な要素である。 本稿では,このコストを桁違いに削減する2つの補完的貢献を紹介する。 実世界のデータセットの実験では、オリジナルの実装と比較して50倍から300倍のスピードアップが確認されている。
  論文  参考訳（メタデータ） (2026-06-04T16:04:31Z)
• The Normalized Maximum Likelihood for Regular Non-Smooth Models: Measure-Theoretic Foundations and Geometric Sampling [0.0]
  非平滑モデルに対する正規化最大公約(NML)符号長を計算するための厳密なフレームワークを提供する。 古典的幾何測度理論を適用して、保守的ヤコビアンとコアレの公式をブリッジすることによって、非滑らかなモデルの複雑さがよく表されることを示す。 本研究は,非平滑モデルに対するNML符号長の理論解析の道を開くものである。
  論文  参考訳（メタデータ） (2026-05-23T08:57:48Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Cubic regularized subspace Newton for non-convex optimization [3.481985817302898]
  我々は、ランダムな部分空間に定常正規化を適用すると解釈できる座標二階SSCNを解析する。 従来の一階法と比較して,大幅な高速化を示した。
  論文  参考訳（メタデータ） (2024-06-24T14:20:02Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。 我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
  論文  参考訳（メタデータ） (2024-03-08T18:50:19Z)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  非定常多重ブロック双レベル最適化問題には$mgg 1$低レベル問題があり、機械学習において重要な応用がある。 a)標準BO問題の最先端の複雑さを1ブロックに合わせること,(b)サンプルブロックごとのサンプルをサンプリングして並列高速化すること,(c)高次元ヘッセン行列推定器の逆計算を避けること,の3つの特性を実現することを目的とする。
  論文  参考訳（メタデータ） (2023-05-30T04:10:11Z)
• Optimal Randomized Approximations for Matrix based Renyi's Entropy [16.651155375441796]
  整数次数$alpha$の場合のランダム近似と非整数$alpha$の場合の直列近似を開発する。 大規模シミュレーションと実世界の応用は、開発した近似の有効性を検証する。
  論文  参考訳（メタデータ） (2022-05-16T02:24:52Z)

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

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