Today we continue discussing the DMB algorithm from the paper titled optimal distributed online prediction using mini-batches by Dekel, Gilad-BachRach, Shamir and Xiao. One of the theorems they propose is one that bounds the expected regret over m samples.
The theorem is stated this way : Let f(w,z) be an L-smooth convex loss function in w for each input in the stream and assume that the stochastic gradient (Big-Delta) computed at the input zi has a std deviation squared variance for all predictions. If the update rule phi has the serial regret bound Psi as a function of this variance and m, then the expected regret of the algorithm over m samples is at most
(b + mu) times Psi as a function of ( std dev squared  / b and upper ceiling of m / (b+mu)).

Specifically if Psi is a function as 2 D -squared L + 2 D std dev square-root(m) which was established earlier as the bound in the ideal serial solution and we set the batch size as b = m power rho for any rho in the range 0 to half, the expected regret bound is 2 D sigma sq.rt(m) + sigma sq.rt(m)
This bound is asymptotically equal to the ideal serial bound and even the constants in the dominant terms are identical. The bound scales nicely with the network latency and the cluster size k, because mu which actually scales logarithmically with k does not appear in the dominant sq.rt(m) term. On the other hand, the naïve no communication theorem is worse than this bound by a factor of square-root(k)

#codingexercise
Question : Find if two binary trees have common subtrees
answer : We find the inorder traversals of the trees as strings and then find common substrings in the two representations.
        static void FindCommonSubTrees(Node tree1, Node tree2)
        {
            var substrs = GetSubstrings(GetInOrder(tree1));
            foreach (var str in substrs)
                Console.WriteLine(str);
            var otherstrs = GetSubstrings(GetInOrder(tree2));
            foreach (var str in otherstrs)
                Console.WriteLine(str);
            var intersection = substrs.Intersect(otherstrs);
            foreach (var str in intersection)
                Console.WriteLine(str);
        }
        static List<string> GetSubstrings(string input)
        {
            var ret = new List<string>();
            ret.Add(input);
            for (int i = 0; i < input.Length; i++)
            {
                for (int pos = 0; pos <= input.Length; pos++)
                {
                    if (pos + i < input.Length)
                    {
                        var substr = input.Substring(pos, i);
                        ret.Add(substr);
                    }
                }
            }
            return ret;
        }