論文の概要: Learning algorithms versus automatability of Frege systems
- arxiv url: http://arxiv.org/abs/2111.10626v1
- Date: Sat, 20 Nov 2021 16:42:55 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-23 17:29:13.011335
- Title: Learning algorithms versus automatability of Frege systems
- Title（参考訳）: フレーゲシステムの学習アルゴリズムと自動化性
- Authors: J\'an Pich, Rahul Santhanam
- Abstract要約: 我々は,命題証明システムにおける証明探索を自動化する学習アルゴリズムとアルゴリズムを結合する。
十分に強く、よく理解された命題証明システム$P$に対して、以下の文が等価であることを証明する。
- 参考スコア（独自算出の注目度）: 0.30458514384586394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We connect learning algorithms and algorithms automating proof search in
propositional proof systems: for every sufficiently strong, well-behaved
propositional proof system $P$, we prove that the following statements are
equivalent,
1. Provable learning: $P$ proves efficiently that p-size circuits are
learnable by subexponential-size circuits over the uniform distribution with
membership queries.
2. Provable automatability: $P$ proves efficiently that $P$ is automatable by
non-uniform circuits on propositional formulas expressing p-size circuit lower
bounds.
Here, $P$ is sufficiently strong and well-behaved if I.-III. holds: I. $P$
p-simulates Je\v{r}\'abek's system $WF$ (which strengthens the Extended Frege
system $EF$ by a surjective weak pigeonhole principle); II. $P$ satisfies some
basic properties of standard proof systems which p-simulate $WF$; III. $P$
proves efficiently for some Boolean function $h$ that $h$ is hard on average
for circuits of subexponential size. For example, if III. holds for $P=WF$,
then Items 1 and 2 are equivalent for $P=WF$.
If there is a function $h\in NE\cap coNE$ which is hard on average for
circuits of size $2^{n/4}$, for each sufficiently big $n$, then there is an
explicit propositional proof system $P$ satisfying properties I.-III., i.e. the
equivalence of Items 1 and 2 holds for $P$.
- Abstract（参考訳）: 命題証明システムにおける証明探索を自動化する学習アルゴリズムとアルゴリズムを接続する: 十分に強力で十分に整備された命題証明システム $p$ に対して、次の文が等価であることを証明する 1. 証明可能な学習: $p$ は、メンバーシップクエリを伴う一様分布上のサブ指数回路によってpサイズ回路が学習できることを効率的に証明する。
2. 確率的自動化性:$P$は、pサイズの回路の下位境界を表す命題式上の一様でない回路によって自動化可能であることを効率よく証明する。
ここでは、$P$は十分強力で、ぼくなら十分だ。
-III。
hold: i. $p$ p-simulates je\v{r}\'abek's system $wf$ (これは拡大フレージ系$ef$ を単射的な弱ピローホール原理で強化する) ii。
p$ は p-simulate $wf$; iii という標準証明システムの基本的な性質を満たす。
p$ は、いくつかのブール関数 $h$ に対して効率的に証明され、$h$ は、サブ指数サイズの回路では平均で難しい。
例えば、III の場合。
1 と 2 は $p=wf$ と等価である。
もし関数 $h\in NE\cap coNE$ が存在して、大きさが 2^{n/4}$ の回路では平均的に困難であるなら、各大きな$n$ に対して、プロパティ I を満たす明示的な命題証明システム $P$ が存在する。
-III。
つまり、アイテム1と2の等価性が$P$である。
関連論文リスト
- Testing Support Size More Efficiently Than Learning Histograms [0.18416014644193066]
分布のヒストグラムを$p$で学習するよりも, より効率的にテストを行うことができることを示す。
この証明は、チェビシェフ近似が良い近似であるように設計されている範囲外の分析に依存する。
論文 参考訳（メタデータ） (2024-10-24T17:05:34Z) - On the Power of Interactive Proofs for Learning [3.785008536475385]
我々は、PAC学習を検証するための2倍効率の証明システムの研究を継続する。
任意の関数$f colon 0,1n から 0,1$ までの最大フーリエ文字を任意に小さな誤りまで学習するための対話的プロトコルを構築する。
二重効率証明系を主張しないならば、モデルは自明になる。
論文 参考訳（メタデータ） (2024-04-11T23:16:21Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳（メタデータ） (2022-02-15T03:49:28Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳（メタデータ） (2021-11-28T14:08:25Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。
任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
論文 参考訳（メタデータ） (2020-08-20T01:04:32Z) - Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。
我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
論文 参考訳（メタデータ） (2020-06-11T00:55:35Z) - 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) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。