Feat: return indicator vector from argmin and argmax

[b-kamphorst]

Adds the possibility to return an indicator vector from argmin and argmax rather than the index. The number of rounds is still logarithmic. Tests are included.

Core workings: keep track of the binary search to the maximum, then backtrack this path. Tests are included.

Additional improvement: _argmin was removed.

Note: A slightly simpler but less efficient version of this algorithm is also available, please let me know if you are interested.

[codecov-commenter]

Codecov Report

Merging #30 (7783330) into master (79106df) will increase coverage by 0.01%. The diff coverage is 95.55%.

@@            Coverage Diff             @@
##           master      #30      +/-   ##
==========================================
+ Coverage   90.20%   90.22%   +0.01%     
==========================================
  Files          15       15              
  Lines        5943     5963      +20     
==========================================
+ Hits         5361     5380      +19     
- Misses        582      583       +1     

Impacted Files	Coverage Δ
mpyc/runtime.py	89.07% <95.55%> (+0.07%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 79106df...7783330. Read the comment docs.

[b-kamphorst]

Temporarily marking as draft as I found a bug when a list of length 1 is provided.

[lschoe]

Thanks for the PR! So, let's discuss it a bit. Maybe first to check that you are really after a performance gain with this approach? A reasonably efficient solution can also be obtained by putting a, m = mpc.argmin(x); a = mpc.unit_vector(a, len(x)). In fact, this is the approach currently used in lpsolver.py for instance. And this replaced a direct method that computes the indicator vector in one go, which can still be found in older versions of the demos, like in MPyC v0.6, see lpsolver.py.

Also there the indicator vector is needed, for the location of the extreme. The round complexity of the overall approach is still logarithmic, but of course the concrete complexity gets worse.

Actually, looking at your solution I also wonder a bit if an explicit binary tree is needed. I would expect that this tree can be kept implicit by using a suitable recursion? And then still using like n-1 secure multiplications overall, n = len(x), to construct the indicator vector. That's what the method in the old version of lpsolver.py does. And recursion can also be avoided, like in mpyc.random.random_unit_vector() where the unit vector is generated in an iterative way, also using not more than n secure multiplications (which are even "organized" via mpc.scalar_mul() to make them less costly).

[b-kamphorst]

Hi @lschoe, apologies for the long wait. Busy end-of-the year times and we needed to dive deeper in your remarks.

Summary of the reflection. We feel that the approach a, m = mpc.argmin(x); a = mpc.unit_vector(a, len(x)), albeit very elegant, might incur more communication (rounds) than the MPyC v0.6 approach. Although one might discuss just how much a bottleneck that is, this is why we started another approach. Regardless, the MPyC v0.6 approach is indeed similar and perhaps better performing than this PR. In conclusion, I will close the PR.

Final thoughts. We much appreciate your time for reviewing the PR and drawing our attention to existing and prior solutions in MPyC. The best results are achieved through such interaction. Thank you for that!

For constructive feedback, we'd like to share that the delay on our end was for a bit caused by our difficulties in understanding the MPyC core code (how and why do runtime.unit_vector and MPyC v0.6 lpsolver.argmin work?). The implementations appear to be extremely efficiently programmed, but the non-informative names of the variables and eventual lack of (references to) documentation (containing proofs) made it harder on us to understand. This may be a personal preference, but nevertheless we thought you might be interested to know.

With that, I will actually close the PR, look forward to our next collaboration and wish you happy holidays!

[lschoe]

Hi @b-kamphorst, Thanks for your feedback, which is very much appreciated. Indeed by combining the work for computing the argmin and the unit_vector some savings can be made, as you have also demonstrated with your PR. And you are right that some of the code is rather (read: too) intricate. A basic explanation here and there is welcome, although I must also admit that I'm sometimes using these code fragments as exercises for students to prove correctness and security. Some food for thought for our traditional end-of-year lockdown;) Best wishes to you as well!!