Hedge and online gradient descent — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Hedge with two experts over two rounds

Example

Take two experts and two rounds, use learning rate $ϵ = \log 2$ , and fix the full-information loss vectors in advance as $ℓ_{1} = (0, 1)$ and $ℓ_{2} = (1, 0)$ . Hedge starts from $W_{1} = (1, 1)$ , so $x_{1} = (1 / 2, 1 / 2)$ ; after the first vector it has $W_{2} = (1, 1 / 2)$ and $x_{2} = (2 / 3, 1 / 3)$ . The expected sampled loss is $1 / 2 + 2 / 3 = 7 / 6$ . Each fixed expert has total loss $1$ , so the expected static regret is $1 / 6$ .

Example references

Hedge: the weight update and normalized sampling distribution.

Adversary and feedback models: full-information loss vectors fixed before learner randomization.

Static, dynamic, interval, and strongly adaptive regret: expected static regret against the best fixed expert.

The natural logarithm as the inverse of the exponential function: $\log 2$ is the exponent whose exponential is $2$ .

Expectation of a nonnegative or integrable random variable: bounded measurable losses have finite expectations.

Facts & Assumptions

Given: The two fixed loss vectors and the Hedge learning rate in the Example.

[F1]

Hedge: $W_{1} (i) = 1$ , $x_{t} (i) = W_{t} (i) / \sum_{j} W_{t} (j)$ , and $W_{t + 1} (i) = W_{t} (i) \exp (- ϵ ℓ_{t} (i))$ .

[F2]

Adversary and feedback models: the complete loss vector is revealed after the choice, and the sequence is fixed before randomization.

[F3]

Static, dynamic, interval, and strongly adaptive regret: expected static regret is the expectation of sampled cumulative loss minus the best fixed expert's cumulative loss.

[F4]

The expectation of an indicator is the probability of the event and Linearity, monotonicity, and the modulus bound for expectation: a finite categorical draw has expected loss equal to its probability-weighted sum, and finite sums commute with expectation.

[F5]

The natural logarithm as the inverse of the exponential function and The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ : $\exp (\log 2) = 2$ and $\exp (- \log 2) = 1 / 2$ .

[F6]

Expectation of a nonnegative or integrable random variable: expectation is defined for nonnegative or integrable random variables.

[F7]

Online decision protocol: the learner chooses using only its previous history and does not observe the current loss before its choice.

Verification

1.1F1F2F5F7algebra

The learner chooses before round-one feedback by [F7]; the displayed loss vectors are fixed in advance by [F2]. Initially $x_{1} = (1 / 2, 1 / 2)$ . By [F5], the round-one update multiplies expert 2's weight by $1 / 2$ and expert 1's by $1$ , giving $W_{2} = (1, 1 / 2)$ and $x_{2} = (2 / 3, 1 / 3)$ .

2.1F1F2F4F6step 1.1algebra

The mixed losses are $\sum_{i} x_{1} (i) ℓ_{1} (i) = 1 / 2$ and $\sum_{i} x_{2} (i) ℓ_{2} (i) = 2 / 3$ . By [F2], [F4], [F6], and the algorithm's measurable sampling in [F1], these are the expected sampled losses, so the expected cumulative loss is $7 / 6$ .

3.1F3F6step 2.1algebra∎

Expert 1's total loss is $0 + 1 = 1$ , and expert 2's is $1 + 0 = 1$ . Hence the best fixed expert has loss $1$ and [F3] gives expected static regret $7 / 6 - 1 = 1 / 6$ ; the finite losses are integrable by [F6].

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A projected gradient step on an interval

Example

Assume Countable Choice for the nondegenerate projection step. For $K = [0, 1] \subset R$ , let $P_{K} (z)$ be the point in $K$ minimizing $∣ z - v ∣$ . Then $P_{K} (z) = 0$ for $z < 0$ , $P_{K} (z) = z$ for $0 \leq z \leq 1$ , and $P_{K} (z) = 1$ for $z > 1$ . In one OGD round take $D = 1$ , $G = 2$ , $x_{1} = 1 / 4$ , and $f_{1} (x) = 2 x$ with supplied subgradient $g_{1} = 2$ . Then $η_{1} = 1 / 2$ , the unprojected point is $y_{2} = - 3 / 4$ , and the projected point is $x_{2} = 0$ . The number line places the trial point to the left of the thick segment $K$ and marks its nearest point at the left endpoint.

diagram failed to render:
\begin{tikzpicture}[x=2cm,y=1cm]
\draw[->] (-1.05,0) -- (1.35,0);
\draw[ultra thick] (0,0) -- (1,0);
\fill (-0.75,0) circle (1.5pt) node[above] {$y_2=-3/4$};
\fill (0,0) circle (1.5pt) node[below] {$x_2=P_K(y_2)=0$};
\fill (1,0) circle (1.5pt) node[below] {$1$};
\node[above] at (0.5,0.2) {$K=[0,1]$};
\end{tikzpicture}

Example references

