Regret Bound

The Unknown-Horizon Problem

Online Gradient Descent applies a repeated prediction-and-update process to online convex learning problems. Some online algorithms choose parameters using the total number of rounds T. This is inconvenient when the algorithm must begin before the final duration of the process is known. The doubling trick addresses this problem by replacing one run that requires the complete horizon with a sequence of runs on periods whose lengths grow geometrically.

Periods That Double

The doubling trick labels periods with m. Period m covers rounds from 2^m through 2^(m+1) − 1, inclusive, so its size is 2^m. The first periods therefore have lengths 1, 2, 4, 8, and so on. When one period ends, the construction advances to the next period.

Tracing a Round

1. Start with the candidate period's start round, 2^m.
2. Compute its ending round, 2^(m+1) − 1.
3. Check whether the target round lies between those two endpoints, inclusive.
4. If the target round is beyond the ending round, advance to period m + 1.

Regret Expression and Parameter Role

α√T

The expression α√T describes the stated form of the original algorithm's regret bound. In that expression, α is the factor multiplying √T, while T is the time horizon. This role should be kept separate from the source's statement about the parameter η, whose choice depends on T in the referenced theorem. The doubling trick is introduced to remove that dependence on the unknown horizon from the way the algorithm is run.

When a Period Ends

A period ends at round 2^(m+1) − 1. If another round arrives after that endpoint, the schedule advances to m + 1 and the algorithm is run on the next interval. For example, period 3 ends at round 15. Round 16 is therefore handled in period 4, whose interval begins at 2^4 and continues through 2^5 − 1.

• Treating the period length as its ending round.

  Period 3 has size 2^3, or 8. Its ending round is 2^4 − 1, or 15.

  Fix: Keep the two quantities separate: period m has length 2^m and ends at round 2^(m+1) − 1.

• Starting period 0 at round 0.

  The stated period rule gives period 0 as rounds 2^0 through 2^1 − 1, which is round 1.

  Fix: Use the inclusive interval from 2^m through 2^(m+1) − 1.

• Confusing α with the time horizon T.

  The source describes α as the factor multiplying √T, while T is the time horizon.

  Fix: Read α√T as a product: α is the factor and T is the horizon.

• Assuming the doubling trick requires knowing the final T.

  The construction is designed to continue when another round arrives by advancing to the next prescribed period.

  Fix: When a period ends, move to the next period rather than requiring the final horizon.

Check Your Understanding

Key Takeaways

1. A parameter chosen using the total horizon T creates a difficulty when the process length is unknown at the start.
2. The doubling trick replaces one horizon-dependent run with consecutive periods whose lengths are 2^m.
3. Period m covers rounds 2^m through 2^(m+1) − 1.
4. When a period ends and another round arrives, the schedule advances to the next period.
5. In α√T, α is the factor multiplying √T and T is the time horizon; the source separately identifies η as a parameter that depends on T.