Barrier method $O(\sqrt m)$ Newton complexity

Fix naturals $n, m_I$ with $m_I > 0$, and reals $\alpha, \beta, t_0, \varepsilon, \varepsilon_{nt}$ with $0 < \alpha < 1/2$, $0 < \beta < 1$, $t_0 > 0$, $\varepsilon > 0$, and $0 < \varepsilon_{nt} < 1/4$. Hypotheses on the problem data: $f_0 : \mathbb{R}^n \to \mathbb{R}$ is convex on all of $\mathbb{R}^n$, and each of the $m_I$ constraint functions $f_i$ is convex on all of $\mathbb{R}^n$ — note that, unlike the two central-path theorems, NO differentiability hypotheses on $f_0$ or the $f_i$ appear here. Writing $B(x) = -\sum_i \log(-f_i(x))$ for the log-barrier (total real logarithm: $\log 0 = 0$, $\log y = \log|y|$ for $y < 0$; genuine on the strictly feasible set) and $S = \{x : f_i(x) < 0 \text{ for all } i\}$: (H1) for EVERY real $t \ge 0$ (including $t = 0$), the function $x \mapsto t f_0(x) + B(x)$ is self-concordant on $S$, meaning $S$ is convex with the convexity inequality for this function on $S$, the function is three times continuously differentiable on $S$ (within-set sense), and for every $x \in S$ and every $v \in \mathbb{R}^n$ its line restriction $\varphi(s) = t f_0(x+sv) + B(x+sv)$ satisfies $|\varphi'''(0)| \le 2(\varphi''(0))^{3/2}$ at $s = 0$ (total possibly-junk derivatives; real power with $b^{3/2} = 0$ for $b \le 0$); (H2) a two-parameter field $g$ such that for every $t > 0$ and every $x \in S$, the function $y \mapsto t f_0(y) + B(y)$ is differentiable at $x$ with gradient $g_t(x)$; (H3) a field $H$ of continuous linear operators such that for every $t > 0$ and $x \in S$, the map $g_t$ is Fréchet-differentiable at $x$ with derivative $H_t(x)$; (H4) for every $t > 0$, $x \in S$, and $v \ne 0$: $\langle H_t(x)v, v\rangle > 0$; (H5) a map $x_c : \mathbb{R} \to \mathbb{R}^n$ (defined for all reals, constrained only at $t > 0$) such that for every $t > 0$: $x_c(t) \in S$ (strictly feasible) and $t f_0(x_c(t)) + B(x_c(t)) \le t f_0(y) + B(y)$ for every $y \in S$ — a central point is hypothesized to exist for every positive parameter; if $S = \emptyset$ this hypothesis is unsatisfiable and the theorem is vacuous. Conclusion (existential): writing $\theta = 1 + 1/\sqrt{m_I}$ (real square root; $m_I \ge 1$ so $\sqrt{m_I} \ge 1$ and $1 < \theta \le 2$), there exist a doubly-indexed family $w : \mathbb{N} \to \mathbb{N} \to \mathbb{R}^n$ (outer stage $i$, inner iterate $k$) and a map $K : \mathbb{N} \to \mathbb{N}$ such that ALL FIVE of the following hold. (1) For every $i$: $w_i(0) = x_c(\theta^i t_0)$ — each stage's inner run starts at the EXACT central point for the pre-update parameter $\theta^i t_0$ (exponent $i$); in particular $w_0(0) = x_c(t_0)$, and stage $i+1$ starts at $x_c(\theta^{i+1} t_0)$, not at the terminal iterate of stage $i$. (2) For every $i$: the sequence $k \mapsto w_i(k)$ is a damped Newton sequence on $S$ for the stage objective $F_{i+1}(x) = \theta^{i+1} t_0\, f_0(x) + B(x)$ (exponent $i+1$), with gradient field $g_{\theta^{i+1} t_0}$, operator field $H_{\theta^{i+1} t_0}$, and parameters $\alpha, \beta$; unfolded: for every $k$, $w_i(k) \in S$, and there exist $\Delta$ and $s$ with $H_{\theta^{i+1}t_0}(w_i(k))\,\Delta = -g_{\theta^{i+1}t_0}(w_i(k))$, $s = \beta^{\,j}$ for some natural $j$, $F_{i+1}(w_i(k) + s\Delta) \le F_{i+1}(w_i(k)) + \alpha s \langle g_{\theta^{i+1}t_0}(w_i(k)), \Delta\rangle$, ($s = 1$ or the candidate $s/\beta$ fails this inequality), and $w_i(k+1) = w_i(k) + s\Delta$. (3) For every $i$:

i.e. at the designated index $K_i$ the stage-$(i{+}1)$ objective value of the inner iterate is within $\varepsilon_{nt}$ of its value at the exact center for parameter $\theta^{i+1} t_0$. (4) For every $i$, as reals:

a bound uniform in $i$ whose leading term is HALF of $(20-8\alpha)/(\alpha\beta(1-2\alpha)^2)$ — no factor of an initial gap appears — and whose additive constant is $2$ (compare $+1$ in the single-Newton-phase iteration bound); $\log_2 y = \log y/\log 2$ is total (here $\varepsilon_{nt} < 1/4$ makes $\log_2(1/\varepsilon_{nt}) > 2$, so both logs are genuine and positive). (5)

where $\lceil\cdot\rceil_{\mathbb{N}}$ is the natural-number ceiling (smallest natural $\ge$ the real value, and $0$ if that value is $\le 0$, e.g. when $m_I \le t_0\varepsilon$, in which case the claim reduces to $m_I/t_0 \le \varepsilon$); $m_I/(t_0\varepsilon) > 0$ under the hypotheses so its $\log_2$ is genuine (possibly negative if the ratio is $< 1$). Note that conjunct (5) mentions only $m_I, t_0, \varepsilon$ — none of $w$, $K$, $f_0$, $f_i$ — it is a standalone arithmetic inequality asserting that after $N$ multiplicative parameter updates the quantity $m_I/t$ is at most $\varepsilon$. The theorem does not assert any inequality of the form $f_0(w_i(K_i)) - \inf \le \ldots$; no suboptimality bound on the iterates, and no link between the stage count $N$ of conjunct (5) and the per-stage statements (1)–(4) (which hold for every $i \in \mathbb{N}$), is part of the statement. The whole conclusion is existential: SOME such family of runs and index map exists.