Projected online gradient descent: the step-size and projected update.

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice for the nondegenerate projection branch.

Intervals of $R$ : the nine order-convex forms, nondegeneracy, and length: the closed interval $[0, 1]$ is nonempty when its endpoints are ordered.

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: closedness in the real Euclidean metric.

A convex subset of $R^{m}$ contains every line segment between two of its points: convexity of the decision set.

Subgradients and the subdifferential of a convex function: the supporting-inequality meaning of the supplied vector $g_{1}$ .

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : the norm used for the diameter and gradient bounds.

Metric projection onto a closed convex set satisfies the variational inequality: the criterion used to verify the interval projection.

Facts & Assumptions

Given: $K = [0, 1]$ , $f_{1} (x) = 2 x$ , $x_{1} = 1 / 4$ , $D = 1$ , and $G = 2$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): the nondegenerate OGD update uses Countable Choice through the metric-projection existence theorem.

[F1]

Intervals of $R$ : the nine order-convex forms, nondegeneracy, and length: $[0, 1] = {x \in R : 0 \leq x \leq 1}$ .

[F2]

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: a set is closed when its complement is open, and an open set contains a ball around each of its points.

[F3]

A convex subset of $R^{m}$ contains every line segment between two of its points: a set is convex when it contains every convex combination of two of its points.

[F4]

Metric projection onto a closed convex set satisfies the variational inequality: $p = P_{K} (z)$ if and only if $⟨ z - p, v - p ⟩ \leq 0$ for every $v \in K$ .

[F5]

Subgradients and the subdifferential of a convex function: $g$ is a subgradient at $x$ if $f (v) \geq f (x) + ⟨ g, v - x ⟩$ for every point $v$ of the convex domain.

[F6]

Projected online gradient descent: when $D, G > 0$ , $η_{t} = D / (G \sqrt{t})$ and $x_{t + 1} = P_{K} (x_{t} - η_{t} g_{t})$ .

[F7]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : on $R$ , $∥ g ∥_{2} = ∣ g ∣$ .

[F8]

Projection onto a nonempty closed convex set: under Countable Choice, the metric projection onto $K$ exists and is unique.

Verification

1.1F1F2F3givenalgebra

The interval $[0, 1]$ is nonempty because $0 \in K$ . For $u, v \in K$ and $λ \in [0, 1]$ , $0 \leq (1 - λ) u + λ v \leq (1 - λ) + λ = 1$ , so [F3] makes $K$ convex. Its complement is $(- \infty, 0) \cup (1, \infty)$ . If $z < 0$ , the ball of radius $- z / 2$ about $z$ lies in $(- \infty, 0)$ ; if $z > 1$ , the ball of radius $(z - 1) / 2$ about $z$ lies in $(1, \infty)$ . Thus the complement is open by [F2], so $K$ is closed. Also $∣ u - v ∣ \leq 1$ for $u, v \in K$ , with equality at the endpoints, so its diameter is $1$ .

1.2A1F1F4F8cases

By [A1] and [F8], the projection exists uniquely. If $z < 0$ , then for every $v \in [0, 1]$ , $(z - 0) (v - 0) \leq 0$ , so [F4] and uniqueness give $P_{K} (z) = 0$ . If $0 \leq z \leq 1$ , then $z \in K$ and its distance to itself is zero, so $P_{K} (z) = z$ . If $z > 1$ , then $(z - 1) (v - 1) \leq 0$ for every $v \in [0, 1]$ , and [F4] and uniqueness give $P_{K} (z) = 1$ . These cases prove the stated projection formula.

2.1F5F6F7givenstep 1.2algebra∎

For every $v \in R$ , $f_{1} (v) = 2 v = f_{1} (x_{1}) + 2 (v - x_{1})$ , so [F5] makes $g_{1} = 2$ a valid subgradient and [F7] gives $∥ g_{1} ∥_{2} = 2 = G$ . Hence [F6] gives $η_{1} = 1 / 2$ and $y_{2} = x_{1} - η_{1} g_{1} = 1 / 4 - 1 = - 3 / 4$ . By step 1.2, $x_{2} = P_{K} (y_{2}) = 0$ .

CounterexampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

The projected OGD bound does not cover infeasible comparators

Statement refuted

Refuted claim: For integers $d, T \geq 1$ , let $K \subseteq R^{d}$ be nonempty, closed, and convex with diameter at most a finite $D > 0$ . Let each $f_{t} : R^{d} \to R$ be differentiable and convex on an open convex neighborhood of $K$ , and suppose the projected online-gradient algorithm starts at $x_{1} \in K$ , uses $η_{t} = D / (G \sqrt{t})$ for finite $G > 0$ , and has $∥ \nabla f_{t} (x_{t}) ∥_{2} \leq G$ on every round. Assume Countable Choice for the metric projections. The refuted claim is that

\sum_{t = 1}^{T} (f_{t} (x_{t}) - f_{t} (u)) \leq \frac{3}{2} D G \sqrt{T}

