Cvxpy consuming several gigabytes of memory

[Behzad Tabibian]

Hi,

I am trying to understand the behavior of cvxpy vstack. I have a model for a collection of documents which for every document, d, there are several items, i, each of them indexes into a cvx variable vector, S. In my python implementation I iterate over documents, call cvxpy vstack to collect all the relevant variables from vector S. Running it for 10 documents each with a few thousands of items and vector S of size about 1000 consumes several Gigabytes of memory. This happens before cvxpy calls ECOS so I assume this is because of how the expression tree is constructed and I believe this is because of how vstack works. Can someone help me understand why a model a vectorized model could expand into several Gigabytes?

Thanks for your help,

Behzad

[Steven Diamond]

I'm not sure I understand what you're doing. Are you saying that you create a variable 

S = Variable(1000)

then you call vstack(S1,...,Sk) where S1,..,Sk are of the form S[i] for some i? If so, what is the size of k?

[Behzad Tabibian]

Hi,

Thanks for your reply.

You are correct. The size of S is about 10K and k can be as large as 10K too, but number of unique values of k is about 500.

Best,

Behzad

[Behzad Tabibian]

Hi,

Here is a code snippet of what I am doing:

There are 2 items in my run. The shape of sites variable in every iteration is about 10K and size of cvx variables pi and alpha is 500x1.

for item in items:
    sites = item[0]
    tDiff = item[1]
    d = item[2]
    t = item[3]
    tDiff_cdf = item[4]
    survived = item[5]
    if tDiff_cdf.shape[0] == 0:
      continue
    beta_d = tDiff_cdf*beta_temp[d,:].T
    sites_pi = cvx.vstack(*[pi[i] for i in sites])
    sites_alpha = cvx.vstack(*[alpha[i] for i in sites])
    loglikelihood += cvx.sum_entries(cvx.log(sites_pi[:survived])+
                                       cvx.log(sites_alpha[:survived]+t[:survived]*beta_temp[d,:].T)
                                       -(cvx.mul_elemwise(tDiff[:survived],sites_alpha[:survived])+beta_d[:survived]))
    loglikelihood += cvx.sum_entries(cvx.log(sites_pi[survived:]) \
    -(cvx.mul_elemwise(tDiff[survived:], sites_alpha[survived:])  +beta_d[survived:]))

Best,

B.

[Steven Diamond]

Does the memory use decrease after ECOS starts running? Or is it still using gigabytes of memory.

The algorithm cvxpy uses to generate the problem representation for the solver doesn't work super well with indexing, especially indexing into large variables. It creates a lot of temporary matrices, which use memory proportional to the size of the full variable for each indexed entry.

If this is a big issue, you should avoid indexing individual entries as much as possible. Try replacing indexing and vstack with multiplication by a sparse matrix that selects all the entries at once.

[Behzad Tabibian]

Thanks for your reply.

Yes the memory size decreases after ECOS starts.

I will try with that solution.

Best,

Behzad 

[Behzad Tabibian]

Hi Steven,

I just ran my model with a sparse matrix instead of cvx vstack and gained Huge improvement. I was wondering what might be the reason vstack has such a huge impact on performance and would be interested to fix it if you could point me in right direction. I assume any call to vstack can be replaces with product of a sparse matrix and original variables(s).

[Steven Diamond]

It's a bit complicated. The algorithm that CVXPY uses is described in the "Sparse matrix representation" appendix of this paper (http://stanford.edu/~boyd/papers/pdf/abs_ops.pdf). The algorithm in the paper is for a DAG whereas everything in CVXPY is a tree, but the idea is the same.

Basically each linear operator is replaced with multiplication by a sparse matrix, and then the tree is reduced to a sum of variables A_1x_1 + A_2x_2 + ...

The reason this uses so much memory is that every indexing and vstack operation yields a sparse matrix.

I've thought about different ways to improve this. The most obvious is to do simplifications of the expression tree before running the algorithm. For example, vstack(x[2],x[1],x[3]) could be reduced to a generalized slice that selects entries 2, then 1, then 3 from x. This sort of slicing should be supported for the user as well, and might help a lot with your case.

I'd be very interested in any ideas you have.

[Behzad Tabibian]

Hi,

Thanks for your reply. Can you elaborate a little bit how for example vstack(x[2],x[1],x[3]) gets expanded? 

From what you said, I get that x[2] is replaced with multiplication of a sparse matrix and vector x. What happens next? One idea I was thinking was to merge sparse matrices as we find it possible to do. This can start with merging matrices that are in the sum, i.e if two terms involve x, their correspond sparse matrices get summed.

B.

[Steven Diamond]

That's an excellent idea. The coefficients for each x[i] are not being summed ever in the algorithm, which explains why the total memory usage grows so large. I'll make this change to the code.

[Behzad Tabibian]

Great,

Let me know when it is done and I can test it with my code.