We study fast learning rates when the losses are not necessarily bounded and may have a distribution with heavy tails. To enable such analyses, we introduce two new conditions: (i) the envelope function @math , where @math is the loss function and @math is the hypothesis class, exists and is @math -integrable, and (ii) @math satisfies the multi-scale Bernstein's condition on @math . Under these assumptions, we prove that learning rate faster than @math can be obtained and, depending on @math and the multi-scale Bernstein's powers, can be arbitrarily close to @math . We then verify these assumptions and derive fast learning rates for the problem of vector quantization by @math -means clustering with heavy-tailed distributions. The analyses enable us to obtain novel learning rates that extend and complement existing results in the literature from both theoretical and practical viewpoints.
Fast learning rates for unbounded loses are previously derived in @cite_0 for sub-Gaussian losses and in @cite_8 for hypothesis classes that have sub-exponential envelope functions. In @cite_0 , the Bernstein's condition is not directly imposed, but is replaced by condition (ii) of Lemma @math with @math on the whole hypothesis class, while the assumption of sub-Gaussian hypothesis class validates condition (i). This implies the standard Bernstein's condition with @math and makes the convergence rate @math consistent with our result (note that for sub-Gaussian losses, @math can be chosen arbitrary large). The analysis of @cite_8 concerns about (rather than the we investigate in this paper) and can not be directly compared with our results.
@cite_0 @cite_8
6657555 2547508527 2896834587 2034365297
We establish an excess risk bound of O(H R_n^2 + R_n H L* ) for empirical risk minimization with an H-smooth loss function and a hypothesis class with Rademacher complexity R_n, where L* is the best risk achievable by the hypothesis class. For typical hypothesis classes where R_n = R n , this translates to a learning rate of O(RH n) in the separable (L*=0) case and O(RH n + L^* RH n ) more generally. We also provide similar guarantees for online and stochastic convex optimization with a smooth non-negative objective. We present an algorithm for the statistical learning setting with a bounded exp-concave loss in @math dimensions that obtains excess risk @math with probability at least @math . The core technique is to boost the confidence of recent in-expectation @math 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 @math the standard ERM method obtains excess risk @math . 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. We study the implicit bias of gradient descent methods in solving a binary classification problem over a linearly separable dataset. The classifier is described by a nonlinear ReLU model and the objective function adopts the exponential loss function. We first characterize the landscape of the loss function and show that there can exist spurious asymptotic local minima besides asymptotic global minima. We then show that gradient descent (GD) can converge to either a global or a local max-margin direction, or may diverge from the desired max-margin direction in a general context. For stochastic gradient descent (SGD), we show that it converges in expectation to either the global or the local max-margin direction if SGD converges. We further explore the implicit bias of these algorithms in learning a multi-neuron network under certain stationary conditions, and show that the learned classifier maximizes the margins of each sample pattern partition under the ReLU activation. In this letter, we investigate the impact of choosing different loss functions from the viewpoint of statistical learning theory. We introduce a convexity assumption, which is met by all loss functions commonly used in the literature, and study how the bound on the estimation error changes with the loss. We also derive a general result on the minimizer of the expected risk for a convex loss function in the case of classification. The main outcome of our analysis is that for classification, the hinge loss appears to be the loss of choice. Other things being equal, the hinge loss leads to a convergence rate practically indistinguishable from the logistic loss rate and much better than the square loss rate. Furthermore, if the hypothesis space is sufficiently rich, the bounds obtained for the hinge loss are not loosened by the thresholding stage.