Join the Goergen Institute for Data Science for Margin and Dimensionality in Machine Learning and Communication Complexity with Kaave Hosseini, Assistant Professor of Computer Science at University of Rochester.

Abstract: Margin and dimensionality are two important parameters that capture the complexity of data. A well-known phenomenon in machine learning and many other fields is the curse of dimensionality: the performance of many machine learning algorithms deteriorates significantly once the dimension of the data (i.e., the number of input features) is large. Nevertheless, many important learning algorithms such as the perceptron algorithm from the ’50s, perform well, no matter how large the dimension is, albeit, with one assumption about the data: the data must have a large margin (i.e., the data points are not too close to decision boundaries). Two very basic questions regarding the trade-off between margin and dimension have remained unresolved until recently. 

Question one: is it true that if the margin of data is large, then the data is inherently low-dimensional? In other words, if one is not concerned with keeping a large margin, can one choose a smarter feature space with a low dimension? We answer this question in the negative, which also gives tight lower bounds on dimensionality reduction given by the Johnson-Lindenstrauss lemma. Question two: is it true that if data is low-dimensional, then there is a choice of feature space (with possibly high dimension) that has a large margin? We also answer this question in the negative. 

The above two questions come up in the context of communication complexity. We explain the connection between these two fields and briefly explain the ideas that go into resolving the questions above.

Bio: Kaave Hosseini is an assistant professor in the Computer Science department at University of Rochester. Hosseini has received BSc. Degrees in mathematics and computer science at Sharif University of Technology, Tehran. He obtained his Ph.D. in Computer Science at UC San Diego. He was a postdoctoral associate in the Department of Mathematical Sciences at Carnegie Mellon University prior to joining URCS. His area of research is in theoretical computer science. More particularly, his research has to do with computational complexity and pseudo-randomness, and approximate algebraic structures.

We are providing a Zoom option for this event. Please use the link below to enter the Zoom webinar.

Webinar link: https://rochester.zoom.us/j/98909559637

Webinar ID: 989 0955 9637