Fetching the paper…
Reading the bibliography…
This paper presents a new approach, called perturb-max, for high-dimensional statistical inference that is based on applying random perturbations followed by optimization.
R. A. Fisher and L. H. C. Tippett, “Limiting forms of the frequency distribution of the largest or smallest member of a sample,” Mathematical Proceedings of the Cambridge Philosophical Society , vol. 24, no. 02, pp. 180–190, April 1928. [Online]. Available: http://dx.doi.org/10.1017/S0305004100015681
1928
Earlier work this paper cites.
B. Gnedenko, “Sur la distribution limite du terme maximum d’une serie aleatoire,” Annals of Mathematics , vol. 44, no. 3, pp. 423–453, July 1943. [Online]. Available: http://dx.doi.org/10.2307/1968974
1943
Earlier work this paper cites.
E. J. Gumbel, Statistical theory of extreme values and some practical applications: a series of lectures , ser. National Bureau of Standards Applied Mathematics Series. Washington, DC, USA: US Govt. Print. Office, 1954, no. 33
1954
Earlier work this paper cites.
R. D. Luce, Individual Choice Behavior: A Theoretical Analysis . New York, NY, USA: John Wiley and Sons, 1959
1959
Earlier work this paper cites.
W. K. Hastings, “Monte Carlo sampling methods using Markov chains and their applications,” Biometrika , vol. 57, no. 1, pp. 97–109, April 1970. [Online]. Available: http://dx.doi.org/10.1093/biomet/57.1.97
1970
Earlier work this paper cites.
D. McFadden, “Conditional logit analysis of qualitative choice behavior,” in Frontiers in Econometrics , P. Zarembka, Ed. New York, NY, USA: Academic Press, 1974, ch. 4, pp. 105–142
1974
Earlier work this paper cites.
H. J. Brascamp and E. H. Lieb, “On extensions of the Brunn-Minkowski and Prékopa-Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation,” Journal of Functional Analysis , vol. 22, no. 4, pp. 366–389, August 1976. [Online]. Available: http://dx.doi.org/10.1016/0022-1236(76)90004-5
1976
Earlier work this paper cites.
L. G. Valiant, “The complexity of computing the permanent,” Theoretical Computer Science , vol. 8, no. 2, pp. 189–201, 1979. [Online]. Available: http://dx.doi.org/10.1016/0304-3975(79)90044-6
1979
Earlier work this paper cites.
S. Geman and D. Geman, “Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. PAMI-6, no. 6, pp. 721–741, November 1984. [Online]. Available: http://dx.doi.org/10.1109/TPAMI.1984.4767596
1984
Earlier work this paper cites.
M. Ben-Akiva and S. R. Lerman, Discrete Choice Analysis: Theory and Application to Travel Demand . Cambridge, MA, USA: MIT press, 1985, vol. 9
1985
Earlier work this paper cites.
R. H. Swendsen and J.-S. Wang, “Nonuniversal critical dynamics in Monte Carlo simulations,” Physical Review Letters , vol. 58, no. 2, pp. 86–88, January 1987. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.58.86
1987
Earlier work this paper cites.
M. Jerrum and A. Sinclair, “Polynomial-time approximation algorithms for the Ising model,” SIAM Journal on computing , vol. 22, no. 5, pp. 1087–1116, October 1993. [Online]. Available: http://dx.doi.org/10.1137/0222066
1993
Earlier work this paper cites.
S. Aida, T. Masuda, and I. Shigekawa, “Logarithmic Sobolev inequalities and exponential integrability,” Journal of Functional Analysis , vol. 126, no. 1, pp. 83–101, November 1994. [Online]. Available: http://dx.doi.org/10.1006/jfan.1994.1142
1994
Earlier work this paper cites.
J. M. Eisner, “Three new probabilistic models for dependency parsing: an exploration,” in Proceedings of the 16th Conference on Computational Linguistics (COLING ’96) , vol. 1. Association for Computational Linguistics, 1996, pp. 340–345. [Online]. Available: http://dx.doi.org/10.3115/992628.992688
1996
Earlier work this paper cites.
S. Bobkov and M. Ledoux, “Poincaré’s inequalities and Talagrand’s concentration phenomenon for the exponential distribution,” Probability Theory and Related Fields , vol. 107, no. 3, pp. 383–400, March 1997. [Online]. Available: http://dx.doi.org/10.1007/s004400050090
1997
Earlier work this paper cites.
M. Jordan, Z. Ghahramani, T. Jaakkola, and L. Saul, “An introduction to variational methods for graphical models,” Machine learning , vol. 37, no. 2, pp. 183–233, 1999
1999
Earlier work this paper cites.
S. Kotz and S. Nadarajah, Extreme value distributions: theory and applications . London, UK: Imperial College Press, 2000
2000
Earlier work this paper cites.
Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 23, no. 11, pp. 1222–1239, November 2001. [Online]. Available: http://dx.doi.org/10.1109/34.969114
2001
Earlier work this paper cites.
M. Ledoux, The Concentration of Measure Phenomenon , ser. Mathematical Surveys and Monographs. American Mathematical Society, 2001, vol. 89
2001
Earlier work this paper cites.
H. A. David and H. N. Nagaraja, Order Statistics , 3rd ed. Hoboken, NJ, USA: John Wiley & Sons, 2003
2003
Earlier work this paper cites.
D. P. Bertsekas, A. Nedić, and A. E. Ozdaglar, Convex Analysis and Optimization . Nashua, NH, USA: Athena Scientific, 2003
2003
Earlier work this paper cites.
A. Kalai and S. Vempala, “Efficient algorithms for online decision problems,” Journal of Computer and System Sciences , vol. 71, no. 3, pp. 291–307, October 2005. [Online]. Available: http://dx.doi.org/10.1016/j.jcss.2004.10.016
2004
Earlier work this paper cites.
V. Kolmogorov and R. Zabih, “What energy functions can be minimized via graph cuts?” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 26, no. 2, pp. 147–159, February 2004. [Online]. Available: http://dx.doi.org/10.1109/TPAMI.2004.1262177
2004
Earlier work this paper cites.
M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, “MAP estimation via agreement on trees: Message-passing and linear programming,” IEEE Transactions on Information Theory , vol. 51, no. 11, pp. 3697–3717, November 2005. [Online]. Available: http://dx.doi.org/10.1109/TIT.2005.856938
2005
Cited alongside, same era.
M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, “A new class of upper bounds on the log partition function,” IEEE Transactions on Information Theory , vol. 51, no. 7, pp. 2313–2335, July 2005. [Online]. Available: http://dx.doi.org/10.1109/TIT.2005.850091
2005
Cited alongside, same era.
V. Kolmogorov, “Convergent tree-reweighted message passing for energy minimization,” IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 28, no. 10, pp. 1568–1583, October 2006. [Online]. Available: http://dx.doi.org/10.1109/TPAMI.2006.200
2006
Cited alongside, same era.
I. Tsochantaridis, T. Joachims, T. Hofmann, and Y. Altun, “Large margin methods for structured and interdependent output variables,” Journal of Machine Learning Research , vol. 6, no. 2, p. 1453, 2006
A. G. Schwing and R. Urtasun, “Efficient exact inference for 3D indoor scene understanding,” in Computer Vision – ECCV 2012 : 12th European Conference on Computer Vision , ser. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2012, vol. 7577, ch. 22, pp. 299–313. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-33783-3
2012
Later among the works it cites.
M. Sun, M. Telaprolu, H. Lee, and S. Savarese, “An efficient branch-and-bound algorithm for optimal human pose estimation,” in Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , Providence, RI, 2012, pp. 1616–1623. [Online]. Available: http://dx.doi.org/10.1109/CVPR.2012.6247854
2012
Later among the works it cites.
T. M. Cover and J. A. Thomas, Elements of Information Theory . Hoboken, NJ, USA: John Wiley & Sons, 2012
2012
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2006
Cited alongside, same era.
L. A. Goldberg and M. Jerrum, “The complexity of ferromagnetic Ising with local fields,” Combinatorics Probability and Computing , vol. 16, no. 1, p. 43, January 2007. [Online]. Available: http://dx.doi.org/10.1017/S096354830600767X
2007
Cited alongside, same era.
Y. Weiss, C. Yanover, and T. Meltzer, “MAP estimation, linear programming and belief propagation with convex free energies,” in Proceedings of the Twenty-Third Conference Conference on Uncertainty in Artificial Intelligence (2007) . Corvallis, Oregon, USA: AUAI Press, 2007, pp. 416–425. [Online]. Available: https://dslpitt.org/papers/07/p416-weiss.pdf
2007
Cited alongside, same era.
A. Globerson and T. S. Jaakkola, “Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations,” in Advances in Neural Information Processing Systems 20 , J. Platt, D. Koller, Y. Singer, and S. Roweis, Eds. Curran Associates, Inc., 2007, vol. 21, pp. 553–560. [Online]. Available: http://papers.nips.cc/paper/3200-fixing-max-product-convergent-message-passing-algorithms-for-map-lp-relaxations.pdf
2007
Cited alongside, same era.
A. S. Willsky, E. B. Sudderth, and M. J. Wainwright, “Loop series and Bethe variational bounds in attractive graphical models,” in Advances in Neural Information Processing Systems 20 , J. Platt, D. Koller, Y. Singer, and S. Roweis, Eds. Curran Associates, Inc., 2007, pp. 1425–1432. [Online]. Available: http://papers.nips.cc/paper/3354-loop-series-and-bethe-variational-bounds-in-attractive-graphical-models.pdf
2007
Cited alongside, same era.
D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss, “Tightening LP relaxations for MAP using message passing,” in Proceedings of the Twenty-Fourth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-08) . Corvallis, Oregon, USA: AUAI Press, 2008, pp. 503–510. [Online]. Available: https://dslpitt.org/papers/08/p503-sontag.pdf
2008
Cited alongside, same era.
T. Werner, “High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (MAP-MRF),” in Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) , 2008, pp. 1–8. [Online]. Available: http://dx.doi.org/10.1109/CVPR.2008.4587355
2008
Cited alongside, same era.
M. Wainwright and M. Jordan, “Graphical models, exponential families, and variational inference,” Foundations and Trends in Machine Learning , vol. 1, no. 1-2, pp. 1–305, 2008. [Online]. Available: http://dx.doi.org/10.1561/2200000001
2008
Cited alongside, same era.
D. Sontag and T. S. Jaakkola, “New outer bounds on the marginal polytope,” in Advances in Neural Information Processing Systems 20 , J. Platt, D. Koller, Y. Singer, and S. Roweis, Eds. Curran Associates, Inc., 2008, pp. 1393–1400. [Online]. Available: http://papers.nips.cc/paper/3274-new-outer-bounds-on-the-marginal-polytope.pdf
2008
Cited alongside, same era.
2012
Later among the works it cites.
T. Hazan, S. Maji, and T. Jaakkola, “On sampling from the Gibbs distribution with random maximum a-posteriori perturbations,” in Advances in Neural Information Processing Systems 26 , C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 1268–1276. [Online]. Available: http://papers.nips.cc/paper/4962-on-sampling-from-the-gibbs-distribution-with-random-maximum-a-posteriori-perturbations
2013
Later among the works it cites.
P. Swoboda, B. Savchynskyy, J. Kappes, and C. Schnörr, “Partial optimality via iterative pruning for the Potts model,” in Scale Space and Variational Methods in Computer Vision: 4th International Conference , ser. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2013, vol. 7893, ch. 40, pp. 477–488. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-38267-3
2013
Later among the works it cites.
S. Ermon, C. Gomes, A. Sabharwal, and B. Selman, “Taming the curse of dimensionality: Discrete integration by hashing and optimization,” in Proceedings of The 30th International Conference on Machine Learning , ser. JMLR: Workshop and Conference Proceedings, S. Dasgupta and D. McAllester, Eds., vol. 28, no. 2, 2013, pp. 334–342. [Online]. Available: http://jmlr.org/proceedings/papers/v28/ermon13.html
2013
Later among the works it cites.
——, “Optimization with parity constraints: From binary codes to discrete integration,” in Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13) . Corvallis, Oregon: AUAI Press, 2013, pp. 202–211
2013
Later among the works it cites.
G. B. Folland, Real Analysis: Modern Techniques and Their Applications , 2nd ed. New York, NY, USA: John Wiley & Sons, 2013
2013
Later among the works it cites.
V. H. Nguyen, “Dimensional variance inequalities of Brascamp–Lieb type and a local approach to dimensional Prékopaʼs theorem,” Journal of Functional Analysis , vol. 266, no. 2, pp. 931–955, January 2014. [Online]. Available: http://dx.doi.org/10.1016/j.jfa.2013.11.003
2013
Later among the works it cites.
M. R. Spiegel, S. Lipschutz, and J. Liu, Mathematical Handbook of Formulas and Tables , 4th ed., ser. Schaum’s Outlines. New York, NY, USA: McGraw-Hill Education, 2013
2013
Later among the works it cites.
T. Hazan, S. Maji, J. Keshet, and T. Jaakkola, “Learning efficient random maximum a-posteriori predictors with non-decomposable loss functions,” in Advances in Neural Information Processing Systems 26 , C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 1887–1895. [Online]. Available: http://papers.nips.cc/paper/4962-on-sampling-from-the-gibbs-distribution-with-random-maximum-a-posteriori-perturbations
2013
Later among the works it cites.
F. Orabona, T. Hazan, A. Sarwate, and T. Jaakkola, “On measure concentration of random maximum a-posteriori perturbations,” in Proceedings of The 31st International Conference on Machine Learning , ser. JMLR: Workshop and Conference Proceedings, E. P. Xing and T. Jebara, Eds., vol. 32, 2014, p. 1. [Online]. Available: http://jmlr.csail.mit.edu/proceedings/papers/v32/orabona14.html
2014
Later among the works it cites.
S. Maji, T. Hazan, and T. Jaakkola, “Active boundary annotation using random MAP perturbations,” in Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS) , ser. JMLR: Workshop and Conference Proceedings, S. Kaski and J. Corander, Eds., vol. 33, 2014, pp. 604–613. [Online]. Available: http://jmlr.org/proceedings/papers/v33/maji14.html
2014
Later among the works it cites.
——, “Low-density parity constraints for hashing-based discrete integration,” in Proceedings of The 31st International Conference on Machine Learning , ser. JMLR: Workshop and Conference Proceedings, E. P. Xing and T. Jebara, Eds., vol. 32, no. 1, 2014, pp. 271–279. [Online]. Available: http://jmlr.org/proceedings/papers/v32/ermon14.html
2014
Later among the works it cites.
G. Papandreou and A. Yuille, “Perturb-and-MAP random fields: Reducing random sampling to optimization, with applications in computer vision,” in Advanced Structured Prediction , S. Nowozin, P. V. Gehler, J. Jancsary, and C. H. Lampert, Eds. Cambridge, MA, USA: MIT Press, 2014, ch. 7, pp. 159–186
2014
Later among the works it cites.
A. Gane and T. S. J. Tamir Hazan, “Learning with maximum a-posteriori perturbation models,” in Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics (AISTATS) , ser. JMLR: Workshop and Conference Proceedings, S. Kaski and J. Corander, Eds., vol. 33, 2014, pp. 247—256. [Online]. Available: http://jmlr.org/proceedings/papers/v33/gane14.html
2014
Later among the works it cites.
D. Bakry, I. Gentil, and M. Ledoux, Analysis and Geometry of Markov Diffusion Operators , ser. Grundlehren der mathematischen Wissenschaften. Switzerland: Springer International Publishing, 2014, vol. 348. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-00227-9
2014
Later among the works it cites.
A. Weller and T. Jebara, “Clamping variables and approximate inference,” in Advances in Neural Information Processing Systems 27 , Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, Eds. Cur, 2014, pp. 909–917. [Online]. Available: http://papers.nips.cc/paper/5529-clamping-variables-and-approximate-inference.pdf
2014
Later among the works it cites.
Gurobi Optimization. (2015) Gurobi optimizer documentation. [Online]. Available: http://www.gurobi.com/documentation/
2015
Later among the works it cites.
2016
Closest in time.
S. Ermon, C. P. Gomes, A. Sabharwal, and B. Selman, “Embed and project: Discrete sampling with universal hashing,” in Advances in Neural Information Processing Systems 26 (NIPS 2013) , C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Weinberger, Eds. Curran Associates, Inc., 2013, pp. 2085–2093. [Online]. Available: http://papers.nips.cc/paper/4965-embed-and-project-discrete-sampling-with-universal-hashing.pdf
2093
Closest in time.
C. Maddison, D. Tarlow, and T. Minka, “A ∗ sampling,” in Advances in Neural Information Processing Systems 27 , Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, Eds. Curran Associates, Inc., 2014, pp. 2085–2093. [Online]. Available: http://papers.nips.cc/paper/5449-a-sampling
2093
Closest in time.