Exp-Concave Losses and Online Newton Methods

Why Exp-Concavity Leads to Logarithmic Regret

For online convex optimization, the learner chooses $x_t$ from a feasible set $K$, then incurs the loss $f_t(x_t)$. The comparator regret after $T$ rounds is $\sum_{t=1}^T [f_t(x_t)-f_t(u)]$, for a fixed $u\in K$. Strong convexity is one source of logarithmic regret, as the earlier material on strongly convex losses shows. Exp-concavity provides another: it controls loss differences through the square of the directional gradient. Online Newton Step uses a growing matrix to accumulate this curvature information across rounds.

Definition: A function $f:K\to\mathbb R$ on a convex set $K$ is $\alpha$-exp-concave, for $\alpha>0$, if $x\mapsto \exp(-\alpha f(x))$ is concave on $K$. This condition implies that $f$ is convex: the logarithm is increasing and concave, so its composition with the positive concave function $\exp(-\alpha f)$ is concave; hence $-\alpha f$ is concave.

When $K$ is full-dimensional and $f$ is twice continuously differentiable on a neighborhood of $K$, exp-concavity has a local Hessian characterization in the interior of $K$. Differentiating the exponential twice gives

\nabla^2 \exp(-\alpha f(x)) = \exp(-\alpha f(x)) \left\{ \alpha^2 \nabla f(x)\nabla f(x)^\mathsf{T} - \alpha\nabla^2 f(x) \right\}.

The exponential factor is positive, and a twice differentiable function is concave on a convex open set if and only if its Hessian is negative semidefinite there. Thus the criterion is $\nabla^2 f(x)\succeq\alpha\nabla f(x)\nabla f(x)^\mathsf{T}$. For a set contained in a lower-dimensional affine subspace, apply this condition to derivatives restricted to that affine hull; checking only the ambient interior would be vacuous.

Worked Example: Checking Exp-Concavity With a Hessian

