論文の概要: Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries

• arxiv url: http://arxiv.org/abs/2006.14677v2
• Date: Sun, 25 Oct 2020 23:58:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 03:50:34.049580
• Title: Average-case Complexity of Teaching Convex Polytopes via Halfspace Queries
• Title（参考訳）: ハーフスペース・クエリによる凸多面体の平均複雑度
• Authors: Akash Kumar, Adish Singla, Yisong Yue, Yuxin Chen
• Abstract要約: 平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。 我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
• 参考スコア（独自算出の注目度）: 55.28642461328172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We examine the task of locating a target region among those induced by intersections of $n$ halfspaces in $\mathbb{R}^d$. This generic task connects to fundamental machine learning problems, such as training a perceptron and learning a $\phi$-separable dichotomy. We investigate the average teaching complexity of the task, i.e., the minimal number of samples (halfspace queries) required by a teacher to help a version-space learner in locating a randomly selected target. As our main result, we show that the average-case teaching complexity is $\Theta(d)$, which is in sharp contrast to the worst-case teaching complexity of $\Theta(n)$. If instead, we consider the average-case learning complexity, the bounds have a dependency on $n$ as $\Theta(n)$ for \tt{i.i.d.} queries and $\Theta(d \log(n))$ for actively chosen queries by the learner. Our proof techniques are based on novel insights from computational geometry, which allow us to count the number of convex polytopes and faces in a Euclidean space depending on the arrangement of halfspaces. Our insights allow us to establish a tight bound on the average-case complexity for $\phi$-separable dichotomies, which generalizes the known $\mathcal{O}(d)$ bound on the average number of "extreme patterns" in the classical computational geometry literature (Cover, 1965).
• Abstract（参考訳）: 我々は、$\mathbb{R}^d$における$n$半空間の交叉によって誘導される領域のうち、対象領域を探索するタスクについて検討する。 この一般的なタスクは、パーセプトロンのトレーニングや$\phi$-separable 2chotomyの学習など、基本的な機械学習問題と接続する。 本研究は,教師がランダムに選択した目標の特定を支援するのに必要なサンプル数(半空間問合せ)について,タスクの平均的な教示複雑性について検討する。 我々の主な結果として、平均的なケースの授業複雑性は$\Theta(d)$であり、最悪のケースの授業複雑性は$\Theta(n)$とは対照的である。 平均的な学習の複雑さを考えると、境界は$n$に対して$\Theta(n)$ for \tt{i.i.d.} クエリと$\Theta(d \log(n))$ for active selected query by the learnerとして依存する。 我々の証明手法は計算幾何学からの新たな洞察に基づいており、半空間の配置に依存するユークリッド空間内の凸多面体や面の数を数えることができる。 我々の洞察は、既知の$\mathcal{O}(d)$を古典的な計算幾何学の文献(Cover, 1965)における「極端なパターン」の平均数で一般化する$\phi$-separable dichotomiesに対する平均ケース複雑性の厳密な境界を確立することを可能にする。

関連論文リスト

• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• An Approximation Theory for Metric Space-Valued Functions With A View Towards Deep Learning [25.25903127886586]
  任意のポーランド計量空間 $mathcalX$ と $mathcalY$ の間の連続写像の普遍函数近似器を構築する。 特に、必要なディラック測度数は $mathcalX$ と $mathcalY$ の構造によって決定されることを示す。
  論文  参考訳（メタデータ） (2023-04-24T16:18:22Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
  仮説選択問題に対する最適2ドルの近似学習戦略を導出する。 これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2021-08-17T21:11:20Z)
• Classification Under Misspecification: Halfspaces, Generalized Linear Models, and Connections to Evolvability [39.01599245403753]
  特に、Massartノイズ下でのハーフスペースの学習問題を$eta$で検討する。 我々は任意のSQアルゴリズムが$mathsfOPT + epsilon$を達成するのに超ポリノミカルな多くのクエリを必要とすることを示した。 また、Massartノイズ下でハーフスペースを学習するためのアルゴリズムを実証的に研究し、いくつかの魅力的なフェアネス特性を示すことを示した。
  論文  参考訳（メタデータ） (2020-06-08T17:59:11Z)
• Learning Polynomials of Few Relevant Dimensions [12.122488725065388]
  多項式回帰は学習と統計の基本的な原始である。 およそ$N = O_r,d(n log2(1/epsilon) (log n)d)$と$O_r,d(N n2)$である。
  論文  参考訳（メタデータ） (2020-04-28T18:00:18Z)
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity [63.29100726064574]
  有限格子上の半空間に対して微分プライベート学習器を$mathbbRd$で$G$で、サンプル複雑性を$approx d2.5cdot 2log*|G|$で表す。 学習者のためのビルディングブロックは、線形実現可能性問題を解くために、微分プライベートな新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2020-04-16T16:12:10Z)

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

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