Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

algo updates #10

Merged
merged 4 commits into from
Dec 22, 2022
Merged

algo updates #10

merged 4 commits into from
Dec 22, 2022

Conversation

plusk01
Copy link
Member

@plusk01 plusk01 commented Aug 26, 2022

  • gradF update: After the most recent optimizations, the gradF update was
    missing using the gradFnew calculated in the line search. From what I
    can tell, this fix created no appreciable difference, but values are now
    aligned with the MATLAB implementation.

  • d steps: changed the update strategy for d steps from using the min
    (which meant that no elements of the u vector would need to be projected
    back onto the pos orthant) to using the mean step (which means half of
    the elements will have to be projected onto the pos orthant). This seems
    to have produced a significant (2-4x) speedup on the bunny benchmark,
    with no change on accuracy -- see report below.

  • recale_u0: new parameter added to turn on / off the initial power method step to rescale u0. This does not seem to make an appreciable difference on bunny benchmark.


this version

Benchmarking over 20 trials

Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:44s]

+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0     | 64      |  0.19  ±  0.0 |      0.06  ±  0.0 | 100           | 90         |
| 0     | 256     |  1.05  ±  0.0 |      0.63  ±  0.0 | 100           | 89         |
| 0     | 512     |  3.95  ±  0.1 |      2.41  ±  0.0 | 100           | 89         |
| 0     | 1024    | 15.64  ±  1.0 |      9.86  ±  0.1 | 100           | 89         |
| 0     | 2048    | 94.63  ±  1.4 |     32.53  ±  0.4 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 20    | 64      |  0.20  ±  0.0 |      0.06  ±  0.0 | 100           | 90         |
| 20    | 256     |  1.88  ±  3.9 |      0.63  ±  0.1 | 99            | 89         |
| 20    | 512     |  3.69  ±  0.1 |      2.35  ±  0.4 | 100           | 89         |
| 20    | 1024    | 14.84  ±  0.6 |     13.51  ±  6.3 | 99            | 89         |
| 20    | 2048    | 85.49  ±  1.5 |     59.20  ± 46.9 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 40    | 64      |  0.19  ±  0.0 |      0.04  ±  0.0 | 100           | 90         |
| 40    | 256     |  1.00  ±  0.1 |      0.42  ±  0.1 | 100           | 89         |
| 40    | 512     |  3.46  ±  0.1 |      1.58  ±  0.4 | 100           | 89         |
| 40    | 1024    | 13.77  ±  0.4 |      9.27  ±  3.6 | 99            | 89         |
| 40    | 2048    | 71.14  ±  1.1 |     55.42  ± 27.5 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 80    | 64      |  0.29  ±  0.5 |      0.05  ±  0.0 | 100           | 91         |
| 80    | 256     |  0.89  ±  0.0 |      0.44  ±  0.1 | 100           | 89         |
| 80    | 512     |  3.22  ±  0.1 |      1.62  ±  0.3 | 99            | 90         |
| 80    | 1024    | 12.54  ±  0.1 |      5.71  ±  1.3 | 99            | 90         |
| 80    | 2048    | 66.70  ±  0.5 |     24.55  ± 15.5 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 90    | 64      |  0.18  ±  0.0 |      0.05  ±  0.0 | 100           | 90         |
| 90    | 256     |  0.95  ±  0.3 |      0.38  ±  0.1 | 99            | 90         |
| 90    | 512     |  3.17  ±  0.1 |      1.44  ±  0.5 | 99            | 90         |
| 90    | 1024    | 12.37  ±  0.1 |      6.12  ±  1.7 | 99            | 90         |
| 90    | 2048    | 66.18  ±  0.3 |     27.09  ± 10.1 | 99            | 90         |
+-------+---------+---------------+-------------------+---------------+------------+

previous version

Benchmarking over 20 trials


Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:54s]                                                                                                                           

+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0     | 64      |  0.20  ±  0.0 |      0.06  ±  0.0 | 100           | 90         |
| 0     | 256     |  1.12  ±  0.3 |      0.63  ±  0.3 | 100           | 89         |
| 0     | 512     |  4.37  ±  2.0 |      2.12  ±  0.9 | 100           | 89         |
| 0     | 1024    | 16.27  ±  2.8 |     10.21  ±  4.6 | 100           | 89         |
| 0     | 2048    | 94.61  ±  2.4 |     43.25  ± 19.7 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 20    | 64      |  0.19  ±  0.0 |      0.15  ±  0.0 | 100           | 89         |
| 20    | 256     |  1.02  ±  0.1 |      2.00  ±  0.5 | 100           | 89         |
| 20    | 512     |  3.81  ±  0.7 |      8.84  ±  1.9 | 100           | 89         |
| 20    | 1024    | 14.63  ±  0.6 |     44.83  ± 17.2 | 100           | 89         |
| 20    | 2048    | 84.86  ±  0.9 |    223.11  ± 63.0 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 40    | 64      |  0.28  ±  0.4 |      0.15  ±  0.0 | 100           | 89         |
| 40    | 256     |  0.99  ±  0.2 |      1.81  ±  0.3 | 99            | 89         |
| 40    | 512     |  3.51  ±  0.1 |      7.50  ±  1.8 | 100           | 89         |
| 40    | 1024    | 13.88  ±  1.0 |     32.58  ±  7.6 | 99            | 89         |
| 40    | 2048    | 71.31  ±  1.0 |    192.51  ± 44.8 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 80    | 64      |  0.18  ±  0.0 |      0.11  ±  0.0 | 100           | 91         |
| 80    | 256     |  0.93  ±  0.1 |      1.11  ±  0.2 | 99            | 89         |
| 80    | 512     |  3.20  ±  0.1 |      4.01  ±  0.7 | 99            | 90         |
| 80    | 1024    | 12.61  ±  0.2 |     18.62  ±  4.3 | 99            | 89         |
| 80    | 2048    | 67.52  ±  1.5 |     87.97  ± 15.6 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 90    | 64      |  0.18  ±  0.0 |      0.13  ±  0.0 | 99            | 91         |
| 90    | 256     |  0.90  ±  0.0 |      1.08  ±  0.2 | 99            | 91         |
| 90    | 512     |  3.24  ±  0.1 |      3.76  ±  0.5 | 99            | 90         |
| 90    | 1024    | 12.44  ±  0.1 |     16.57  ±  3.9 | 100           | 90         |
| 90    | 2048    | 66.41  ±  0.4 |     77.50  ± 15.0 | 99            | 90         |
+-------+---------+---------------+-------------------+---------------+------------+

