LocalMAP can cause an infinite loop

[jlmelville]

I have eagerly jumped on the opportunity to test out LocalMAP and to read the accompanying paper. Another very stimulating paper and congratulations to everyone involved.

I have managed to make LocalMAP with default parameters hang indefinitely on several datasets, including the 20NG dataset provided in the data folder of this repo (among others, COIL-100 was also affected).

Although I strongly doubt this bit matters, in the interest of full reproducibility, I grab the .npy file this way (after installing httpx):

from io import BytesIO

import httpx
import numpy as np
from pacmap import pacmap

url = "https://github.com/YingfanWang/PaCMAP/raw/master/data/20NG.npy"

response = httpx.get(url, follow_redirects=True, timeout=10)
response.raise_for_status()

ng20 = np.load(BytesIO(response.content))

And then I am able to reliably (but not 100% of the time) cause LocalMAP to hang indefinitely like this:

localmap = pacmap.LocalMAP(random_state=1337)
ng20_localmap = localmap.fit_transform(ng20)

I think the lack of complete reproducibility might be due to threading issues in the new LocalMAP routines: even when the run completes successfully, costs diverge after the first 200 iterations between runs using a fresh kernel and a fixed seed. I am using numba 0.60.0 and python 3.12.8 on WSL and the frequency of the hanging seems highly dependent on the random_state value.

At any rate, the hanging occurs in sample_FP_nearby, and is almost certainly due to the logic here:

PaCMAP/source/pacmap/pacmap.py

Lines 1129 to 1132 in 803b6cc

	if euclid_dist(Y[self_ind], Y[j]) > low_dist_thres:
	continue
	else:
	reject_sample = False

where an infinite loop will occur if none of the candidate distances exceed low_dist_thres. FWIW one solution would be to fill result with -1, set the while loop to terminate after a fixed number of iterations or failures, and then continue in the FP loop in pacmap_grad_nearby_recip_sqrt if j == -1. This fixes the problem for all the datasets I tried it on without affecting other datasets.

[hyhuang00]

Thank you for your interest in our work! I suspect the problem is due to the mismatch between v0.7.4, which is the previous version we used in the work, versus v0.7.6 in the current main branch. We're actively investigating this issue. Since this issue is LocalMAP-specific, I've also created a mirror in the LocalMAP repo and we will post our further response there.

[hyhuang00]

We've done some investigation on this issue and we managed to reproduce this error on our machines.

• The piece of code you mentioned is the culprit for the infinite loop, and @williamsyy has pushed a hotfix on the LocalMAP repo to fix this issue. The new version will re-use the old FP pairs in case the sampling fail after certain number of rounds.
• The issue seems to be related with hardware specifications as well as other factors such as the random seeds. We didn't implement deterministic features for the LocalMAP, so there might be some randomness in the output even if the seed was fixed, due to pair sampling in the second stage. On our experiment bench, we encountered far less "bad" random seeds and didn't reproduce the divergence of the loss, either with Python 3.11 or 3.12. However, we found a larger amount of "bad" random seeds when running on an older machine. I suspect this is the reason that this problem was neglected during our experiments.

[jlmelville]

I've tested on the latest master and LocalMAP now completes with all datasets I have tried.

Many thanks for such fast work. Happy holidays.