Fetching the paper…

Reading the bibliography…

Universal Barrier is $n$-Self-Concordant · Around

2018

Universal Barrier is $n$-Self-Concordant

Lee, Yin Tat, Yue, Man-Chung

Original
PDF
Post on X

Understand

This paper shows that the self-concordance parameter of the universal barrier on any $n$-dimensional proper convex domain is upper bounded by $n$.

This bound is tight and improves the previous $O(n)$ bound by Nesterov and Nemirovski.
The key to our main result is a pair of new, sharp moment inequalities for $s$-concave distributions, which could be of independent interest.

Built on

Interior-point Polynomial Algorithms in Convex Programming
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
Barrier functions in interior point methods
O. Güler · 1996
Earlier work this paper cites.
The extreme points of subsets of s s -concave probabilities and a geometric localization theorem
M. Fradelizi and O. Guédon · 2004
Earlier work this paper cites.
Beating the adaptive bandit with high probability
J. Abernethy and A. Rakhlin · 2009
Earlier work this paper cites.

Similar

Random walk approach to regret minimization
H. Narayanan and A. Rakhlin · 2010
Cited alongside, same era.
Geometry of Isotropic Convex Bodies
S. Brazitikos, A. Giannopoulos, P. Valettas, and B.-H. Vritsiou · 2014
Cited alongside, same era.
Canonical barriers on convex cones
R. Hildebrand · 2014
Cited alongside, same era.

Then

Path finding methods for linear programming: Solving linear programs in O ~ ( rank ) \tilde{O}(\sqrt{\text{rank}}) iterations and faster algorithms for maximum flow
Y. T. Lee and A. Sidford · 2014
Later among the works it cites.
The entropic barrier: a simple and optimal universal self-concordant barrier
S. Bubeck and R. Eldan · 2015
Later among the works it cites.
A Schwarz lemma for Kähler affine metrics and the canonical potential of a proper convex cone
D. J. Fox · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…