[FEA] Promote FITSNE from experimental

[divyegala]

I'll attach embeddings of some popular datasets using cuML t-sne (FFT), cuML t-sne (BH), and sklearn t-sne (BH)

[divyegala]

Boston Dataset:

1. cuML FFT
   

2. cuML BH
   

3. sklearn BH
   

[divyegala]

Breast Cancer Dataset:

1. cuML FFT
   

2. cuML BH
   

3. sklearn BH
   

[divyegala]

Diabetes Dataset:

1. cuML FFT
   

2. cuML BH
   

3. sklearn BH
   

[divyegala]

Digits Dataset:

1. cuML FFT
   

2. cuML BH
   

3. sklearn BH
   

[divyegala]

Iris Dataset:

1. cuML FFT
   

2. cuML BH
   

3. sklearn BH
   

[zbjornson]

It looks like a lot of those differences can be reduced by adjusting late_exaggeration.

It also looks like there are flyaways in the Iris dataset in cuML B-H.

[github-actions]

This issue has been labeled inactive-30d due to no recent activity in the past 30 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed. This issue will be labeled inactive-90d if there is no activity in the next 60 days.

[cjnolet]

Just want to provide an update here for some tasks that should be completed before we officially promote the FFT TSNE from experimental (and potentially make it the default option). We've shown that the FFT algorithm works well on toy datasets but there has been evidence to suggest that 1) it may not always be providing better results over Barnes-hut, and 2) It may not be faster. To my knowledge, we have not done any formal benchmarks or scale analysis of the FFT algorithm, outside of the initial results that @zbjornson has been gracious enough to perform.

At the very minimum, we should want the results to be at least as correct and performant as Barnes-hut in order to make the FFT variant the default option. If more stable results but not quite as performance, we could probalby still move FFT out of experimental but not make it the default.

From my perspective, there are reall two tasks that remain:

1. Benchmark performance and scale on both real-world datasets and toy datasets
2. Evaluate the stability / correctness on real-world datasets and at scale

One very easy place to try this is https://github.com/clara-parabricks/rapids-single-cell-examples/blob/master/notebooks/hlca_lung_gpu_analysis.ipynb

[lowener]

I ran TSNE on a few real-world datasets to observe the embeddings and the performance.

• From what I found, FFT has correct results. Not always better or worse than B-H.
• FFT is most of the time slower than Barnes-Hut when the number of iterations is lower than 1500. After that treshold, Barnes-Hut is slower than FFT.

I'll add here the results, starting with the dataset that you linked. (shape = (65462, 20))

[lowener]

On a Spotify dataset from Kaggle (link) with shape (2017, 8) and 500 iterations

[lowener]

On a Credit card fraud detection from Kaggle too (link) with multiple iterations choices. Shape=(3492, 30)

[cjnolet]

@lowener, these plots and benchmarks look great and it's nice to see the performance gap isn't prohibitively large between FFT and BH on these datasets. So long as they are converging in a reasonable number of iterations (which look to be similar-ish across BH and FFT), this could be evidence for supporting FFT as the default.

Ideally, before we officially promote FFT to a default, we should also address this concern (since these datasets don't seem to be showing such a signficant slowdown across differing numbers of iterations): #3865 (comment)

[zbjornson]

The runtimes for these examples are only a few seconds. When I benchmarked larger datasets that take between 30 seconds an 10 minutes a V100, FFT was between 1.3 and 2.2x faster than B-H.

Now that K-L divergence can be calculated, it would be cool to plot that over each iteration. The plot in #3058 is partly wrong, but exact, FFT and B-H all seemed to converge at different rates.

[cjnolet]

@zbjornson,

I fully agree we should be comparing larger datasets. It also looks like the early stopping was removed from barnes-hut at some point, which invalidates the benchmarks above. Out of curiosity, what datasets did you use for benchmarking?

[zbjornson]

@cjnolet I was using synthetic N-dimensional Gaussian blobs with between 4 and 50 dimensions, 100k and ~20M rows. I was using a fixed number of iterations without early stopping. (I have some concerns about the min grad norm for early stopping but haven't had time to dig into it yet.)

edit

Your comment here #4361 (comment)

While the FFT implementation is slower iteration for iteration

is the opposite of my observations.