Fast rates with high probability in exp-concave statistical learning

Abstract

We present an algorithm for the statistical learning setting with a bounded exp-concave loss in $d$ dimensions that obtains excess risk $O(d\log (1/\delta )/n)$ with probability at least $1-\delta$. The core technique is to boost the confidence of recent in-expectation $O(d/n)$ excess risk bounds for empirical risk minimization (ERM), without sacrificing the rate, by leveraging a Bernstein condition which holds due to exp-concavity. We also show that with probability $1-\delta$ the standard ERM method obtains excess risk $O(d(\log (n)+\log (1/\delta ))/n)$. We further show that a regret bound for any online learner in this setting translates to a high probability excess risk bound for the corresponding online-to-batch conversion of the online learner. Lastly, we present two high probability bounds for the exp-concave model selection aggregation problem that are quantile-adaptive in a certain sense. The first bound is a purely exponential weights type algorithm, obtains a nearly optimal rate, and has no explicit dependence on the Lipschitz continuity of the loss. The second bound requires Lipschitz continuity but obtains the optimal rate.

added results on model selection aggregation (Section 7)

References in corpus (2)

• Fast learning rates in statistical inference through aggregation
• Excess Risk Bounds for Exponentially Concave Losses

Cited by in corpus (6)

• Generalization Bounds for Stochastic Saddle Point Problems
• Efficient improper learning for online logistic regression
• A Simple Analysis for Exp-concave Empirical Minimization with Arbitrary Convex Regularizer
• Efficient online algorithms for fast-rate regret bounds under sparsity
• Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the $O(1/T)$ Convergence Rate
• Optimal Sketching Bounds for Exp-concave Stochastic Minimization