Publication

From Information Inequalities to Computational Lower Bounds in Learning

Emmanuel Abbé
2020

Abstract

This talk shows how computational lower bounds in learning, which allow to show failure at learning certain function classes due to computational constraints, can be derived using information-theoretic arguments and inequalities. In particular, it is shown that GDbased deep learning cannot learn with polynomial parameters certain function classes that can be learned efficiently with other non-GD based algorithms. Joint work with C. Sandon (MIT).

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Emmanuel Abbé
2020

Abstract

Official source

Related concepts (26)

Computational hardness assumption

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where efficiently typically means "in polynomial time"). It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

Computational science

Computational science, also known as scientific computing, technical computing or scientific computation (SC), is a division of science that uses advanced computing capabilities to understand and solve complex physical problems. This includes Algorithms (numerical and non-numerical): mathematical models, computational models, and computer simulations developed to solve sciences (e.

Romanovski polynomials

In mathematics, the Romanovski polynomials are one of three finite subsets of real orthogonal polynomials discovered by Vsevolod Romanovsky (Romanovski in French transcription) within the context of probability distribution functions in statistics. They form an orthogonal subset of a more general family of little-known Routh polynomials introduced by Edward John Routh in 1884. The term Romanovski polynomials was put forward by Raposo, with reference to the so-called 'pseudo-Jacobi polynomials in Lesky's classification scheme.

Related publications (5)

From Information Inequalities to Computational Lower Bounds in Learning

Chat with Graph Search

Accelerating discovery across scientific disciplines through reproducible workflows with AiiDAlab

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity

Learning efficient representations of complex constraints for scalable optimization