論文の概要: Agnostic Membership Query Learning with Nontrivial Savings: New Results,
Techniques
- arxiv url: http://arxiv.org/abs/2311.06690v1
- Date: Sat, 11 Nov 2023 23:46:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-14 17:34:03.188186
- Title: Agnostic Membership Query Learning with Nontrivial Savings: New Results,
Techniques
- Title（参考訳）: 非自明な貯蓄によるAgnostic Membership Query Learning: 新しい結果、テクニック
- Authors: Ari Karchmer
- Abstract要約: 学習の最前線で授業の会員クエリによる学習を検討する。
このアプローチは、非自明な貯蓄を伴う線形学習の研究にインスパイアされ、継続する」。
ゲートのサブ線形数からなる回路の非依存学習アルゴリズムを確立する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: (Abridged) Designing computationally efficient algorithms in the agnostic
learning model (Haussler, 1992; Kearns et al., 1994) is notoriously difficult.
In this work, we consider agnostic learning with membership queries for
touchstone classes at the frontier of agnostic learning, with a focus on how
much computation can be saved over the trivial runtime of 2^n$. This approach
is inspired by and continues the study of ``learning with nontrivial savings''
(Servedio and Tan, 2017). To this end, we establish multiple agnostic learning
algorithms, highlighted by:
1. An agnostic learning algorithm for circuits consisting of a sublinear
number of gates, which can each be any function computable by a sublogarithmic
degree k polynomial threshold function (the depth of the circuit is bounded
only by size). This algorithm runs in time 2^{n -s(n)} for s(n) \approx
n/(k+1), and learns over the uniform distribution over unlabelled examples on
\{0,1\}^n.
2. An agnostic learning algorithm for circuits consisting of a sublinear
number of gates, where each can be any function computable by a \sym^+ circuit
of subexponential size and sublogarithmic degree k. This algorithm runs in time
2^{n-s(n)} for s(n) \approx n/(k+1), and learns over distributions of
unlabelled examples that are products of k+1 arbitrary and unknown
distributions, each over \{0,1\}^{n/(k+1)} (assume without loss of generality
that k+1 divides n).
- Abstract（参考訳）: (橋渡し)
不可知学習モデル(Haussler, 1992; Kearns et al., 1994)における計算効率のよいアルゴリズムの設計は、非常に難しい。
本研究では,2^n$の自明なランタイム上でどれだけの計算を節約できるかに着目し,非依存学習の最前線におけるタッチストーンクラスのメンバシップクエリによる非依存学習について考察する。
このアプローチは‘非自明な貯蓄による学習’(Servedio and Tan, 2017)にインスパイアされ、継続している。
この目的のために,1 個のゲートからなる回路の非依存学習アルゴリズムを,次数k の多項式しきい値関数で計算可能な任意の関数(回路の深さは大きさのみに制限される)として確立する。
このアルゴリズムは s(n) \approx n/(k+1) の時間 2^{n -s(n)} で実行され、 \{0,1\}^n 上のラベルなし例に対する一様分布を学習する。
2) ゲートのサブ線形数からなる回路の非依存学習アルゴリズムでは,各回路は,サブ指数サイズとサブ対数次数 k の \sym^+ 回路で計算可能な任意の関数を計算できる。
このアルゴリズムは s(n) \approx n/(k+1) に対して時間 2^{n-s(n)} で実行され、k+1 の任意の分布と未知の分布の積である非競合例の分布について学習する(k+1 が n を割る一般性を失うことなく)。
関連論文リスト
- Fast quantum integer multiplication with zero ancillas [0.5755004576310334]
我々は,ゼロアンシラ量子ビットを用いた準四進時間量子乗法の新しいパラダイムを導入する。
関連するキュービットは入力と出力レジスタ自身のみである。
我々のアルゴリズムは、実際的な問題の大きさよりも優れている可能性がある。
論文 参考訳（メタデータ） (2024-03-26T18:00:03Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。
我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。
我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
論文 参考訳（メタデータ） (2023-10-28T19:01:16Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。
我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
論文 参考訳（メタデータ） (2023-05-19T00:07:32Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
統計的クエリモデルでは,ブロックワークランダムな量子回路の出力分布の学習は平均ケースハードであることが示されている。
この学習モデルは、ほとんどの一般的な学習アルゴリズムの抽象的な計算モデルとして広く利用されている。
論文 参考訳（メタデータ） (2023-05-09T20:53:27Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - Practical, Provably-Correct Interactive Learning in the Realizable
Setting: The Power of True Believers [12.09273192079783]
我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。
我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
論文 参考訳（メタデータ） (2021-11-09T02:33:36Z) - Structure learning in polynomial time: Greedy algorithms, Bregman
information, and exponential families [12.936601424755944]
DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。
DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。
この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
論文 参考訳（メタデータ） (2021-10-10T06:37:51Z) - Hybrid Stochastic-Deterministic Minibatch Proximal Gradient:
Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。
損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文 参考訳（メタデータ） (2020-09-18T02:18:44Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳（メタデータ） (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。