Computing Augustin Information via
Hybrid Geodesically Convex Optimization

Nakiboğlu [32] showed that the minimizer of the optimization problem (1) satisfies a fixed-point equation and proved that the associated fixed-point iteration converges to the order-$\alpha$ Augustin information for $\alpha\in(0,1)$. Cheng and Nakiboğlu [11, Lemma 6] provided a descent lemma for a specific update rule, which implies asymptotic convergence for the optimization problem (1) for all $\alpha>0$. Li and Cevher [28] provided a line search gradient-based algorithm to solve optimization problems on the probability simplex, which can also be used to solve the optimization problem (1) for all $\alpha>0$. You et al. [48] proposed a gradient-based method for minimizing quantum Rényi divergences, which includes the optimization problem (1) as a special case for all $\alpha>0$. These works only guarantee asymptotic convergence of the algorithms. Analysis of the convergence rate before the present work is still missing.

Antonakopoulos et al. [2] considered (Euclidean) convex and geodesically Lipschitz objective functions, analyzing the regret rates of the follow-the-regularized-leader algorithm and online mirror descent. Weber and Sra [46] considered geodesically convex and (Euclidean) smooth objective functions, analyzing the optimization error of the convex-concave procedure. The former did not consider the hybrid case of geodesic convexity and geodesic smoothness under different Riemannian metrics. The latter only analyzed a special case of the hybrid scenario we proposed. Neither of them analyzed Riemannian gradient descent.

If an optimization problem is convex, we may consider using (projected) gradient descent to approximate a global minimizer. Existing non-asymptotic error bounds of gradient descent require the objective function to be either Lipschitz or smooth.

Given a convex optimization problem, gradient descent converges at a rate of $\mathcal{O}(1/\sqrt{T})$ for the Lipschitz case and $\mathcal{O}(1/T)$ for the smoothness case, where $T$ denotes the number of iterations. However, You et al. [48, Proposition III.1] showed that the objective function in the optimization problem (1) is neither Lipschitz nor smooth.

An $N$-dimensional topological manifold $\mathcal{M}$ is a topological space that is Hausdorff, second countable, and locally homeomorphic to $\mathbb{R}^{N}$. The tangent space at a point $x\in\mathcal{M}$, denoted as $T_{x}\mathcal{M}$, is the set of all vectors tangent to the manifold at $x$. A Riemannian metric $\mathfrak{g}$ on $\mathcal{M}$ defines an inner product on each tangent space. The inner product on $T_{x}\mathcal{M}$ is denoted as $\langle\cdot,\cdot\rangle_{x}$. A Riemannian manifold $(\mathcal{M},\mathfrak{g})$ is a topological manifold $\mathcal{M}$ equipped with a Riemannian metric $\mathfrak{g}$. Given a Riemannian metric, the induced norm of a tangent vector $v\in T_{x}\mathcal{M}$ is given by $\|v\|_{x}:=\sqrt{\langle v,v\rangle_{x}}$. The length of a curve $\gamma:[0,1]\to\mathcal{M}$ is defined as $L(\gamma):=\int_{0}^{1}\|\gamma^{\prime}(t)\|_{\gamma(t)}\mathrm{d}t$, and the induced distance between two points $x,y\in\mathcal{M}$ is given by $d(x,y)=\inf_{\gamma}L(\gamma)$, where the infimum is taken over all curves $\gamma$ connecting $x$ and $y$. A geodesic is a curve connecting $x$ and $y$ with constant speed and satisfying $L(\gamma)=d(x,y)$. For each $x\in\mathcal{M}$ and $v\in T_{x}\mathcal{M}$, there is a unique geodesic $\gamma_{v}:[0,1]\to\mathcal{M}$ such that $\gamma_{v}(0)=x$ and $\gamma_{v}^{\prime}(0)=v$ [27, Corollary 4.28]. The exponential map at a point $x\in\mathcal{M}$ is the map $\exp_{x}:T_{x}\mathcal{M}\to\mathcal{M}$ such that $\exp_{x}(v)=\gamma_{v}(1)$.²²2In general, the exponential map may only be locally defined, while the exponential map considered in this paper is defined on the whole tangent space. The logarithmic map $\log_{x}:\mathcal{M}\to T_{x}\mathcal{M}$ at a point $x\in\mathcal{M}$ is the inverse of $\exp_{x}$. Given a differentiable function $f:\mathcal{M}\to\mathbb{R}$, the Riemannian gradient of $f$ at $x\in\mathcal{M}$ is the unique tangent vector $\mathrm{grad}f(x)$ that satisfies $\langle\mathrm{grad}f(x),v\rangle_{x}=\mathrm{d}f(x)[v]$ for all $v\in T_{x}\mathcal{M}$.

The notions of convexity and smoothness can be extended for functions defined on Riemannian manifolds.

With the notions of the exponential map and Riemannian gradient, vanilla gradient descent can be extended to the so-called Riemannian gradient descent (RGD) [49, 8, 15], which iterates as follows

where $\eta$ denotes the step size.

For Riemannian gradient descent, there exists a non-asymptotic optimization error bound analogous to that in gradient descent [49].

Consider the manifold $\mathcal{M}=\mathbb{R}^{N}_{++}$. Let $x\in\mathcal{M}$ and $u,v\in T_{x}\mathcal{M}$. The Poincaré metric³³3This metric is not the exact Poincaré metric in standard differential geometry literature (see e.g., [27]) but rather a variation of it. We use this term for convenience, as Antonakopoulos et al. [2] did. is given by

