Machine learning is the sub-field of computer science concerned with creating programs and machines that can improve from experience and interaction. It relies upon mathematical optimization, statistics, and algorithm design. The talk will be an introduction to machine learning for a mathematical audience. We describe the mathematical formulations of basic types of learning such as supervised, unsupervised, interactive, etc., and the philosophical and scientific issues raised by them.
Spectral gaps of matrices are related to many basic properties, like mixing times, expansion, isoperimetry and more. We will see a connection between spectral gaps and sign-rank. The sign-rank of a boolean matrix is the minimum dimension of real space in which the matrix can be realized as a point-halfspace incidence matrix. Sign-rank is deeply related to learning theory and communication complexity. We will see that regular matrices with large spectral gaps have high sign-rank; roughly speaking, this means that a matrix with large spectral gap can not be realized in low-dimensional real space using halfspaces. This is another aspect in which matrices with a large spectral gap are pseudo-random.
You must be logged in to post a comment.