Let $K=[-1,1]$ and $f(x)=x^2/2$. For $\alpha=1$, the Hessian condition in one dimension is $f''(x)\ge (f'(x))^2$. Here $f'(x)=x$, $f''(x)=1$, and $x^2\le1$ throughout $K$. Therefore $f$ is 1-exp-concave on this interval. Directly, $\exp(-f(x))=\exp(-x^2/2)$ has second derivative $(x^2-1)\exp(-x^2/2)\le0$ on $K$, confirming concavity.

The Curvature Inequality

Exp-concavity gives a logarithmic bound on loss differences in terms of the directional gradient. When directional gradients are bounded, this can be converted into a quadratic bound with an adjusted constant, which is useful for Online Newton Step.

Lemma: Suppose $K$ is convex, $f$ is differentiable and $\alpha$-exp-concave on $K$, and $x,y\in K$. Then $$ f(x)-f(y) \le \frac{1}{\alpha}\log\left(1+\alpha\nabla f(x)^\mathsf{T}(x-y)\right). $$

Proof. Write $g=\nabla f(x)$ and $z=g^\mathsf{T}(y-x)$. Concavity of $\exp(-\alpha f)$ implies that its value at $y$ is at most its tangent at $x$:

\exp(-\alpha f(y)) \le \exp(-\alpha f(x))(1-\alpha z).

The left side is positive, so $1-\alpha z>0$. Taking logarithms and rearranging gives $f(x)-f(y)\le\alpha^{-1}\log(1-\alpha z)$. Since $z=\nabla f(x)^\mathsf{T}(y-x)$, this is the stated bound. $\square$

Worked Example: A Direct Exp-Concavity Check

Take $f(x)=-\log x$ on $K=[1,2]$. For $\alpha=1$, $\exp(-\alpha f(x))=x$, which is affine and therefore concave. Thus $f$ is 1-exp-concave on $K$. At $x=1.5$ and $y=1$, the lemma gives $f(x)-f(y)\le \log(1-(1/x)(x-y))$. Both sides equal $\log(2/3)\approx-0.4055$, illustrating that the logarithmic bound can be tight.

Online Newton Step

Let $g_t=\nabla f_t(x_t)$. Online Newton Step (ONS) maintains a positive definite matrix $A_t$, adding the current gradient’s outer product each round. The inverse matrix scales the gradient step: directions with substantial accumulated gradient information receive smaller updates. A projection keeps the next decision feasible.

Definition: Given $\lambda>0$, set $A_0=\lambda I_d$. For a step parameter $\beta>0$, the ONS update is $$ A_t=A_{t-1}+g_tg_t^\mathsf{T}, \qquad x_{t+1}=\mathop{\arg\min}_{x\in K} \left(x-\left[x_t-\beta^{-1}A_t^{-1}g_t\right]\right)^\mathsf{T} A_t \left(x-\left[x_t-\beta^{-1}A_t^{-1}g_t\right]\right). $$

This is projection in the $A_t$-quadratic metric, not necessarily ordinary Euclidean projection. If $K$ is nonempty, closed, and convex, the minimizer exists and is unique: the objective is strictly convex and tends to infinity as the distance from its center tends to infinity, while $K$ is closed. In the theorem below, finite diameter also makes $K$ compact.

Worked Example: Two Scalar ONS Updates

Let $K=[0,1]$, $\lambda=100$, $\beta=1/16=0.0625$, and $x_1=0.0639772051$. Use $f_1(x)=-\log(1-cx)$, where $c=0.2/(1+0.2x_1)$, and $f_2(x)=(x-0.4)^2/2$. Both are 1-exp-concave on $K$: the exponential transform of $f_1$ is the positive affine function $1-cx$, and for the second $f_2''=1\ge (x-0.4)^2=(f_2')^2$ on $K$.

At round 1, $g_1=0.2$ and $A_1=100+0.2^2=100.04$. The unprojected update is $x_1-0.2/(0.0625\cdot100.04)=0.0639772051-0.0319872051=0.0319900000$, which lies in $K$, so $x_2=0.0319900000$.

At round 2, $g_2=x_2-0.4=-0.36801$, and $A_2=100.04+(-0.36801)^2=100.1754313601$. Thus $x_3=x_2-(-0.36801)/(0.0625\cdot100.1754313601)\approx0.09076848$. This also lies in $K$, so no projection changes either update.

Logarithmic Regret Guarantee

Theorem: Let $K\subset\mathbb R^d$ be nonempty, closed, and convex, with diameter at most $D<\infty$. Suppose each $f_t$ is differentiable and $\alpha$-exp-concave on $K$, and $\|\nabla f_t(x)\|_2\le G$ for every $x\in K$ and $t$. Run ONS with $x_1\in K$, $\lambda>0$, and $0<\beta\le\frac{\alpha}{1+\alpha GD}$. Then for every $u\in K$, $$ \sum_{t=1}^T [f_t(x_t)-f_t(u)] \le \frac{\beta\lambda D^2}{2} + \frac{d}{2\beta} \log\left(1+\frac{TG^2}{d\lambda}\right). $$

Proof. Write $\delta_t=x_t-u$, $s_t=g_t^\mathsf{T}\delta_t$, and $q_t=g_t^\mathsf{T}A_t^{-1}g_t$. Set $\gamma=\alpha/(1+\alpha GD)$. The lemma gives a bound by $\alpha^{-1}\log(1+\alpha s_t)$, and $|s_t|\le GD$. For $v\ge0$, $\log(1+v)\le v-v^2/[2(1+v)]$; for $-1<v\le0$, $\log(1+v)\le v-v^2/2$. These bounds imply $f_t(x_t)-f_t(u)\le s_t-\gamma s_t^2/2$. By the defining property of projection in the $A_t$ metric, the projected point is no farther from $u$ than the unprojected point. Expanding that squared-distance inequality gives

s_t\le \frac{\beta}{2} \left( \|\delta_t\|_{A_t}^2-\|x_{t+1}-u\|_{A_t}^2 \right) +\frac{q_t}{2\beta}, \qquad \|v\|_A^2=v^\mathsf{T}Av.

Since $A_t=A_{t-1}+g_tg_t^\mathsf{T}$, we have $\|\delta_t\|_{A_t}^2=\|\delta_t\|_{A_{t-1}}^2+s_t^2$. After subtracting $\gamma s_t^2/2$ from the projection inequality and summing, the squared-gradient terms have coefficient $(\beta-\gamma)/2\le0$. The potential terms telescope to $\frac{\beta}{2}(\|x_1-u\|_{A_0}^2-\|x_{T+1}-u\|_{A_T}^2)$; dropping nonpositive terms and using $A_0=\lambda I_d$ and $\|x_1-u\|_2\le D$ gives

\sum_{t=1}^T [f_t(x_t)-f_t(u)] \le \frac{\beta\lambda D^2}{2} +\frac{1}{2\beta}\sum_{t=1}^T q_t.

To bound the sum, let $r_t=g_t^\mathsf{T}A_{t-1}^{-1}g_t$. The matrix determinant lemma gives $\det(A_t)/\det(A_{t-1})=1+r_t$, while $q_t=r_t/(1+r_t)\le\log(1+r_t)$. Hence $\sum_t q_t\le\log(\det A_T/\det A_0)$. The eigenvalues of $A_T$ are positive, so the arithmetic-geometric mean inequality and $\operatorname{tr}(A_T)\le d\lambda+TG^2$ imply

\log\frac{\det A_T}{\det A_0} \le d\log\left(\frac{\operatorname{tr}(A_T)}{d\lambda}\right) \le d\log\left(1+\frac{TG^2}{d\lambda}\right).

Combining the two bounds proves the theorem. $\square$

For fixed $d,\lambda,\beta,G$, the time-dependent term grows logarithmically in $T$, rather than linearly. The dimension enters through the determinant bound, which summarizes accumulated curvature across directions. This is the central advantage of the matrix update over a single scalar step size.

Common Mistakes

Checking the Hessian only on the ambient interior. If $K$ has empty interior in $\mathbb R^d$, that check says nothing about concavity on $K$. Restrict derivatives to the affine hull, or use the definition directly.
Assuming bounded diameter guarantees a projection. It does not if $K$ is not closed: a nearest point may fail to be attained. The theorem requires a nonempty closed convex set.
Dropping the squared-gradient term. Under the theorem's bound on directional gradients, exp-concavity yields a negative quadratic term in the regret bound. It is this curvature contribution that offsets the changing-matrix potential in the regret proof.
Confusing the metric projection with Euclidean projection. ONS minimizes distance measured by $A_t$; substituting an ordinary Euclidean projection generally changes the algorithm and invalidates the displayed proof.

Key takeaway: Exp-concavity supplies a quadratic directional-curvature term, and ONS accumulates gradient information in a positive definite matrix. Together they yield a logarithmic regret bound whose leading complexity depends on the dimension.

Check Your Understanding

Try these questions without looking back.

State the definition of $\alpha$-exp-concavity and explain why it implies convexity.
For $f(x)=x^2/2$ on $[-1,1]$, what is the largest $\alpha$ certified by the Hessian criterion?
Why does the ONS theorem require $K$ to be closed as well as convex?
In the regret proof, where does the condition $\beta\le\alpha$ enter?
What quantity controls the dimension-dependent logarithmic term in the bound?