Found a case where isotonic regression takes non-polynomial time

[neggert]

I discovered an edge case in the new Isotonic Regression algorithm introduced in #7444 that causes it to take non-polynomial time.

To reproduce, add a case to bench_isotonic.py:

def generate_alternating_dataset(size):
    x = np.asarray([yi  if i % 2 == 0 else yi - 1.5
                       for (i, yi) in enumerate(np.arange(size, 0, -1))])
    return x

I get this:

I suspect what happening is that it backtracks all the way to the beginning at each iteration. There's a similar problem in the Spark implementation that I'm working on over in apache/spark#15018.

[amueller]

@neggert do you have a suggested fix?

[neggert]

I don't have time to port it to scikit-learn myself (and my Cython is rusty), but someone is welcome to borrow the solution over at apache/spark#15018. It uses a lot of the ideas from #7444 anyway.

[Akshay0724]

Hello @amueller, Can I get this issue for start.Thanks

[Akshay0724]

I have studied both the algorithm i.e #7444 and apache/spark#15018.

The only difference I found that I think is possible for such a behavior is that in our implementation when a present active block is merged with next block, then we backtrack to the beginning if possible(i.e try to merge new block with all previous mergeable block iteratively).

While in implementation of apache/spark#15018 new block generated(after merging with next block) is merged with the block which is just previous to it if possible while all other previous block are not merged (even if they are mergeable), a violation introduced can be caught in next iteration. (Hence reducing the complexity)

I can try to implement the same in _isotonic.pyx to sort out this issue. Some pointers will be really helpful.Thanks

[kovarn]

I tested with the suggested data generator, and the complexity is actually linear. This is the output of the benchmark test

1000 0.000116
10000 0.0001815
100000 0.0016005
1000000 0.0180955
10000000 0.2129485
100000000 1.8207755

I couldn't find any problem with the source either.

[Micky774]

When trying to reproduce as suggested, I get this:

While the behavior does change for sample sizes around 1e4, it seems polynomial time for large enough sample sizes. For sample sizes of 1e4 and smaller it seems that the algorithm takes so little time that other sources of overhead contribute more to the actual variance in behavior.