Answers.Body: <p>At least you should be aware of two points:</p>
  
  <ul>
  <li>P/NP/NP-hard (and all other class of complexities) are thoroughly valid for the machine learning area as well. Because these concepts are related to the fundamental of computations (<a href="https://en.wikipedia.org/wiki/Theory_of_computation" rel="nofollow noreferrer">theory of computation</a>), and machine learning is not an exception here. </li>
  <li>One of the useful concepts in the complexity of the learning problem is the <a href="https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension" rel="nofollow noreferrer">VC dimension</a>, <a href="https://en.wikipedia.org/wiki/Probably_approximately_correct_learning" rel="nofollow noreferrer">PAC learnability</a>, and their related concepts (such as <a href="https://en.wikipedia.org/wiki/Sample_complexity" rel="nofollow noreferrer">sample complexity</a>). Although these concepts can't be enough to measure the time complexity, they are useful for finding the learner model's capacity. </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-05T16:33:42.007Z
Answers.LastActivityDate: 2020-06-05T16:39:05.553Z
Answers.LastEditDate: 2020-06-05T16:39:05.553Z
Answers.UserDisplayName: OmG
Answers.Body: <p>Unsupervised disentanglement learning with arbitrary generative models is impossible without inductive biases [1].</p>
  
  <p>In fact, in general, any kind of learning is impossible without inductive biases.</p>
  
  <p>[1]: <a href="https://arxiv.org/abs/1811.12359" rel="nofollow noreferrer">Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations</a></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-06T17:35:53.603Z
Answers.Text: Maybe you could explain what UDL is and why UDL with arbitrary generative models is _impossible_ without inductive bias.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-06T16:40:33.027Z
Answers.LastActivityDate: 2020-06-06T16:40:33.027Z
Answers.UserDisplayName: nyumerics
Body: <p>For the problems that can be solved algorithmically.</p>
  
  <p>We have very good formal literature for which problems can be solved in polynomial, exponential time and which cannot. <strong>P/NP/NP-hard</strong></p>
  
  <p>But do we know some problems in machine learning paradigm for which no model can be trained? (With/without infinite computation capacity)</p>
  
Tags: <neural-networks><machine-learning><training>
Title: What kind of problems cannot be solved using machine learning techniques?
UserDisplayName: Kaivalya Swami
ThreadText: # What kind of problems cannot be solved using machine learning techniques?
  
  (Asked by: username_0 on 2020-06-05)
  
  For the problems that can be solved algorithmically.
  
  We have very good formal literature for which problems can be solved in polynomial, exponential time and which cannot. **P/NP/NP-hard**
  
  But do we know some problems in machine learning paradigm for which no model can be trained? (With/without infinite computation capacity)
  
  **Tags:** neural-networks, machine-learning, training
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-06-05. Score: 2
  
  At least you should be aware of two points:
  
  * P/NP/NP-hard (and all other class of complexities) are thoroughly valid for the machine learning area as well. Because these concepts are related to the fundamental of computations ([theory of computation](https://en.wikipedia.org/wiki/Theory_of_computation)), and machine learning is not an exception here.
  * One of the useful concepts in the complexity of the learning problem is the [VC dimension](https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_dimension), [PAC learnability](https://en.wikipedia.org/wiki/Probably_approximately_correct_learning), and their related concepts (such as [sample complexity](https://en.wikipedia.org/wiki/Sample_complexity)). Although these concepts can't be enough to measure the time complexity, they are useful for finding the learner model's capacity.
  
  
  ---
  
  ### Answer by username_2 on 2020-06-06. Score: 0
  
  Unsupervised disentanglement learning with arbitrary generative models is impossible without inductive biases [1].
  
  In fact, in general, any kind of learning is impossible without inductive biases.
  
  [1]: [Challenging Common Assumptions in the Unsupervised Learning of Disentangled Representations](https://arxiv.org/abs/1811.12359)
  
  > **Comments:**
  > **username_3**: Maybe you could explain what UDL is and why UDL with arbitrary generative models is _impossible_ without inductive bias.  
  
  ---
  
  