We were discussing the MicrosoftML rxFastLinear algorithm which is a fast linear model trainer based on the Stochastic Dual Coordinate Ascent method. It combines the capabilities of logistic regressions and  SVM algorithms. The algorithm implements an optimization associated with the regularized loss minimization  of linear predictors. The approach for solving SVM is usually stochastic gradient descent. This method uses dual coordinate descent. Here the objective is framed as a maximization in terms of a dual variable associated with each example in the training set. In each iteration, a single dual variable is optimized while keeping the rest in tact.  At the optimal solution the objective is known, so we have a duality gap which helps us put an upper bound on the sub-optimality. The method is stochastic and at each round of the iteration, a dual coordinate is chosen at random
The paper provides the rigor to understand the convergence of the duality gap for Stochastic Dual Coordinate Ascent (SDCA). They performed experiments involving randomization which improved the analysis performed earlier. They derived the rate of convergence for SDCA with two types of loss functions - Lipschitz loss and Smooth loss.
This technique of calculating the duality gap at few random points leads to the same type of guarantee with high probability as averaging In fact this this technique now has advantage over averaging because the stopping criteria is easier to implement. The duality gap is checked at some random points and the iterations are terminated when it is sufficiently small.  The number of iterations and the iteration at which to calculate averaging are no longer required.  This theorem assumes that all the linear predictors are normalized. Further, all the sequence of scalar functions evaluate to non-negative values. And this theorem also assumes that all the scalar functions have initial values less than one. By using parameters for the number of iterations just for illustration, this technique now bounds the total number of iterations In the averaging option, we needed to set the number of iterations up front and the iteration, usually midpoint, at which the averaging is done. This is no longer needed because the convergence is now done with the same type of guarantee.
#codingexercise
Find four elements in an integer array such that a+b = c+d
bool GetPairs(List<int>A)
{
var h = new Hashtable();
for (int i = 0; i < A.Count; i++)
  for (int j = 0; j < A.Count; j++)
  {
      int sum = A[i] + A[j];
      if (h.Contains(sum)){
            Console.WriteLine("{0} {1} {2} {3}",h[sum].first, h[sum].second, i, j);
            return true;
      }else{
         h.Add(sum, new Tuple<int, int>(){i,j});
      }
   }
return false;
}
codingexercise: http://collabedit.com/sghvg