線上學習與遺憾

拋開「資料是從固定分布獨立抽取」這個令人安心的假設。在線上學習中，樣本一個接一個到來，可能由對手挑選，而你必須在看到每個結果之前就承諾一個預測。你無法奢望完美，所以用遺憾來衡量成敗：你的累積損失，比起你事後（若早知整個序列）所能承諾的單一最佳固定策略，到底差了多少。

在 T 個回合中，遺憾是你的總損失減去比較類別中最佳固定專家或決策的損失。目標是次線性遺憾——遺憾增長慢於 T——如此平均遺憾趨於零，你便漸近地與最佳固定選擇一樣好。典範演算法可達成此目標：乘法權重法（Hedge）在 N 個專家上得到約「T 乘以 log N」的平方根之遺憾；線上梯度下降與追隨正則化領導者（FTRL），對凸損失達到約根號 T，在強凸下達到對數遺憾。資料無需任何統計假設——這些界對任意、甚至對抗性的序列都成立。

遺憾最小化統一了線上凸優化、專家建議預測、吃角子老虎（bandit）、以及賽局式學習，其中無遺憾動態收斂到均衡。線上轉批次（online-to-batch）的轉換，能把任何低遺憾的線上演算法在獨立同分布設定下轉成泛化界，把這個框架接回統計學習。誠實的提醒是：只與最佳固定比較者競爭，在高度非平穩的環境中是個薄弱標竿，這促成了動態遺憾與自適應遺憾的概念。