Efficient Minimax Strategies for Square Loss Games
We consider online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and its generalization, the squared Mahalanobis distance. We derive the minimax solutions for the case where the prediction and action spaces are the simplex (this setup is sometimes called the Brier game) and the 2 ball (this setup is related to Gaussian density estimation). We show that in both cases the value of each sub-game is a quadratic function of a simple statistic of the state, with coefficients that can be efficiently computed using an explicit recurrence relation. The resulting deterministic minimax strategy and randomized maximin strategy are linear functions of the statistic.
Summary:This paper derived the minimax solutions for online prediction problems where the loss between the prediction and the outcome is measured by the squared Euclidean distance and the squared Mahalanobis distance. Two cases of prediction and action space are included: probability simplex and L_2 ball. For each problem, it provides detailed analysis for the optimal strategy and regret bound. This is a purely theoretical work without experiments. Quality:This paper is of poor quality. Although lots of detailed analysis are given, there seems an important mistake in its mathematic calculation, making the correctness of one of the two contributions of this paper, the minimax strategy for probability simplex, being in doubt. Clarity:This presentation is clear in most cases, although there are a few typos. Another problem appears at the end of the first page. To make the presentation clear, it should provide a detailed mathematic definition for the probability simplex. Originality:This seems an original work. Although minimax analysis has been proposed in existing works, the specific problem, Mahalanobis distance loss in simplex or L2 ball, has not been studied.Significance:This is obviously a theoretical work. There is no experiment in the paper. Also there is no discussion for its application to real world problems. It is unknown for the significance of the theory. Comments on the main problem, the simplex problem:One of the two main contributions of this work is the minimax solutions for predictions and actions on probability simplex. And all this section is based on Lemma 4.1. This lemma is about the solution of an optimization problem on “probability simplex”. Since there is no clear definition of “probability simplex” in this paper, we have to use the usual definition: sum_i(p_i)=1 and p_i > 0. But in this lemma, “positive” is not mentioned as a constraint and not involved in Lagrange multiplier. Thus, the optimizer p* and optimized value are obtained without positive constraint. In addition, it is easy to show that the p* derived in this lemma is not always positive: for example, take c=[2,1;1,2] which is symmetric and positive definite, d=[2;5], p*=c*(d-(sum(c*d)-1)/sum(sum(c)))=[-1;2], not positive.Theorem 4.2 is based on Lemma 4.1, where p is assumed as the distribution of k and thus should be positive. This obviously contradicts with the assumption (p does not need to be positive) of lemma 4.1.  Therefore, it is not proper for Theorem 4.2 to apply the conclusion of Lemma 4.1.  We can conclude that Theorem 4.2 is wrong.Theorem 4.3 and Lemma 4.4 are based on 4.2 and thus should be incorrect. Thus, for the simplex problem, both the strategy and the regret bound are problematic.