Learning the Hypotheses Space from data: Learning Space and U-curve Property

• URL: http://arxiv.org/abs/2001.09532v3
• Date: Fri, 10 Sep 2021 12:33:44 GMT
• Title: Learning the Hypotheses Space from data: Learning Space and U-curve Property
• Authors: Diego Marcondes, Adilson Simonis and Junior Barrera
• Abstract summary: 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)$.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents an extension of the classical agnostic PAC learning model in which learning problems are modelled not only by a Hypothesis Space $\mathcal{H}$, but also by a Learning Space $\mathbb{L}(\mathcal{H})$, which is a cover of $\mathcal{H}$, constrained by a VC-dimension property, that is a suitable domain for Model Selection algorithms. Our main contribution is a data driven general learning algorithm to perform regularized Model Selection on $\mathbb{L}(\mathcal{H})$. A remarkable, formally proved, consequence of this approach are conditions on $\mathbb{L}(\mathcal{H})$ and on the loss function that lead to estimated out-of-sample error surfaces which are true U-curves on $\mathbb{L}(\mathcal{H})$ chains, enabling a more efficient search on $\mathbb{L}(\mathcal{H})$. To our knowledge, this is the first rigorous result asserting that a non exhaustive search of a family of candidate models can return an optimal solution. In this new framework, an U-curve optimization algorithm becomes a natural component of Model Selection, hence of learning algorithms. The abstract general framework proposed here may have important implications on modern learning models and on areas such as Neural Architecture Search.

Related papers

• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
  arXiv  Detail & Related papers  (2023-07-24T14:37:22Z)
• A framework for overparameterized learning [0.0]
  An explanation for the success of deep neural networks is a central question in theoretical machine learning. We propose a framework consisting of a prototype learning problem, which is general enough to cover many popular problems. We then demonstrate that supervised learning, variational autoencoders and training with gradient penalty can be translated to the prototype problem.
  arXiv  Detail & Related papers  (2022-05-26T17:17:46Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• 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)
• Model Selection with Near Optimal Rates for Reinforcement Learning with General Model Classes [27.361399036211694]
  We address the problem of model selection for the finite horizon episodic Reinforcement Learning (RL) problem. In the model selection framework, instead of $mathcalP*$, we are given $M$ nested families of transition kernels. We show that textttARL-GEN obtains a regret of $TildemathcalO(d_mathcalE*H2+sqrtd_mathcalE* mathbbM* H2 T)$
  arXiv  Detail & Related papers  (2021-07-13T05:00:38Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Learning the Hypotheses Space from data Part II: Convergence and Feasibility [0.0]
  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.
  arXiv  Detail & Related papers  (2020-01-30T21:48:37Z)

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.