On Learning from Average-Case Errorless Computing (Extended Abstract)

• Item type: SIG Technical Reports(1)
• 公開日: 2021-04-30
• タイトル: On Learning from Average-Case Errorless Computing (Extended Abstract)
• タイトル / 言語: en
• タイトル: On Learning from Average-Case Errorless Computing (Extended Abstract)
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Mathematical and Computing Science, Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Mathematical and Computing Science, Tokyo Institute of Technology
• 著者名: Mikito, Nanashima
• 著者名(英): Mikito, Nanashima
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A PAC learning model contains a worst-case sense due to the following requirement : a learner must learn (1) all functions in a concept class on (2) all example distributions. Thus, whether average-case computation on a fixed distribution is sufficient for such learning is quite non-trivial and a significant question to understand the nature of learning. Recent studies on complexity theory implicitly revealed that average-case errorless computation for a distributional NP-problem is sufficient to resolve the worst-case requirement (1) alone. In this paper, we addressed the worst-case requirement (2) (alone) and the requirements (1) and (2) simultaneously to identify where the current non-average aspect of learning essentially arises. Specifically, we will show the following theorems: (i) polynomial-size circuits are efficiently distribution-free PAC learnable on average iff there exist auxiliary-input pseudorandom generators, and (ii) if DistNP ⊆ AvgP, then polynomial-size circuits are efficiently agnostic learnable under all P/poly-computable example distributions. Our learning algorithm works without specified an example distribution as a usual distribution-free learner, but the time and sample complexity depends on the complexity of example distributions.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A PAC learning model contains a worst-case sense due to the following requirement : a learner must learn (1) all functions in a concept class on (2) all example distributions. Thus, whether average-case computation on a fixed distribution is sufficient for such learning is quite non-trivial and a significant question to understand the nature of learning. Recent studies on complexity theory implicitly revealed that average-case errorless computation for a distributional NP-problem is sufficient to resolve the worst-case requirement (1) alone. In this paper, we addressed the worst-case requirement (2) (alone) and the requirements (1) and (2) simultaneously to identify where the current non-average aspect of learning essentially arises. Specifically, we will show the following theorems: (i) polynomial-size circuits are efficiently distribution-free PAC learnable on average iff there exist auxiliary-input pseudorandom generators, and (ii) if DistNP ⊆ AvgP, then polynomial-size circuits are efficiently agnostic learnable under all P/poly-computable example distributions. Our learning algorithm works without specified an example distribution as a usual distribution-free learner, but the time and sample complexity depends on the complexity of example distributions.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2021-AL-183, 号 5, p. 1-8, 発行日 2021-04-30
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会