gradF update: After the most recent optimizations, the gradF update was
missing using the gradFnew calculated in the line search. From what I
can tell, this fix created no appreciable difference, but values are now
aligned with the MATLAB implementation.

d steps: changed the update strategy for d steps from using the min
(which meant that no elements of the u vector would need to be projected
back onto the pos orthant) to using the mean step (which means half of
the elements will have to be projected onto the pos orthant). This seems
to have produced a significant (2-4x) speedup on the bunny benchmark,
with no change on accuracy -- see report below.

---

Benchmarking over 20 trials

Benchmarking ρ = 90% [██████████████████████████████████████████████████] 100% [00m:44s]

+-------+---------+---------------+-------------------+---------------+------------+
| ρ [%] | # assoc | affinity [ms] | dense clique [ms] | precision [%] | recall [%] |
+-------+---------+---------------+-------------------+---------------+------------+
| 0     | 64      |  0.19  ±  0.0 |      0.06  ±  0.0 | 100           | 90         |
| 0     | 256     |  1.05  ±  0.0 |      0.63  ±  0.0 | 100           | 89         |
| 0     | 512     |  3.95  ±  0.1 |      2.41  ±  0.0 | 100           | 89         |
| 0     | 1024    | 15.64  ±  1.0 |      9.86  ±  0.1 | 100           | 89         |
| 0     | 2048    | 94.63  ±  1.4 |     32.53  ±  0.4 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 20    | 64      |  0.20  ±  0.0 |      0.06  ±  0.0 | 100           | 90         |
| 20    | 256     |  1.88  ±  3.9 |      0.63  ±  0.1 | 99            | 89         |
| 20    | 512     |  3.69  ±  0.1 |      2.35  ±  0.4 | 100           | 89         |
| 20    | 1024    | 14.84  ±  0.6 |     13.51  ±  6.3 | 99            | 89         |
| 20    | 2048    | 85.49  ±  1.5 |     59.20  ± 46.9 | 100           | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 40    | 64      |  0.19  ±  0.0 |      0.04  ±  0.0 | 100           | 90         |
| 40    | 256     |  1.00  ±  0.1 |      0.42  ±  0.1 | 100           | 89         |
| 40    | 512     |  3.46  ±  0.1 |      1.58  ±  0.4 | 100           | 89         |
| 40    | 1024    | 13.77  ±  0.4 |      9.27  ±  3.6 | 99            | 89         |
| 40    | 2048    | 71.14  ±  1.1 |     55.42  ± 27.5 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 80    | 64      |  0.29  ±  0.5 |      0.05  ±  0.0 | 100           | 91         |
| 80    | 256     |  0.89  ±  0.0 |      0.44  ±  0.1 | 100           | 89         |
| 80    | 512     |  3.22  ±  0.1 |      1.62  ±  0.3 | 99            | 90         |
| 80    | 1024    | 12.54  ±  0.1 |      5.71  ±  1.3 | 99            | 90         |
| 80    | 2048    | 66.70  ±  0.5 |     24.55  ± 15.5 | 99            | 89         |
+-------+---------+---------------+-------------------+---------------+------------+
| 90    | 64      |  0.18  ±  0.0 |      0.05  ±  0.0 | 100           | 90         |
| 90    | 256     |  0.95  ±  0.3 |      0.38  ±  0.1 | 99            | 90         |
| 90    | 512     |  3.17  ±  0.1 |      1.44  ±  0.5 | 99            | 90         |
| 90    | 1024    | 12.37  ±  0.1 |      6.12  ±  1.7 | 99            | 90         |
| 90    | 2048    | 66.18  ±  0.3 |     27.09  ± 10.1 | 99            | 90         |
+-------+---------+---------------+-------------------+---------------+------------+
@plusk01 plusk01 merged commit b66b329 into main Dec 22, 2022
@plusk01 plusk01 deleted the algo-updates branch December 22, 2022 15:56
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

1 participant