1
$\begingroup$

Let's say we're solving a regression problem where $X$ is an $n \times p$ matrix, $Y$ is $n \times 1$, and $\beta$ is $p \times 1.$

Then if we use the naive approach to solving the least squares problem, $\hat{\beta} = (X^{T}X)^{-1}X^{T}y$, the complexity is $O(np^2 +p^3 + np + p^2)$ if we use Cholesky decomposition to compute the inverses.

But what does this actually mean? Can I simulate some data, solve the least squares problem, and confirm this result numerically by looking at how long the function took to run?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

Yes, you can actually fit polynomial functions to run time of the numerical algorithms. However, you'll have to take into account parallelization and properties of the particular library that is being used.

Here's an example with polynomial fit to the execution time, which is proportional to complexity and computing power of my laptop:

enter image description here

Here's a code for p=1000 to 10000:

mport numpy as np
import time
s = 0
times = np.ones(10)
A=np.random.uniform(0,1,(10000,10000))
B=np.matmul(np.transpose(A),A)

for i in range(10):
    t0 = time.time()
    s += np.linalg.cholesky(B[0:(i+1)*1000,0:(i+1)*1000])[0,0]
    t = time.time() - t0
    times[i] = t
    print(t)
print(s)

x = range(0,10)
p = np.poly1d(np.polyfit(x,times,3))
print(p)
plt.plot(x, times, '.', x, p(x), '-')
plt.show()

Output:

         3           2
0.01443 x - 0.05016 x + 0.3148 x - 0.04357
Improve this answer
$\endgroup$
2
$\begingroup$

You need to distinguish between worst case complexity and average case complexity.

When speaking of NP-Complete, NP-hard, etc... people are usually referring to worst case complexity, which can only be confirmed theoretically by coming up with a proof of the algorithm's complexity class.

Average case complexity on the other hand is frequently confirmed empirically (i.e. by running simulations). I've seen many papers on optimization and search methods which propose a new algorithms and validate their proposed approach by comparing its average complexity to the average complexity of other algorithms - even if the problem is theoretically NP-hard or NP-complete.

By this is usually done for intractable problems - your problem seems to be polynomial, which are considered "easy" from complexity point of view, so why are concerned with it's complexity?

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'm just using regression because it's an example that's easy to understand. $\endgroup$
    – user9685396
    Commented Apr 23, 2018 at 17:05
  • $\begingroup$ The distinction between various orders of polynomials can definitely be of concern in a practical context, to say otherwise just because there exist problems that don't have a polynomial complexity solution is a bit ridiculous. $\endgroup$
    – Chris Haug
    Commented Apr 23, 2018 at 18:08
  • $\begingroup$ @ChrisHaug I'm just regurgitating what I read in theoretical CS class. Can you point me to a real world problem where a polynomial time algorithm, say of complexity $O(n^4)$ took too long and we needed to find an algorithm that run in $O(n^2)$ that couldn't be simply solved by increasing memory and/or number of CPUs? $\endgroup$
    – Skander H.
    Commented Apr 23, 2018 at 18:14
  • $\begingroup$ @Alex, if your problem is $O(n)$, then to tackle 10 times larger problem you need 10 times more power, the same for $O(n^2)$ problem will be 100 times more CPUs. So, yes, increasing the CPU power works always, the question is by how much? $\endgroup$
    – Aksakal
    Commented Apr 23, 2018 at 18:41
  • $\begingroup$ @Alex You don't really have to look further than the above regression example: the closed-form solution is of polynomial order in the number of features, so why does anyone use SGD to solve the same problem when they have thousands of features? Because it matters and computers aren't free. $\endgroup$
    – Chris Haug
    Commented Apr 24, 2018 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.