The Entropic Barrier: Exponential Families, Log-Concave Geometry, and Self-Concordance

References

• Abernethy J, Hazan E (2016) Faster convex optimization: Simulated annealing with an efficient universal barrier. Proc. 33rd Intl. Conf. Machine Learning, PMLR 48:2520–2528.Google Scholar
• Abernethy J, Hazan E, Rakhlin A (2008) Competing in the dark: An efficient algorithm for bandit linear optimization. Proc. 21st Annual Conf. Learn. Theory (COLT).Google Scholar
• Ball K, Nguyen VH (2012) Entropy jumps for isotropic log-concave random vectors and spectral gap. Studia Math. 213(1):81–96.Crossref, Google Scholar
• Bertsimas D, Vempala S (2004) Solving convex programs by random walks. J. ACM 51:540–556.Crossref, Google Scholar
• Borell C (1975) Convex set functions in d-space. Periodica Mathematica Hungarica 6(2):111–136.Crossref, Google Scholar
• Bubeck S (2015) Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learn. 8(3–4):231–357.Crossref, Google Scholar
• Bubeck S, Cesa-Bianchi N (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learn. 5(1):1–122.Crossref, Google Scholar
• Bubeck S, Cesa-Bianchi N, Kakade S (2012) Towards minimax policies for online linear optimization with bandit feedback. Proc. 25th Annual Conf. Learn. Theory (COLT).Google Scholar
• Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, New York).Crossref, Google Scholar
• Cover TM (1991) Universal portfolios. Math. Finance 1(1):1–29.Crossref, Google Scholar
• Eldan R, Klartag B (2011) Approximately gaussian marginals and the hyperplane conjecture. Contemporary Math. 545:44–68.Google Scholar
• Fox D (2015) A Schwarz lemma for Kähler affine metrics and the canonical potential of a proper convex cone. Annali di Matematica Pura ed Applicata 194:1–42.Crossref, Google Scholar
• Fradelizi M, Guédon O (2004) The extreme points of subsets of s-concave probabilities and a geometric localization theorem. Discrete and Computational Geometry 31(2):327–335.Crossref, Google Scholar
• Güler O (1996) Barrier functions in interior point methods. Math. Oper. Res. 21(4):860–885.Link, Google Scholar
• Güler O (1997) On the self-concordance of the universal barrier function. SIAM J. Optim. 7(2):295–303.Crossref, Google Scholar
• Hazan E, Karnin Z, Meka R (2014) Volumetric spanners: An efficient exploration basis for learning. Proc. 27th Conf. Learn. Theory.Google Scholar
• Hildebrand R (2014) Canonical barriers on convex cones. Math. Oper. Res. 39:841–850.Link, Google Scholar
• Kannan R, Narayanan H (2012) Random walks on polytopes and an affine interior point method for linear programming. Math. Oper. Res. 37:1–20.Link, Google Scholar
• Karmarkar N (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4:373–395.Crossref, Google Scholar
• Kivinen J, Warmuth M (1997) Exponentiated gradient versus gradient descent for linear predictors. Inform. Comput. 132(1):1–63.Crossref, Google Scholar
• Klartag B (2006) On convex perturbations with a bounded isotropic constant. Geometric and Functional Anal. 16(6):1274–1290.Crossref, Google Scholar
• Klartag B (2014) Logarithmically-concave moment measures I. (English Summary) Geometric Aspects of Functional Analysis, Lecture Notes in Mathematics, Vol. 2116 (Springer, Cham), 231–260.Crossref, Google Scholar
• Klartag B, Milman E (2012) Centroid bodies and the logarithmic Laplace transform a unified approach. J. Functional Anal. 262(1):10–34.Crossref, Google Scholar
• Ledoux M (2001) The Concentration of Measure Phenomenon (American Mathematical Society, Providence, RI).Google Scholar
• Lee YT, Sidford A (2014) Path-finding methods for linear programming: Solving linear programs in Õ(rank) iterations and faster algorithms for maximum flow. 55th IEEE Sympos. Foundations Comput. Sci. (FOCS).Google Scholar
• Levin A (1965) On an algorithm for the minimization of convex functions. Soviet Mathematics Doklady, Vol. 160, 1244–1247.Google Scholar
• Lovász L, Vempala S (2007) The geometry of logconcave functions and sampling algorithms. Random Structures and Algorithms 30(3):307–358.Crossref, Google Scholar
• Meyer M, Pajor A (1990) On the Blaschke-Santaló inequality. Arch. Math. (Basel) 55(1):82–93.Crossref, Google Scholar
• Nemirovski A (2004) Interior point polynomial time methods in convex programming. Lecture Notes. https://www2.isye.gatech.edu/~nemirovs/Lect_IPM.pdf.Google Scholar
• Nemirovski A, Yudin D (1983) Problem Complexity and Method Efficiency in Optimization (Wiley Interscience, New York).Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course (Kluwer Academic Publishers, Dordrecht, Netherlands).Crossref, Google Scholar
• Nesterov Y, Nemirovski A (1994) Interior-Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia).Crossref, Google Scholar
• Newman D (1965) Location of the maximum on unimodal surfaces. J. ACM (JACM) 12(3):395–398.Crossref, Google Scholar
• Wainwright MJ, Jordan MI (2008) Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learn. 1(1–2):1–305.Google Scholar