2
$\begingroup$

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)

$\endgroup$
2
$\begingroup$

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), and machine learning is not an exception here.
  • One of the useful concepts in the complexity of the learning problem is the VC dimension, PAC learnability, and their related concepts (such as sample complexity). Although these concepts can't be enough to measure the time complexity, they are useful for finding the learner model's capacity.
$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Maybe you could explain what UDL is and why UDL with arbitrary generative models is impossible without inductive bias. $\endgroup$ – nbro Jun 6 '20 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.