where (denoting the current second best value of i by β),

$$\delta_{i}=\left\{\begin{array}{l l}{{\psi_{i v}+w_{\alpha v}-\psi_{i\beta}-w_{\alpha\beta}+\gamma_{\beta}}}&{{\beta\neq\alpha}}\\ {{}}&{{}}\\ {{\frac{1}{2}(\psi_{i v}+w_{\alpha v}-\psi_{i\alpha}-w_{\alpha\alpha}-\sum_{\beta\neq v}\gamma_{v})}}&{{\beta=\alpha}}\end{array}\right.$$

In spite of its simplicity, Golden Search suffers from a few drawbacks that come to light during experimentation. First, it always performs θ(log UB(v)) evaluations of L(γ**). This can drive up the overall runtime of the**
algorithm. Second, a change in γv affects the modified vertex potentials for values v and α **(Equation 32). Thus,**
a large change in γv may flip many vertices to α, causing a big change in the current assignment z**, and we**
may end up spending the next few iterations repairing these changes. Third, line search methods zero-in on the optima by evaluating the objective at various points and choosing a sub-interval accordingly. In our case, due to the integrality of z**, ties can happen at many places in an interval. In such a scenario, arbitrary tie resolution**
may cause a wrong sub-interval to be chosen for further consideration.

To tackle these issues, we use a more conservative coordinate descent approach, which we describe next and also use in our experiments.

## Conservative Coordinate Descent

We can avoid a large number of flips in the current assignment if we replace our golden search method with a more conservative one. Let v **be the worst violating value in the current iteration. We will first consider the case** when its count exceeds that of α**, so that Equation 34 does not hold.**
To decrease the count of v, we need to increase γv. Let i be a vertex currently assigned v and let β(i**) be**
its second most preferred value under the vertex potentials ψ α i
. The vertex j **= argmax**i:ziv=1ψ α iβ(i) − ψ α iv **is the**
easiest to flip. So we increase γv till the point when this difference becomes zero. The new value of γv **is therefore**
given by:

$$\gamma_{v}=\min_{i:z_{uv}=1}\left\{\begin{array}{ll}\Delta\psi(i,v,\beta(i))+\gamma_{\beta(i)}&\beta(i)\neq\alpha\\ \frac{1}{2}(\Delta\psi(i,v,\alpha)-\sum_{v^{\prime}\neq v}\gamma_{v^{\prime}})&\beta(i)=\alpha\end{array}\right.\tag{37}$$

where ∆ψ(i, v, v′) denotes ψiv + wαv − ψiv′ − wαv′ . It is possible that by flipping vertex j, β(j**) now violates**
Equation 34. Further, increasing γv **also increases** ψ α iα, so some other vertices that are not assigned v **may also**
move to α**. However since the change is conservative, we expect this behavior to be limited. In our experiments,** we found that this conservative scheme converges much faster than golden section over a variety of data.

We now look at the case when Equation 34 is satisfied by all values but Equation 35 is violated by some value v. In this scenario, we need to decrease γv **to decrease the magnitude of the violation. Here too, we** conservatively decrease γv barely enough to flip one vertex to v. If i is any vertex not assigned value v and β(i)
is its current value, then the new value of γv **is given by:**

$$\gamma_{v}=\max_{i\leq i\leq v\neq1}\left\{\begin{array}{ll}\Delta\psi(i,v,\beta(i))+\gamma_{\beta(i)}&\beta(i)\neq\alpha\\ \frac{1}{2}(\Delta\psi(i,v,\alpha)-\sum_{v^{\prime}\neq v}\gamma_{v^{\prime}})&\beta(i)=\alpha\end{array}\right.\tag{38}$$

Note that the arguments of Equations 37 and 38 are the same. In this case too, in spite of a conservative move, more than one vertex marked α **may flip to some other value, although at most one of them will be flipped to** v. As before, the small magnitude of the change restricts this behavior in practice.

## 7 Applications And Experiments

We present results of three different experiments.

First, in Section 7.1 we compare our clique inference algorithms against applicable alternatives in the literature. We compare the algorithms on speed and accuracy of the output assignments. For Potts potentials, we show that α**-pass is superior to the TRW-S and min-cut based algorithms. For** majority **potentials, we compare**
the modified α**-pass and Lagrangian relaxation based algorithms against the exact LP-based approach and the** iterated conditional modes (ICM) algorithm.