Online Learning и Regret Bounds

GPT-4 имеет VC dimension бесконечность - классическая теория предсказывает катастрофическое переобучение. Но не предсказывает. Online learning объясняет почему: SGD - это online gradient descent с regret O(√T), и это гарантирует generalization без предположений о распределении данных.

• **Google Ads:** FTRL-Proximal используется в click-through rate prediction на триллионах примеров. Sparse L1 решение - критично для efficient inference.
• **AdaGrad:** изобретён в Google 2011, стандарт для NLP. Основа Adam, AdamW, которые используются для GPT/LLaMA.
• **AlphaGo MCTS:** Hedge algorithm внутри - выбор хода как задача N экспертов с exponential weights.

Онлайн-обучение как игра против природы

**GPT-4 имеет VC dimension буквально бесконечность - но обобщает.** Классическая теория говорит: невозможно. Только online learning объясняет, почему SGD на трансформерах работает - это алгоритм с sublinear regret против последовательности лоссов, не статистическая оценка.

Online learning протокол: T раундов, без предположений о распределении данных. На каждом шаге t алгоритм выбирает предсказание wₜ, получает пример (xₜ, yₜ), несёт потери ℓₜ(wₜ). Цель: минимизировать **regret** - насколько алгоритм хуже лучшего фиксированного решения задним числом.

**Regret:** R_T = Σᵢ₌₁ᵀ ℓₜ(wₜ) - min_{w*} Σᵢ₌₁ᵀ ℓₜ(w*) Алгоритм называется no-regret если R_T/T → 0 при T → ∞. Оптимальная граница: R_T = O(√T) для выпуклых потерь. Online-to-batch конверсия: если R_T = O(√T), то для w_avg = (1/T)Σwₜ: E[ℓ(w_avg)] - min ℓ(w) = O(1/√T) Это та же скорость что у SGD - потому что SGD и есть online gradient descent!

EWA и Hedge: оптимальный выбор экспертов

Проблема N экспертов: на каждом шаге выбрать одного из N «советников», минимизировать суммарные потери. **Exponential Weights Algorithm (EWA)** - оптимальный алгоритм с regret O(√T·log N). Это математическая основа boosting, Bayesian model averaging, и attention механизмов.

**EWA (Hedge algorithm):** Веса: wᵢ^(t) = exp(-η·Σₛ<ₜ ℓᵢ(s)) / Z Предсказание: распределение p^(t) = w^(t) / Σwᵢ^(t) Regret bound: R_T ≤ (log N)/η + η·T/8 (для потерь в [0,1]) Оптимальный η = √(8·log N / T): R_T ≤ √(T·log N / 2) Замечательное свойство: bound зависит от log N, не от N. Из 10⁶ экспертов оптимальный находится за цену √(T·log 10⁶) ≈ √(14T) - практически бесплатно.

Attention механизм в трансформерах - это EWA в одном раунде: softmax(QK^T/√d) - это веса экспертов, V - их предсказания. Сходство не случайно: attention оптимально агрегирует информацию из N токенов.

FTRL: Follow-the-Regularized-Leader

**Follow-the-Regularized-Leader (FTRL):** на каждом шаге выбрать w, минимизирующий сумму всех прошлых потерь плюс регуляризатор R(w). Это унифицированный фреймворк, объединяющий онлайн-градиентный спуск, Hedge, и Adagrad в одну теорему.

**FTRL обновление:** wₜ₊₁ = argmin_w [Σₛ≤ₜ ℓₛ(w) + (1/η)·R(w)] **Частные случаи:** - R(w) = ||w||²/2 → Online Gradient Descent - R(w) = Σᵢ wᵢ log wᵢ (энтропия) → Hedge/EWA - R(w) = ||w||₁ → онлайн L1 (sparse предсказания) **Regret bound (общий):** R_T ≤ R(w*)/η + η·Σₜ ||∇ℓₜ||²* где ||·||* - dual norm. AdaGrad адаптивно выбирает η покоординатно: ηᵢ^(t) = η₀/√(Σₛ≤ₜ (∂ℓₛ/∂wᵢ)²) Частые признаки получают меньший шаг - именно то, что нужно для sparse features.

Ключевые идеи

• **Online learning:** T раундов против adversary, без предположений о данных. Regret R_T = алгоритм - лучший w* задним числом.
• **Online Gradient Descent:** R_T = O(D·G·√T) с шагом η = D/(G√T). Online-to-batch: w_avg имеет generalization error O(1/√T).
• **EWA/Hedge:** N экспертов, R_T ≤ √(T·log N / 2). Зависимость логарифмическая - из 10⁶ экспертов оптимальный дёшево.
• **FTRL:** унифицирует OGD (L2 регуляризация) и Hedge (энтропия) через argmin прошлых потерь + R(w).
• **AdaGrad:** FTRL с покоординатным lr = η/√(Σgrad²) - реальная основа Adam/AdamW в GPT.

Связанные темы

Online learning как мост теории и практики:

• Regret bounds (базовый) — Онлайн обучение и базовый regret analysis
• Boosting theory — Следующий урок: AdaBoost как Hedge на weak classifiers

Связанные уроки

• lt-12-online-regret — Углубление regret analysis из базового курса
• lt-09-pac-bayes — EWA - это PAC-Bayes в онлайн-сеттинге
• lt-13-deep-generalization — SGD как online algorithm с implicit regret bound