constituents

Functions is self-concordant if:

\begin{align} \mid f’’’\qty(x)\mid \leq 2f’’\qty(x)^{\frac{3}{2}}, \forall x \in \text{dom } f \end{align}

and \(f\) is self-concordant if \(g\qty(t) = f\qty(x+tv)\) is self concordant for all \(x \in \text{dom } f\).

requirements

Convergence analysis! There exists \(\eta \in (0, \frac{1}{4}]\), \(\gamma > 0\) such that:

• if \(\lambda \qty(x) > \eta\), then \(f\qty(x^{(k+1)}) - f\qty(x^{(k)}) \leq -y\)
• if \(\lambda \qty(x) \leq \eta\), then \(2\lambda \qty(x^{(k+1)}) \leq \qty(2 \lambda \qty(x^{(k)}))^{2}\)

and \(\eta, \gamma\) depends only on backtracking line search parameters. This gives bounds:

\begin{align} \frac{f\qty(x^{(0)}) -p^{*}}{\gamma} + \log \log \qty(\frac{1}{\epsilon}) \end{align}

additional information

things that are self concordant

• linear and quadratic functions
• negative logarithm \(f\qty(x) = -\log x\)
• negative entropy plus negative logarithm

calculus of self-concordant functions

• perserved under postiive scaling, summing
• preserved under composition affine function