Margin and Dimensionality in Machine Learning and Communication Complexity

Margin and Dimensionality in Machine Learning and Communication Complexity (via Zoom)

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 basic questions regarding the trade-off between margin and dimension have remained unresolved until recently. 
Question one: is it true that if the data margin 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, also giving 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 briefly mention a negative answer to this question from prior work.
The above two questions (precisely) come up in the context of communication complexity with a different notation. 

Bio: Kaave Hosseini is an assistant professor in the Computer Science department at the 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 before 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.