論文の概要: Minimax optimal submatrix detection: Sharp non-asymptotic rates

• arxiv url: http://arxiv.org/abs/2605.09569v2
• Date: Tue, 19 May 2026 00:41:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-21 01:01:02.763533
• Title: Minimax optimal submatrix detection: Sharp non-asymptotic rates
• Title（参考訳）: 最小限の最適部分行列検出:シャープ非漸近速度
• Abstract要約: 平均行列 $mathbf X$ における植木部分行列を検出する問題を考える。 2つの仮説が高い確率で識別可能であることを保証するために、$がどれほど大きいかを示すミニマックス最適化を確立する。 我々の漸近的でない上境界と下限は、これらのパラメータの任意の構成に一致する。
• 参考スコア（独自算出の注目度）: 1.7188280334580195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given an observation $\mathbf Y \in \mathbb{R}^{d_1\times d_2}$ from the model $\mathbf Y = \mathbf X + \mathbf E$ where $\mathbf X$ is constant and $\mathbf E$ has i.i.d. $N(0,1)$ entries, we consider the problem of detecting a planted submatrix in the mean matrix $\mathbf X$. Specifically, we aim to distinguish the null hypothesis $\mathbf X = 0$ from the alternative hypothesis in which $\mathbf X$ is non-zero only on a submatrix of size $s_1 \times s_2$ with elevated entries bounded below by $μ>0$. We establish a minimax lower bound characterizing how large $μ$ must be to ensure that the two hypotheses are distinguishable with high probability. Furthermore, we derive novel minimax-optimal tests achieving the lower bound, and describe extensions of these tests that are adaptive to unknown sparsity levels $s_1$ and $s_2$. In contrast with previous work, which required restrictive assumptions on $s_1,s_2, d_1$ and $d_2$, our non-asymptotic upper and lower bounds match for any configuration of these parameters.
• Abstract（参考訳）: モデル $\mathbf Y = \mathbf X + \mathbf E$ where $\mathbf X$ is constant and $\mathbf E$ has i.d.$N(0,1)$ entry から、平均行列 $\mathbf X$ における植込み部分行列を検出する問題を考える。 具体的には、 null 仮説 $\mathbf X = 0$ を $\mathbf X$ が 0 でないという別の仮説と区別することを目的としている。 2つの仮説が高い確率で識別可能であることを保証するために、μ$がどれほど大きいかを示すミニマックスの下界を確立する。 さらに, 未知の空間レベルである$s_1$および$s_2$に適応する, 下位境界を達成するための新しいミニマックス最適テストの導出と, これらのテストの拡張について述べる。 以前の研究では、s_1,s_2,d_1$,dd_2$の制限的な仮定が必要であったが、我々の非漸近的上界と下界はこれらのパラメータの構成に一致する。

関連論文リスト

• Simple-regret rates and minimax optimality of fixed-prior expected improvement in Matérn and squared-exponential RKHSs [0.0]
  非空コンパクト集合 $mathcal X の部分集合 Rd$ 上で、決定論的目的関数 $f$ を最小化するための期待された改善 (EI) ポリシーについて検討する。
  論文  参考訳（メタデータ） (2026-07-31T10:18:54Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• On the Capacity Region of Individual Key Rates in Vector Linear Secure Aggregation [55.126702858312456]
  すべてのユーザがキーを保持する必要はないことを示し、それによって文学における最もよく知られた到達可能な領域を厳密に拡大する。 以上の結果から,各ユーザがキーを保持する必要はないという新たな事実が明らかになった。
  論文  参考訳（メタデータ） (2026-01-06T18:34:07Z)
• Optimal community detection in dense bipartite graphs [0.0]
  我々は、n_1×n$の高次元二部グラフにおいて、密連結頂点のコミュニティを検出する問題を考える。 我々は,最小信号強度$delta*$の非漸近的上界および下界を,必要かつ十分であり,かつ,最小のタイプ1とタイプ2の誤差でテストが存在することを保証する。 提案試験は, 隣接行列の非線形統計値と, 独立性のある解析値を組み合わせたものである。
  論文  参考訳（メタデータ） (2025-05-23T20:58:55Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。 本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。 最悪の場合、$m$に対する指数的依存は避けられないことを示す。
  論文  参考訳（メタデータ） (2024-02-06T15:39:09Z)
• Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
  我々は不連続線形回帰の問題を考察する。 正則ノルムにおいて$mathbfw*$を$tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$の誤差まで推定し、一致する下界を証明できる。
  論文  参考訳（メタデータ） (2023-06-25T16:32:00Z)
• Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
  本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。 目標は、低ランク因子の積として$mathbfA$を近似することである。 我々の手法はBMF問題の他の一般的な変種に一般化する。
  論文  参考訳（メタデータ） (2023-06-02T18:55:27Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。 ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。 以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
  論文  参考訳（メタデータ） (2022-11-15T23:53:39Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Nonasymptotic one-and two-sample tests in high dimension with unknown covariance structure [0.0]
  テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。 本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
  論文  参考訳（メタデータ） (2021-09-01T06:22:53Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  非パラメトリック回帰に対するグラフに基づくアプローチであるラプラシア平滑化の統計的性質について検討する。 ラプラシアン滑らか化が多様体適応であることを証明する。
  論文  参考訳（メタデータ） (2021-06-03T01:20:41Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  ガウス境界の下では、半空間とReLUを不可知的に学習する基本的な問題について検討する。 我々の下限は、これらのタスクの現在の上限が本質的に最良のものであるという強い証拠を与える。
  論文  参考訳（メタデータ） (2020-06-29T17:10:10Z)

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

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