Fugu-MT 論文翻訳(概要): Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

論文の概要: Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

arxiv url: http://arxiv.org/abs/2609.15268v1
Date: Mon, 14 Sep 2026 09:27:00 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-16 07:15:06.207502
Title: Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm
Title（参考訳）: 一様ランダム解からCNF式を学習する:ヴァリアントのアルゴリズムにおける近距離サンプル複素性
Abstract要約: 我々は、$n$-variable CNF式を学ぶために、Valiantのアルゴリズム (Commun. ACM'84) を再検討する。 Valiantのアルゴリズムは、対数係数まで最適なサンプル複雑性を持つことを示す。
参考スコア（独自算出の注目度）: 1.5229705287183657
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We revisit Valiant's algorithm (Commun. ACM'84) for learning $n$-variable CNF formulas with clause size $k$ and variable degree $d$ from i.i.d. uniform random solutions in the local lemma regime. For fixed $t\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieves total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)$ sample complexity. For $t>1$, we prove a matching lower bound for Valiant's algorithm. At $t=1$ (covering $0<t<1$), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound $\widetildeΩ(n/\varepsilon)$.
Abstract（参考訳）: バリアントのアルゴリズム (Commun. ACM'84) を、局所補題系における一様ランダム解から、節サイズ$k$および変数次数$d$を持つ$n$-variable CNF式を学ぶために再検討する。 for fixed $t\geq1$, under $k\gtrsim(1+1/t)\log d$, Valiant's algorithm achieve a total variation error $\varepsilon$ with $\widetilde{O}(n^{\lceil t \rceil}/\varepsilon)$ sample complexity。 for $t>1$, we prove a matching lower bound for Valiant's algorithm。 t=1$ (covering $0<t<1$) において、ヴァリアントのアルゴリズムは情報理論的下界$\widetildeΩ(n/\varepsilon)$によって対数的因子まで最適なサンプル複雑性を持つことを示した。

関連論文リスト

Oracle Complexity of Stochastic Fixed-Point Equations with Nonexpansive Maps [28.438129186461598]
コンパクト凸集合の一般ノルム $|cdot|$ と自己写像 $T$ に対して、小さな固定点残差 $|T(x)-x| leq $ を持つ点を計算するオラクル複雑性について検討する。弱ラデマッハ型$q > 1$の任意のノルムに対して、高い確率でそのような問題を解くアルゴリズムを提供する。
論文参考訳（メタデータ） (2026-09-08T23:09:39Z)
A Simple Algorithm for Best Separable State [5.5559749120901385]
本研究では,無絡状態上での量子測定の最大受容確率を求める最適分離状態問題 (BSS) について検討する。古典的な意味での目標は、$langle(x otimes y), M (x otimes y)rangle$ over unit vectors $x,y$ where $0 preceq M preceq I$である。
論文参考訳（メタデータ） (2026-08-10T19:04:15Z)
Learning CNF formulas from uniform random solutions in the local lemma regime [1.4816117998909835]
我々は、その一様ランダム解から$n$-variables $k$-CNF式$Phi$を学習する問題を研究する。 O(log n)$サンプルから、(Lov'aszの局所補題型条件下で)有界節サイズを持つ$k$-CNFsを、(Scisfiability閾値付近で)$widetildeO(nexp(-sqrtk)$サンプルから、(Sqrtk)$サンプルから)ランダムな$k$-CNFsを正確に学習できることが示されています。
論文参考訳（メタデータ） (2025-11-04T11:22:05Z)
Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
ランク1テンソルを$otimes_i=1N mathbbRd$で完了する際のサンプルと計算複雑性を再考する。本稿では,一対のランダム線形系上で,ガウス・ヨルダンに相当するアルゴリズムを許容する問題のキャラクタリゼーションを提案する。
論文参考訳（メタデータ） (2024-08-10T04:26:19Z)
Algorithms for Sparse LPN and LSPN Against Low-noise [1.2143710013809321]
ランダムノイズ(LPN)問題を伴う古典的学習環境のスパース変種を考察する。我々の主な貢献は、LSPN(Learning Sparse Parities)問題とスパースCSP(SparseCSP)問題の両方に対して、低雑音に対する学習アルゴリズムを提供する新しいフレームワークである。
論文参考訳（メタデータ） (2024-07-27T08:57:04Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文参考訳（メタデータ） (2023-07-13T18:59:28Z)
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。目標は、低ランク因子の積として$mathbfA$を近似することである。我々の手法はBMF問題の他の一般的な変種に一般化する。
論文参考訳（メタデータ） (2023-06-02T18:55:27Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time [14.990725929840892]
ここでは、$T(N, d)$は、その変換によって$d倍のN$行列を乗算するのに要する時間である。我々のランタイムは、外乱のない共分散推定において最も高速なアルゴリズムと一致し、最大で多対数因子となる。
論文参考訳（メタデータ） (2020-06-23T20:21:27Z)
Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文参考訳（メタデータ） (2020-06-06T13:34:41Z)

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