Difference between `UseADMM=False` and `UseADMM=True`

[bkj]

I'm getting very different results w/ UseADMM=True vs UseADMM=False on a fairly small problem -- wondering if someone here might be able to help me understand the source of the difference.

import numpy as np
from snapvx import *

# --
# Random signal

np.random.seed(123)
y = np.cumsum(np.random.normal(0, 1, 500))

# --
# Construct graph

snap_graph = PUNGraph.New()
_ = [snap_graph.AddNode(i) for i in range(len(y))]
for i in range(1, len(y) - 1):
    _ = snap_graph.AddEdge(i - 1, i)
    _ = snap_graph.AddEdge(i, i + 1)

# --
# Set up optimization problem

gvx = TGraphVX(snap_graph)
X = []
for i in range(len(y)):
    x = Variable(1, name='x')
    gvx.SetNodeObjective(i, norm(x - y[i]))
    X.append(x)

def edge_objective(src, dst, data):
    return 10 * norm1(src['x'] - dst['x']), []

gvx.AddEdgeObjectives(edge_objective)

gvx.Solve(UseADMM=False, Verbose=True) # .. or True ..
X = np.vstack([np.asarray(x.value).squeeze() for x in X])

_ = plt.plot(X[:,0])
_ = plt.plot(y)
plt.show()

With UseADMM=False, I get the following results in ~ 1 second:

With UseADMM=True, it runs for ~ a minute and returns:

The former is much closer to what I was expecting than the latter. Any thoughts on what's going on here? The graph is just a chain -- is that some kind of extreme case for the ADMM solver?

Thanks

[davidhallac]

Yes, a chain graph is an extreme case and the absolute "worst" graph configuration for SnapVX. This is due to the underlying ADMM algorithm, which diffuses information between neighbors in the graph at each step. This takes n-1 steps (for n total nodes) to go from one edge of the chain to another, which means it often takes a long long time to converge. So UseADMM=True will almost always be slower than a serialized solution (aka: UseADMM=False) on chain graph problems.

I think the different solutions between the two is because of the stopping criteria in SnapVX being too lenient (when UseADMM = True). If you replace "gvx.Solve(UseADMM=False, Verbose=True)" with "gvx.Solve(UseADMM=False, Verbose=True, epsAbs = 0.001, epsRel = 0.001)", then the solutions should be much more closely matched, though it will unfortunately take even longer to converge than before...

[bkj]

OK -- makes sense. Thanks!