為何上界只是故事的一半
至此一切都是上界：承諾某演算法的誤差至多是某個量。但你怎麼知道自己不是單純不夠聰明？也許更好的演算法所需樣本少得多。下界回答了這點：它證明沒有任何演算法——無論多巧妙——能用給定的資料量打敗某個誤差。讓上界與下界吻合是黃金標準——它證實某問題的難度已被完全理解，且你的方法在常數倍意義下是最優的。
下界也馴服了炒作。當有人聲稱某方法只需指數般少的樣本，一個吻合的下界正是那道紀律，判定這在原則上是否可能、抑或只是行銷。我們對上界提過的同一個 樣本複雜度 問題，如今反向運行：每一個演算法都必然承受的最大誤差是多少？
極大極小框架
提問「這問題有多難？」最乾淨的方式是 極大極小框架（minimax framework）：對所有演算法取最小、對問題類中所有分佈取最大的風險。內層的 max 是一個對手，為你的方法挑選最壞的分佈；外層的 min 是你，挑選對抗該對手的最佳方法。所得的極大極小速率，就是問題的內稟難度——與任何特定演算法無關，是學習任務本身的性質。
极小极大风险：任何算法在整个问题类上所能保证的最优最坏情形误差。
證明極大極小下界的策略是一個優美的歸約：挑選一族「統計上彼此接近——從 m 個樣本難以區分——卻有著截然不同最佳答案」的有限分佈。若連區分它們都很難，那麼估計答案至少同樣難，這便把一個「檢定的不可能」轉換成「估計的下界」。Le Cam 的兩點法是最小的實例；Fano 方法則是其多點的推廣。
Fano 方法：資訊限制了估計
Fano 不等式 是下界的資訊論引擎。植入一大批彼此分隔良好的候選真相，並把學習視為「解碼出是哪一個生成了資料」——一個通訊問題。Fano 說：除非真相與樣本之間的互資訊超過「填裝大小的對數」，否則你無法以低誤差還原正確的索引。用候選之間的 KL 散度 約束該互資訊，一個極大極小下界便應運而出：估計不可能快過資訊抵達的速度。
法诺不等式：当互信息预算过小时，给出译码出错误真值的概率下界。
這單一範本——一個分隔的填裝、一份互資訊預算、假設間的 KL 界——便產出統計學中的經典極大極小速率：β-平滑無母數回歸的 n^(−β/(2β+d)) 速率、d 維有母數估計的 sqrt(d/n) 速率，以及稀疏還原的吻合下界。第 2 篇覆蓋數為上界所度量的同一個問題 熵，在此重新現身，如今則下界了「什麼是可達成的」。容量與難度，是同一個量的兩張臉。
天下沒有白吃的午餐：普適的極限
最全面的下界是 天下沒有白吃的午餐定理（no free lunch theorem）：在所有可能的目標函數上取平均，每一個學習演算法的期望誤差都相同——沒有任何學習器普遍地優於隨機猜測。這不是虛無主義；它是一個精確的陳述：泛化需要假設。學習在實務中之所以可行，唯一的原因是真實目標並非均勻隨機——它們平滑、有結構、可壓縮——而一個演算法成功的程度，恰恰取決於其 歸納偏置（inductive bias） 與那份結構吻合的程度。
後悔：在沒有分佈時的學習
以上一切都假設資料是來自固定分佈的獨立同分佈（i.i.d.）。線上學習（online learning） 把這個假設丟掉：樣本一次來一個，甚至可能由對手挑選，你先預測、再承受損失、再更新——永無止境。沒有分佈就沒有「真實風險」，因此基準改為 後悔（regret）：你的累積損失，減去事後看來最佳的單一固定決策之損失。次線性後悔——後悔成長慢於回合數——意味著你的平均損失趨近最佳固定策略，於是即使面對對手，你仍在學習。
遗憾衡量相对于事后最优固定动作的累计损失；最优在线算法能将其控制为亚线性的 √T 量级。
值得注意的是，即使面對全然敵對的序列，次線性後悔仍可達成：線上梯度下降與乘法權重 / Hedge 演算法，在 T 個回合上都達到 sqrt(T) 階的後悔。多臂吃角子老虎機（multi-armed bandit） 是其部分資訊的表親，你只看得到你所採取動作的損失。線上轉批次（online-to-batch）轉換隨即閉合了迴圈：一個低後悔的演算法，餵以 i.i.d. 資料並取平均，便產出一個帶 泛化 保證的假設——於是敵對理論把統計理論交還給你，學習理論的兩個半邊就此相會。