Efficiently computing minimax expected-size confidence regions

ABSTRACT

Given observed data and a collection of parameterized candidate models, a 1 -- α confidence region in parameter space provides useful insight as to those models which are a good fit to the data, all while keeping the probability of incorrect exclusion below α. With complex models, optimally precise procedures (those with small expected size) are, in practice, difficult to derive; one solution is the Minimax Expected-Size (MES) confidence procedure. The key computational problem of MES is computing a minimax equilibria to a certain zero-sum game. We show that this game is convex with bilinear payoffs, allowing us to apply any convex game solver, including linear programming. Exploiting the sparsity of the matrix, along with using fast linear programming software, allows us to compute approximate minimax expected-size confidence regions orders of magnitude faster than previously published methods. We test these approaches by estimating parameters for a cosmological model.

REFERENCES

• 1: Astier, P., et al. (2006). The Supernova Legacy Survey: measurement of Ω<inf>M</inf>, Ω and w from the first year data set. Astronomy and Astrophysics, 447, 31--48.
• 2: Bryan, B., et al. (2005). Active learning for identifying function threshold boundaries. In Advances in neural information processing systems 18. Cambridge, MA: MIT Press.
• 3: Evans, S. N., Hansen, B. B., & Stark, P. B. (2005). Minimax expected measure confidence sets for restricted location parameters. Bernoulli, 11, 571--590.
• 4: Genovese, C. et al. (2004). Nonparametric inference for the cosmic microwave background. Statistical Science, 19, 308--321.
• 5: Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195451]
• 6: McMahan, H. B. (2006). Robust planning in domains with stochastic outcomes, adversaries, and partial observability. Doctoral dissertation, Carnegie Mellon University.
• 7: McMahan, H. B., & Gordon, G. J. (2007). A fast bundle-based anytime algorithm for poker and other convex games. Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS).
• 8: McMahan, H. B., Gordon, G. J., & Blum, A. (2003). Planning in the presence of cost functions controlled by an adversary. ICML 2003.
• 9: Morrison, D., Wolff, S., & Fraknoi, A. (1995). Abell's exploration of the universe. Saunders College Publishing. 7th edition.
• 10: Neyman, J., & Pearson, K. (1933). On the problem of the most efficient test of statistical hypotheses. Phil. Trans. of Royal Soc. of London, 231, 289--337.
• 11: Pratt, J. W. (1961). Length of confidence intervals. Journal of the American Statistical Association, 56, 549--567.
• 12: Robertson, H. (1936). An interpretation of page's "new relativity". Phyiscal Review, 49, 755--760.
• 13: Schafer, C., & Stark, P. (2006). Constructing Confidence Sets of Optimal Expected Size (Technical Report 836). Department of Statistics, Carnegie Mellon University.
• 14: Schafer, C. M., & Stark, P. B. (2003). Using what we know: Inference with physical constraints. PHYSTAT 2003: Statiscal Problems in Particle Physics, Astrophysics, and Cosmology.
• 15: Wasserman, L. (2004). All of statistics. New York: Springer-Verlag.