Instance-wise risk comparisons in linear regression: Dominance and admissibility

This talk sketches a program extending the concepts of "dominance" and "admissibility" from statistical decision theory to machine learning. I will do so by presenting two instance-wise risk comparison results in linear regression (with Gaussian design).

First, gradient descent (GD) dominates ridge regression: with comparable regularization (stopping time for GD and l2 penalty for ridge), the excess risk of GD is uniformly within a constant factor of that of ridge for every problem instance, but ridge can be polynomially worse even when tuned optimally. Second, principal component regression (PCR) dominates GD in the same sense, with the number of selected components controlling regularization. As a consequence, both GD and ridge are inadmissible. These results formalize an idea for evaluating algorithms by their instance-wise, instead of worst-case, performance.