Localization, Convexity, and Star Aggregation
  Offset Rademacher complexities have been shown to provide tight upper bounds
for the square loss in a broad class of problems including improper statistical
learning and online learning. We show that the offset complexity can be
generalized to any loss that satisfies a certain general convexity condition.
Further, we show that this condition is closely related to both exponential
concavity and self-concordance, unifying apparently disparate results. By a
novel geometric argument, many of our bounds translate to improper learning in
a non-convex class with Audibert's star algorithm. Thus, the offset complexity
provides a versatile analytic tool that covers both convex empirical risk
minimization and improper learning under entropy conditions. Applying the
method, we recover the optimal rates for proper and improper learning with the
$p$-loss for $1 < p < \infty$, and show that improper variants of empirical
risk minimization can attain fast rates for logistic regression and other
generalized linear models.
