could snapvx handle global variables?

[DanqingZ]

I have a decision variable that is shared among all all nodes. like below code:

W = Variable(3,name='W')
for i in range(500):
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx.SetNodeObjective(i, Objective=obj)

Then I gave got a error concerning shared variables.

Exception: Objective at NId 1 shares a variable.

wondering how snapvx handle this shared variables problem. Thanks!

[DanqingZ]

Found this link. umm, I can handle the problems where I can list all constraints with known node variables like x1,x2,x3...but I am stuck on my current code to add constraints.

[davidhallac]

Yes, exactly, you'll need to use constraints to share the variable. For example, if 2 nodes share a W variable, you let node 1 have a variable W1 and node 2 have a variable W2, and then at the edge you set the constraint that W1 = W2. So the code would look something like:

gvx.SetEdgeObjective(i,j, Objective = L1*norm(x1 - x2)
gvx.SetEdgeConstraints(i,j, Constraints = [W1 = W2]).

[DanqingZ]

This is the current code I have, but stuck on the step how to add objectives and constraints of edges through a loop, also posted on another issue but that issue is closed, so I copy and paste here

num_nodes = 500
temp = GenRndDegK(num_nodes, 3)
gvx2= TGraphVX()

for i in range(500):
    W = Variable(3,name='W')
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx2.AddNode(i, Objective=obj)

L1 = 0.02
for EI in temp.Edges(): 
    count = count +1
    if count % epoch ==0:
        print "edge (%d, %d)" % (EI.GetSrcNId(), EI.GetDstNId())
    a = EI.GetSrcNId()
    b = EI.GetDstNId()
    gvx2.AddEdge(a,b,Objective=L1*norm(a['b']-b['b']),Constraints=[a['W']=b['W']])


edges = []
for EI in temp.Edges(): 
    count = count +1
    if count % epoch ==0:
        print "edge (%d, %d)" % (EI.GetSrcNId(), EI.GetDstNId())
    edges.append([EI.GetSrcNId(), EI.GetDstNId()])

count = 0
for i in range(500):
    if [i,i+1] not in edges and [i+1,i] not in edges:
        count +=1
        j = i+1
        gvx2.AddEdge(i,j,Constraints=[i['W']=j['W']])

print count

[DanqingZ]

when I just have the node_id, I do not know how to get node variables to use them in edge objectives and edge constraints. That is exactly my question.

[DanqingZ]

My above code obviously has error since node_ids are just integer than a class.

[DanqingZ]

Look foward to something like below code:

def laplace_reg(src, dst, data):
    return (L*norm(src['x'] - dst['x']), [])

gvx.AddEdgeObjectives(laplace_reg)

[DanqingZ]

I have got another implementation, but again...I have to force W on all nodes equal, so I still have the above problem for adding constraints that "W" on all nodes are equal.

gvx3 = TGraphVX(temp)

for i in range(500):
    W = Variable(3,name='W')
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx3.SetNodeObjective(i, Objective=obj)

def laplace_reg(src, dst, data):
    return (norm(src['b'] - dst['b']), [src['W'] == dst['W']])
gvx3.AddEdgeObjectives(laplace_reg)

for i in range(500):
    if [i,i+1] not in edges and [i+1,i] not in edges:
        j = i+1
        gvx3.AddEdge(i,j,Constraints=[i['W']=j['W']])

[DanqingZ]

Even for my current running code, that I only force "W" on connected edges equal, it seems to takes a very very long time each iteration(almost 30 minutes for 2 iterations), I currently have 500 nodes for the graph

gvx3.Solve(Verbose=True, Rho=0.1)

Distributed ADMM (4 processors)
Iteration 1
...

[davidhallac]

See my comment on (#19) for how to access the node variable given just the ID name.

Hmm, it takes 15 minutes per iteration? That is way too long... One thing that should speed it up significantly is that the way you are adding consensus edges ends up behaving quite slowly (since it's a chain graph). What you could do is add a "dummy node", call it node 501, with objective = 0, variable = W, and then add 500 different edges, from 501 to each of the nodes in 1 to 500, such at i['W'] = j['W']. Does that make sense? If not, I can help by writing some pseudocode for how it would work

[DanqingZ]

I will first try this "dummy node" method, and I will report it here if it is still too slow.

[davidhallac]

Ok sounds great, thanks!

[DanqingZ]

I takes around 2 hours to finish running my current code. And well I guess the constraints are not perfectly met for ADMM?

for ni in gvx3.Nodes():

    n_id=ni.GetId()

    count += 1

    if n_id< num_nodes:

        nodes.append(list(gvx3.GetNodeValue(n_id,'W')))

        print gvx3.GetNodeValue(n_id,'W')

[-0.93490258 -1.06014059 -1.10749516]
[-1.09831406 -1.13666708 -0.91840317]
[-1.06936111 -1.02778103 -1.09265889]
[-0.97509732 -1.01286559 -0.9661932 ]
[-1.01876936 -0.98791517 -1.13132814]
[-1.00945953 -0.98719882 -0.99396125]
[-0.97556013 -0.94569544 -1.08815447]
[-1.05924329 -0.96876215 -0.99126286]
[-1.04988142 -0.98938958 -1.05924281]

[davidhallac]

That could be due to convergence criteria not being strict enough, which would make all the W's agree with each other, but would slow down the runtime... Hopefully the dummy node method can fix that

[DanqingZ]

umm, how to say. What I am intending to do is that : I have both global variables and local variables at the node objectives. I understand I can make these global variables local and make them equal to each other....but I am thinking whether this also slow down the program.

My mistake, I guess I should use "global variable" instead of "shared variables" here.

[DanqingZ]

I will first try this method out and report it later! :)

[DanqingZ]

looks it takes even more time when I use the "dummy node method", the kernel automatically died....

gvx3 = TGraphVX(temp)


# In[26]:

for i in range(500):
    W = Variable(3,name='W')
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx3.SetNodeObjective(i, Objective=obj)


# In[29]:

W = Variable(3,name='W')
b = Variable(1,name='b')
gvx3.AddNode(500,Objective=W-W)


# In[31]:

for i in range(500):
    node1 = gvx3.GetNodeVariables(i)
    node2 = gvx3.GetNodeVariables(500)
    gvx3.AddEdge(i,500,Constraints=[node1['W']==node2['W']])


# In[ ]:

gvx3.Solve(Verbose=True, Rho=0.1)

[davidhallac]

One thing that pops out is at "# In[29]", you're setting the objective for node 500 to be equal to "W - W", which is a 3-dimensional vector (even though it's all zero's...). In CVXPY syntax, the objective must resolve to a scalar.

You can quickly fix that by replacing "Objective=W-W" with "Objective=norm(W-W)". Let me know if that fixes things

[DanqingZ]

oops, that's right, I have changed Objective to norm(W-W), running the code now.

[DanqingZ]

unfortunately, the kernel died again...

[davidhallac]

I just tried running it on my setup, and it seems to have something to do with the fact that there is no objective defined on the consensus edges. (SnapVX sometimes acts weirdly if no objective is defined). So you could create a dummy objective like before, replacing

"gvx3.AddEdge(i,500,Constraints=[node1['W']==node2['W']])"

with

"gvx3.AddEdge(i,500,Objective=(norm(node1['W'] - node1['W'])),Constraints=[node1['W']==node2['W']])"

[DanqingZ]

David, I found that when I use the AddEdge method to solve this problem.I cannot even see ADMM getting started, since when I run other models, I can see below:

Distributed ADMM (4 processors)
Iteration 1

[davidhallac]

I'm a bit confused about what do you mean. Did the AddEdge method work before, or did it just break when you added the objective line? More specifically, what's the exact code that you used that caused the "Distributed ADMM" method to not even show up?

[DanqingZ]

This works

gvx3 = TGraphVX(temp)

for i in range(500):
    W = Variable(3,name='W')
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx3.SetNodeObjective(i, Objective=obj)

def laplace_reg(src, dst, data):
    return (norm(src['b'] - dst['b']), [src['W'] == dst['W']])
gvx3.AddEdgeObjectives(laplace_reg)

And this cause "Distributed ADMM" not show up:

gvx3 = TGraphVX(temp)


# In[26]:

for i in range(500):
    W = Variable(3,name='W')
    b = Variable(1,name='b')
#     obj = logistic(-y[i]*x.T*A[i,:])
    obj = logistic(A[i,:].T*W+b-y[i])
    gvx3.SetNodeObjective(i, Objective=obj)


# In[29]:

W = Variable(3,name='W')
b = Variable(1,name='b')
gvx3.AddNode(500,Objective=norm(W-W))


# In[31]:

for i in range(500):
    node1 = gvx3.GetNodeVariables(i)
    node2 = gvx3.GetNodeVariables(500)
    gvx3.AddEdge(i,500,Objective=(norm(node1['W'] - node1['W'])),Constraints=[node1['W']==node2['W']])


# In[ ]:

gvx3.Solve(Verbose=True, Rho=0.1)

So I am thinking there might be something strange with AddEdge.

[davidhallac]

Hmm, for now I'd just recommend going with the first method, since that seems to work. I'm not sure why the dummy node method is not working (I'll try to work it down to the simplest example where it breaks and debug exactly what's going on in the code when that happens...).

The first method will be slower, but it should at least converge to the right answer. I know earlier you said that the method did not exactly converge, but you can fix that with stricter convergence criteria parameters (eps_abs and eps_rel) when you call solve. They default to 10e-2, but you could set them both to 10e-3 or 10e-4, which will take longer but be more accurate.

[DanqingZ]

I am thinking maybe W should be global instead of local, so that each iteration of ADMM, I also update W based on b,z,u, but for dual variable update, it is has nothing to do with W, since W is not in the linear constraints. I am going through your network lasso implementation to try to implement it myself 🔢

[davidhallac]

Yes, you're 100% correct. If you could combine SnapVX with some global solver, that would work best in terms of scalability. Global variables are not something we currently support in SnapVX, but I'd be curious to see how it performs. If you have any questions about the Network Lasso implementation, please let us know.