論文の概要: Learning CNF formulas from uniform random solutions in the local lemma regime
- arxiv url: http://arxiv.org/abs/2511.02487v1
- Date: Tue, 04 Nov 2025 11:22:05 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-11-05 18:47:05.968256
- Title: Learning CNF formulas from uniform random solutions in the local lemma regime
- Title（参考訳）: 局所補題系における一様ランダム解からのCNF公式の学習
- Authors: Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang,
- Abstract要約: 我々は、その一様ランダム解から$n$-variables $k$-CNF式$Phi$を学習する問題を研究する。
O(log n)$サンプルから、(Lov'aszの局所補題型条件下で)有界節サイズを持つ$k$-CNFsを、(Scisfiability閾値付近で)$widetildeO(nexp(-sqrtk)$サンプルから、(Sqrtk)$サンプルから)ランダムな$k$-CNFsを正確に学習できることが示されています。
- 参考スコア（独自算出の注目度）: 1.4816117998909835
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning a $n$-variables $k$-CNF formula $\Phi$ from its i.i.d. uniform random solutions, which is equivalent to learning a Boolean Markov random field (MRF) with $k$-wise hard constraints. Revisiting Valiant's algorithm (Commun. ACM'84), we show that it can exactly learn (1) $k$-CNFs with bounded clause intersection size under Lov\'asz local lemma type conditions, from $O(\log n)$ samples; and (2) random $k$-CNFs near the satisfiability threshold, from $\widetilde{O}(n^{\exp(-\sqrt{k})})$ samples. These results significantly improve the previous $O(n^k)$ sample complexity. We further establish new information-theoretic lower bounds on sample complexity for both exact and approximate learning from i.i.d. uniform random solutions.
- Abstract（参考訳）: 我々は、その一様ランダム解から$n$-variables $k$-CNF式$\Phi$を学習する問題を研究する。
Valiant のアルゴリズム (Commun. ACM'84) を再検討した結果,(1)$k$-CNFs を Lov\'asz の局所補題型条件下で,$O(\log n)$ サンプルから,(2)$k$-CNFs を$\widetilde{O}(n^{\exp(-\sqrt{k})} サンプルから正確に学習できることが判明した。
これらの結果は以前の$O(n^k)$サンプルの複雑さを大幅に改善した。
さらに、一様ランダム解からの正確かつ近似的な学習のために、サンプル複雑性に関する情報理論の下限を新たに確立する。
関連論文リスト
- 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) - Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。
各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。
第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - 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) - 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) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。