SOURCE-LINKED INTELLIGENCE

Statistical Optimality and Computational Efficiency: batch and sequential unsupervised learning under additional structure and sampling constraints

CORDIS · observation · Publication date unknown

Statistical Optimality and Computational Efficiency: batch and sequential unsupervised learning under additional structure and sampling constraints Unsupervised learning is a key problem of artificial intelligence, at the crossroad of statistics and machine learning. The aim is to infer patterns from unlabelled data, by providing learning algorithms that are computationally efficient - i.e. polynomial time - and statistically performant - i.e. minimising an error criterion - and by characterising the fundamental limits for learning. In the last decade, deep and important phenomena of statistical-computational trade-offs have been unveiled: for some canonical vanilla problems, it is now admitted that no algorithm is both statistically optimal and computationally efficient. However, and somewhat surprisingly, many extensions of these commonly admitted conjectures to other models that present slight variations have been recently proven wrong. The reason is that these model variations give rise to additional structure. This could be a blessing if it can be exploited by a well

Read original source ↗ Open in workspace

recordType

award

status

SIGNED

region

EU

value

1979797

unit

EUR