Since we consider the finite alphabet $\mathcal{Y}$ case, we can identify $P_{Y|X}$ and $Q_{Y}$ as vectors in $\Delta^{N}_{+}$. Denote $Q_{Y}$ by $x$ and view $P_{Y|X}$ as a random variable $p$ in $\Delta^{N}_{+}$. Then, the order-$\alpha$ Augustin information (1) for $p$ can be written as

where $\alpha\in\mathbb{R}_{+}\setminus\{1\}$ and $D_{\alpha}(y\|x):=\frac{1}{\alpha-1}\log\langle y^{\alpha},x^{1-\alpha}\rangle$ is the order-$\alpha$ Rényi divergence between two probability vectors $x,y\in\Delta^{N}_{+}$.

The constraint set in the optimization problem (3) is the probability simplex $\Delta^{N}_{+}$, while the Poincaré metric is defined over the whole positive orthant $\mathbb{R}^{N}_{++}$. We address this inconsistency by the following lemma. Define

With Lemma 5.3, we may consider minimizing $g_{\alpha}$ on $\mathbb{R}^{N}_{+}$ via RGD with the Poincaré metric and step size $\eta=1/(|1-\alpha|+1)$. Starting with $x_{1}\in\mathbb{R}^{N}_{+}$, the iteration rule proceeds as

Note that we additionally require that $x\leq\mathbbm{1}$ for the g-smoothness of $g_{\alpha}$. We justify this requirement by the following lemma.

Since the function $\langle\mathbbm{1},x\rangle$ is convex in the Euclidean sense, the objective function $g_{\alpha}$ is also convex in the Euclidean sense. It is desirable to apply Theorem 4.6 to $g_{\alpha}$ with $\mathfrak{g}$ as the standard Euclidean metric and $\mathfrak{h}$ as the Poincaré metric. However, the Poincaré metric is only defined on the interior of the constraint set $\mathbb{R}^{N}_{+}$, whereas RGD for the function $g_{\alpha}(x)$ may yield iterates that violate the assumption that $\lim_{t\to\infty}x_{t}\in\mathcal{M}$ of Lemma 4.5. We show that even if the limit point falls on the boundary of $\mathbb{R}^{N}_{++}$, the limit point is still a minimizer when considering the Poincaré metric on $\mathbb{R}^{N}_{++}$.

Consequently, we still have a non-asymptotic error bound for the optimization problem $\min_{x\in\mathbb{R}^{N}_{+}}g_{\alpha}(x)$.

Since the iteration rule (4) is for the optimization problem $\min_{x\in\mathbb{R}^{N}_{+}}g_{\alpha}(x)$, these iterates may fall outside the constraint set $\Delta^{N}_{+}$ of the original problem. We show that the sequence of normalized iterates still converges at a rate of $\mathcal{O}(1/T)$.

Note that the term $\sup_{t\in\mathbb{N}}\|x^{\star}\oslash x_{t}-\mathbbm{1}\|^{2}_{2}$ is bounded since $\lim_{t\to\infty}x_{t}=x^{\star}$ (Remark 4.7).

We conducted numerical experiments⁴⁴4The code is available on GitHub at the following repository: https://github.com/CMGRWang/Computing-Augustin-Information-via-Hybrid-Geodesically-Convex-Optimization. on the optimization problem (1) by RGD, using the explicit iteration rule (4). The experimental setting is as follows: the support cardinality of $p$ is $2^{14}$, and the parameter dimension $N$ is $2^{4}$. The random variable $p$ is uniformly generated from the probability simplex $\Delta^{N}_{+}$. We implemented all methods in Python on a machine equipped with an Intel(R) Core(TM) i7-9700 CPU running at 3.00GHz and 16.0GB memory. The elapsed time represents the actual running time of each algorithm.

Figure 1 demonstrates the results of computing the order-$3$ Augustin information using RGD, the fixed-point iteration in Nakıboğlu’s paper [32], the method proposed by Li and Cevher [28], and the method proposed by You et al. [48]. We tuned the parameters for the latter two methods to achieve faster convergence speeds. We set $\bar{\alpha}=0.4$, $r=0.7$, $\tau=0.5$ for the method proposed by Li and Cevher [28], and set $\delta_{1}=1$, $\delta=10^{-5}$, $\beta=0.99$, $\gamma=1.25$, $c=10$ for the method proposed by You et al. [48]. We approximate the optimal value based on the result obtained from the method proposed by Li and Cevher [28] after $20$ iterations.

The numerical results validate our theoretical analysis, showing that RGD converges to the optimum. The fixed-point iteration proposed by Nakiboğlu [32] diverges, as it is only guaranteed to converge for $\alpha<1$. We observe that RGD is slower than the methods proposed by Li and Cevher [28] and by You et al. [48]. However, the latter two methods guarantee only asymptotic convergence, and tuning parameters is required to achieve faster convergence. We found that slightly adjusting parameters can result in slow convergence speed for these two algorithms. Figure 2 shows that if we change $\bar{\alpha}$ from $0.4$ to $0.04$ and $c$ from $10$ to $100$, both methods become slower than RGD in terms of elapsed time. Directly comparing numerical results would be unfair, given that these two methods lack convergence rate guarantees and require tuning to get better results.