論文の概要: Quality control in sublinear time: a case study via random graphs

• arxiv url: http://arxiv.org/abs/2508.16531v1
• Date: Fri, 22 Aug 2025 16:54:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-25 16:42:36.464153
• Title: Quality control in sublinear time: a case study via random graphs
• Title（参考訳）: 線形時間における品質制御--ランダムグラフによるケーススタディ
• Authors: Cassandra Marcussen, Ronitt Rubinfeld, Madhu Sudan,
• Abstract要約: これを「品質制御問題」と呼ぶアルゴリズム問題の新しいクラスを同定する。 これらの問題は(正、実数値の)「品質関数」$rho$と分布$D$によって指定され、高い確率で$D$から引き出されたサンプルは「高品質」である。 我々は,$G_n,p$に対する品質制御問題を$p-O(k)$クエリと時間でテストできることを示し,この設定では品質制御が極めて効率的であることを示す。
• 参考スコア（独自算出の注目度）: 17.340766930817335
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many algorithms are designed to work well on average over inputs. When running such an algorithm on an arbitrary input, we must ask: Can we trust the algorithm on this input? We identify a new class of algorithmic problems addressing this, which we call "Quality Control Problems." These problems are specified by a (positive, real-valued) "quality function" $\rho$ and a distribution $D$ such that, with high probability, a sample drawn from $D$ is "high quality," meaning its $\rho$-value is near $1$. The goal is to accept inputs $x \sim D$ and reject potentially adversarially generated inputs $x$ with $\rho(x)$ far from $1$. The objective of quality control is thus weaker than either component problem: testing for "$\rho(x) \approx 1$" or testing if $x \sim D$, and offers the possibility of more efficient algorithms. In this work, we consider the sublinear version of the quality control problem, where $D \in \Delta(\{0,1\}^N)$ and the goal is to solve the $(D ,\rho)$-quality problem with $o(N)$ queries and time. As a case study, we consider random graphs, i.e., $D = G_{n,p}$ (and $N = \binom{n}2$), and the $k$-clique count function $\rho_k := C_k(G)/\mathbb{E}_{G' \sim G_{n,p}}[C_k(G')]$, where $C_k(G)$ is the number of $k$-cliques in $G$. Testing if $G \sim G_{n,p}$ with one sample, let alone with sublinear query access to the sample, is of course impossible. Testing if $\rho_k(G)\approx 1$ requires $p^{-\Omega(k^2)}$ samples. In contrast, we show that the quality control problem for $G_{n,p}$ (with $n \geq p^{-ck}$ for some constant $c$) with respect to $\rho_k$ can be tested with $p^{-O(k)}$ queries and time, showing quality control is provably superpolynomially more efficient in this setting. More generally, for a motif $H$ of maximum degree $\Delta(H)$, the respective quality control problem can be solved with $p^{-O(\Delta(H))}$ queries and running time.
• Abstract（参考訳）: 多くのアルゴリズムは、平均的な入力よりもうまく動作するように設計されている。 このようなアルゴリズムを任意の入力で実行する場合、私たちは次のような質問をしなければならない。 この問題に対処するアルゴリズムの新たなクラスを特定し,これを「品質制御問題」と呼ぶ。 これらの問題は(正、実数値の)「品質関数」$\rho$と分布$D$によって指定され、高い確率で、D$から引き出されたサンプルは「高品質」であり、$\rho$-値が1ドル近くである。 目標は、$x \sim D$の入力を受け取り、$x$と$\rho(x)$の可能性のある入力を、$$$から遠く離れた形で拒否することである。 したがって、品質管理の目標は、"$\rho(x) \approx 1$"のテストや、$x \sim D$のテストなど、いずれのコンポーネント問題よりも弱い。 本研究では,$D \in \Delta(\{0,1\}^N)$と$o(N)$クエリと時間による$(D ,\rho)$品質問題の解決を目標とする品質制御問題のサブ線形バージョンを検討する。 例えば、$D = G_{n,p}$ (and $N = \binom{n}2$) と $k$-clique count function $\rho_k := C_k(G)/\mathbb{E}_{G' \sim G_{n,p}}[C_k(G')]$ を考える。 1つのサンプルで$G \sim G_{n,p}$をテストすれば、サンプルへのサブ線形クエリアクセスは、もちろん不可能である。 もし$\rho_k(G)\approx 1$なら、$p^{-\Omega(k^2)}$サンプルが必要である。 対照的に、$G_{n,p}$(ある定数$c$に対して$n \geq p^{-ck}$)に対する品質制御問題は、$\rho_k$に対して$p^{-O(k)}$クエリと時間でテスト可能である。 より一般的には、最大次数$\Delta(H)$のモチーフ$H$に対して、各品質制御問題は$p^{-O(\Delta(H))}$クエリと実行時間で解決できる。

関連論文リスト

• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
  ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。 我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。 平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
  論文  参考訳（メタデータ） (2023-04-17T10:38:08Z)
• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。 この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
  論文  参考訳（メタデータ） (2023-02-07T10:39:44Z)
• Coresets for Data Discretization and Sine Wave Fitting [39.18104905459739]
  N]:=1,cdots,N$の整数列は、センサから受信される。 目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。 経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
  論文  参考訳（メタデータ） (2022-03-06T17:07:56Z)
• Optimal SQ Lower Bounds for Learning Halfspaces with Massart Noise [9.378684220920562]
  マスアートノイズの存在下でハーフスペースを学習するための、最も厳密な統計クエリ(SQ)の下界。 任意の $eta in [0,1/2]$ に対して、$eta$ よりも誤り分類誤差の少ない全ての SQ アルゴリズムは、スーパーポリノミカルな精度のクエリを必要とすることを示す。
  論文  参考訳（メタデータ） (2022-01-24T17:33:19Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
  我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。 加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
  論文  参考訳（メタデータ） (2020-07-16T04:23:57Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

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

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