Regret Bound
The expression α√T describes the stated form of the original algorithm's 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 2m through 2m+1 − 1, inclusive, so its size is 2m. The first periods therefore have lengths 1, 2, 4, 8, and so on. When one period ends, the construction advances to the next period.
| Period | Start round | End round | Length |
|---|---|---|---|
| m = 0 | 1 | 1 | 1 |
| m = 1 | 2 | 3 | 2 |
| m = 2 | 4 | 7 | 4 |
| m = 3 | 8 | 15 | 8 |
The first four periods obtained from the rule for period m.
Tracing a Round
Locating Round 13
Determine which doubling-trick period contains round 13.
- 1Test period 2
Period 2 covers rounds 22 through 23 − 1, which is rounds 4 through 7. Round 13 is not in this interval.
- 2Test period 3
Period 3 covers rounds 23 through 24 − 1, which is rounds 8 through 15. Round 13 is in this interval.
- 3Check the period length
The length of period 3 is 23, or 8 rounds, matching the interval from round 8 through round 15.
Round 13 belongs to period m = 3, which covers rounds 8 through 15.
- 1Start with the candidate period's start round, 2m.
- 2Compute its ending round, 2m+1 − 1.
- 3Check whether the target round lies between those two endpoints, inclusive.
- 4If the target round is beyond the ending round, advance to period m + 1.
Regret Expression and Parameter Role
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 2m+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 24 and continues through 25 − 1.
Common mistake Treating the period length as its ending round.
What it looks likeCalling period 3 a period that has length 15.
Why it failsPeriod 3 has size 23, or 8. Its ending round is 24 − 1, or 15.
Do this insteadKeep the two quantities separate: period m has length 2^m and ends at round 2^(m+1) − 1.
Common mistake Starting period 0 at round 0.
What it looks likeAssigning round 1 to period 1.
Why it failsThe stated period rule gives period 0 as rounds 20 through 21 − 1, which is round 1.
Do this insteadUse the inclusive interval from 2^m through 2^(m+1) − 1.
Common mistake Confusing α with the time horizon T.
What it looks likeDescribing α as the number of rounds.
Why it failsThe source describes α as the factor multiplying √T, while T is the time horizon.
Do this insteadRead α√T as a product: α is the factor and T is the horizon.
Common mistake Assuming the doubling trick requires knowing the final T.
What it looks likeStopping because the process lasts longer than the current period.
Why it failsThe construction is designed to continue when another round arrives by advancing to the next prescribed period.
Do this insteadWhen a period ends, move to the next period rather than requiring the final horizon.
Check Your Understanding
A process reaches round 6. Determine its period number, starting round, ending round, and period length. Then state whether round 8 begins a new period.
Hints
- Compare round 6 with the intervals for periods 1 and 2.
- For period 2, use the interval from 22 through 23 − 1.
- Round 8 is the first round of the next interval after period 2.
What do you think happens?
Which period contains round 6?
Reveal answer
Period 2
Period 2 covers rounds 22 through 23 − 1, or rounds 4 through 7. Therefore round 6 is in period 2.
Key Takeaways
- 1A parameter chosen using the total horizon T creates a difficulty when the process length is unknown at the start.
- 2The doubling trick replaces one horizon-dependent run with consecutive periods whose lengths are 2m.
- 3Period m covers rounds 2m through 2m+1 − 1.
- 4When a period ends and another round arrives, the schedule advances to the next period.
- 5In α√T, α is the factor multiplying √T and T is the time horizon; the source separately identifies η as a parameter that depends on T.
At a glance
- The doubling trick handles algorithms whose parameter choice depends on an unknown time horizon.
- It partitions rounds into periods with lengths 1, 2, 4, 8, and generally 2m.
- Period m begins at round 2m and ends at round 2m+1 − 1.
- The regret expression α√T uses α as the multiplying factor and T as the time horizon.
- The construction continues by advancing to the next period whenever the current period ends.