論文の概要: One-Shot Learning for k-SAT

• arxiv url: http://arxiv.org/abs/2502.07135v1
• Date: Mon, 10 Feb 2025 23:56:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-12 14:08:45.215073
• Title: One-Shot Learning for k-SAT
• Title（参考訳）: k-SATのためのワンショット学習
• Authors: Andreas Galanis, Leslie Ann Goldberg, Xusheng Zhang,
• Abstract要約: 我々は、$k$-SATのワンショット学習が、満足度しきい値を大きく下回っていることを示す。 学習アルゴリズムの解析を単純化し、$d$のより強いバウンダリを$beta$で取得する。
• 参考スコア（独自算出の注目度）: 2.6293381978389787
• License:
• Abstract: Consider a $k$-SAT formula $\Phi$ where every variable appears at most $d$ times, and let $\sigma$ be a satisfying assignment of $\Phi$ sampled proportionally to $e^{\beta m(\sigma)}$ where $m(\sigma)$ is the number of variables set to true and $\beta$ is a real parameter. Given $\Phi$ and $\sigma$, can we learn the value of $\beta$ efficiently? This problem falls into a recent line of works about single-sample ("one-shot") learning of Markov random fields. The $k$-SAT setting we consider here was recently studied by Galanis, Kandiros, and Kalavasis (SODA'24) where they showed that single-sample learning is possible when roughly $d\leq 2^{k/6.45}$ and impossible when $d\geq (k+1) 2^{k-1}$. Crucially, for their impossibility results they used the existence of unsatisfiable instances which, aside from the gap in $d$, left open the question of whether the feasibility threshold for one-shot learning is dictated by the satisfiability threshold of $k$-SAT formulas of bounded degree. Our main contribution is to answer this question negatively. We show that one-shot learning for $k$-SAT is infeasible well below the satisfiability threshold; in fact, we obtain impossibility results for degrees $d$ as low as $k^2$ when $\beta$ is sufficiently large, and bootstrap this to small values of $\beta$ when $d$ scales exponentially with $k$, via a probabilistic construction. On the positive side, we simplify the analysis of the learning algorithm and obtain significantly stronger bounds on $d$ in terms of $\beta$. In particular, for the uniform case $\beta\rightarrow 0$ that has been studied extensively in the sampling literature, our analysis shows that learning is possible under the condition $d\lesssim 2^{k/2}$. This is nearly optimal (up to constant factors) in the sense that it is known that sampling a uniformly-distributed satisfying assignment is NP-hard for $d\gtrsim 2^{k/2}$.
• Abstract（参考訳）: a $k$-SAT formula $\Phi$ ここで、すべての変数が最大$d$倍に出現し、$\Phi$を$e^{\beta m(\sigma)}$に比例して$e^{\beta m(\sigma)}$に充足する満足な代入とし、$\beta$を真に設定された変数の数、$\beta$を実パラメータとする。 $\Phi$と$\sigma$が与えられたら、$\beta$の値を効率的に学べますか? この問題は、マルコフ確率場のシングルサンプル(ワンショット)学習に関する最近の研究の行に端を発する。 ここで考える$k$-SAT設定は、Galanis, Kandiros, Kalavasis (SODA'24) によって最近研究され、約$d\leq 2^{k/6.45}$のとき単サンプル学習が可能であり、$d\geq (k+1) 2^{k-1}$のとき不可能であることを示した。 重要なことに、彼らは、$d$のギャップを除いて、一発学習の実現可能性しきい値が有界な$k$-SATの公式の満足度しきい値によって決定されるかどうかという疑問を解き放った、満足できないインスタンスの存在を利用した。 私たちの主な貢献は、この質問に答えることです。 実のところ、$\beta$が十分に大きい場合、$k^2$のような低い場合、$d$は$k$と指数関数的にスケールすると$\beta$の小さな値にブートストラップする。 正の面では、学習アルゴリズムの解析を単純化し、$$\beta$という観点で$d$の強いバウンダリを得る。 特に、サンプリング文献で広く研究されている一様の場合 $\beta\rightarrow 0$ に対して、我々は、学習は $d\lesssim 2^{k/2}$ という条件の下で可能であることを示した。 これは、均一に分散された満足な代入をサンプリングすることが、$d\gtrsim 2^{k/2}$に対してNPハードであることが知られているという意味で、ほぼ最適である(定数因子まで)。

関連論文リスト

• Phase Transitions in the Detection of Correlated Databases [12.010807505655238]
  本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。 この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
  論文  参考訳（メタデータ） (2023-02-07T10:39:44Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• 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)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• 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)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)
• 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)
• 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)
• Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
  未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か? この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
  論文  参考訳（メタデータ） (2019-04-26T21:42:44Z)

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

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