Learning the Hypotheses Space from data Part II: Convergence and Feasibility

• URL: http://arxiv.org/abs/2001.11578v2
• Date: Fri, 10 Sep 2021 12:34:05 GMT
• Title: Learning the Hypotheses Space from data Part II: Convergence and Feasibility
• Authors: Diego Marcondes, Adilson Simonis and Junior Barrera
• Abstract summary: We show consistency of a model selection framework based on Learning Spaces. We show that it is feasible to learn the Hypotheses Space from data.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In part \textit{I} we proposed a structure for a general Hypotheses Space $\mathcal{H}$, the Learning Space $\mathbb{L}(\mathcal{H})$, which can be employed to avoid \textit{overfitting} when estimating in a complex space with relative shortage of examples. Also, we presented the U-curve property, which can be taken advantage of in order to select a Hypotheses Space without exhaustively searching $\mathbb{L}(\mathcal{H})$. In this paper, we carry further our agenda, by showing the consistency of a model selection framework based on Learning Spaces, in which one selects from data the Hypotheses Space on which to learn. The method developed in this paper adds to the state-of-the-art in model selection, by extending Vapnik-Chervonenkis Theory to \textit{random} Hypotheses Spaces, i.e., Hypotheses Spaces learned from data. In this framework, one estimates a random subspace $\hat{\mathcal{M}} \in \mathbb{L}(\mathcal{H})$ which converges with probability one to a target Hypotheses Space $\mathcal{M}^{\star} \in \mathbb{L}(\mathcal{H})$ with desired properties. As the convergence implies asymptotic unbiased estimators, we have a consistent framework for model selection, showing that it is feasible to learn the Hypotheses Space from data. Furthermore, we show that the generalization errors of learning on $\hat{\mathcal{M}}$ are lesser than those we commit when learning on $\mathcal{H}$, so it is more efficient to learn on a subspace learned from data.

Related papers

• An Approximation Theory for Metric Space-Valued Functions With A View Towards Deep Learning [25.25903127886586]
  We build universal functions approximators of continuous maps between arbitrary Polish metric spaces $mathcalX$ and $mathcalY$. In particular, we show that the required number of Dirac measures is determined by the structure of $mathcalX$ and $mathcalY$.
  arXiv  Detail & Related papers  (2023-04-24T16:18:22Z)
• Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
  Ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
  arXiv  Detail & Related papers  (2023-02-27T16:34:21Z)
• Optimal Rates for Regularized Conditional Mean Embedding Learning [32.870965795423366]
  We derive a novel and adaptive statistical learning rate for the empirical CME estimator under the misspecified setting. Our analysis reveals that our rates match the optimal $O(log n / n)$ rates without assuming $mathcalH_Y$ to be finite dimensional.
  arXiv  Detail & Related papers  (2022-08-02T19:47:43Z)
• Cryptographic Hardness of Learning Halfspaces with Massart Noise [59.8587499110224]
  We study the complexity of PAC learning halfspaces in the presence of Massart noise. We show that no-time Massart halfspace learners can achieve error better than $Omega(eta)$, even if the optimal 0-1 error is small.
  arXiv  Detail & Related papers  (2022-07-28T17:50:53Z)
• Learning the hypotheses space from data through a U-curve algorithm: a statistically consistent complexity regularizer for Model Selection [0.0]
  This paper proposes a data-driven systematic, consistent and non-exhaustive approach to Model Selection. Our main contributions are a data-driven general learning algorithm to perform regularized Model Selection on $mathbbL(mathcalH)$. A remarkable consequence of this approach are conditions under which a non-exhaustive search of $mathbbL(mathcalH)$ can return an optimal solution.
  arXiv  Detail & Related papers  (2021-09-08T18:28:56Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Universal Regular Conditional Distributions via Probability Measure-Valued Deep Neural Models [3.8073142980733]
  We find that any model built using the proposed framework is dense in the space $C(mathcalX,mathcalP_1(mathcalY))$. The proposed models are also shown to be capable of generically expressing the aleatoric uncertainty present in most randomized machine learning models.
  arXiv  Detail & Related papers  (2021-05-17T11:34:09Z)
• Hardness of Learning Halfspaces with Massart Noise [56.98280399449707]
  We study the complexity of PAC learning halfspaces in the presence of Massart (bounded) noise. We show that there an exponential gap between the information-theoretically optimal error and the best error that can be achieved by a SQ algorithm.
  arXiv  Detail & Related papers  (2020-12-17T16:43:11Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  We study a variant of the linear bandit problem wherein we optimize a linear objective function but rewards are accrued only to an unknown subspace. In particular, at each round, the learner must choose whether to query the objective or the protected subspace alongside choosing an action. Our algorithm, derived from the OFUL principle, uses some of the queries to get an estimate of the protected space.
  arXiv  Detail & Related papers  (2020-11-02T14:59:39Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Learning the Hypotheses Space from data: Learning Space and U-curve Property [0.0]
  This paper presents an extension of the classical PAC learning model in which learning problems are modelled not only by a Hypothesis Space $mathcalH$, but also by a Learning Space $mathbbL(mathcalH)$. Our main contribution is a data driven general learning algorithm to perform regularized Model Selection on $mathbbL(mathcalH)$.
  arXiv  Detail & Related papers  (2020-01-26T22:29:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.