Online learning and online learning and online convex optimization – convexity method 4

　　Some online prediction problems can be translated into online convex optimization framework. The following two kinds of convexity techniques are introduced:

　　Some online prediction problems do not seem to fit the online convex optimization framework. For example, in the online classification problem, the prediction domain (predictions domain) or the loss function are not convex. We describe two convex techniques that allow us to use online convex optimization frameworks in other scenarios.

　　1.Convexification by Randomization

　　To demonstrate the randomization technique, we consider a prediction problem suggested by an expert: in each online round, the learner must choose from the recommendations of a given D expert.

　　Represents the selected experts, and the learning machine receives a vector.，amongExpressing complianceThe loss caused by the advice of a specialist is the loss that the learning machine needs to pay.。In this case, decision space is discrete, so it is not convex.

　　The problem of online classification of finite hypothesis classes can easily be used as a special case of prediction with expert advice. Therefore, Cover ‘s impossibility result means no algorithm.Low Regret is obtained from the problem of expert advice.

　　However, as we show below, by allowing learners to randomize their predictions, we can transform the problem into an on-line convex optimization framework, and thus obtain a low Regret algorithm for the problem. orderIt is probability simplex, S is a convex set.　　

　　In the TRound, learner choice，And based onaccording toAn expert is randomly selected to learn the machine to pay the expected loss.

　　

　　Now, we turn the problem into online convex optimization.

　　2.Convexification by Surrogate Loss Functions

　　To explain the second convexity technique, we start again with the specific problem of online classification of finite hypothesis classes. Recall that one of the techniques we used to circumvent Cover’s impossibility result relies on realizabilIty assumption). We assume existence.Makes all t available.。With this assumption, we describe the Halving algorithm and show that it is the most.A prediction error. We now use the online convex optimization language to arrive at similar guarantees:

　　

　　

　　SIt is a convex set.For all t is a convex function, we transform an online convex optimization problem.

　　In the next section, we will derive an algorithm for online convex optimization problems. In particular, one of these algorithms has the following regret bound:

　　

　　Among them,Is a parameter set here to 1/4.It’s a functionOn the Lipschitz parameter of the L1 norm. In our case,,Therefore:

　　

　　adoptSurrogate property, we obtained:

　　

　　This type of bound, where the number of errors is capped by the convex surrogate loss of competing hypothesis, is often referred to as relative loss bound.

　　In the case of realizable, we can further simplify the relative loss bound as follows. Since bound is applicable to all U < S, it is particularly applicable to vectors u = (0,..., 0, 1, 0,..., 0), where 1Corresponding to true hypothesisPosition.

　　 Through our construction, for all t,，Produce:

　　

　　

　　To be continued,…

　　The next section analyzes the FTL algorithm.