Exploring Viable Algorithmic Options for Learning from Demonstration (LfD): A Parameterized Complexity Approach. (arXiv:2205.04989v1 [cs.LG])

Web: http://arxiv.org/abs/2205.04989

The key to reconciling the polynomial-time intractability of many machine
learning tasks in the worst case with the surprising solvability of these tasks
by heuristic algorithms in practice seems to be exploiting restrictions on
real-world data sets. One approach to investigating such restrictions is to
analyze why heuristics perform well under restrictions. A complementary
approach would be to systematically determine under which sets of restrictions
efficient and reliable machine learning algorithms do and do not exist. In this
paper, we …

arxiv complexity learning