3 ms·

I learned so much from Bourgain's work. While most of his work was in Fourier analysis, and later in number theory, he really was a very versatile analyst. Jus

I learned so much from Bourgain's work. While most of his work was in Fourier analysis, and later in number theory, he really was a very versatile analyst. Just two of his early papers, on embeddings of metric spaces, and on concentration for covariance matrices started whole fields later. They are very useful now in theoretical machine learning.

heinrichf 8y ago
Interesting! Could you share examples of works in theoretical ML using these ?
- cosmic_ape 8y ago
  Well, lets try. For the embeddings, you'll have to search the internet for details, and this may be not a "proper" ML. But the general idea is that if you have some nice euclidean algorithm, like k-means, and you want to cluster some data w.r.t a different metric, you could try putting the data in the euclidean space without distorting the distances too much and then apply the algo. there. For k-means in particular the nearest neighbor search in Euclidean space can be made efficient, I think. This didn't take off much because most of the results were unfortunately negative. Although there were some recent positive results, even with discussion here [1]. Bourgain had some early results on the embeddability of finite metric spaces into classical spaces. The concentration of covariance matrices is fundamental for most "spectral" methods, in particular spectral clustering. See for instance [2]. People proved and reproved these concentration results a lot of times, but Bourgain's was the earliest with N\log N sample complexity for log concave measures, improving on a result of Lovazs et al. (!!!) More importantly, the method with which he proved this, controlling the concentration by decomposing into bounded and "rarely non-zero" parts is now all around in statistical learning theory. So each time people want to prove uniform law of large numbers and nothing standard works, people try to find a good decomposition. [1] https://news.ycombinator.com/item?id=17752836 https://news.ycombinator.com/item?id=17752836 [2] Clustering with Spectral Norm and the k-means Algorithm, Amit Kumar and Ravindran Kannan (Section 6...)

heinrichf 8y ago

Interesting! Could you share examples of works in theoretical ML using these ?

cosmic_ape 8y ago
Well, lets try. For the embeddings, you'll have to search the internet for details, and this may be not a "proper" ML. But the general idea is that if you have some nice euclidean algorithm, like k-means, and you want to cluster some data w.r.t a different metric, you could try putting the data in the euclidean space without distorting the distances too much and then apply the algo. there. For k-means in particular the nearest neighbor search in Euclidean space can be made efficient, I think. This didn't take off much because most of the results were unfortunately negative. Although there were some recent positive results, even with discussion here [1]. Bourgain had some early results on the embeddability of finite metric spaces into classical spaces. The concentration of covariance matrices is fundamental for most "spectral" methods, in particular spectral clustering. See for instance [2]. People proved and reproved these concentration results a lot of times, but Bourgain's was the earliest with N\log N sample complexity for log concave measures, improving on a result of Lovazs et al. (!!!) More importantly, the method with which he proved this, controlling the concentration by decomposing into bounded and "rarely non-zero" parts is now all around in statistical learning theory. So each time people want to prove uniform law of large numbers and nothing standard works, people try to find a good decomposition. [1] https://news.ycombinator.com/item?id=17752836 https://news.ycombinator.com/item?id=17752836 [2] Clustering with Spectral Norm and the k-means Algorithm, Amit Kumar and Ravindran Kannan (Section 6...)