Concepts / Agnostic PAC Model

Agnostic PAC Model

Regret measures how much worse an online algorithm performed than a fixed reference predictor.

  • Programming

When Perfect Prediction Is Unavailable

In an unrealizable online-learning setting, we do not assume that some hypothesis labels every example correctly. That makes a perfect-prediction question unsuitable: the learner may have no perfectly correct hypothesis to discover. Regret provides a different standard. It asks whether the online algorithm performed nearly as well as a fixed predictor that could have been followed throughout the same sequence.

Perfect predictorrequired benchmarkFixed comparatorretrospective benchmarkEvery label correctnot assumedRegretloss differencerequiresmeasures
What changes when no hypothesis in the class predicts every example correctly?

Comparing with One Fixed Hypothesis

Suppose an online algorithm A makes predictions over a sequence of T examples. Choose one named hypothesis h as the reference predictor. Regret relative to h measures how much more loss A accumulated than h on that same sequence. The comparison is made after recording both performances. Algorithm A does not need to copy h while the sequence unfolds.

Algorithm Atotal lossHypothesis hfixed predictor2difference10loss of A8loss of haccumulatesaccumulatesminus 8subtracted
How is the online algorithm's total loss compared with the total loss of a single fixed reference predictor?
Worked example

Regret Relative to h

On the same sequence of examples, algorithm A has loss 10 and the fixed hypothesis h has loss 8. What is A's regret relative to h?

  1. 1
    Use the same sequence

    Both losses must describe performance on the same sequence of T examples.

  2. 2
    Compare the losses

    Algorithm A accumulated loss 10, while h accumulated loss 8.

  3. 3
    Find the difference

    A accumulated 2 more units of loss than h.

Result

The regret of A relative to h is 2.

Changing the Comparator to a Class

The phrase relative to h identifies one particular benchmark. If the benchmark changes, the regret value can change because the comparison loss changes. Regret relative to a hypothesis class H uses a stronger benchmark: instead of choosing one named hypothesis in advance, compare the algorithm with the best fixed predictor available within H.

Algorithm Aloss 10hloss 8h1loss 8Best in Hloss 8h2larger lossselectednot selectedcomparecompare
How does the comparator change from one fixed hypothesis to the best-performing hypothesis in a whole class?
Worked example

Class Regret

Algorithm A has loss 10. A hypothesis class H contains fixed predictors, and the best one has loss 8. What is the regret relative to H?

  1. 1
    Search the class conceptually

    The class comparator is the best fixed predictor available within H, not an arbitrary named member.

  2. 2
    Identify the benchmark loss

    The best fixed predictor in H has loss 8.

  3. 3
    Compare with A

    Algorithm A has loss 10, so it accumulated 2 more units of loss than the class benchmark.

Result

The regret relative to H is 2.

Accumulating Loss Across Rounds

Regret is based on total loss, so the individual losses from successive rounds must first be accumulated. On each round, record the algorithm's loss and the fixed comparator's loss. After the final round T, compare the two totals. The difference between those totals is the regret for that comparator.

Round 1A: 1, h: 0TotalsA: 2, h: 1Regret 12 minus 1Round 2A: 0, h: 1Round 3A: 1, h: 0nextnextaccumulatecompare
How do the algorithm's and comparator's losses accumulate over rounds, and how does their difference produce regret?
RoundAlgorithm A lossComparator h lossCumulative A lossCumulative h loss
11010
20111
31021

Generated bookkeeping example showing how per-round losses become total losses.

In this bookkeeping example, A's total loss is 2 and h's total loss is 1. The regret relative to h is therefore 1. The important discipline is to compare totals from the same three rounds, rather than comparing a round from one record with a different round from the other.

Round 1A 1, h 0A total 21 plus 0 plus 1Round 2A 0, h 1h total 10 plus 1 plus 0Round 3A 1, h 0timetimesum A lossessum h losses
How do individual prediction losses across successive rounds combine into the quantities used for regret?

Mistakes in Regret Comparisons

  • Common mistake

    Assuming the unrealizable setting contains a perfectly correct hypothesis.

    What it looks like

    Treating the goal as discovering a hypothesis that labels every example correctly.

    Why it fails

    The unrealizable setting does not assume that any hypothesis labels every example correctly.

    Do this instead

    Judge the algorithm by how competitive it is with a fixed predictor.

  • Common mistake

    Comparing losses from different example sequences.

    What it looks like

    Using A's loss on one sequence and h's loss on another sequence.

    Why it fails

    Regret is defined by comparing performances on the same sequence of T examples.

    Do this instead

    Record both losses on the same sequence before taking their difference.

  • Common mistake

    Confusing one-hypothesis regret with class regret.

    What it looks like

    Using an arbitrary h as the class benchmark even though another member of H has lower loss.

    Why it fails

    Class regret uses the best fixed predictor available within H.

    Do this instead

    First identify the best fixed predictor in H, then compare A with it.

  • Common mistake

    Thinking the algorithm must have followed the comparator.

    What it looks like

    Assuming A can be compared with h only if A copied h on every round.

    Why it fails

    The comparison is retrospective; A makes its own online predictions while the sequence unfolds.

    Do this instead

    Compare the recorded total losses after the sequence is complete.

Best practice

When calculating regret, write down three items in order: the sequence being evaluated, the algorithm's total loss, and the comparator's total loss. Only then compute the difference. If the comparator is a class, identify its best fixed predictor before comparing totals.

Check Your Understanding

MEDIUM

Algorithm A has total loss 13 on a sequence of T examples. A named hypothesis h has total loss 11 on that same sequence. A hypothesis class H contains h and other fixed predictors, and the best fixed predictor in H has total loss 9. Determine A's regret relative to h and A's regret relative to H. Then explain why the two values differ.

Hints
  • For regret relative to h, compare 13 with 11.
  • For regret relative to H, use the best fixed loss, which is 9.
  • The comparator changes, so the difference can change.

What do you think happens?

Using the practice values, what is A's regret relative to the class H?

  • 2

  • 4

  • 9

Reveal answer
Answer:

4

The best fixed predictor in H has loss 9, while A has loss 13. The class comparison therefore gives a difference of 4.

The Regret Perspective

  1. 1
    In the unrealizable setting, no hypothesis is assumed to label every example correctly.
  2. 2
    Regret measures how much more loss the online algorithm accumulated than a fixed comparator on the same sequence.
  3. 3
    Relative to one hypothesis h, the comparator is that named fixed predictor.
  4. 4
    Relative to a class H, the comparator is the best fixed predictor available within H.
  5. 5
    To calculate regret, accumulate each party's losses over the same T examples and compare the resulting totals.

Key Takeaways

  • Regret replaces the demand for perfect prediction with a comparison to a fixed predictor.
  • Regret relative to h compares the algorithm with one named hypothesis.
  • Regret relative to H compares the algorithm with the best fixed predictor in the class.
  • All losses must be measured on the same sequence of examples.
  • Regret is obtained from the difference between the algorithm's total loss and the comparator's total loss.

Related Topics

Related concepts

More concepts starting with A