jmlr jmlr2013 jmlr2013-97 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chao Zhang, Dacheng Tao
Abstract: L´ vy processes refer to a class of stochastic processes, for example, Poisson processes and Browe nian motions, and play an important role in stochastic processes and machine learning. Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process (or briefly called learning process for L´ vy process). It is noteworthy that samples e e in this learning process are not independently and identically distributed (i.i.d.). Therefore, results in traditional statistical learning theory are not applicable (or at least cannot be applied directly), because they are obtained under the sample-i.i.d. assumption. In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process, and then analyze the e asymptotical behavior of the learning process. In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. By using the resultant inequalities, we then obtain the risk bounds based on the covering number. Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. Meanwhile, we also give a comparison to the related results under the samplee i.i.d. assumption. Keywords: L´ vy process, risk bound, deviation inequality, symmetrization inequality, statistical e learning theory, time-dependent
Reference: text
sentIndex sentText sentNum sentScore
1 Journal of Machine Learning Research 14 (2013) 351-376 Submitted 11/11; Revised 11/12; Published 2/13 Risk Bounds of Learning Processes for L´ vy Processes e Chao Zhang∗ ZHANGCHAO 1015@ GMAIL . [sent-1, score-0.693]
2 Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process (or briefly called learning process for L´ vy process). [sent-8, score-1.851]
3 In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process, and then analyze the e asymptotical behavior of the learning process. [sent-17, score-1.046]
4 In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. [sent-18, score-0.304]
5 By using the resultant inequalities, we then obtain the risk bounds based on the covering number. [sent-19, score-0.237]
6 Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. [sent-20, score-1.043]
7 Keywords: L´ vy process, risk bound, deviation inequality, symmetrization inequality, statistical e learning theory, time-dependent 1. [sent-25, score-1.038]
8 Generally, there are three essential parts in the process of obtaining risk bounds: deviation or concentration inequalities, symmetrization inequalities and complexity measures of function classes. [sent-27, score-0.53]
9 For example, Van der Vaart and Wellner (1996) showed risk bounds based on the Rademacher complexity and the covering number by using Hoeffding’s inequality. [sent-28, score-0.237]
10 Instead, one feasible scheme is to find some representative processes, such as the L´ vy process and the mixing process that cover several useful e cases in the scenario of non-i. [sent-56, score-0.907]
11 L´ vy processes are the stochastic processes with stationary and independent increments and e cover a large class of stochastic processes, for example, Brownian motions, Poisson processes, stable processes and subordinators (see Kyprianou, 2006). [sent-77, score-1.11]
12 Moreover, L´ vy processes have been e regarded as prototypes of semimartingales and Feller-Markov processes (Applebaum, 2004b; Sato, 2004). [sent-78, score-0.885]
13 L´ vy processes have been successfully applied to practical applications in finance (Cont and e Tankov, 2006), physics (Applebaum, 2004a), signal processing (Duncan, 2009), image processing (Pedersen et al. [sent-79, score-0.789]
14 Figueroa-L´ pez and o Houdr´ (2006) used projection estimators to estimate the L´ vy density, and then gave a bound to e e exhibit the discrepancy between a projection estimator and the orthogonal projection by using the concentration inequalities for functionals of Poisson integrals. [sent-82, score-0.839]
15 , 1998) to develop e e the deviation inequalities for L´ vy processes and then obtain the risk bounds by using the resulted e deviation inequalities. [sent-84, score-1.159]
16 1 Overview of Main Results This paper is mainly concerned with the theoretical analysis of the learning process for the timedependent samples drawn from a L´ vy process. [sent-87, score-0.797]
17 There are four major concerns in this paper: the e deviation inequality for L´ vy process; the symmetrization inequality of the learning process; the e risk bounds and the asymptotical behavior of the learning process. [sent-88, score-1.222]
18 Generally, in order to obtain the risk bounds of a certain learning process, it is necessary to first obtain the corresponding concentration (or deviation) inequalities for the learning process. [sent-89, score-0.291]
19 , 1998) to develop the deviation inequalities e e for the L´ vy process, which are suitable for the sequence of random variables at different time e points. [sent-91, score-0.817]
20 We then present the symmetrization inequality of the learning process for L´ vy process. [sent-92, score-0.958]
21 By e applying the derived deviation and symmetrization inequalities, we obtain the risk bounds of the learning process, which is based on the covering number. [sent-93, score-0.427]
22 Finally, we use the resulted risk bounds to analyze the asymptotical convergence and the rate of convergence of the learning process for L´ vy e process, respectively. [sent-94, score-1.079]
23 Zhang and Tao (2010) discussed risk bounds for L´ vy process with zero Gaussian component, e but their results are based on some specific assumptions to function classes. [sent-99, score-0.969]
24 The current results do not require any conditions of function classes except the boundedness and the Lipschitz continuity and are valid for a more general scenario where the considered L´ vy process has non-zero Gaussian e component, so they are more general than the previous results. [sent-100, score-0.815]
25 Section 3 introduces some preliminaries of the infinitely divisible (ID) distribution and the L´ vy process. [sent-104, score-0.802]
26 We present the deviation inequalities and the symmetrization inequality of the e learning process for L´ vy process in Section 4. [sent-105, score-1.167]
27 Let Z = (X , Y ) ⊂ RK (K = I + J) and {Zt }t≥0 be an undetermined L´ vy process. [sent-111, score-0.71]
28 Given a function class G and a sample set ZN := {Ztn }N drawn from Z in the n=1 1 time interval [T1 , T2 ] with T1 ≤ t1 < · · · < tN ≤ T2 , we define the empirical risk of g ∈ G as EN (ℓ ◦ g) := 1 N ∑ ℓ(g(xtn ), ytn ), N n=1 (2) which is considered as an approximation to the expected risk (1). [sent-117, score-0.379]
29 The following are the reasons why we suppose that Z is a segment of an undetermined L´ vy process: e • In fact, the tasks of the estimation of channel state information are time-dependent and can be regarded as the approximation to unknown stochastic processes. [sent-125, score-0.794]
30 • The L´ vy process is one of representative processes and covers a large body of stochastic proe cesses, that is, Brownian motions, Poisson processes, compound Poisson processes, Gamma processes and inverse Gaussian processes (see Kyprianou, 2006). [sent-126, score-1.11]
31 g∈G The supremum sup E(ℓ ◦ g) − EN (ℓ ◦ g) (3) g∈G is the so-called risk bound of the learning process for a L´ vy process {Zt }t≥0 . [sent-138, score-1.111]
32 According to (3), (4), (5) and (6), we have sup |E f − EN f | f ∈F = sup E(ℓ ◦ g) − EN (ℓ ◦ g) g∈G T2 1 T g∈G = sup T1 ≤2 sup g∈G t∈[T1 ,T2 ] =2 sup f ∈F t∈[T1 ,T2 ] ℓ(g(xt ), yt )dPt dt − ℓ(g(xt ), yt )dPt − 1 N ∑ ℓ(g(xtn ), ytn ) N n=1 1 N ∑ ℓ(g(xtn ), ytn ) N n=1 Et f − EN f . [sent-141, score-0.517]
33 Therefore, the supremum sup f ∈F t∈[T1 ,T2 ] Et f − EN f plays an important role in studying the risk bound sup f ∈F |E f − EN f | of the learning process for L´ vy process. [sent-142, score-1.119]
34 Infinitely Divisible Distributions and L´ vy Processes e Since the infinitely divisible (ID) distribution is strongly related to the L´ vy process, this section e first introduces the ID distribution and then briefs the L´ vy process for the subsequent discussion. [sent-144, score-2.273]
35 By (7), given a characteristic function φ(θ), we define the corresponding characteristic exponent as ψ(θ) := ln φ(θ) = ln EeiθZ . [sent-155, score-0.487]
36 Before the formal presentation, we need to give a definition of the L´ vy measure e (see Applebaum, 2004a). [sent-157, score-0.693]
37 This ν will be a L´ vy measure if e RK \{0} min{ u 2 , 1}ν(du) < ∞, and ν({0}) = 0. [sent-159, score-0.693]
38 The L´ vy measure describes the expected number of a certain height jump in a time interval of e the unit length. [sent-160, score-0.734]
39 and ·, · and · stand for the inner product and the norm in R Theorem 3 shows that an ID distribution can be completely determined by a triplet (a, A, ν), where a is a drift, A is a Gaussian component and ν is a L´ vy measure. [sent-163, score-0.794]
40 2 L´ vy Processes e First, we give a rigorous definition of L´ vy processes. [sent-166, score-1.386]
41 e Definition 4 A stochastic process {Zt }t≥0 on RK is a L´ vy process if it satisfies the following cone ditions: 1. [sent-167, score-0.89]
42 10 of Sato (2004), a L´ vy process {Zt }t≥0 can be distinguished by the e distribution of Z1 , which has an ID distribution with the generating triplet (a1 , A1 , ν1 ), and at any time t > 0, Zt ∈ {Zt }t≥0 has an ID distribution with the generating triplet (at , At , νt ). [sent-176, score-0.98]
43 Therefore, we call (a1 , A1 , ν1 ) the characteristic triplet of the L´ vy process {Zt }t≥0 . [sent-177, score-0.973]
44 Next, we introduce the L´ vy-Ito decomposition to discuss the relationship between the path of a e L´ vy process and its characteristic triplet (a1 , A1 , ν1 ). [sent-179, score-0.973]
45 Theorem 5 (L´ vy-Ito Decomposition) Consider a triplet (a1 , A1 , ν1 ) where a1 ∈ RK , A1 is a K × e K positive-definite symmetric matrix, ν1 is a L´ vy measure on RK \ {0}. [sent-181, score-0.794]
46 Then, there exist four ine dependent L´ vy processes, L(1) , L(2) , L(3) and L(4) , where L(1) is a constant drift, L(2) is a Brownian e motion, L(3) is a compound Poisson process and L(4) is a square integrable (pure jump) martingale with an a. [sent-182, score-0.795]
47 Taking L = L(1) + L(2) + L(3) + L(4) , there then exists a L´ vy process L = {Zt }0≤t≤T with characteristic e exponent in the form of (8). [sent-185, score-0.911]
48 We only go through some steps of the proof to reveal the relationship between the path of a L´ vy process and its characteristic triplet (a1 , A1 , ν1 ). [sent-187, score-0.973]
49 We also refer to Jacobsen (2005) for the knowledge on jump processes as well as L´ vy processes. [sent-189, score-0.806]
50 • A scaled Brownian motion with linear drift is also a L´ vy process with the characteristic e triplet (a1 , A1 , 0) in the L´ vy-Khintchine representation. [sent-193, score-0.995]
51 Deviation Inequalities and Symmetrization Inequalities In this section, we present the deviation inequalities and symmetrization inequality of the learning process for L´ vy process. [sent-196, score-1.082]
52 1 N OTATIONS Assume that F is a function class consisting of λ-Lipschitz functions and {Zt }t≥0 ⊂ RK is a L´ vy e N = {Z }N process with the characteristic triplet (a1 , A1 , ν1 ). [sent-201, score-0.973]
53 For any t ∈ [T1 , T2 ], we give the following definitions: (∗) 1 N ∑ sup |Etn f − Et f |; t∈[T1 ,T2 ] N n=1 f ∈F (D1) ΣN := sup N (D2) ϕ(α) := ∑ λ2 πK 2 αtn + n=1 (D3) V (n) := RK RK λ u eλα u 2 νtn (du) = tn RK u − 1 νtn (du); u 2 ν1 (du); (D4) Γ(x) := x − (x + 1) ln(x + 1). [sent-203, score-0.239]
54 2 C ONDITIONS In order to achieve the desired risk bounds, some necessary conditions need to be introduced to specify the behavior of L´ vy processes. [sent-211, score-0.866]
55 Condition (C3) implies the L´ vy measure ν1 has a bounded support. [sent-218, score-0.693]
56 To e take an example of Conditions (C2)-(C3), we refer to Poisson processes whose characteristic triplet is (0, 0, ν1 ) with ν1 supporting on {1}. [sent-219, score-0.291]
57 Afterwards, we come up with the deviation inequalities of the learning process for L´ vy process. [sent-220, score-0.902]
58 2 Deviation Inequalities Deviation inequalities play an essential role in obtaining risk bounds of a certain learning process. [sent-222, score-0.26]
59 Moreover, there have been the deviation inequalities for ID distributions and L´ vy processes both with zero Gaussian e components proposed by Houdr´ (2002); Houdr´ and Marchal (2008), respectively. [sent-228, score-0.913]
60 Here, we exe e tend the deviation results in Houdr´ (2002) to develop the deviation inequalities of the learning e process for L´ vy process, which is related to a sequence of random variables taking values from a e L´ vy process at different time points. [sent-229, score-1.735]
61 Theorem 6 Assume that f is a function satisfying Condition (C1) and {Zt }t≥0 ⊂ RK is a L´ vy e N = {Z }N process with the characteristic triplet (a1 , A1 , ν1 ) satisfying Condition (C2). [sent-233, score-0.973]
62 In Theorem 6, we present a deviation inequality of the learning process for the L´ vy process e satisfying Condition (C2). [sent-237, score-0.963]
63 Next, we present the symmetrization inequality of the learning process for L´ vy process. [sent-249, score-0.958]
64 3 Symmetrization Inequality Symmetrization inequalities are mainly used to replace the expected risk by an empirical risk computed on another sample set that is independent of the given sample set but has the identical distribution. [sent-251, score-0.379]
65 Afterward, we propose the symmetrization inequality of the learning process for L´ vy process. [sent-258, score-0.958]
66 Theorem 8 Assume that F is a function class with the range [a, b] and {Zt }t≥0 ⊂ RK is a L´ vy e N and Z′ N be drawn from {Z } process. [sent-262, score-0.712]
67 In the next section, we use the resulted deviation inequalities and symmetrization inequality to achieve the risk bounds of the learning process for L´ vy process. [sent-271, score-1.273]
68 Risk Bounds of Learning Processes for L´ vy Processes e In this section, we present the risk bounds of the learning process for L´ vy process. [sent-273, score-1.662]
69 Theorem 11 Assume that F is a function class composed of functions satisfying Condition (C1) with the range [a, b] and {Zt }t≥0 ⊂ RK is a L´ vy process with the characteristic triplet (a1 , A1 , ν1 ) e satisfying Condition (C2). [sent-281, score-0.973]
70 The righthand-side of the inequality (13) is represented by using the integrals of ϕ−1 , so it is difficult to find − the asymptotic behavior of the risk bound as N goes to the infinity. [sent-285, score-0.258]
71 To overcome the two drawbacks, we develop another risk bound of the learning process for L´ vy e process by adding a mild condition (C3) that requires that the L´ vy measure ν have a bounded e support. [sent-288, score-1.711]
72 Following this result, the next section will discuss the asymptotical behavior of the learning process for L´ vy e process. [sent-293, score-0.836]
73 Convergence Analysis Based on the risk bound (14), this section presents a detailed theoretical analysis to asymptotic convergence and the rate of convergence of the learning process for L´ vy process. [sent-295, score-1.043]
74 Based on Theorem 12, we show that the asymptotic convergence of the learning process for L´ vy process is affected by two factors: the covering number N (F , ξ′ /8, ℓ1 (Z2N )) and the quantity e 1 (∗) ΣN . [sent-305, score-0.992]
75 Thus, according to Theorem 12, we can obtain the following result that describes the asymptotic convergence of the learning process for L´ vy process. [sent-307, score-0.844]
76 e Theorem 13 Assume that F is a function class composed of functions satisfying Condition (C1) with the range [a, b] and {Zt }t≥0 ⊂ RK is a L´ vy process with the characteristic triplet (a1 , A1 , ν1 ) e satisfying Conditions (C2) and (C3). [sent-308, score-0.973]
77 3 of Mendelson (2003): the probability of the event sup E f − EN f > ξ (17) f ∈F 364 ´ R ISK B OUNDS FOR L E VY P ROCESSES will converge to zero for any ξ > 0, if the covering number N F , ξ, ℓ1 (ZN ) satisfies the following 1 condition: ln E N F , ξ, ℓ1 (ZN ) 1 lim < +∞. [sent-313, score-0.32]
78 (18) N→+∞ N Note that in the learning process for L´ vy process, the uniform convergence of the empirical e risk EN f to the expected risk E f may not hold, because the limit (16) does not hold for any ξ > 0 (∗) but for any ξ > ΣN . [sent-314, score-1.114]
79 (∗) Interestingly, we show below that by ignoring the quantity ΣN , the learning process for L´ vy e process has a faster rate of convergence than the classical result (see Mendelson, 2003, Theorem 2. [sent-320, score-0.951]
80 Thus, it is said to be of Hoeffding-type and can directly lead to its alternative expression as follows: 1 2 N) − ln(ε/8) ln E N F , ξ, ℓ1 (Z1 , sup EN f − E f ≤ O (19) N f ∈F √ which implies that the rate of convergence of the i. [sent-325, score-0.267]
81 365 Z HANG AND TAO Here, we adopt a new method to obtain another alternative expression of the Bennett-type risk 1 bound (14) and show that the rate of convergence of the learning process can be up to o(1/N 1. [sent-340, score-0.284]
82 Remark 14 Here, “large-deviation” means that the discrepancy between the empirical risk and (∗) (∗) the expected risk is large (or not small). [sent-342, score-0.339]
83 ln x The above theorem provides another upper bound of the risk bound sup f ∈F EN f − E f in the large-deviation case, where 1. [sent-351, score-0.407]
84 Conclusion In this paper, we study the risk bounds of the learning process for time-dependent samples drawn from a L´ vy process. [sent-360, score-0.988]
85 We first provide the deviation inequalities and the symmetrization inequality e of the learning process, respectively. [sent-361, score-0.304]
86 We then use the resulted deviation inequalities and symmetrization inequality to derive the risk bounds based on the covering number. [sent-362, score-0.541]
87 366 ´ R ISK B OUNDS FOR L E VY P ROCESSES By using the risk bound shown in Theorem 12, we analyze the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. [sent-363, score-1.043]
88 Due to the quantity ΣN , the uniform convergence of the learning process for L´ vy process may not be valid. [sent-369, score-0.906]
89 Furthermore, we adopt a new method to obtain another alternative expression of the risk bound 1 (14) and then find that the rate of convergence of the learning process can reach o(1/N 1. [sent-374, score-0.284]
90 Then, we will develop the risk bounds of the learning process for L´ vy process by using other complexity measures, for example, the e Rademacher complexity and the fat-shattering dimension. [sent-379, score-1.054]
91 (27) Z HANG AND TAO Moreover, we denote the event 1 → → 2N − − ε , h (Z1 ) 2N A := Pr sup h∈Λ > ξ′ 8 , and let 1A be the characteristic function of the event A. [sent-407, score-0.257]
92 (33) By combining Theorem 12, (31), (32) and (33), we can straightforwardly show an upper bound of the risk bound sup f ∈F EN f − E f in the large-deviation case: letting 2N ε := 8EN F , ξ′ /8, ℓ1 (Z1 ) exp NT1 (λ2 πK 2 α +V ) Γ (λR)2 (∗) λR(ξ − ΣN ) 8T2 (λ2 πK 2 α +V ) . [sent-427, score-0.248]
93 L´ vy processes-from probability to finance and quantum groups. [sent-474, score-0.729]
94 Retrieving l´ vy processes from option prices: Regularization of an ill-posed e inverse problem. [sent-525, score-0.789]
95 Mutual information for stochastic signals and l´ vy processes. [sent-530, score-0.72]
96 Risk bounds for the non-parametric estimation of l´ vy proo e e cesses. [sent-536, score-0.729]
97 Introductory Lectures on Fluctuations of L´ vy Processes with Applications (Univere sitext). [sent-582, score-0.693]
98 On α kernels, l´ vy processes, and natural image statistics. [sent-636, score-0.693]
99 L´ vy Processes and Infinite Divisible Distributions (Cambridge Studies in Advanced Mathe ematics). [sent-657, score-0.693]
100 Risk bounds for l´ vy processes in the pac-learning framework. [sent-703, score-0.825]
wordName wordTfidf (topN-words)
[('vy', 0.693), ('en', 0.361), ('etn', 0.213), ('ztn', 0.162), ('zt', 0.156), ('risk', 0.155), ('houdr', 0.142), ('symmetrization', 0.135), ('ln', 0.13), ('pr', 0.112), ('divisible', 0.109), ('triplet', 0.101), ('processes', 0.096), ('characteristic', 0.094), ('isk', 0.094), ('rocesses', 0.094), ('sup', 0.093), ('process', 0.085), ('zn', 0.084), ('tao', 0.083), ('ounds', 0.072), ('inequalities', 0.069), ('rk', 0.066), ('hang', 0.063), ('id', 0.061), ('channel', 0.057), ('poisson', 0.056), ('deviation', 0.055), ('tn', 0.053), ('gn', 0.052), ('nitely', 0.051), ('mendelson', 0.048), ('covering', 0.046), ('inequality', 0.045), ('sato', 0.043), ('rademacher', 0.042), ('asymptotical', 0.04), ('dpt', 0.04), ('kyprianou', 0.04), ('bennett', 0.04), ('asymptotic', 0.04), ('exponent', 0.039), ('bounds', 0.036), ('event', 0.035), ('increments', 0.035), ('meanwhile', 0.032), ('concentration', 0.031), ('dacheng', 0.03), ('tulino', 0.03), ('theorem', 0.029), ('discrepancy', 0.029), ('du', 0.028), ('bousquet', 0.027), ('classical', 0.027), ('stochastic', 0.027), ('rj', 0.027), ('convergence', 0.026), ('love', 0.026), ('kallenberg', 0.026), ('applebaum', 0.026), ('xtn', 0.026), ('ytn', 0.026), ('hoeffding', 0.026), ('cover', 0.024), ('interval', 0.024), ('vaart', 0.023), ('brownian', 0.023), ('ei', 0.023), ('ee', 0.022), ('drawbacks', 0.022), ('drift', 0.022), ('antenna', 0.02), ('biguesh', 0.02), ('bose', 0.02), ('cont', 0.02), ('pedersen', 0.02), ('quantum', 0.02), ('sutivong', 0.02), ('noteworthy', 0.02), ('motions', 0.02), ('scenario', 0.02), ('integral', 0.02), ('drawn', 0.019), ('curve', 0.018), ('zs', 0.018), ('rate', 0.018), ('behavior', 0.018), ('wellner', 0.017), ('reid', 0.017), ('undetermined', 0.017), ('sriperumbudur', 0.017), ('compound', 0.017), ('pez', 0.017), ('lectures', 0.017), ('jump', 0.017), ('quantity', 0.017), ('valid', 0.017), ('recalling', 0.017), ('probability', 0.016), ('stationary', 0.016)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000001 97 jmlr-2013-Risk Bounds of Learning Processes for Lévy Processes
Author: Chao Zhang, Dacheng Tao
Abstract: L´ vy processes refer to a class of stochastic processes, for example, Poisson processes and Browe nian motions, and play an important role in stochastic processes and machine learning. Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process (or briefly called learning process for L´ vy process). It is noteworthy that samples e e in this learning process are not independently and identically distributed (i.i.d.). Therefore, results in traditional statistical learning theory are not applicable (or at least cannot be applied directly), because they are obtained under the sample-i.i.d. assumption. In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process, and then analyze the e asymptotical behavior of the learning process. In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. By using the resultant inequalities, we then obtain the risk bounds based on the covering number. Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. Meanwhile, we also give a comparison to the related results under the samplee i.i.d. assumption. Keywords: L´ vy process, risk bound, deviation inequality, symmetrization inequality, statistical e learning theory, time-dependent
2 0.089557193 7 jmlr-2013-A Risk Comparison of Ordinary Least Squares vs Ridge Regression
Author: Paramveer S. Dhillon, Dean P. Foster, Sham M. Kakade, Lyle H. Ungar
Abstract: We compare the risk of ridge regression to a simple variant of ordinary least squares, in which one simply projects the data onto a finite dimensional subspace (as specified by a principal component analysis) and then performs an ordinary (un-regularized) least squares regression in this subspace. This note shows that the risk of this ordinary least squares method (PCA-OLS) is within a constant factor (namely 4) of the risk of ridge regression (RR). Keywords: risk inflation, ridge regression, pca
3 0.072056584 105 jmlr-2013-Sparsity Regret Bounds for Individual Sequences in Online Linear Regression
Author: Sébastien Gerchinovitz
Abstract: We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T . We introduce the notion of sparsity regret bound, which is a deterministic online counterpart of recent risk bounds derived in the stochastic setting under a sparsity scenario. We prove such regret bounds for an online-learning algorithm called SeqSEW and based on exponential weighting and data-driven truncation. In a second part we apply a parameter-free version of this algorithm to the stochastic setting (regression model with random design). This yields risk bounds of the same flavor as in Dalalyan and Tsybakov (2012a) but which solve two questions left open therein. In particular our risk bounds are adaptive (up to a logarithmic factor) to the unknown variance of the noise if the latter is Gaussian. We also address the regression model with fixed design. Keywords: sparsity, online linear regression, individual sequences, adaptive regret bounds
4 0.071651272 102 jmlr-2013-Sparse Matrix Inversion with Scaled Lasso
Author: Tingni Sun, Cun-Hui Zhang
Abstract: We propose a new method of learning a sparse nonnegative-definite target matrix. Our primary example of the target matrix is the inverse of a population covariance or correlation matrix. The algorithm first estimates each column of the target matrix by the scaled Lasso and then adjusts the matrix estimator to be symmetric. The penalty level of the scaled Lasso for each column is completely determined by data via convex minimization, without using cross-validation. We prove that this scaled Lasso method guarantees the fastest proven rate of convergence in the spectrum norm under conditions of weaker form than those in the existing analyses of other ℓ1 regularized algorithms, and has faster guaranteed rate of convergence when the ratio of the ℓ1 and spectrum norms of the target inverse matrix diverges to infinity. A simulation study demonstrates the computational feasibility and superb performance of the proposed method. Our analysis also provides new performance bounds for the Lasso and scaled Lasso to guarantee higher concentration of the error at a smaller threshold level than previous analyses, and to allow the use of the union bound in column-by-column applications of the scaled Lasso without an adjustment of the penalty level. In addition, the least squares estimation after the scaled Lasso selection is considered and proven to guarantee performance bounds similar to that of the scaled Lasso. Keywords: precision matrix, concentration matrix, inverse matrix, graphical model, scaled Lasso, linear regression, spectrum norm
5 0.059547722 114 jmlr-2013-The Rate of Convergence of AdaBoost
Author: Indraneel Mukherjee, Cynthia Rudin, Robert E. Schapire
Abstract: The AdaBoost algorithm was designed to combine many “weak” hypotheses that perform slightly better than random guessing into a “strong” hypothesis that has very low error. We study the rate at which AdaBoost iteratively converges to the minimum of the “exponential loss.” Unlike previous work, our proofs do not require a weak-learning assumption, nor do they require that minimizers of the exponential loss are finite. Our first result shows that the exponential loss of AdaBoost’s computed parameter vector will be at most ε more than that of any parameter vector of ℓ1 -norm bounded by B in a number of rounds that is at most a polynomial in B and 1/ε. We also provide lower bounds showing that a polynomial dependence is necessary. Our second result is that within C/ε iterations, AdaBoost achieves a value of the exponential loss that is at most ε more than the best possible value, where C depends on the data set. We show that this dependence of the rate on ε is optimal up to constant factors, that is, at least Ω(1/ε) rounds are necessary to achieve within ε of the optimal exponential loss. Keywords: AdaBoost, optimization, coordinate descent, convergence rate
6 0.059088316 80 jmlr-2013-One-shot Learning Gesture Recognition from RGB-D Data Using Bag of Features
7 0.052981269 35 jmlr-2013-Distribution-Dependent Sample Complexity of Large Margin Learning
8 0.049570747 36 jmlr-2013-Distributions of Angles in Random Packing on Spheres
9 0.043460943 94 jmlr-2013-Ranked Bandits in Metric Spaces: Learning Diverse Rankings over Large Document Collections
10 0.041381821 77 jmlr-2013-On the Convergence of Maximum Variance Unfolding
11 0.039303187 18 jmlr-2013-Beyond Fano's Inequality: Bounds on the Optimal F-Score, BER, and Cost-Sensitive Risk and Their Implications
12 0.03885955 26 jmlr-2013-Conjugate Relation between Loss Functions and Uncertainty Sets in Classification Problems
13 0.035104673 58 jmlr-2013-Language-Motivated Approaches to Action Recognition
14 0.033706218 4 jmlr-2013-A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
15 0.033167329 70 jmlr-2013-Maximum Volume Clustering: A New Discriminative Clustering Approach
16 0.033068471 43 jmlr-2013-Fast MCMC Sampling for Markov Jump Processes and Extensions
17 0.031194948 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization
18 0.029395223 101 jmlr-2013-Sparse Activity and Sparse Connectivity in Supervised Learning
19 0.028597409 2 jmlr-2013-A Binary-Classification-Based Metric between Time-Series Distributions and Its Use in Statistical and Learning Problems
20 0.028067619 10 jmlr-2013-Algorithms and Hardness Results for Parallel Large Margin Learning
topicId topicWeight
[(0, -0.149), (1, 0.06), (2, -0.008), (3, 0.082), (4, -0.024), (5, -0.136), (6, 0.058), (7, -0.029), (8, 0.064), (9, -0.015), (10, -0.018), (11, 0.024), (12, -0.021), (13, 0.013), (14, -0.012), (15, 0.088), (16, -0.062), (17, -0.247), (18, 0.091), (19, 0.129), (20, -0.074), (21, 0.061), (22, 0.101), (23, -0.075), (24, 0.004), (25, 0.287), (26, -0.2), (27, -0.064), (28, 0.167), (29, -0.142), (30, -0.134), (31, 0.044), (32, -0.042), (33, 0.07), (34, -0.129), (35, 0.009), (36, 0.132), (37, 0.09), (38, -0.112), (39, -0.18), (40, -0.071), (41, -0.073), (42, 0.007), (43, -0.101), (44, 0.037), (45, -0.029), (46, 0.09), (47, 0.118), (48, 0.045), (49, 0.041)]
simIndex simValue paperId paperTitle
same-paper 1 0.96772248 97 jmlr-2013-Risk Bounds of Learning Processes for Lévy Processes
Author: Chao Zhang, Dacheng Tao
Abstract: L´ vy processes refer to a class of stochastic processes, for example, Poisson processes and Browe nian motions, and play an important role in stochastic processes and machine learning. Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process (or briefly called learning process for L´ vy process). It is noteworthy that samples e e in this learning process are not independently and identically distributed (i.i.d.). Therefore, results in traditional statistical learning theory are not applicable (or at least cannot be applied directly), because they are obtained under the sample-i.i.d. assumption. In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process, and then analyze the e asymptotical behavior of the learning process. In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. By using the resultant inequalities, we then obtain the risk bounds based on the covering number. Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. Meanwhile, we also give a comparison to the related results under the samplee i.i.d. assumption. Keywords: L´ vy process, risk bound, deviation inequality, symmetrization inequality, statistical e learning theory, time-dependent
2 0.70615971 7 jmlr-2013-A Risk Comparison of Ordinary Least Squares vs Ridge Regression
Author: Paramveer S. Dhillon, Dean P. Foster, Sham M. Kakade, Lyle H. Ungar
Abstract: We compare the risk of ridge regression to a simple variant of ordinary least squares, in which one simply projects the data onto a finite dimensional subspace (as specified by a principal component analysis) and then performs an ordinary (un-regularized) least squares regression in this subspace. This note shows that the risk of this ordinary least squares method (PCA-OLS) is within a constant factor (namely 4) of the risk of ridge regression (RR). Keywords: risk inflation, ridge regression, pca
Author: Ming-Jie Zhao, Narayanan Edakunni, Adam Pocock, Gavin Brown
Abstract: Fano’s inequality lower bounds the probability of transmission error through a communication channel. Applied to classification problems, it provides a lower bound on the Bayes error rate and motivates the widely used Infomax principle. In modern machine learning, we are often interested in more than just the error rate. In medical diagnosis, different errors incur different cost; hence, the overall risk is cost-sensitive. Two other popular criteria are balanced error rate (BER) and F-score. In this work, we focus on the two-class problem and use a general definition of conditional entropy (including Shannon’s as a special case) to derive upper/lower bounds on the optimal F-score, BER and cost-sensitive risk, extending Fano’s result. As a consequence, we show that Infomax is not suitable for optimizing F-score or cost-sensitive risk, in that it can potentially lead to low F-score and high risk. For cost-sensitive risk, we propose a new conditional entropy formulation which avoids this inconsistency. In addition, we consider the common practice of using a threshold on the posterior probability to tune performance of a classifier. As is widely known, a threshold of 0.5, where the posteriors cross, minimizes error rate—we derive similar optimal thresholds for F-score and BER. Keywords: balanced error rate, F-score (Fβ -measure), cost-sensitive risk, conditional entropy, lower/upper bound
4 0.33997935 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization
Author: Yuchen Zhang, John C. Duchi, Martin J. Wainwright
Abstract: We analyze two communication-efficient algorithms for distributed optimization in statistical settings involving large-scale data sets. The first algorithm is a standard averaging method that distributes the N data samples evenly to m machines, performs separate minimization on each subset, and then averages the estimates. We provide a sharp analysis of this average mixture algorithm, showing that under a reasonable set of conditions, the combined parameter achieves √ mean-squared error (MSE) that decays as O (N −1 + (N/m)−2 ). Whenever m ≤ N, this guarantee matches the best possible rate achievable by a centralized algorithm having access to all N samples. The second algorithm is a novel method, based on an appropriate form of bootstrap subsampling. Requiring only a single round of communication, it has mean-squared error that decays as O (N −1 + (N/m)−3 ), and so is more robust to the amount of parallelization. In addition, we show that a stochastic gradient-based method attains mean-squared error decaying as O (N −1 + (N/m)−3/2 ), easing computation at the expense of a potentially slower MSE rate. We also provide an experimental evaluation of our methods, investigating their performance both on simulated data and on a large-scale regression problem from the internet search domain. In particular, we show that our methods can be used to efficiently solve an advertisement prediction problem from the Chinese SoSo Search Engine, which involves logistic regression with N ≈ 2.4 × 108 samples and d ≈ 740,000 covariates. Keywords: distributed learning, stochastic optimization, averaging, subsampling
5 0.29416505 35 jmlr-2013-Distribution-Dependent Sample Complexity of Large Margin Learning
Author: Sivan Sabato, Nathan Srebro, Naftali Tishby
Abstract: We obtain a tight distribution-specific characterization of the sample complexity of large-margin classification with L2 regularization: We introduce the margin-adapted dimension, which is a simple function of the second order statistics of the data distribution, and show distribution-specific upper and lower bounds on the sample complexity, both governed by the margin-adapted dimension of the data distribution. The upper bounds are universal, and the lower bounds hold for the rich family of sub-Gaussian distributions with independent features. We conclude that this new quantity tightly characterizes the true sample complexity of large-margin classification. To prove the lower bound, we develop several new tools of independent interest. These include new connections between shattering and hardness of learning, new properties of shattering with linear classifiers, and a new lower bound on the smallest eigenvalue of a random Gram matrix generated by sub-Gaussian variables. Our results can be used to quantitatively compare large margin learning to other learning rules, and to improve the effectiveness of methods that use sample complexity bounds, such as active learning. Keywords: supervised learning, sample complexity, linear classifiers, distribution-dependence
7 0.27284631 102 jmlr-2013-Sparse Matrix Inversion with Scaled Lasso
8 0.25666487 43 jmlr-2013-Fast MCMC Sampling for Markov Jump Processes and Extensions
9 0.24127989 77 jmlr-2013-On the Convergence of Maximum Variance Unfolding
10 0.23703696 114 jmlr-2013-The Rate of Convergence of AdaBoost
11 0.22241835 105 jmlr-2013-Sparsity Regret Bounds for Individual Sequences in Online Linear Regression
12 0.21226983 36 jmlr-2013-Distributions of Angles in Random Packing on Spheres
13 0.20942982 94 jmlr-2013-Ranked Bandits in Metric Spaces: Learning Diverse Rankings over Large Document Collections
15 0.19162931 14 jmlr-2013-Asymptotic Results on Adaptive False Discovery Rate Controlling Procedures Based on Kernel Estimators
16 0.18536921 9 jmlr-2013-A Widely Applicable Bayesian Information Criterion
17 0.17674322 26 jmlr-2013-Conjugate Relation between Loss Functions and Uncertainty Sets in Classification Problems
18 0.17165275 4 jmlr-2013-A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
19 0.15959804 58 jmlr-2013-Language-Motivated Approaches to Action Recognition
20 0.15750654 64 jmlr-2013-Lovasz theta function, SVMs and Finding Dense Subgraphs
topicId topicWeight
[(0, 0.02), (5, 0.113), (6, 0.026), (10, 0.051), (20, 0.014), (23, 0.027), (68, 0.014), (70, 0.561), (75, 0.017), (85, 0.039), (87, 0.013)]
simIndex simValue paperId paperTitle
same-paper 1 0.88714087 97 jmlr-2013-Risk Bounds of Learning Processes for Lévy Processes
Author: Chao Zhang, Dacheng Tao
Abstract: L´ vy processes refer to a class of stochastic processes, for example, Poisson processes and Browe nian motions, and play an important role in stochastic processes and machine learning. Therefore, it is essential to study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process (or briefly called learning process for L´ vy process). It is noteworthy that samples e e in this learning process are not independently and identically distributed (i.i.d.). Therefore, results in traditional statistical learning theory are not applicable (or at least cannot be applied directly), because they are obtained under the sample-i.i.d. assumption. In this paper, we study risk bounds of the learning process for time-dependent samples drawn from a L´ vy process, and then analyze the e asymptotical behavior of the learning process. In particular, we first develop the deviation inequalities and the symmetrization inequality for the learning process. By using the resultant inequalities, we then obtain the risk bounds based on the covering number. Finally, based on the resulting risk bounds, we study the asymptotic convergence and the rate of convergence of the learning process for L´ vy process. Meanwhile, we also give a comparison to the related results under the samplee i.i.d. assumption. Keywords: L´ vy process, risk bound, deviation inequality, symmetrization inequality, statistical e learning theory, time-dependent
2 0.87600851 65 jmlr-2013-Lower Bounds and Selectivity of Weak-Consistent Policies in Stochastic Multi-Armed Bandit Problem
Author: Antoine Salomon, Jean-Yves Audibert, Issam El Alaoui
Abstract: This paper is devoted to regret lower bounds in the classical model of stochastic multi-armed bandit. A well-known result of Lai and Robbins, which has then been extended by Burnetas and Katehakis, has established the presence of a logarithmic bound for all consistent policies. We relax the notion of consistency, and exhibit a generalisation of the bound. We also study the existence of logarithmic bounds in general and in the case of Hannan consistency. Moreover, we prove that it is impossible to design an adaptive policy that would select the best of two algorithms by taking advantage of the properties of the environment. To get these results, we study variants of popular Upper Confidence Bounds (UCB) policies. Keywords: stochastic bandits, regret lower bounds, consistency, selectivity, UCB policies 1. Introduction and Notations Multi-armed bandits are a classical way to illustrate the difficulty of decision making in the case of a dilemma between exploration and exploitation. The denomination of these models comes from an analogy with playing a slot machine with more than one arm. Each arm has a given (and unknown) reward distribution and, for a given number of rounds, the agent has to choose one of them. As the goal is to maximize the sum of rewards, each round decision consists in a trade-off between exploitation (i.e., playing the arm that has been the more lucrative so far) and exploration (i.e., testing another arm, hoping to discover an alternative that beats the current best choice). One possible application is clinical trial: a doctor wants to heal as many patients as possible, the patients arrive sequentially, and the effectiveness of each treatment is initially unknown (Thompson, 1933). Bandit problems have initially been studied by Robbins (1952), and since then they have been applied to many fields such as economics (Lamberton et al., 2004; Bergemann and Valimaki, 2008), games (Gelly and Wang, 2006), and optimisation (Kleinberg, 2005; Coquelin and Munos, 2007; Kleinberg et al., 2008; Bubeck et al., 2009). ∗. Also at Willow, CNRS/ENS/INRIA - UMR 8548. c 2013 Antoine Salomon, Jean-Yves Audibert and Issam El Alaoui. S ALOMON , AUDIBERT AND E L A LAOUI 1.1 Setting In this paper, we consider the following model. A stochastic multi-armed bandit problem is defined by: • a number of rounds n, • a number of arms K ≥ 2, • an environment θ = (ν1 , · · · , νK ), where each νk (k ∈ {1, · · · , K}) is a real-valued measure that represents the distribution reward of arm k. The number of rounds n may or may not be known by the agent, but this will not affect the present study. We assume that rewards are bounded. Thus, for simplicity, each νk is a probability on [0, 1]. Environment θ is initially unknown by the agent but lies in some known set Θ. For the problem to be interesting, the agent should not have great knowledges of its environment, so that Θ should not be too small and/or only contain too trivial distributions such as Dirac measures. To make it simple, we may assume that Θ contains all environments where each reward distribution is a Dirac distribution or a Bernoulli distribution. This will be acknowledged as Θ having the Dirac/Bernoulli property. For technical reason, we may also assume that Θ is of the form Θ1 × . . . × ΘK , meaning that Θk is the set of possible reward distributions of arm k. This will be acknowledged as Θ having the product property. The game is as follows. At each round (or time step) t = 1, · · · , n, the agent has to choose an arm It in the set {1, · · · , K}. This decision is based on past actions and observations, and the agent may also randomize his choice. Once the decision is made, the agent gets and observes a reward that is drawn from νIt independently from the past. Thus a policy (or strategy) can be described by a sequence (σt )t≥1 (or (σt )1≤t≤n if the number of rounds n is known) such that each σt is a mapping from the set {1, . . . , K}t−1 × [0, 1]t−1 of past decisions and rewards into the set of arm {1, . . . , K} (or into the set of probabilities on {1, . . . , K}, in case the agent randomizes his choices). For each arm k and all time step t, let Tk (t) = ∑ts=1 ½Is =k denote the sampling time, that is, the number of times arm k was pulled from round 1 to round t, and Xk,1 , Xk,2 , . . . , Xk,Tk (t) the corresponding sequence of rewards. We denote by Pθ the distribution on the probability space such that for any k ∈ {1, . . . , K}, the random variables Xk,1 , Xk,2 , . . . , Xk,n are i.i.d. realizations of νk , and such that these K sequences of random variables are independent. Let Eθ denote the associated expectation. Let µk = xdνk (x) be the mean reward of arm k. Introduce µ∗ = maxk∈{1,...,K} µk and fix an arm ∗ ∈ argmax ∗ k k∈{1,...,K} µk , that is, k has the best expected reward. The agent aims at minimizing its regret, defined as the difference between the cumulative reward he would have obtained by always drawing the best arm and the cumulative reward he actually received. Its regret is thus n n Rn = ∑ Xk∗ ,t − ∑ XIt ,TIt (t) . t=1 t=1 As most of the publications on this topic, we focus on the expected regret, for which one can check that: K E θ Rn = ∑ ∆k Eθ [Tk (n)], k=1 188 (1) L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS where ∆k is the optimality gap of arm k, defined by ∆k = µ∗ − µk . We also define ∆ as the gap between the best arm and the second best arm, that is, ∆ := mink:∆k >0 ∆k . Other notions of regret exist in the literature. One of them is the quantity n max ∑ Xk,t − XIt ,TIt (t) , k t=1 which is mostly used in adversarial settings. Results and ideas we want to convey here are more suited to expected regret, and considering other definitions of regret would only bring some more technical intricacies. 1.2 Consistency and Regret Lower Bounds Former works have shown the existence of lower bounds on the expected regret of a large class of policies: intuitively, to perform well the agent has to explore all arms, and this requires a significant amount of suboptimal choices. In this way, Lai and Robbins (1985) proved a lower bound of order log n in a particular parametric framework, and they also exhibited optimal policies. This work has then been extended by Burnetas and Katehakis (1996). Both papers deal with consistent policies, meaning that they only consider policies such that: ∀a > 0, ∀θ ∈ Θ, Eθ [Rn ] = o(na ). (2) Let us detail the bound of Burnetas and Katehakis, which is valid when Θ has the product property. Given an environment θ = (ν1 , · · · , νK ) and an arm k ∈ {1, . . . , K}, define: Dk (θ) := inf ˜ νk ∈Θk :E[˜ k ]>µ∗ ν ˜ KL(νk , νk ), where KL(ν, µ) denotes the Kullback-Leibler divergence of measures ν and µ. Now fix a consistent policy and an environment θ ∈ Θ. If k is a suboptimal arm (i.e., µk = µ∗ ) such that 0 < Dk (θ) < ∞, then (1 − ε) log n ∀ε > 0, lim P Tk (n) ≥ = 1. n→+∞ Dk (θ) This readily implies that: lim inf n→+∞ Eθ [Tk (n)] 1 ≥ . log n Dk (θ) Thanks to Formula (1), it is then easy to deduce a lower bound of the expected regret. One contribution of this paper is to generalize the study of regret lower bounds, by considering weaker notions of consistency: α-consistency and Hannan consistency. We will define αconsistency (α ∈ [0, 1)) as a variant of Equation (2), where equality Eθ [Rn ] = o(na ) only holds for all a > α. We show that the logarithmic bound of Burnetas and Katehakis still holds, but coefficient 1−α 1 Dk (θ) is turned into Dk (θ) . We also prove that the dependence of this new bound with respect to the term 1 − α is asymptotically optimal when n → +∞ (up to a constant). We will also consider the case of Hannan consistency. Indeed, any policy achieves at most an expected regret of order n: because of the equality ∑K Tk (n) = n and thanks to Equation (1), one k=1 can show that Eθ Rn ≤ n maxk ∆k . More intuitively, this comes from the fact that the average cost of pulling an arm k is a constant ∆k . As a consequence, it is natural to wonder what happens when 189 S ALOMON , AUDIBERT AND E L A LAOUI dealing with policies whose expected regret is only required to be o(n), which is equivalent to Hannan consistency. This condition is less restrictive than any of the previous notions of consistency. In this larger class of policy, we show that the lower bounds on the expected regret are no longer logarithmic, but can be much smaller. Finally, even if no logarithmic lower bound holds on the whole set Θ, we show that there necessarily exist some environments θ for which the expected regret is at least logarithmic. The latter result is actually valid without any assumptions on the considered policies, and only requires a simple property on Θ. 1.3 Selectivity As we exhibit new lower bounds, we want to know if it is possible to provide optimal policies that achieve these lower bounds, as it is the case in the classical class of consistent policies. We answer negatively to this question, and for this we solve the more general problem of selectivity. Given a set of policies, we define selectivity as the ability to perform at least as good as the policy that is best suited to the current environment θ. Still, such an ability can not be implemented. As a by-product it is not possible to design a procedure that would specifically adapt to some kinds of environments, for example by selecting a particular policy. This contribution is linked with selectivity in on-line learning problem with perfect information, commonly addressed by prediction with expert advice (see, e.g., Cesa-Bianchi et al., 1997). In this spirit, a closely related problem is the one of regret against the best strategy from a pool studied by Auer et al. (2003). The latter designed an algorithm in the context of adversarial/nonstochastic bandit whose decisions are based on a given number of recommendations (experts), which are themselves possibly the rewards received by a set of given policies. To a larger extent, model selection has been intensively studied in statistics, and is commonly solved by penalization methods (Mallows, 1973; Akaike, 1973; Schwarz, 1978). 1.4 UCB Policies Some of our results are obtained using particular Upper Confidence Bound algorithms. These algorithms were introduced by Lai and Robbins (1985): they basically consist in computing an index for each arm, and selecting the arm with the greatest index. A simple and efficient way to design such policies is as follows: choose each index as low as possible such that, conditional to past observations, it is an upper bound of the mean reward of the considered arm with high probability (or, say, with high confidence level). This idea can be traced back to Agrawal (1995), and has been popularized by Auer et al. (2002), who notably described a policy called UCB1. In this policy, each index Bk,s,t is defined by an arm k, a time step t, an integer s that indicates the number of times arm k has been pulled before round t, and is given by: ˆ Bk,s,t = Xk,s + 2 logt , s ˆ ˆ where Xk,s is the empirical mean of arm k after s pulls, that is, Xk,s = 1 ∑s Xk,u . s u=1 To summarize, UCB1 policy first pulls each arm once and then, at each round t > K, selects an arm k that maximizes Bk,Tk (t−1),t . Note that, by means of Hoeffding’s inequality, the index Bk,Tk (t−1),t is indeed an upper bound of µk with high probability (i.e., the probability is greater than 1 − 1/t 4 ). ˆ Another way to understand this index is to interpret the empiric mean Xk,Tk (t−1) as an ”exploitation” 190 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS term, and the square root 2 logt/s as an ”exploration” term (because the latter gradually increases when arm k is not selected). Policy UCB1 achieves the logarithmic bound (up to a multiplicative constant), as it was shown that: ∀θ ∈ Θ, ∀n ≥ 3, Eθ [Tk (n)] ≤ 12 K log n log n log n ≤ 12K . and Eθ Rn ≤ 12 ∑ 2 ∆ ∆k k=1 ∆k Audibert et al. (2009) studied some variants of UCB1 policy. Among them, one consists in changing the 2 logt in the exploration term into ρ logt, where ρ > 0. This can be interpreted as a way to tune exploration: the smaller ρ is, the better the policy will perform in simple environments where information is disclosed easily (for example when all reward distributions are Dirac measures). On the contrary, ρ has to be greater to face more challenging environments (typically when reward distributions are Bernoulli laws with close parameters). This policy, that we denote UCB(ρ), was proven by Audibert et al. to achieve the logarithmic bound when ρ > 1, and the optimality was also obtained when ρ > 1 for a variant of UCB(ρ). 2 Bubeck (2010) showed in his PhD dissertation that their ideas actually enable to prove optimality 1 of UCB(ρ) for ρ > 1 . Moreover, the case ρ = 2 corresponds to a confidence level of 1 (because 2 t of Hoeffding’s inequality, as above), and several studies (Lai and Robbins, 1985; Agrawal, 1995; Burnetas and Katehakis, 1996; Audibert et al., 2009; Honda and Takemura, 2010) have shown that this level is critical. We complete these works by a precise study of UCB(ρ) when ρ ≤ 1 . We prove that UCB(ρ) 2 is (1 − 2ρ)-consistent and that it is not α-consistent for any α < 1 − 2ρ (in view of the definition above, this means that the expected regret is roughly of order n1−2ρ ). Thus it does not achieve the logarithmic bound, but it performs well in simple environments, for example, environments where all reward distributions are Dirac measures. Moreover, we exhibit expected regret bounds of general UCB policies, with the 2 logt in the exploration term of UCB1 replaced by an arbitrary function. We give sufficient conditions for such policies to be Hannan consistent and, as mentioned before, find that lower bounds need not be logarithmic any more. 1.5 Outline The paper is organized as follows: in Section 2, we give bounds on the expected regret of general 1 UCB policies and of UCB (ρ) (ρ ≤ 2 ), as preliminary results. In Section 3, we focus on α-consistent policies. Then, in Section 4, we study the problem of selectivity, and we conclude in Section 5 by general results on the existence of logarithmic lower bounds. Throughout the paper ⌈x⌉ denotes the smallest integer not less than x whereas ⌊x⌋ denotes the largest integer not greater than x, ½A stands for the indicator function of event A, Ber(p) is the Bernoulli law with parameter p, and δx is the Dirac measure centred on x. 2. Preliminary Results In this section, we estimate the expected regret of the paper. UCB 191 policies. This will be useful for the rest of S ALOMON , AUDIBERT AND E L A LAOUI 2.1 Bounds on the Expected Regret of General UCB Policies We first study general UCB policies, defined by: • Draw each arm once, • then, at each round t, draw an arm It ∈ argmax Bk,Tk (t−1),t , k∈{1,...,K} ˆ where Bk,s,t is defined by Bk,s,t = Xk,s + creasing. fk (t) s and where functions fk (1 ≤ k ≤ K) are in- This definition is inspired by popular UCB1 algorithm, for which fk (t) = 2 logt for all k. The following lemma estimates the performances of UCB policies in simple environments, for which reward distributions are Dirac measures. Lemma 1 Let 0 ≤ b < a ≤ 1 and n ≥ 1. For θ = (δa , δb ), the random variable T2 (n) is uniformly 1 upper bounded by ∆2 f2 (n) + 1. Consequently, the expected regret of UCB is upper bounded by 1 ∆ f 2 (n) + 1. Proof In environment θ, best arm is arm 1 and ∆ = ∆2 = a − b. Let us first prove the upper bound of the sampling time. The assertion is true for n = 1 and n = 2: the first two rounds consists in 1 drawing each arm once, so that T2 (n) ≤ 1 ≤ ∆2 f2 (n) + 1 for n ∈ {1, 2}. If, by contradiction, the as1 1 sertion is false, then there exists t ≥ 3 such that T2 (t) > ∆2 f2 (t) + 1 and T2 (t − 1) ≤ ∆2 f2 (t − 1) + 1. Since f2 (t) ≥ f2 (t − 1), this leads to T2 (t) > T2 (t − 1), meaning that arm 2 is drawn at round t. Therefore, we have a + f1 (t) T1 (t−1) ≤ b+ f2 (t) T2 (t−1) , hence a − b = ∆ ≤ f2 (t) T2 (t−1) , which implies 1 1 T2 (t − 1) ≤ ∆2 f2 (t) and thus T2 (t) ≤ ∆2 f2 (t) + 1. This contradicts the definition of t, and this ends the proof of the first statement. The second statement is a direct consequence of Formula (1). Remark: throughout the paper, we will often use environments with K = 2 arms to provide bounds on expected regrets. However, we do not lose generality by doing so, because all corresponding proofs can be written almost identically to suit to any K ≥ 2, by simply assuming that the distribution of each arm k ≥ 3 is δ0 . We now give an upper bound of the expected sampling time of any arm such that ∆k > 0. This bound is valid in any environment, and not only those of the form (δa , δb ). Lemma 2 For any θ ∈ Θ and any β ∈ (0, 1), if ∆k > 0 the following upper bound holds: n Eθ [Tk (n)] ≤ u + where u = 4 fk (n) ∆2 k ∑ t=u+1 1+ logt 1 log( β ) . 192 e−2β fk (t) + e−2β fk∗ (t) , L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS An upper bound of the expected regret can be deduced from this lemma thanks to Formula 1. Proof The core of the proof is a peeling argument and the use of Hoeffding’s maximal inequality (see, e.g., Cesa-Bianchi and Lugosi, 2006, section A.1.3 for details). The idea is originally taken from Audibert et al. (2009), and the following is an adaptation of the proof of an upper bound of UCB (ρ) in the case ρ > 1 which can be found in S. Bubeck’s PhD dissertation. 2 First, let us notice that the policy selects an arm k such that ∆k > 0 at time step t ≤ n only if at least one of the three following equations holds: Bk∗ ,Tk∗ (t−1),t ≤ µ∗ , (3) fk (t) , Tk (t − 1) (4) ˆ Xk,t ≥ µk + Tk (t − 1) < 4 fk (n) . ∆2 k (5) Indeed, if none of the equations is true, then: fk (n) ˆ > Xk,t + Tk (t − 1) Bk∗ ,Tk∗ (t−1),t > µ∗ = µk + ∆k ≥ µk + 2 fk (t) = Bk,Tk (t−1),t , Tk (t − 1) which implies that arm k can not be chosen at time step t. We denote respectively by ξ1,t , ξ2,t and ξ3,t the events corresponding to Equations (3), (4) and (5). We have: n ∑ ½I =k Eθ [Tk (n)] = Eθ t n n ∑ ½{I =k}∩ξ = Eθ t t=1 + Eθ 3,t ∑ ½{I =k}\ξ t 3,t . t=1 t=1 n Let us show that the sum ∑t=1 ½{It =k}∩ξ3,t is almost surely lower than u := ⌈4 fk (n)/∆2 ⌉. We assume k m−1 n by contradiction that ∑t=1 ½{It =k}∩ξ3,t > u. Then there exists m < n such that ∑t=1 ½{It =k}∩ξ3,t < m 4 fk (n)/∆2 and ∑t=1 ½{It =k}∩ξ3,t = ⌈4 fk (n)/∆2 ⌉. Therefore, for any s > m, we have: k k m m t=1 t=1 Tk (s − 1) ≥ Tk (m) = ∑ ½{It =k} ≥ ∑ ½{It =k}∩ξ3,t = 4 fk (n) 4 fk (n) ≥ , 2 ∆k ∆2 k so that ½{Is =k}∩ξ3,s = 0. But then m n ∑ ½{I =k}∩ξ t t=1 3,t = ∑ ½{It =k}∩ξ3,t = t=1 4 fk (n) ≤ u, ∆2 k which is the contradiction expected. n n We also have ∑t=1 ½{It =k}\ξ3,t = ∑t=u+1 ½{It =k}\ξ3,t : since Tk (t − 1) ≤ t − 1, event ξ3,t always happens at time step t ∈ {1, . . . , u}. And then, since event {It = k} is included in ξ1,t ∪ ξ2,t ∪ ξ3,t : n Eθ ∑ ½{It =k}\ξ3,t ≤ Eθ t=u+1 n n t=u+1 t=u+1 ∑ ½ξ1,t ∪ξ2,t ≤ ∑ Pθ (ξ1,t ) + Pθ (ξ2,t ). 193 S ALOMON , AUDIBERT AND E L A LAOUI It remains to find upper bounds of Pθ (ξ1,t ) and Pθ (ξ2,t ). To this aim, we apply the peeling argument with a geometric grid over the time interval [1,t]: fk∗ (t) ≤ µ∗ Tk∗ (t − 1) ˆ Pθ (ξ1,t ) = Pθ Bk∗ ,Tk∗ (t−1),t ≤ µ∗ = Pθ Xk∗ ,Tk∗ (t−1) + ˆ ≤ Pθ ∃s ∈ {1, · · · ,t}, Xk∗ ,s + fk∗ (t) ≤ µ∗ s logt log(1/β) ≤ ∑ j=0 ˆ Pθ ∃s : {β j+1t < s ≤ β j t}, Xk∗ ,s + logt log(1/β) ≤ ∑ j=0 s Pθ ∃s : {β j+1t < s ≤ β j t}, logt log(1/β) ≤ ∑ j=0 ∑ j=0 ∑ (Xk ,l − µ∗ ) ≤ − ∗ s fk∗ (t) β j+1t fk∗ (t) l=1 ∑ (µ∗ − Xk ,l ) ≥ t < s ≤ β j t}, logt log(1/β) = fk∗ (t) ≤ µ∗ s j ∗ β j+1t fk∗ (t) l=1 s Pθ max ∑ (µ∗ − Xk∗ ,l ) ≥ s≤β j t l=1 β j+1t fk∗ (t) . As the range of the random variables (Xk∗ ,l )1≤l≤s is [0, 1], Hoeffding’s maximal inequality gives: 2 logt log(1/β) β j+1t fk∗ (t) 2 logt Pθ (ξ1,t ) ≤ + 1 e−2β fk∗ (t) . ≤ ∑ exp − jt β log(1/β) j=0 Similarly, we have: logt + 1 e−2β fk (t) , log(1/β) and the result follows from the combination of previous inequalities. Pθ (ξ2,t ) ≤ 2.2 Bounds on the Expected Regret of UCB(ρ), ρ ≤ We study the performances of UCB (ρ) 1 2 1 policy, with ρ ∈ (0, 2 ]. We recall that ρ logt s . UCB (ρ) is the UCB ˆ policy defined by fk (t) = ρ log(t) for all k, that is, Bk,s,t = Xk,s + Small values of ρ can be interpreted as a low level of experimentation in the balance between exploration and exploitation. 1 Precise regret bound orders of UCB(ρ) when ρ ∈ (0, 2 ] are not documented in the literature. We first give an upper bound of expected regret in simple environments, where it is supposed to perform well. As stated in the following proposition (which is a direct consequence of Lemma 1), the order of the bound is ρ log n . ∆ 194 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS Lemma 3 Let 0 ≤ b < a ≤ 1 and n ≥ 1. For θ = (δa , δb ), the random variable T2 (n) is uniformly ρ upper bounded by ∆2 log(n) + 1. Consequently, the expected regret of UCB(ρ) is upper bounded by ρ ∆ log(n) + 1. One can show that the expected regret of UCB(ρ) is actually equivalent to ρ log n as n goes to ∆ infinity. These good performances are compensated by poor results in more complex environments, as showed in the following theorem. We exhibit an expected regret upper bound which is valid for any θ ∈ Θ, and which is roughly of order n1−2ρ . We also show that this upper bound is asymptot1 ically optimal. Thus, with ρ ∈ (0, 2 ), UCB(ρ) does not perform enough exploration to achieve the logarithmic bound, as opposed to UCB(ρ) with ρ ∈ ( 1 , +∞). 2 1 Theorem 4 For any ρ ∈ (0, 2 ], any θ ∈ Θ and any β ∈ (0, 1), one has Eθ [Rn ] ≤ 4ρ log n ∑ ∆k + ∆k + 2∆k k:∆k >0 log n n1−2ρβ +1 . log(1/β) 1 − 2ρβ Moreover, if Θ has the Dirac/Bernoulli property, then for any ε > 0 there exists θ ∈ Θ such that Eθ [Rn ] lim n→+∞ n1−2ρ−ε = +∞. 1 1 The value ρ = 2 is critical, but we can deduce from the upper bound of this theorem that UCB( 2 ) is consistent in the classical sense of Lai and Robbins (1985) and of Burnetas and Katehakis (1996). log Proof We set u = 4ρ∆2 n . By Lemma 2 we get: k n Eθ [Tk (n)] ≤ u + 2 = u+2 ∑ logt + 1 e−2βρ log(t) log(1/β) ∑ logt 1 + 1 2ρβ log(1/β) t t=u+1 n t=u+1 n 1 ≤ u+2 log n +1 log(1/β) ≤ u+2 log n +1 log(1/β) 1+ ∑ ≤ u+2 log n +1 log(1/β) 1+ ≤ u+2 log n +1 . log(1/β) 1 − 2ρβ ∑ t 2ρβ t=1 n 1 t 2ρβ t=2 n−1 1 1−2ρβ n 1 t 2ρβ dt As usual, the upper bound of the expected regret follows from Formula (1). Now, let us show the lower bound. The result is obtained by considering an environment θ of the √ 1 form Ber( 1 ), δ 1 −∆ , where ∆ lies in (0, 2 ) and is such that 2ρ(1 + ∆)2 < 2ρ + ε. This notation is 2 2 obviously consistent with the definition of ∆ as an optimality gap. We set Tn := ⌈ ρ log n ⌉, and define ∆ the event ξn by: 1 1 ˆ ξn = X1,Tn < − (1 + √ )∆ . 2 ∆ 195 S ALOMON , AUDIBERT AND E L A LAOUI When event ξn occurs, one has for any t ∈ {Tn , . . . , n} ˆ X1,Tn + ρ logt Tn ˆ ≤ X1,Tn + ≤ √ ρ log n 1 1 < − (1 + √ )∆ + ∆ Tn 2 ∆ 1 − ∆, 2 so that arm 1 is chosen no more than Tn times by UCB(ρ) policy. Consequently: Eθ [T2 (n)] ≥ Pθ (ξn )(n − Tn ). We will now find a lower bound of the probability of ξn thanks to Berry-Esseen inequality. We denote by C the corresponding constant, and by Φ the c.d.f. of the standard normal distribution. For convenience, we also define the following quantities: σ := E X1,1 − Using the fact that Φ(−x) = e− √ 2 β(x) 2πx 1 2 2 1 = , M3 := E 2 X1,1 − 1 2 3 1 = . 8 x2 with β(x) − − → 1, we have: −− x→+∞ ˆ √ X1,Tn − 1 √ 1 2 Tn ≤ −2 1 + √ ∆ Tn σ ∆ √ √ CM3 Φ −2(∆ + ∆) Tn − 3 √ σ Tn √ 2 exp −2(∆ + ∆) Tn √ √ CM3 √ √ √ β 2(∆ + ∆) Tn − 3 √ σ Tn 2 2π(∆ + ∆) Tn √ 2 ρ log n exp −2(∆ + ∆) ( ∆ + 1) √ √ CM3 √ √ √ β 2(∆ + ∆) Tn − 3 √ σ Tn 2 2π(∆ + ∆) Tn √ √ −2ρ(1+ ∆)2 exp −2(∆ + ∆)2 √ √ CM3 n √ √ √ β 2(∆ + ∆) Tn − 3 √ . Tn σ Tn 2 2π(∆ + ∆) Pθ (ξn ) = Pθ ≥ ≥ ≥ ≥ Previous calculations and Formula (1) give Eθ [Rn ] = ∆Eθ [T2 (n)] ≥ ∆Pθ (ξn )(n − Tn ), √ 1−2ρ(1+ ∆)2 so that we finally obtain a lower bound of Eθ [Rn ] of order n √log n . Therefore, nEθ [Rn ] is at least 1−2ρ−ε √ 2 √ 2 n2ρ+ε−2ρ(1+ ∆) √ of order . Since 2ρ + ε − 2ρ(1 + ∆) > 0, the numerator goes to infinity, faster than log n √ log n. This concludes the proof. 196 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS 3. Bounds on the Class α-consistent Policies In this section, our aim is to find how the classical results of Lai and Robbins (1985) and of Burnetas and Katehakis (1996) can be generalised if we do not restrict the study to consistent policies. As a by-product, we will adapt their results to the present setting, which is simpler than their parametric frameworks. We recall that a policy is consistent if its expected regret is o(na ) for all a > 0 in all environments θ ∈ Θ. A natural way to relax this definition is the following. Definition 5 A policy is α-consistent if ∀a > α, ∀θ ∈ Θ, Eθ [Rn ] = o(na ). For example, we showed in the previous section that, for any ρ ∈ (0, 1 ], UCB(ρ) is (1−2ρ)-consistent 2 and not α-consistent if α < 1 − 2ρ. Note that the relevant range of α in this definition is [0, 1): the case α = 0 corresponds to the standard definition of consistency (so that throughout the paper the term ”consistent” also means ”0-consistent”), and any value α ≥ 1 is pointless as any policy is then α-consistent. Indeed, the expected regret of any policy is at most of order n. This also lead us to wonder what happens if we only require the expected regret to be o(n): ∀θ ∈ Θ, Eθ [Rn ] = o(n). This requirement corresponds to the definition of Hannan consistency. The class of Hannan consistent policies includes consistent policies and α-consistent policies for any α ∈ [0, 1). Some results about this class will be obtained in Section 5. We focus on regret lower bounds on α-consistent policies. We first show that the main result of Burnetas and Katehakis can be extended in the following way. Theorem 6 Assume that Θ has the product property. Fix an α-consistent policy and θ ∈ Θ. If ∆k > 0 and if 0 < Dk (θ) < ∞, then ∀ε > 0, lim Pθ Tk (n) ≥ (1 − ε) n→+∞ (1 − α) log n = 1. Dk (θ) Consequently lim inf n→+∞ 1−α Eθ [Tk (n)] ≥ . log n Dk (θ) Remind that the lower bound of the expected regret is then deduced from Formula (1), and that coefficient Dk (θ) is defined by: Dk (θ) := inf ˜ νk ∈Θk :E[˜ k ]>µ∗ ν ˜ KL(νk , νk ), where KL(ν, µ) denotes the Kullback-Leibler divergence of measures ν and µ. Note that, as opposed to Burnetas and Katehakis (1996), there is no optimal policy in general (i.e., a policy that would achieve the lower bound in all environment θ). This can be explained intuitively as follows. If by contradiction there existed such a policy, its expected regret would be of order log n and consequently it would be (0-)consistent. Then the lower bounds in the case of 197 S ALOMON , AUDIBERT AND E L A LAOUI 1−α 0-consistency would necessarily hold. This can not happen if α > 0 because Dk (θ) < Dk1 . (θ) Nevertheless, this argument is not rigorous because the fact that the regret would be of order log n is only valid for environments θ such that 0 < Dk (θ) < ∞. The non-existence of optimal policies is implied by a stronger result of the next section (yet, only if α > 0.2). Proof We adapt Proposition 1 in Burnetas and Katehakis (1996) and its proof. Let us denote θ = (ν1 , . . . , νK ). We fix ε > 0, and we want to show that: lim Pθ n→+∞ Set δ > 0 and δ′ > α such that ˜ that E[νk ] > µ∗ and 1−δ′ 1+δ Tk (n) (1 − ε)(1 − α) < log n Dk (θ) = 0. ˜ > (1 − ε)(1 − α). By definition of Dk (θ), there exists νk such ˜ Dk (θ) < KL(νk , νk ) < (1 + δ)Dk (θ). ˜ ˜ ˜ Let us set θ = (ν1 , . . . , νk−1 , νk , νk+1 , . . . , νK ). Environment θ lies in Θ by the product property and δ = KL(ν , ν ) and arm k is its best arm. Define I k ˜k ′ Aδ := n Tk (n) 1 − δ′ < δ log n I ′′ δ , Cn := log LTk (n) ≤ 1 − δ′′ log n , where δ′′ is such that α < δ′′ < δ′ and Lt is defined by log Lt = ∑ts=1 log δ′ δ′ δ′′ δ′ dνk ˜ d νk (Xk,s ) . δ′′ Now, we show that Pθ (An ) = Pθ (An ∩Cn ) + Pθ (An \Cn ) − − → 0. −− n→+∞ On the one hand, one has: ′′ ′′ ′ ′′ ′ δ δ Pθ (Aδ ∩Cn ) ≤ n1−δ Pθ (Aδ ∩Cn ) ˜ n n ′′ ′ (6) ′′ ≤ n1−δ Pθ (Aδ ) = n1−δ Pθ n − Tk (n) > n − ˜ ˜ n 1 − δ′ Iδ log n ′′ ≤ n1−δ Eθ [n − Tk (n)] ˜ (7) ′ n − 1−δ log n Iδ ′′ = n−δ Eθ ∑K Tℓ (n) − Tk (n) ˜ l=1 ′ n − 1−δ Iδ log n n ′′ ≤ ∑ℓ=k n−δ Eθ [Tℓ (n)] ˜ ′ 1 − 1−δ Iδ log n n − − → 0. −− (8) n→+∞ ′ Equation (6) results from a partition of Aδ into events {Tk (n) = a}, 0 ≤ a < n ′′ 1−δ′ Iδ log n . Each event ′′ δ {Tk (n) = a} ∩ Cn equals {Tk (n) = a} ∩ ∏a dνk (Xk,s ) ≤ n1−δ and is measurable with respect s=1 d νk ˜ to Xk,1 , . . . , Xk,a and to Xℓ,1 , . . . , Xℓ,n (ℓ = k). Thus, ½{Tk (n)=a}∩Cn ′′ can be written as a function f of δ the latter r.v. and we have: ′′ δ Pθ {Tk (n) = a} ∩Cn = f (xk,s )1≤s≤a , (xℓ,s )ℓ=k,1≤s≤n ∏ ℓ=k 1≤s≤n ≤ f (xk,s )1≤s≤a , (xℓ,s )ℓ=k,1≤s≤n ∏ ℓ=k 1≤s≤n ′′ ′′ δ = n1−δ Pθ {Tk (n) = a} ∩Cn ˜ 198 . dνℓ (xℓ,s ) ∏ dνk (xk,s ) 1≤s≤a ′′ dνℓ (xℓ,s )n1−δ ∏ 1≤s≤a ˜ d νk (xk,s ) L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS Equation (7) is a consequence of Markov’s inequality, and the limit in (8) is a consequence of α-consistency. ′ On the other hand, we set bn := 1−δ log n, so that Iδ ′ ′′ δ Pθ (Aδ \Cn ) ≤ P n ≤ P max log L j > (1 − δ′′ ) log n j≤⌊bn ⌋ 1 1 − δ′′ max log L j > I δ bn j≤⌊bn ⌋ 1 − δ′ . This term tends to zero, as a consequence of the law of large numbers. ′ Now that Pθ (Aδ ) tends to zero, the conclusion results from n 1 − δ′ 1 − δ′ (1 − ε)(1 − α) > ≥ . δ (1 + δ)Dk (θ) Dk (θ) I The previous lower bound is asymptotically optimal with respect to its dependence in α, as claimed in the following proposition. Proposition 7 Assume that Θ has the Dirac/Bernoulli property. There exist θ ∈ Θ and a constant c > 0 such that, for any α ∈ [0, 1), there exists an α-consistent policy such that: lim inf n→+∞ Eθ [Tk (n)] ≤ c, (1 − α) log n for any k satisfying ∆k > 0. Proof In any environment of the form θ = (δa , δb ) with a = b, Lemma 3 implies the following estimate for UCB(ρ): Eθ Tk (n) ρ lim inf ≤ 2, n→+∞ log n ∆ where k = k∗ . Because 1−α ∈ (0, 1 ) and since UCB(ρ) is (1 − 2ρ)-consistent for any ρ ∈ (0, 1 ] (Theorem 4), we 2 2 2 1 obtain the result by choosing the α-consistent policy UCB( 1−α ) and by setting c = 2∆2 . 2 4. Selectivity In this section, we address the problem of selectivity. By selectivity, we mean the ability to adapt to the environment as and when rewards are observed. More precisely, a set of two (or more) policies is given. The one that performs the best depends on environment θ. We wonder if there exists an adaptive procedure that, given any environment θ, would be as good as any policy in the given set. Two major reasons motivate this study. On the one hand this question was answered by Burnetas and Katehakis within the class of consistent policies. They exhibits an asymptotically optimal policy, that is, that achieves the regret 199 S ALOMON , AUDIBERT AND E L A LAOUI lower bounds they have proven. The fact that a policy performs as best as any other one obviously solves the problem of selectivity. On the other hand, this problem has already been studied in the context of adversarial bandit by Auer et al. (2003). Their setting differs from our not only because their bandits are nonstochastic, but also because their adaptive procedure takes only into account a given number of recommendations, whereas in our setting the adaptation is supposed to come from observing rewards of the chosen arms (only one per time step). Nevertheless, one can wonder if an ”exponentially weighted forecasters” procedure like E XP 4 could be transposed to our context. The answer is negative, as stated in the following theorem. To avoid confusion, we make the notations of the regret and of sampling time more precise by adding the considered policy: under policy A , Rn and Tk (n) will be respectively denoted Rn (A ) and Tk (n, A ). ˜ Theorem 8 Let A be a consistent policy and let ρ be a real number in (0, 0.4). If Θ has the ˜ Dirac/Bernoulli property and the product property, there is no policy which can both beat A and UCB (ρ), that is: ∀A , ∃θ ∈ Θ, lim sup n→+∞ Eθ [Rn (A )] > 1. ˜ min(Eθ [Rn (A )], Eθ [Rn (UCB(ρ))]) Thus the existence of optimal policies does not hold when we extend the notion of consistency. Precisely, as UCB(ρ) is (1 − 2ρ)-consistent, we have shown that there is no optimal policy within the class of α-consistent policies, with α > 0.2. Consequently, there do not exist optimal policies in the class of Hannan consistent policies either. Moreover, Theorem 8 shows that methods that would be inspired by related literature in adversarial bandit can not apply to our framework. As we said, this impossibility may come from the fact that we can not observe at each time step the decisions and rewards of more than one algorithm. If we were able to observe a given set of policies from step to step, then it would be easy to beat them all: it would be sufficient to aggregate all the observations and simply pull the arm with the greater empiric mean. The case where we only observe decisions (and not rewards) of a set of policies may be interesting, but is left outside of the scope of this paper. Proof Assume by contradiction that ∃A , ∀θ ∈ Θ, lim sup un,θ ≤ 1, n→+∞ [Rn where un,θ = min(E [R (Eθ)],E(A )](UCB(ρ))]) . ˜ θ n A θ [Rn For any θ, we have Eθ [Rn (A )] = Eθ [Rn (A )] ˜ ˜ Eθ [Rn (A )] ≤ un,θ Eθ [Rn (A )], ˜ Eθ [Rn (A )] (9) ˜ so that the fact that A is a consistent policy implies that A is also consistent. Consequently the lower bound of Theorem 6 also holds for policy A . For the rest of the proof, we focus on environments of the form θ = (δ0 , δ∆ ) with ∆ > 0. In this case, arm 2 is the best arm, so that we have to compute D1 (θ). On the one hand, we have: D1 (θ) = inf ˜ ν1 ∈Θ1 :E[˜ 1 ν ]>µ∗ ˜ KL(ν1 , ν1 ) = inf ˜ ν1 ∈Θ1 :E[˜ 1 ]>∆ ν 200 ˜ KL(δ0 , ν1 ) = inf ˜ ν1 ∈Θ1 :E[˜ 1 ]>∆ ν log 1 . ˜ ν1 (0) L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS ˜ ˜ As E[ν1 ] ≤ 1 − ν1 (0), we get: D1 (θ) ≥ inf ˜ ν1 ∈Θ1 :1−˜ 1 (0)≥∆ ν log 1 ˜ ν1 (0) ≥ log 1 . 1−∆ One the other hand, we have for any ε > 0: D1 (θ) ≤ KL(δ0 , Ber(∆ + ε)) = log Consequently D1 (θ) = log 1 1−∆ 1 1−∆−ε , and the lower bound of Theorem 6 reads: lim inf n→+∞ 1 Eθ [T1 (n, A )] . ≥ 1 log n log 1−∆ Just like Equation (9), we have: Eθ [Rn (A )] ≤ un,θ Eθ [Rn (UCB(ρ))]. Moreover, Lemma 3 provides: Eθ [Rn (UCB(ρ))] ≤ 1 + ρ log n . ∆ Now, by gathering the three previous inequalities and Formula (1), we get: 1 log 1 1−∆ ≤ lim inf n→+∞ Eθ [T1 (n, A )] Eθ [Rn (A )] = lim inf n→+∞ log n ∆ log n un,θ Eθ [Rn (UCB(ρ))] un,θ ρ log n 1+ ≤ lim inf n→+∞ ∆ log n ∆ log n ∆ ρun,θ un,θ ρ ρ + lim inf 2 = 2 lim inf un,θ ≤ 2 lim sup un,θ ≤ lim inf n→+∞ ∆ n→+∞ ∆ log n ∆ n→+∞ ∆ n→+∞ ρ . ≤ ∆2 ≤ lim inf n→+∞ This means that ρ has to be lower bounded by ∆2 , 1 log( 1−∆ ) but this is greater than 0.4 if ∆ = 0.75, hence the contradiction. Note that this proof gives a simple alternative to Theorem 4 to show that UCB(ρ) is not consistent (if ρ ≤ 0.4). Indeed if it were consistent, then in environment θ = (δ0 , δ∆ ) the same contradiction between the lower bound of Theorem 6 and the upper bound of Lemma 3 would hold. 5. General Bounds In this section, we study lower bounds on the expected regret with few requirements on Θ and on the class of policies. With a simple property on Θ but without any assumption on the policy, we show that there always exist logarithmic lower bounds for some environments θ. Then, still with a 201 S ALOMON , AUDIBERT AND E L A LAOUI simple property on Θ, we show that there exists a Hannan consistent policy for which the expected regret is sub-logarithmic for some environment θ. Note that the policy that always pulls arm 1 has a 0 expected regret in environments where arm 1 has the best mean reward, and an expected regret of order n in other environments. So, for this policy, expected regret is sub-logarithmic in some environments. Nevertheless, this policy is not Hannan consistent because its expected regret is not always o(n). 5.1 The Necessity of a Logarithmic Regret in Some Environments The necessity of a logarithmic regret in some environments can be explained by a simple sketch proof. Assume that the agent knows the number of rounds n, and that he balances exploration and exploitation in the following way: he first pulls each arm s(n) times, and then selects the arm that has obtained the best empiric mean for the rest of the game. Denote by ps(n) the probability that the best arm does not have the best empiric mean after the exploration phase (i.e., after the first Ks(n) rounds). The expected regret is then of the form c1 (1 − ps(n) )s(n) + c2 ps(n) n. (10) Indeed, if the agent manages to match the best arm then he only suffers the pulls of suboptimal arms during the exploration phase. That represents an expected regret of order s(n). If not, the number of pulls of suboptimal arms is of order n, and so is the expected regret. Now, let us approximate ps(n) . It has the same order as the probability that the best arm gets X ∗ −µ∗ an empiric mean lower than the second best mean reward. Moreover, k ,s(n) s(n) (where σ is σ ∗ ,1 ) has approximately a standard normal distribution by the central limit theorem. the variance of Xk Therefore, we have: ps(n) ≈ Pθ (Xk∗ ,s(n) ≤ µ∗ − ∆) = Pθ ≈ ≈ σ 1 1 √ exp − 2 2π ∆ s(n) Xk∗ ,s(n) − µ∗ σ 2 ∆ s(n) σ s(n) ≤ − ∆ s(n) σ 1 σ ∆2 s(n) √ . exp − 2σ2 2π ∆ s(n) It follows that the expected regret has to be at least logarithmic. Indeed, to ensure that the second term c2 ps(n) n of Equation (10) is sub-logarithmic, s(n) has to be greater than log n. But then first term c1 (1 − ps(n) )s(n) is greater than log n. Actually, the necessity of a logarithmic regret can be written as a consequence of Theorem 6. n Indeed, if we assume by contradiction that lim supn→+∞ Eθ Rn = 0 for all θ (i.e., Eθ Rn = o(log n)), log the considered policy is consistent. Consequently, Theorem 6 implies that lim sup n→+∞ E θ Rn E θ Rn ≥ lim inf > 0. n→+∞ log n log n Yet, this reasoning needs Θ having the product property, and conditions of the form 0 < Dk (θ) < ∞ also have to hold. The following proposition is a rigorous version of our sketch, and it shows that the necessity of a logarithmic lower bound can be based on a simple property on Θ. 202 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS ˜ ˜ ˜ Proposition 9 Assume that there exist two environments θ = (ν1 , . . . , νK ) ∈ Θ, θ = (ν1 , . . . , νK ) ∈ Θ, and an arm k ∈ {1, . . . , K} such that 1. k has the best mean reward in environment θ, ˜ 2. k is not the winning arm in environment θ, ˜ 3. νk = νk and there exists η ∈ (0, 1) such that dνℓ ∏ d νℓ (Xℓ,1 ) ≥ η ˜ ℓ=k Pθ − a.s. ˜ (11) ˆ Then, for any policy, there exists θ ∈ Θ such that lim sup n→+∞ E θ Rn ˆ > 0. log n ˜ Let us explain the logic of the three conditions of the proposition. If νk = νk , and in case νk seems to be the reward distribution of arm k, then arm k has to be pulled often enough for the regret to be small if the environment is θ. Nevertheless, one has to explore other arms to know ˜ whether the environment is actually θ. Moreover, Inequality (11) makes sure that the distinction ˜ is tough to make: it ensures that pulling any arm ℓ = k gives a reward which is between θ and θ likely in both environments. Without such an assumption the problem may be very simple, and providing a logarithmic lower bound is hopeless. Indeed, the distinction between any pair of tricky ˜ environments (θ, θ) may be solved in only one pull of a given arm ℓ = k, that would almost surely give a reward that is possible in only one of the two environments. The third condition can be seen as an alternate version of condition 0 < Dk (θ) < ∞ in Theorem 6, though there is no logical connection with it. Finally, let us remark that one can check that any set Θ that has the Dirac/Bernoulli property satisfies the conditions of Proposition 9. Proof The proof consists in writing a proper version of Expression (10). To this aim we compute a lower bound of Eθ Rn , expressed as a function of Eθ Rn and of an arbitrary function g(n). ˜ ˜ ˜ In the following, ∆k denotes the optimality gap of arm k in environment θ. As event ∑ℓ=k Tℓ (n) ≤ g(n) is measurable with respect to Xℓ,1 , . . . , Xℓ,⌊g(n)⌋ (ℓ = k) and to Xk,1 , . . . , Xk,n , we also introduce the function q such that ½{∑ℓ=k Tℓ (n)≤g(n)} = q (Xℓ,s )ℓ=k, s=1..⌊g(n)⌋ , (Xk,s )s=1..n . 203 S ALOMON , AUDIBERT AND E L A LAOUI We have: ˜ ˜ ˜ Eθ Rn ≥ ∆k Eθ [Tk (n)] ≥ ∆k (n − g(n))Pθ (Tk (n) ≥ n − g(n)) ˜ ˜ (12) ˜ = ∆k (n − g(n))Pθ n − ∑ Tℓ (n) ≥ n − g(n) ˜ ℓ=k ˜ = ∆k (n − g(n))Pθ ˜ ˜ = ∆k (n − g(n)) ∑ Tℓ (n) ≤ g(n) ℓ=k q (xℓ,s )ℓ=k, s=1..⌊g(n)⌋ , (xk,s )s=1..n ˜ ˜ ∏ d νℓ (xℓ,s )∏d νk (xk,s ) ℓ=k s = 1..⌊g(n)⌋ s=1..n ˜ ≥ ∆k (n − g(n)) q (xℓ,s )ℓ=k, s=1..⌊g(n)⌋ , (xk,s )s=1..n η⌊g(n)⌋∏ dνℓ (xℓ,s )∏dνk (xk,s ) ℓ=k s = 1..⌊g(n)⌋ ˜ ≥ ∆k (n − g(n))ηg(n) q (xℓ,s )ℓ=k, s=1..⌊g(n)⌋ , (xk,s )s=1..n ∏ dνℓ (xℓ,s )∏dνk (xk,s ) ℓ=k s = 1..⌊g(n)⌋ ˜ = ∆k (n − g(n))ηg(n) Pθ (13) s=1..n s=1..n ∑ Tℓ (n) ≤ g(n) ℓ=k ˜ = ∆k (n − g(n))ηg(n) 1 − Pθ ∑ Tℓ (n) > g(n) ℓ=k ˜ ≥ ∆k (n − g(n))ηg(n) 1 − Eθ ∑ℓ=k Tℓ (n) g(n) (14) ˜ ≥ ∆k (n − g(n))ηg(n) 1 − Eθ ∑ℓ=k ∆ℓ Tℓ (n) ∆g(n) (15) E θ Rn ˜ ≥ ∆k (n − g(n))ηg(n) 1 − , ∆g(n) where the first inequality of (12) is a consequence of Formula (1), the second inequality of (12) and inequality (14) come from Markov’s inequality, Inequality (13) is a consequence of (11), and Inequality (15) results from the fact that ∆ℓ ≥ ∆ for all ℓ. n θ −− Now, let us conclude. If Eθ Rn − − → 0, we set g(n) = 2E∆Rn , so that log n→+∞ g(n) ≤ min n − log n 2 , 2 log η for n large enough. Then, we have: √ − log n ˜ k n − g(n) ηg(n) ≥ ∆k n η 2 log η = ∆k n . ˜ ˜ E θ Rn ≥ ∆ ˜ 2 4 4 In particular, Eθ Rn ˜ −− log n − − → n→+∞ +∞, and the result follows. 204 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS 5.2 Hannan Consistency We will prove that there exists a Hannan consistent policy such that there can not be a logarithmic lower bound for every environment θ of Θ. To this aim, we make use of general UCB policies again (cf. Section 2.1). Let us first give sufficient conditions on the fk for UCB policy to be Hannan consistent. Proposition 10 Assume that fk (n) = o(n) for all k ∈ {1, . . . , K}. Assume also that there exist γ > 1 2 and N ≥ 3 such that fk (n) ≥ γ log log n for all k ∈ {1, . . . , K} and for all n ≥ N. Then UCB is Hannan consistent. Proof Fix an arm k such that ∆k > 0 and choose β ∈ (0, 1) such that 2βγ > 1. By means of Lemma 2, we have for n large enough: n Eθ [Tk (n)] ≤ u + 2 ∑ 1+ t=u+1 logt 1 log( β ) e−2βγ log logt , k where u = 4 f∆(n) . 2 k Consequently, we have: n Eθ [Tk (n)] ≤ u + 2 ∑ t=2 1 1 1 + 1 (logt)2βγ−1 2βγ (logt) log( β ) . (16) n n 1 Sums of the form ∑t=2 (logt)c with c > 0 are equivalent to (log n)c as n goes to infinity. Indeed, on the one hand we have n n n 1 dx 1 ∑ (logt)c ≤ 2 (log x)c ≤ ∑ (logt)c , t=2 t=3 n 1 so that ∑t=2 (logt)c ∼ n dx 2 (log x)c . n 2 On the other hand, we have n x dx = c (log x) (log x)c n dx 2 (log x)c+1 n 1 n ∑t=2 (logt)c ∼ (log n)c n +c 2 2 dx . (log x)c+1 n dx 2 (log x)c n dx 2 (log x)c n (log n)c . As both integrals are divergent we have =o Combining the fact that constant C > 0 such that with Equation (16), we get the existence of a Eθ [Tk (n)] ≤ , so that ∼ Cn 4 fk (n) + . 2 ∆ (log n)2βγ−1 Since fk (n) = o(n) and 2βγ − 1 > 0, the latter inequality shows that Eθ [Tk (n)] = o(n). The result follows. We are now in the position to prove the main result of this section. Theorem 11 If Θ has the Dirac/Bernoulli property, there exist Hannan consistent policies for which the expected regret can not be lower bounded by a logarithmic function in all environments θ. 205 S ALOMON , AUDIBERT AND E L A LAOUI Proof If f1 (n) = f2 (n) = log log n for n ≥ 3, UCB is Hannan consistent by Proposition 10. According to Lemma 1, the expected regret is then of order log log n in environments of the form (δa , δb ), a = b. Hence the conclusion on the non-existence of logarithmic lower bounds. Thus we have obtained a lower bound of order log log n. This order is critical regarding the methods we used. Yet, we do not know if this order is optimal. Acknowledgments This work has been supported by the French National Research Agency (ANR) through the COSINUS program (ANR-08-COSI-004: EXPLO-RA project). References R. Agrawal. Sample mean based index policies with o(log n) regret for the multi-armed bandit problem. Advances in Applied Mathematics, 27:1054–1078, 1995. H. Akaike. Information theory and an extension of the maximum likelihood principle. In Second International Symposium on Information Theory, volume 1, pages 267–281. Springer Verlag, 1973. J.-Y. Audibert, R. Munos, and C. Szepesv´ ri. Exploration-exploitation tradeoff using variance estia mates in multi-armed bandits. Theoretical Computer Science, 410(19):1876–1902, 2009. P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2-3):235–256, 2002. P. Auer, N. Cesa-Bianchi, Y. Freund, and R.E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2003. D. Bergemann and J. Valimaki. Bandit problems. In The New Palgrave Dictionary of Economics, 2nd ed. Macmillan Press, 2008. S. Bubeck. Bandits Games and Clustering Foundations. PhD thesis, Universit´ Lille 1, France, e 2010. S. Bubeck, R. Munos, G. Stoltz, and C. Szepesvari. Online optimization in X-armed bandits. In Advances in Neural Information Processing Systems 21, pages 201–208. 2009. A.N. Burnetas and M.N. Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122–142, 1996. N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, New York, NY, 2006. N. Cesa-Bianchi, Y. Freund, D. Haussler, D.P. Helmbold, R.E. Schapire, and M.K. Warmuth. How to use expert advice. Journal of the ACM (JACM), 44(3):427–485, 1997. 206 L OWER B OUNDS , W EAK C ONSISTENCY AND S ELECTIVITY IN BANDIT P ROBLEMS P.A. Coquelin and R. Munos. Bandit algorithms for tree search. In Uncertainty in Artificial Intelligence, 2007. S. Gelly and Y. Wang. Exploration exploitation in go: UCT for Monte-Carlo go. In Online Trading between Exploration and Exploitation Workshop, Twentieth Annual Conference on Neural Information Processing Systems (NIPS 2006), 2006. J. Honda and A. Takemura. An asymptotically optimal bandit algorithm for bounded support models. In Proceedings of the Twenty-Third Annual Conference on Learning Theory (COLT), 2010. R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 681–690, 2008. R. D. Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Advances in Neural Information Processing Systems 17, pages 697–704. 2005. T. L. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6:4–22, 1985. D. Lamberton, G. Pag` s, and P. Tarr` s. When can the two-armed bandit algorithm be trusted? e e Annals of Applied Probability, 14(3):1424–1454, 2004. C.L. Mallows. Some comments on cp. Technometrics, pages 661–675, 1973. H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematics Society, 58:527–535, 1952. G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6(2):461–464, 1978. W.R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294, 1933. 207
3 0.86551869 30 jmlr-2013-Counterfactual Reasoning and Learning Systems: The Example of Computational Advertising
Author: Léon Bottou, Jonas Peters, Joaquin Quiñonero-Candela, Denis X. Charles, D. Max Chickering, Elon Portugaly, Dipankar Ray, Patrice Simard, Ed Snelson
Abstract: This work shows how to leverage causal inference to understand the behavior of complex learning systems interacting with their environment and predict the consequences of changes to the system. Such predictions allow both humans and algorithms to select the changes that would have improved the system performance. This work is illustrated by experiments on the ad placement system associated with the Bing search engine. Keywords: causation, counterfactual reasoning, computational advertising
4 0.44023773 94 jmlr-2013-Ranked Bandits in Metric Spaces: Learning Diverse Rankings over Large Document Collections
Author: Aleksandrs Slivkins, Filip Radlinski, Sreenivas Gollapudi
Abstract: Most learning to rank research has assumed that the utility of different documents is independent, which results in learned ranking functions that return redundant results. The few approaches that avoid this have rather unsatisfyingly lacked theoretical foundations, or do not scale. We present a learning-to-rank formulation that optimizes the fraction of satisfied users, with several scalable algorithms that explicitly takes document similarity and ranking context into account. Our formulation is a non-trivial common generalization of two multi-armed bandit models from the literature: ranked bandits (Radlinski et al., 2008) and Lipschitz bandits (Kleinberg et al., 2008b). We present theoretical justifications for this approach, as well as a near-optimal algorithm. Our evaluation adds optimizations that improve empirical performance, and shows that our algorithms learn orders of magnitude more quickly than previous approaches. Keywords: online learning, clickthrough data, diversity, multi-armed bandits, contextual bandits, regret, metric spaces
5 0.41244861 105 jmlr-2013-Sparsity Regret Bounds for Individual Sequences in Online Linear Regression
Author: Sébastien Gerchinovitz
Abstract: We consider the problem of online linear regression on arbitrary deterministic sequences when the ambient dimension d can be much larger than the number of time rounds T . We introduce the notion of sparsity regret bound, which is a deterministic online counterpart of recent risk bounds derived in the stochastic setting under a sparsity scenario. We prove such regret bounds for an online-learning algorithm called SeqSEW and based on exponential weighting and data-driven truncation. In a second part we apply a parameter-free version of this algorithm to the stochastic setting (regression model with random design). This yields risk bounds of the same flavor as in Dalalyan and Tsybakov (2012a) but which solve two questions left open therein. In particular our risk bounds are adaptive (up to a logarithmic factor) to the unknown variance of the noise if the latter is Gaussian. We also address the regression model with fixed design. Keywords: sparsity, online linear regression, individual sequences, adaptive regret bounds
6 0.39801043 25 jmlr-2013-Communication-Efficient Algorithms for Statistical Optimization
7 0.39274564 31 jmlr-2013-Derivative Estimation with Local Polynomial Fitting
8 0.38269109 62 jmlr-2013-Learning Theory Approach to Minimum Error Entropy Criterion
10 0.3798497 61 jmlr-2013-Learning Theory Analysis for Association Rules and Sequential Event Prediction
11 0.37902367 14 jmlr-2013-Asymptotic Results on Adaptive False Discovery Rate Controlling Procedures Based on Kernel Estimators
12 0.37125781 68 jmlr-2013-Machine Learning with Operational Costs
14 0.35571346 81 jmlr-2013-Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality
15 0.35418132 102 jmlr-2013-Sparse Matrix Inversion with Scaled Lasso
16 0.34859872 4 jmlr-2013-A Max-Norm Constrained Minimization Approach to 1-Bit Matrix Completion
17 0.33974195 26 jmlr-2013-Conjugate Relation between Loss Functions and Uncertainty Sets in Classification Problems
18 0.33541232 43 jmlr-2013-Fast MCMC Sampling for Markov Jump Processes and Extensions
19 0.32984391 79 jmlr-2013-On the Mutual Nearest Neighbors Estimate in Regression
20 0.32909843 107 jmlr-2013-Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization