論文の概要: Learning algorithms from circuit lower bounds
- arxiv url: http://arxiv.org/abs/2012.14095v1
- Date: Mon, 28 Dec 2020 04:47:36 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-19 10:53:50.043052
- Title: Learning algorithms from circuit lower bounds
- Title（参考訳）: 回路下限からの学習アルゴリズム
- Authors: J\'an Pich
- Abstract要約: 構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。
難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We revisit known constructions of efficient learning algorithms from various
notions of constructive circuit lower bounds such as distinguishers breaking
pseudorandom generators or efficient witnessing algorithms which find errors of
small circuits attempting to compute hard functions. As our main result we
prove that if it is possible to find efficiently, in a particular interactive
way, errors of many p-size circuits attempting to solve hard problems, then
p-size circuits can be PAC learned over the uniform distribution with
membership queries by circuits of subexponential size. The opposite implication
holds as well. This provides a new characterisation of learning algorithms and
extends the natural proofs barrier of Razborov and Rudich. The proof is based
on a method of exploiting Nisan-Wigderson generators introduced by
Kraj\'{i}\v{c}ek (2010) and used to analyze complexity of circuit lower bounds
in bounded arithmetic.
An interesting consequence of known constructions of learning algorithms from
circuit lower bounds is a learning speedup of Oliveira and Santhanam (2016). We
present an alternative proof of this phenomenon and discuss its potential to
advance the program of hardness magnification.
- Abstract（参考訳）: 擬似乱数生成器を分割する識別器や、ハード関数を計算しようとする小さな回路の誤りを見つける効率的な目撃アルゴリズムなど、構成的回路下限の様々な概念から、効率的な学習アルゴリズムの既知の構成を再検討する。
その結果,特定の対話的な方法で,難解な問題を解こうとする多数のpサイズ回路の誤りを効率的に見つけることができれば,pサイズ回路は,サブ指数サイズの回路によって,メンバシップクエリによる一様分布上で学習できることがわかった。
逆の意味でも同様である。
これは学習アルゴリズムの新たな特徴付けを提供し、RazborovとRudichの自然証明障壁を拡張する。
この証明は、Kraj\'{i}\v{c}ek (2010) が導入したニサン・ウィグダーソン発生器を利用する方法に基づいており、有界算術における回路下界の複雑さを解析するために用いられる。
回路下界からの学習アルゴリズムの既知の構築の興味深い結果は、Oliveira と Santhanam (2016) の学習スピードアップである。
本稿では,この現象の代替的な証明を示し,硬度拡大プログラムの進展可能性について考察する。
関連論文リスト
- Functional Faithfulness in the Wild: Circuit Discovery with Differentiable Computation Graph Pruning [14.639036250438517]
本稿では、DiscoGPとともにCircuit Discoveryと呼ばれるタスクを包括的に再構築する。
DiscoGPは、回路発見のための識別可能なマスキングに基づく、新しく効果的なアルゴリズムである。
論文 参考訳（メタデータ） (2024-07-04T09:42:25Z) - Finding Transformer Circuits with Edge Pruning [71.12127707678961]
自動回路発見の効率的かつスケーラブルなソリューションとしてエッジプルーニングを提案する。
本手法は,従来の手法に比べてエッジ数の半分未満のGPT-2の回路を探索する。
その効率のおかげで、Edge PruningをCodeLlama-13Bにスケールしました。
論文 参考訳（メタデータ） (2024-06-24T16:40:54Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
論文 参考訳（メタデータ） (2023-06-25T01:30:37Z) - Gaussian Elimination versus Greedy Methods for the Synthesis of Linear
Reversible Circuits [0.0]
可逆回路は、量子コンピューティングに多くの応用がある可逆回路のサブクラスを表す。
ガウス除去アルゴリズムの最適化版と調整LU分解を用いて,任意の線形可逆作用素に対する新しいアルゴリズムを提案する。
全体として、我々のアルゴリズムは特定の問題サイズに対する最先端の手法を改善している。
論文 参考訳（メタデータ） (2022-01-17T16:31:42Z) - Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。
我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
論文 参考訳（メタデータ） (2021-05-18T05:23:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z) - Investigating the Scalability and Biological Plausibility of the
Activation Relaxation Algorithm [62.997667081978825]
アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。
このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。
また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
論文 参考訳（メタデータ） (2020-10-13T08:02:38Z) - ACSS-q: Algorithmic complexity for short strings via quantum accelerated
approach [1.4873907857806357]
符号化定理法を用いて,アルゴリズムの複雑性を推定する量子回路を提案する。
ユースケースとして,アルゴリズムの複雑さに基づくタンパク質-タンパク質相互作用の応用フレームワークを提案する。
論文 参考訳（メタデータ） (2020-09-18T14:41:41Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。