論文の概要: Information Limits of Low-Rank Approximation Certification

• arxiv url: http://arxiv.org/abs/2610.03321v1
• Date: Fri, 02 Oct 2026 13:56:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-06 00:14:30.407073
• Title: Information Limits of Low-Rank Approximation Certification
• Title（参考訳）: 低域近似認証の情報限界
• Abstract要約: 低ランク近似は、その誤差が所定の許容値を満たすことを確認するために追加の行列ベクトル積を必要とする。 相対行列誤差と平均二乗出力誤差の双方に対して,この認証コストを特徴付ける。 単一の近似行列候補に対して、許容される故障確率がなくなると、精度の高い次元一様ミニマックスクエリ定数を決定する。
• 参考スコア（独自算出の注目度）: 9.536496868754533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Low-rank approximation can require additional matrix--vector products to verify that its error meets a prescribed tolerance. We characterize this certification cost for both relative matrix error and mean-square output error. For a single approximation matrix candidate, we determine the exact dimension-uniform minimax query constant as the allowed failure probability vanishes. Our main result concerns reusing validation responses as the approximation space expands. For a candidate family constructed independently of validation, one batch supports an entire nested path without increasing the query budget with the number of checks. Across \(W\) paths, a concentration bound exploiting shared residual energy yields a \(\sqrt{\log(W+1)}\) dependence. A matching lower bound establishes its optimality for fixed interior error targets and sufficiently small separation gaps. Finally, we compare two uniformly valid certificates on the same dispersed-spectrum family. Optimizing the validation budget within each rule family yields costs of orders \(N^{1/3}\) and \(N^{2/3}\) for validation and construction beyond the true target. Code is available at https://anonymous.4open.science/r/Low-rank-approximation-1275/
• Abstract（参考訳）: 低ランク近似は、その誤差が所定の許容値を満たすことを確認するために追加の行列ベクトル積を必要とする。 相対行列誤差と平均二乗出力誤差の双方に対して,この認証コストを特徴付ける。 単一の近似行列候補に対して、許容される故障確率がなくなると、精度の高い次元一様ミニマックスクエリ定数を決定する。 本研究の主な成果は,近似空間の拡大に伴う検証応答の再利用である。 検証から独立して構築された候補ファミリーでは、チェック数でクエリ予算を増やすことなく、ネストされたパス全体をサポートする。 共有残エネルギーを悪用する濃度は、(W\) の経路全体で \(\sqrt{\log(W+1)}\) に依存する。 一致した下界は、固定された内部誤差ターゲットと十分に小さな分離ギャップに対する最適性を確立する。 最後に、同じ分散スペクトルファミリー上の2つの均一に有効な証明書を比較した。 各ルールファミリ内の検証予算を最適化すると、真の目標を超える検証と構築のための注文(N^{1/3}\)と注文(N^{2/3}\)のコストが生じる。 コードはhttps://anonymous.4open.science/r/Low-rank-approximation-1275/で公開されている。

関連論文リスト

• Stability-Constrained Approximation in Spline KANs: Exact Layer Balancing and Budget-Compatible Saturation [51.56484100374058]
  我々は、ハードレイヤーワイドリプシッツ予算の下で近似を研究する。 構成条件下では、対応するレイヤエラーをキャンセルする必要はないことを示す。 クラスのすべての作用素に対して、安定した深さ-$L$タワーが存在し、累積誤差の定数分を実現できる。
  論文  参考訳（メタデータ） (2026-09-14T20:17:04Z)
• The geometry of AI validation: Exact certification limits for iid best-of-N search [0.0]
  信頼性面上での検証とデプロイメントのルールをカーネルとして表現する。 B_m,N=1+2sum_r=1m(-1)rcos2Nr/[(m+1)]$
  論文  参考訳（メタデータ） (2026-08-21T15:18:11Z)
• AI-Assisted Discovery of Convex Relaxations via Dual Agents [56.60366723277675]
  すべての許容関数に対して下界が成り立ち、より強い境界を与える凸緩和から従うことを示す。 理論は各エージェントを検証し、反例を検索し、報告されたすべての境界はインターバルにおける明示的な二重実現可能な点によって認証される。
  論文  参考訳（メタデータ） (2026-06-30T06:10:25Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Multi-LLM Query Optimization [1.7435005683276596]
  我々は、ステートワイドなエラー制約を受ける総クエリコストを最小限に抑える、堅牢でオフラインなクエリ計画問題を定式化する。 本研究は,サロゲート保存コストと真の最適コストとの比が,誤差耐性が小さくなるにつれて1つに収束することを示す。
  論文  参考訳（メタデータ） (2026-03-24T19:51:57Z)
• Overconfident Errors Need Stronger Correction: Asymmetric Confidence Penalties for Reinforcement Learning [17.384089089363382]
  既存の手法が見落としている根本原因を同定する。 現在のアプローチでは、グループ内のすべての誤ったロールアウトを同一に扱う。 非対称信頼度を考慮した誤り罰(ACE)を提案する。
  論文  参考訳（メタデータ） (2026-02-24T22:46:43Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• The Structure of Cross-Validation Error: Stability, Covariance, and Minimax Limits [3.3008315224941978]
  アルゴリズム分布対の性質が$k$-foldクロスバリデーションにおける折りたたみ数の選択にどのように影響するかを示す。 また、CVが$n$の検証セットによって1/n$達成可能なオーダーの最適値を得ることができないことも証明する。
  論文  参考訳（メタデータ） (2025-11-05T15:35:46Z)
• Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
  カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。 我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。 MRP のサブクラスに対する minimax の下位境界を証明する。
  論文  参考訳（メタデータ） (2021-09-24T14:48:20Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  そこで本研究では,対数様比統計量と正規化フローに基づく新しい分布アライメント手法を提案する。 入力領域の局所構造を保存する領域アライメントにおいて,結果の最小化を実験的に検証する。
  論文  参考訳（メタデータ） (2020-03-26T22:10:04Z)
• New Bounds For Distributed Mean Estimation and Variance Reduction [25.815612182815702]
  本稿では,ローカルな$d$-dimensional vector $x_v を mathbbRd$ で与えられた$n$マシンが分散平均推定(DME)問題を考える。 提案手法は, 従来の手法と比較して, 応用の実践的改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-02-21T13:27:13Z)

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

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