holds for every comparator $u \in R^{d}$ , including points outside $K$ .

Statement references

Projected online gradient descent has static regret at most three-halves of DG square-root T: its stated comparator belongs to $K$ .

Facts & Assumptions

Given: The projected OGD algorithm, $K = [0, 1]$ , diameter bound $D = 1$ , horizon $T = 2$ , losses $f_{t} : R \to R$ defined by $f_{t} (x) = - x$ for $t = 1, 2$ , initial point $x_{1} = 0$ , gradient bound $G = 1$ , and infeasible comparator $u = 2$ .

[A1]

The Axiom of Countable Choice ( ${A C}_{ω}$ ): Countable Choice is assumed for the nondegenerate projection updates.

[F1]

Projected online gradient descent: $η_{t} = D / (G \sqrt{t})$ and $x_{t + 1} = P_{K} (x_{t} - η_{t} g_{t})$ when $D, G > 0$ .

[F2]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : in $R$ , $∥ x ∥_{2} = ∣ x ∣$ .

[F3]

Intervals of $R$ : the nine order-convex forms, nondegeneracy, and length and A convex subset of $R^{m}$ contains every line segment between two of its points: $[0, 1]$ is a nonempty convex set.

[F4]

The metric topology: a set is open when every one of its points has a ball around it inside the set; closed means open complement: a set is closed when its complement is open.

[F5]

The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case: the gradient of a scalar-valued differentiable function on $R$ is its ordinary derivative.

[F6]

Metric projection onto a closed convex set satisfies the variational inequality: $p = P_{K} (z)$ exactly when $(z - p) (v - p) \leq 0$ for every $v \in K$ .

[F7]

Convex and strictly convex functions on Euclidean convex sets: a function is convex when it lies below the chord between any two points of its convex domain.

[F8]

Projection onto a nonempty closed convex set: under Countable Choice, the metric projection onto $K$ exists and is unique.

Counterexample

technique · direct

1.1F2F3F4givenalgebra

The interval $K = [0, 1]$ is nonempty. For $v, w \in K$ and $λ \in [0, 1]$ , $0 \leq (1 - λ) v + λ w \leq (1 - λ) + λ = 1$ , so [F3] makes it convex. Its complement is $(- \infty, 0) \cup (1, \infty)$ . If $z < 0$ , the ball of radius $- z / 2$ about $z$ lies in $(- \infty, 0)$ ; if $z > 1$ , the ball of radius $(z - 1) / 2$ about $z$ lies in $(1, \infty)$ . Thus [F4] makes $K$ closed. Its diameter is $D = 1$ because $∣ v - w ∣ \leq 1$ for $v, w \in [0, 1]$ and the endpoints attain distance $1$ .

1.2F2F5F7givenalgebra

For each $t$ and $h \neq 0$ , $(f_{t} (x + h) - f_{t} (x)) / h = (- (x + h) + x) / h = - 1$ , so the derivative is $g_{t} = - 1$ by [F5]; the affine identity $f_{t} ((1 - λ) x + λ y) = (1 - λ) f_{t} (x) + λ f_{t} (y)$ and [F7] show convexity. Also $∣ g_{t} ∣ = 1 = G$ .

2.1A1F1F6F8step 1.1step 1.2algebra

By [A1] and [F8], both metric projections exist uniquely. Since $D = G = 1$ , $η_{1} = 1$ and $η_{2} = 1 / \sqrt{2}$ . The first unprojected point is $x_{1} - η_{1} g_{1} = 1$ ; for every $v \in [0, 1]$ , $(1 - 1) (v - 1) = 0$ , so [F6] gives $x_{2} = P_{K} (1) = 1$ . The next unprojected point is $x_{2} - η_{2} g_{2} = 1 + 1 / \sqrt{2} > 1$ ; for every $v \in [0, 1]$ , $(1 + 1 / \sqrt{2} - 1) (v - 1) \leq 0$ , so [F6] gives $x_{3} = P_{K} (1 + 1 / \sqrt{2}) = 1$ .

3.1givenstep 1.1step 2.1algebra

The learner's two played losses sum to $f_{1} (x_{1}) + f_{2} (x_{2}) = 0 - 1 = - 1$ , whereas the infeasible comparator has $\sum_{t = 1}^{2} f_{t} (2) = - 4$ . Its regret is therefore $3$ .

4.1givenstep 3.1algebra∎

The proposed right-hand side is $\frac{3}{2} \cdot 1 \cdot 1 \cdot \sqrt{2} = \frac{3}{2} \sqrt{2} < 3$ , since $\sqrt{2} < 2$ . Thus the regret inequality fails for $u = 2 \notin K$ .

Hedge and online gradient descent — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Hedge with two experts over two rounds

Example

Example references

Facts & Assumptions

Verification

A projected gradient step on an interval

Example

Example references

Facts & Assumptions

Verification

The projected OGD bound does not cover infeasible comparators

Statement refuted

Statement references

Facts & Assumptions

Counterexample

Sources