Enabling k-binary search for GPU-use

[AWbosman]

Background

In the original work proposing robustness distributions, we introduced an adapted version of binary search called k-binary search (k-bin).
The motivation behind k-bin was to allow verification queries to run in parallel and exchange information between nodes, improving efficiency.

However, after extensive testing, we were unable to get k-bin to function correctly on GPU. As a result, later work reverted to using standard binary search, and k-bin is currently not available in VERONA.

Problem

The main challenge we faced was GPU communication:

• When one GPU node finished a verification query, its results needed to be communicated to other nodes.
• If the information was relevant, the other nodes’ queries had to be terminated early.
• This early termination led to lag and various bugs that we could not resolve at the time.

Because of these issues, GPU execution of k-bin was abandoned.

Proposal

It would be valuable to reintroduce k-binary search with proper GPU support.
Specifically, this would involve:

• Enabling GPU nodes to exchange information efficiently.
• Ensuring safe and lag-free termination of ongoing queries when a result makes them redundant.

The relevant part of the codebase is:
robustness_experiment_box/epsilon_value_estimator

Who Might Be Interested

This issue may be best suited for someone with experience in GPU communication, distributed systems, or PyTorch multiprocessing.

Benefits

• Restores functionality from the original robustness distribution proposal.
• Improves efficiency of epsilon estimation compared to plain binary search.
• Opens up new experimental possibilities within VERONA.

[henba1]

We need a framework that starts multiple jobs with a varying parameter (epsilon) in parallel and if a certain return condition is met, we stop the jobs.

Idea: use Hydra and Ray (need to research this more). The jobs need to be able to inform each other and it should be relatively easy to set up.