論文の概要: On Bounded Advice Classes
- arxiv url: http://arxiv.org/abs/2405.18155v1
- Date: Tue, 28 May 2024 13:16:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-29 18:29:23.894068
- Title: On Bounded Advice Classes
- Title（参考訳）: 境界アドバイザクラスについて
- Authors: Simon Marshall, Casper Gyurik, Vedran Dunjko,
- Abstract要約: 本研究では,有界アドバイスクラス,量子有界アドバイスクラス,ランダム化された有界アドバイスクラスの関係について検討する。
本研究は,アドバイス関数の複雑さに関する既存の研究において,技術の現状を改善した。
- 参考スコア（独自算出の注目度）: 1.9662978733004604
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: Advice classes in computational complexity have frequently been used to model real-world scenarios encountered in cryptography, quantum computing and machine learning, where some computational task may be broken down into a preprocessing and deployment phase, each associated with a different complexity. However, in these scenarios, the advice given by the preprocessing phase must still be generated by some (albeit more powerful) bounded machine, which is not the case in conventional advice classes. To better model these cases we develop `bounded advice classes', where a more powerful Turing machine generates advice for another, less powerful, Turing machine. We then focus on the question of when various classes generate useful advice, to answer this we connect bounded advice to unary languages. This connection allows us to state various conditional and unconditional results on the utility of advice generated by $\mathsf{EXP}$, $\mathsf{NP}$, $\mathsf{BQP}$, $\mathsf{PSPACE}$, and more. We study the relations between bounded advice classes, quantum bounded advice classes, and randomised bounded advice. We also examine how each of these concepts interact with recently introduced classes, like $\mathsf{BPP/samp}$. Our results also improve the state of the art in existing research on the complexity of advice functions.
- Abstract（参考訳）: 計算複雑性のアドバイスクラスは、暗号、量子コンピューティング、機械学習で遭遇する現実世界のシナリオをモデル化するために頻繁に用いられており、計算タスクは前処理と展開フェーズに分解され、それぞれが異なる複雑さに関連付けられている。
しかし、これらのシナリオでは、前処理フェーズによって与えられるアドバイスは、従来のアドバイスクラスではそうではないいくつかの(より強力な)有界マシンによって生成されなければならない。
より強力なチューリングマシンは、より強力でないチューリングマシンに対してアドバイスを生成する。
次に、様々なクラスが有用なアドバイスをいつ生成するかという問題に焦点を合わせ、これに答えるために、有界なアドバイスを一意の言語に結びつける。
この接続により、$\mathsf{EXP}$, $\mathsf{NP}$, $\mathsf{BQP}$, $\mathsf{PSPACE}$などによって生成されるアドバイスの効用について、様々な条件付きおよび無条件の結果を記述することができます。
本研究では,有界アドバイスクラス,量子有界アドバイスクラス,ランダム化された有界アドバイスクラスの関係について検討する。
また、これらの概念が、例えば$\mathsf{BPP/samp}$のような最近導入されたクラスとどのように相互作用するかについても調べる。
また,既存のアドバイス関数の複雑さに関する研究の最先端性も改善した。
関連論文リスト
- An Optimal Transport Approach for Computing Adversarial Training Lower
Bounds in Multiclass Classification [3.447848701446988]
強靭性を強制する一般的なパラダイムは、敵対的訓練(AT)であるが、これは多くの計算的および理論的困難をもたらす。
最近の研究は、ATとマルチクラス分類設定(MOT)の接続を開発し、この問題を研究するための新しいツールセットをアンロックしている。
本稿では,最適対向リスクの普遍的下界を計算するための計算処理可能な数値アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-17T13:03:47Z) - Generalized Convergence Analysis of Tsetlin Machines: A Probabilistic
Approach to Concept Learning [20.519261060300302]
本稿では,Tsetlinオートマトンに基づく機械学習アルゴリズムの総合収束解析について述べる。
本稿では,確率論的概念学習(PCL, Probabilistic Concept Learning)と呼ばれる新しいフレームワークを提案する。
我々は、任意の節$C_k$に対して、PCLが0.5p_k1$のときにリテラルの結合に収束することを確認する理論的証明を確立する。
論文 参考訳（メタデータ） (2023-10-03T12:21:41Z) - Towards a Holistic Understanding of Mathematical Questions with
Contrastive Pre-training [65.10741459705739]
本稿では,数学的問題表現,すなわち QuesCo に対する対照的な事前学習手法を提案する。
まず、コンテンツレベルと構造レベルを含む2段階の質問強化を設計し、類似した目的で文字通り多様な質問ペアを生成する。
そこで我々は,知識概念の階層的情報を完全に活用するために,知識階層を意識したランク戦略を提案する。
論文 参考訳（メタデータ） (2023-01-18T14:23:29Z) - Computability of Optimizers [71.84486326350338]
様々な状況において、チューリングマシンでは実現不可能であり、結果としてデジタルコンピュータでは実現不可能であることを示す。
我々は、人工知能、金融数学、情報理論など、非常に異なる分野からよく知られた様々な問題に対して、そのような結果を証明している。
論文 参考訳（メタデータ） (2023-01-15T17:41:41Z) - Exceeding Computational Complexity Trial-and-Error Dynamic Action and
Intelligence [0.0]
計算複雑性 (Computational complexity) は、計算の難易度を規定する計算機科学のコア理論である。
本稿では,概念を明確にし,不特定型コンピューティング,特化型コンピューティング,コンピュータエージェント,動的検索などの定義を提案する。
また,このフレームワーク,すなわちトライアル・アンド・エラー+動的検索を提案し,議論する。
論文 参考訳（メタデータ） (2022-12-22T21:23:27Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。
本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文 参考訳（メタデータ） (2021-07-05T00:51:02Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z) - Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。
双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文 参考訳（メタデータ） (2020-05-24T18:11:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。