nips nips2009 nips2009-178 knowledge-graph by maker-knowledge-mining

178 nips-2009-On Stochastic and Worst-case Models for Investing

Source: pdf

Author: Elad Hazan, Satyen Kale

Abstract: In practice, most investing is done assuming a probabilistic model of stock price returns known as the Geometric Brownian Motion (GBM). While often an acceptable approximation, the GBM model is not always valid empirically. This motivates a worst-case approach to investing, called universal portfolio management, where the objective is to maximize wealth relative to the wealth earned by the best ﬁxed portfolio in hindsight. In this paper we tie the two approaches, and design an investment strategy which is universal in the worst-case, and yet capable of exploiting the mostly valid GBM model. Our method is based on new and improved regret bounds for online convex optimization with exp-concave loss functions. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 com Abstract In practice, most investing is done assuming a probabilistic model of stock price returns known as the Geometric Brownian Motion (GBM). [sent-5, score-0.354]

2 This motivates a worst-case approach to investing, called universal portfolio management, where the objective is to maximize wealth relative to the wealth earned by the best ﬁxed portfolio in hindsight. [sent-7, score-1.001]

3 In this paper we tie the two approaches, and design an investment strategy which is universal in the worst-case, and yet capable of exploiting the mostly valid GBM model. [sent-8, score-0.185]

4 Our method is based on new and improved regret bounds for online convex optimization with exp-concave loss functions. [sent-9, score-0.512]

5 1 Introduction “Average-case” Investing: Much of mathematical ﬁnance theory is devoted to the modeling of stock prices and devising investment strategies that maximize wealth gain, minimize risk while doing so, and so on. [sent-10, score-0.43]

6 Typically, this is done by estimating the parameters in a probabilistic model of stock prices. [sent-11, score-0.158]

7 Investment strategies are thus geared to such average case models (in the formal computer science sense), and are naturally susceptible to drastic deviations from the model, as witnessed in the recent stock market crash. [sent-12, score-0.229]

8 The performance of an online investment algorithm for arbitrary sequences of stock price returns is measured with respect to the best CRP (constant rebalanced portfolio, see [Cov91]) in hindsight. [sent-16, score-0.501]

9 A universal portfolio selection algorithm is one that obtains sublinear (in the number of trading periods T ) regret, which is the difference in the logarithms of the ﬁnal wealths obtained by the two. [sent-17, score-0.765]

10 Cover [Cov91] gave the ﬁrst universal portfolio selection algorithm with regret bounded by O(log T ). [sent-18, score-0.832]

11 However, the best regret bound is still O(log T ). [sent-20, score-0.385]

12 This dependence of the regret on the number of trading periods is not entirely satisfactory for two main reasons. [sent-21, score-0.634]

13 First, a priori it is not clear why the online algorithm should have high regret (growing with the number of iterations) in an unchanging environment. [sent-22, score-0.438]

14 As an extreme example, consider a setting with two stocks where one has an “upward drift” of 1% daily, whereas the second stock remains at the same price. [sent-23, score-0.194]

15 Trading more frequently potentially leads to higher wealth gain, by capitalizing on short term stock movements. [sent-29, score-0.324]

16 However, increasing trading frequency increases T , and thus one may expect more regret. [sent-30, score-0.288]

17 The problem is actually even worse: since we measure regret as a difference of logarithms of the ﬁnal wealths, a regret bound of O(log T ) implies a poly(T ) factor ratio between the ﬁnal wealths. [sent-31, score-0.771]

18 In reality, however, experiments [AHKS06] show that some known online algorithms actually improve with increasing trading frequency. [sent-32, score-0.311]

19 Bridging Worst-case and Average-case Investing: Both these issues are resolved if one can show that the regret of a “good” online algorithm depends on total variation in the sequence of stock returns, rather than purely on the number of iterations. [sent-33, score-0.673]

20 If the stock return sequence has low variation, we expect our algorithm to be able to perform better. [sent-34, score-0.173]

21 If we trade more frequently, then the per iteration variation should go down correspondingly, so the total variation stays the same. [sent-35, score-0.227]

22 We analyze a portfolio selection algorithm and prove that its regret is bounded by O(log Q), where Q (formally deﬁned in Section 1. [sent-36, score-0.779]

23 Since Q ≤ T (after appropriate normalization), we improve over previous regret bounds and retain the worst-case robustness. [sent-38, score-0.428]

24 Furthermore, in an average-case model such as GBM, the variation can be tied very nicely to the volatility parameter, which explains the experimental observation the regret doesn’t increase with increasing trading frequency. [sent-39, score-0.695]

25 ˜ √ Recently, this conjectured was proved and regret bounds of O( Q) were obtained in the full information and bandit linear optimization settings [HK08, HK09], where Q is the variation in the cost sequence. [sent-43, score-0.55]

26 O(log Q), for the case of online exp-concave optimization, which includes portfolio selection as a special case. [sent-45, score-0.419]

27 They considered a model of “continuous trading”, where there are T “trading intervals”, and in each the online investor chooses a ﬁxed portfolio which is rebalanced k times with k → ∞. [sent-47, score-0.531]

28 They prove familiar regret bounds of O(log T ) (independent of k) in this model w. [sent-48, score-0.429]

29 the best ﬁxed portfolio which is rebalanced T × k times. [sent-51, score-0.399]

30 In this model our algorithm attains the tighter regret bounds of O(log Q), although our algorithm has more ﬂexibility. [sent-52, score-0.468]

31 ˜ √ Our bounds of O(log Q) regret require completely different techniques compared to the O( Q) regret bounds of [HK08, HK09]. [sent-54, score-0.826]

32 This is because progress was measured in terms of the distance between successive portfolios in the usual Euclidean norm, which is insensitive to variation in the cost sequence. [sent-58, score-0.172]

33 This lemma, 1 Cross and Barron give an efﬁcient implementation for some interesting special cases, under assumptions on the variation in returns and bounds on the magnitude of the returns, and assuming k → ∞. [sent-61, score-0.193]

34 2 which may be useful in other contexts when variation bounds on the regret are desired, is proved using the Kahn-Karush-Tucker conditions, and also improves the regret bounds in previous papers. [sent-63, score-0.903]

35 In the universal portfolio management model [Cov91], an online investor iteratively distributes her wealth over n assets before observing the change in asset price. [sent-66, score-0.767]

36 the investor commits to an n-dimensional distribution of her wealth, xt ∈ ∆n = { i xi = 1 , x ≥ 0}. [sent-70, score-0.52]

37 She then observes a price relatives vector rt ∈ Rn , where rt (i) is + the ratio between the closing price of the ith asset on trading period t and the opening price. [sent-71, score-0.594]

38 In the tth trading period, the wealth of the investor changes by a factor of (rt · xt ). [sent-72, score-0.895]

39 The overall change in wealth is thus t (rt · xt ). [sent-73, score-0.606]

40 Since in a typical market wealth grows at an exponential rate, we measure performance by the exponential growth rate, which is log t (rt · xt ) = t log(rt · xt ). [sent-74, score-1.127]

41 A constant rebalanced portfolio (CRP) is an investment strategy which rebalances the wealth in every iteration to keep a ﬁxed distribution. [sent-75, score-0.684]

42 Thus, for a CRP x ∈ ∆n , the change in wealth is t (rt · x). [sent-76, score-0.16]

43 The regret of the investor is deﬁned to be the difference between the exponential growth rate of her investment strategy and that of the best CRP strategy in hindsight, i. [sent-77, score-0.592]

44 log(rt · x∗ ) − Regret := max ∗ x ∈∆n log(rt · xt ) t t Note that the regret doesn’t change if we scale all the returns in any particular period by the same amount. [sent-79, score-0.948]

45 We assume that there is known parameter r > 0, such that for all periods t, mint,i rt (i) ≥ r. [sent-85, score-0.145]

46 This is the only restriction we put on the stock price returns; they could be chosen adversarially as long as they respect the market variability bound. [sent-87, score-0.273]

47 In the online convex optimization problem [Zin03], which generalizes universal portfolio management, the decision space is a closed, bounded, convex set K ∈ Rn , and we are sequentially given a series of convex cost2 functions ft : K → R for t = 1, 2, . [sent-89, score-0.84]

48 The algorithm iteratively produces a point xt ∈ K in every round t, without knowledge of ft (but using the past sequence of cost functions), and incurs the cost ft (xt ). [sent-93, score-1.019]

49 The regret at time T is deﬁned to be T Regret := T ft (xt ) − min x∈K t=1 ft (x). [sent-94, score-0.845]

50 In this paper, we restrict our attention to convex cost functions which can be written as ft (x) = g(vt · x) for some univariate convex function g and a parameter vector vt ∈ Rn (for example, in the portfolio management problem, K = ∆n , ft (x) = − log(rt ·x), g = − log, and vt = rt ). [sent-96, score-2.035]

51 , vT ) := min µ 1 T t=1 T t=1 vt , and thus the quadratic variation is just T − 1 times This expression is minimized at µ = the sample variance of the sequence of vectors {v1 , . [sent-108, score-0.592]

52 Let the cost functions be of the form ft (x) = g(vt ·x). [sent-116, score-0.279]

53 Assume that there are parameters R, D, a, b > 0 such that the following conditions hold: 2 Note the difference from the portfolio selection problem: here we have convex cost functions, rather than concave payoff functions. [sent-117, score-0.478]

54 The portfolio selection problem is obtained by using − log as the cost function. [sent-118, score-0.439]

55 for all t, vt ≤ R, for all x ∈ K, we have x ≤ D, for all x ∈ K, and for all t, either g (vt · x) ∈ [0, a] or g (vt · x) ∈ [−a, 0], and for all x ∈ K, and for all t, g (vt · x) ≥ b. [sent-123, score-0.483]

56 Then there is an algorithm that guarantees the following regret bound: Regret = O((a2 n/b) log(1 + bQ + bR2 ) + aRD log(2 + Q/R2 ) + D2 ). [sent-124, score-0.38]

57 Now we apply Theorem 1 to the portfolio selection problem. [sent-125, score-0.361]

58 For the portfolio selection problem over n assets, there is an algorithm that attains the following regret bound: n Regret = O 2 log(Q + n) . [sent-132, score-0.766]

59 As we are concerned with logarithmic regret bounds, potential functions which behave like harmonic series come into play. [sent-139, score-0.444]

60 vt (A + τ =1 vτ vτ )−1 vt ≤ log |A| t=1 The reader can note that in one dimension, if all vectors vt = 1 and A = 1, then the series above reduces exactly to the regular harmonic series whose sum is bounded, of course, by log(T + 1). [sent-154, score-1.592]

61 2 Algorithm and analysis We analyze the following algorithm and prove that it attains logarithmic regret with respect to the observed variation (rather than number of iterations). [sent-156, score-0.515]

62 In iteration t, use the point xt deﬁned as: t−1 xt arg min x∈∆n fτ (x) + τ =1 1 x 2 2 (1) Note the mathematical program which the algorithm solves is convex, and can be solved in time polynomial in the dimension and number of iterations. [sent-159, score-0.935]

63 In the full version of the paper, for the speciﬁc problem of portfolio selection, where ft (x) = − log(rt · x), we give a faster implementation whose per iteration running time is independent of the number of iterations, using the more sophisticated “online Newton method” of [HKKA06]. [sent-161, score-0.593]

64 For the portfolio selection problem, there is an algorithm that runs in O(n3 ) time per iteration whose regret is bounded by n Regret = O 3 log(Q + n) . [sent-163, score-0.791]

65 Thus, we have 1 ∗ 2 − x0 2 ) Regret ≤ t ft (xt ) − ft (xt+1 ) + ( x 2 1 2 ≤ t ft (xt ) · (xt − xt+1 ) + D 2 1 2 (2) = t g (vt · xt )[vt · (xt − xt+1 )] + D 2 The second inequality is because ft is convex. [sent-174, score-1.426]

66 The last equality follows because ft (xt ) = g (xt · t−1 vt )vt . [sent-175, score-0.723]

67 For this, deﬁne Ft = τ =0 fτ , and note that xt minimizes Ft over K. [sent-177, score-0.446]

68 (3) (4) Equation 3 follows by applying the Taylor expansion of the (multi-variate) function gτ (vτ · x) at t point xt , for some point ζτ on the line segment joining xt and xt+1 . [sent-179, score-0.892]

69 t t Deﬁne At = τ =1 g (vt · ζτ )vt vt + I, where I is the identity matrix, and ∆xt = xt+1 − xt . [sent-181, score-0.929]

70 Then equation (4) can be re-written as: Ft+1 (xt+1 ) − Ft (xt ) − g (vt · xt )vt = At ∆xt . [sent-182, score-0.446]

71 (5) Now, since xt minimizes the convex function Ft over the convex set K, a standard inequality of convex optimization (see [BV04]) states that for any point y ∈ K, we have Ft (xt ) · (y − xt ) ≥ 0. [sent-183, score-1.035]

72 Thus, for y = xt+1 , we get that Ft (xt ) · (xt+1 − xt ) ≥ 0. [sent-184, score-0.446]

73 (6) Thus, using the expression for At ∆xt from (5) we have ∆xt 2 At = At ∆xt · ∆xt = ( Ft+1 (xt+1 ) − Ft (xt ) − g (vt · xt )vt ) · ∆xt ≤ g (vt · xt )[vt · (xt − xt+1 )] 5 (from (6)) (7) Assume that g (vt · x) ∈ [−a, 0] for all x ∈ K and all t. [sent-187, score-0.892]

74 Inequality (7) implies that g (vt · xt ) and vt · (xt − xt+1 ) have the same sign. [sent-189, score-0.929]

75 Thus, we can upper bound g (vt · xt )[vt · (xt − xt+1 )] ≤ a(vt · ∆xt ). [sent-190, score-0.466]

76 Then, we have ˜ t vt · ∆xt = ˜ t vt · ∆xt t 1 τ =1 vt . [sent-192, score-1.449]

77 t+1 T t=2 xt (µt−1 + − µt ) − x1 µ1 + xT +1 µT , (9) T −1 t=1 where vt = vt − µt , µt = ˜ Now, deﬁne ρ = ρ(v1 , . [sent-193, score-1.412]

78 Then we bound T T µ1 + xT +1 µT t=2 xt (µt−1 − µt ) − x1 µ1 + xT +1 µT ≤ t=2 xt µt−1 − µt + x1 ≤ Dρ + 2DR. [sent-197, score-0.912]

79 For now, we turn to bounding the ﬁrst term of (9) using the CauchySchwartz generalization as follows: vt · ∆xt ≤ vt A−1 ∆xt At . [sent-199, score-0.966]

80 ˜ ˜ (11) t By the usual Cauchy-Schwartz inequality, vt ˜ t A−1 t ∆xt ≤ At t vt ˜ 2 A−1 t · ∆xt t 2 At ≤ t vt ˜ 2 A−1 t · t a(vt · ∆xt ) from (7) and (8). [sent-200, score-1.449]

81 We conclude, using (9), (10) and (11), that t a(vt · ∆xt ) ≤ a t vt ˜ 2 A−1 t · t a(vt · ∆xt ) + aDρ + 2aDR. [sent-201, score-0.483]

82 This implies (using the AM-GM inequality applied to the ﬁrst term on the RHS) that 2 ˜ 2 t vt A−1 + 2aDρ + 4aDR. [sent-202, score-0.503]

83 t a(vt · ∆xt ) ≤ a t Plugging this into the regret bound (2) we obtain, via (8), Regret ≤ a2 t vt ˜ 2 A−1 t 1 + 2aDρ + 4aDR + D2 . [sent-203, score-0.868]

84 Since g (vt ·ζτ ) ≥ b, we have At 1 Using the fact that vt = vt − µt and µt = t+1 τ ≤t vτ , we get that ˜ t t τ =1 t t vτ vτ = ˜ ˜ 1 (τ +1)2 1+ t 1 (τ +1)2 s=1 r 0, with probability at least 1 − 2e−δ , we have Regret ≤ O(n(log( σ 2 + n) + δ)). [sent-210, score-0.966]

85 Theorem 10 shows that one expects to achieve constant regret independent of the trading frequency, as long as the total trading period is ﬁxed. [sent-211, score-0.902]

86 This result is only useful if increasing trading frequency improves the performance of the best constant rebalanced portfolio. [sent-212, score-0.362]

87 To obtain a theoretical justiﬁcation for increasing trading frequency, we consider an example where we have two stocks that follow independent Black-Scholes models with the same drifts, but different volatilities σ1 , σ2 . [sent-217, score-0.319]

88 The same drift assumption is necessary because in the long run, the best CRP is the one that puts all its wealth on the stock with the greater drift. [sent-218, score-0.338]

89 Since the drift is 0, the expected return of either stock in any trading period is 1; and since the returns in each period are independent, the expected ﬁnal change in wealth, which is the product of the returns, is also 1. [sent-220, score-0.618]

90 Thus, in expectation, any CRP (indeed, any portfolio selection strategy) has overall return 1. [sent-221, score-0.361]

91 The risk of an investment strategy is measured by the variance of its payoff; thus, if different investment strategies have the same expected payoff, then the one to choose is the one with minimum variance. [sent-223, score-0.241]

92 In the setup where we trade two stocks with zero drift and volatilities σ1 , σ2 , the variance of the minimum variance CRP decreases as the trading frequency increases. [sent-226, score-0.449]

93 Thus, increasing the trading frequency decreases the variance of the minimum variance CRP, which implies that it gets less risky to trade more frequently; in other words, the more frequently we trade, the more likely the payoff will be close to the expected value. [sent-227, score-0.425]

94 On the other hand, as we show in Theorem 10, the regret does not change even if we trade more often; thus, one expects to see improving performance of our algorithm as the trading frequency increases. [sent-228, score-0.732]

95 4 Conclusions and Future Work We have presented an efﬁcient algorithm for regret minimization with exp-concave loss functions whose regret strictly improves upon the state of the art. [sent-229, score-0.745]

96 For the problem of portfolio selection, the regret is bounded in terms of the observed variation in stock returns rather than the number of iterations. [sent-230, score-1.015]

97 Their method prices options using low regret algorithms, and it is possible that our analysis can be applied to options pricing via their method (although that would require a much tighter optimization of the constants involved). [sent-232, score-0.492]

98 Increasing trading frequency in practice means increasing transaction costs. [sent-233, score-0.327]

99 It would be very interesting to extend our portfolio selection algorithm to take into account transaction costs as in the work of Blum and Kalai [BK97]. [sent-235, score-0.432]

100 Algorithms for portfolio management based on the newton method. [sent-238, score-0.381]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('vt', 0.483), ('xt', 0.446), ('regret', 0.365), ('portfolio', 0.325), ('ft', 0.24), ('trading', 0.234), ('stock', 0.158), ('wealth', 0.141), ('rt', 0.11), ('crp', 0.097), ('investing', 0.095), ('investment', 0.095), ('variation', 0.077), ('gbm', 0.074), ('investor', 0.074), ('rebalanced', 0.074), ('universal', 0.069), ('returns', 0.068), ('satyen', 0.06), ('online', 0.058), ('period', 0.05), ('bounds', 0.048), ('kalai', 0.048), ('hazan', 0.047), ('trade', 0.045), ('convex', 0.041), ('elad', 0.04), ('portfolios', 0.039), ('cost', 0.039), ('drift', 0.039), ('market', 0.039), ('brownian', 0.039), ('transaction', 0.039), ('log', 0.039), ('payoff', 0.037), ('harmonic', 0.037), ('selection', 0.036), ('adam', 0.036), ('stocks', 0.036), ('pricing', 0.036), ('kale', 0.036), ('frequency', 0.035), ('options', 0.035), ('periods', 0.035), ('finance', 0.033), ('management', 0.033), ('price', 0.033), ('mansour', 0.032), ('lemma', 0.031), ('cover', 0.03), ('demarzo', 0.03), ('kremer', 0.03), ('volatilities', 0.03), ('wealths', 0.03), ('iteration', 0.028), ('doesn', 0.027), ('colt', 0.026), ('santosh', 0.026), ('adversarially', 0.026), ('attains', 0.025), ('series', 0.025), ('frequently', 0.025), ('motion', 0.025), ('assets', 0.024), ('ctitious', 0.024), ('barron', 0.024), ('asset', 0.024), ('newton', 0.023), ('drifts', 0.022), ('yishay', 0.022), ('bounded', 0.022), ('rn', 0.022), ('strategy', 0.021), ('prices', 0.021), ('amit', 0.021), ('logarithms', 0.021), ('conjectured', 0.021), ('inequality', 0.02), ('bound', 0.02), ('expects', 0.019), ('bq', 0.019), ('increasing', 0.019), ('change', 0.019), ('blum', 0.018), ('deviations', 0.017), ('successive', 0.017), ('usa', 0.017), ('logarithmic', 0.017), ('vectors', 0.017), ('variability', 0.017), ('costs', 0.017), ('prove', 0.016), ('option', 0.016), ('ny', 0.016), ('theorem', 0.016), ('growth', 0.016), ('strategies', 0.015), ('algorithm', 0.015), ('variance', 0.015), ('retain', 0.015)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999994 178 nips-2009-On Stochastic and Worst-case Models for Investing

Author: Elad Hazan, Satyen Kale

2 0.30447283 45 nips-2009-Beyond Convexity: Online Submodular Minimization

Author: Elad Hazan, Satyen Kale

Abstract: We consider an online decision problem over a discrete space in which the loss function is submodular. We give algorithms which are computationally efﬁcient and are Hannan-consistent in both the full information and bandit settings. 1

3 0.22421494 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization

Author: Pierre-arnaud Coquelin, Romain Deguest, Rémi Munos

Abstract: This paper considers a sensitivity analysis in Hidden Markov Models with continuous state and observation spaces. We propose an Inﬁnitesimal Perturbation Analysis (IPA) on the ﬁltering distribution with respect to some parameters of the model. We describe a methodology for using any algorithm that estimates the ﬁltering density, such as Sequential Monte Carlo methods, to design an algorithm that estimates its gradient. The resulting IPA estimator is proven to be asymptotically unbiased, consistent and has computational complexity linear in the number of particles. We consider an application of this analysis to the problem of identifying unknown parameters of the model given a sequence of observations. We derive an IPA estimator for the gradient of the log-likelihood, which may be used in a gradient method for the purpose of likelihood maximization. We illustrate the method with several numerical experiments.

4 0.22038807 220 nips-2009-Slow Learners are Fast

Author: Martin Zinkevich, John Langford, Alex J. Smola

Abstract: Online learning algorithms have impressive convergence properties when it comes to risk minimization and convex games on very large problems. However, they are inherently sequential in their design which prevents them from taking advantage of modern multi-core architectures. In this paper we prove that online learning with delayed updates converges well, thereby facilitating parallel online learning. 1

5 0.18989947 11 nips-2009-A General Projection Property for Distribution Families

Author: Yao-liang Yu, Yuxi Li, Dale Schuurmans, Csaba Szepesvári

Abstract: Surjectivity of linear projections between distribution families with ﬁxed mean and covariance (regardless of dimension) is re-derived by a new proof. We further extend this property to distribution families that respect additional constraints, such as symmetry, unimodality and log-concavity. By combining our results with classic univariate inequalities, we provide new worst-case analyses for natural risk criteria arising in classiﬁcation, optimization, portfolio selection and Markov decision processes. 1

6 0.18029015 14 nips-2009-A Parameter-free Hedging Algorithm

7 0.1775393 154 nips-2009-Modeling the spacing effect in sequential category learning

8 0.16518956 22 nips-2009-Accelerated Gradient Methods for Stochastic Optimization and Online Learning

9 0.14839956 177 nips-2009-On Learning Rotations

10 0.14447245 24 nips-2009-Adapting to the Shifting Intent of Search Queries

11 0.13792381 27 nips-2009-Adaptive Regularization of Weight Vectors

12 0.12970157 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization

13 0.12869801 202 nips-2009-Regularized Distance Metric Learning:Theory and Algorithm

14 0.11671203 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

15 0.11240435 101 nips-2009-Generalization Errors and Learning Curves for Regression with Multi-task Gaussian Processes

16 0.1035342 181 nips-2009-Online Learning of Assignments

17 0.097651124 63 nips-2009-DUOL: A Double Updating Approach for Online Learning

18 0.085636109 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

19 0.070547611 246 nips-2009-Time-Varying Dynamic Bayesian Networks

20 0.070275903 30 nips-2009-An Integer Projected Fixed Point Method for Graph Matching and MAP Inference

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.156), (1, 0.26), (2, 0.177), (3, -0.151), (4, 0.327), (5, 0.303), (6, 0.013), (7, 0.088), (8, -0.023), (9, 0.027), (10, -0.028), (11, 0.024), (12, -0.046), (13, 0.011), (14, -0.024), (15, 0.032), (16, -0.089), (17, 0.095), (18, 0.032), (19, 0.034), (20, 0.03), (21, 0.034), (22, 0.027), (23, 0.024), (24, -0.018), (25, -0.002), (26, 0.054), (27, -0.011), (28, 0.025), (29, -0.074), (30, -0.049), (31, -0.032), (32, 0.067), (33, -0.032), (34, 0.006), (35, 0.069), (36, -0.076), (37, 0.05), (38, -0.04), (39, -0.001), (40, 0.031), (41, 0.074), (42, 0.044), (43, -0.004), (44, 0.032), (45, -0.062), (46, 0.085), (47, -0.044), (48, 0.015), (49, -0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97950208 178 nips-2009-On Stochastic and Worst-case Models for Investing

Author: Elad Hazan, Satyen Kale

2 0.76242465 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization

Author: Pierre-arnaud Coquelin, Romain Deguest, Rémi Munos

3 0.72792119 27 nips-2009-Adaptive Regularization of Weight Vectors

Author: Koby Crammer, Alex Kulesza, Mark Dredze

Abstract: We present AROW, a new online learning algorithm that combines several useful properties: large margin training, conﬁdence weighting, and the capacity to handle non-separable data. AROW performs adaptive regularization of the prediction function upon seeing each new instance, allowing it to perform especially well in the presence of label noise. We derive a mistake bound, similar in form to the second order perceptron bound, that does not assume separability. We also relate our algorithm to recent conﬁdence-weighted online learning techniques and show empirically that AROW achieves state-of-the-art performance and notable robustness in the case of non-separable data. 1

4 0.72368473 45 nips-2009-Beyond Convexity: Online Submodular Minimization

Author: Elad Hazan, Satyen Kale

5 0.71644163 220 nips-2009-Slow Learners are Fast

Author: Martin Zinkevich, John Langford, Alex J. Smola

6 0.60030401 154 nips-2009-Modeling the spacing effect in sequential category learning

7 0.5685122 22 nips-2009-Accelerated Gradient Methods for Stochastic Optimization and Online Learning

8 0.56786329 24 nips-2009-Adapting to the Shifting Intent of Search Queries

9 0.54364842 177 nips-2009-On Learning Rotations

10 0.50623178 14 nips-2009-A Parameter-free Hedging Algorithm

11 0.48573411 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization

12 0.46838275 11 nips-2009-A General Projection Property for Distribution Families

13 0.41353455 63 nips-2009-DUOL: A Double Updating Approach for Online Learning

14 0.38930362 101 nips-2009-Generalization Errors and Learning Curves for Regression with Multi-task Gaussian Processes

15 0.38728324 181 nips-2009-Online Learning of Assignments

16 0.35498336 76 nips-2009-Efficient Learning using Forward-Backward Splitting

17 0.34866306 228 nips-2009-Speeding up Magnetic Resonance Image Acquisition by Bayesian Multi-Slice Adaptive Compressed Sensing

18 0.34537446 146 nips-2009-Manifold Regularization for SIR with Rate Root-n Convergence

19 0.34155774 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

20 0.30946293 73 nips-2009-Dual Averaging Method for Regularized Stochastic Learning and Online Optimization

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(7, 0.023), (24, 0.11), (25, 0.055), (35, 0.041), (36, 0.077), (39, 0.023), (53, 0.316), (58, 0.068), (61, 0.014), (71, 0.103), (81, 0.018), (86, 0.041), (91, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82253653 178 nips-2009-On Stochastic and Worst-case Models for Investing

Author: Elad Hazan, Satyen Kale

2 0.69763929 78 nips-2009-Efficient Moments-based Permutation Tests

Author: Chunxiao Zhou, Huixia J. Wang, Yongmei M. Wang

Abstract: In this paper, we develop an efficient moments-based permutation test approach to improve the test s computational efficiency by approximating the permutation distribution of the test statistic with Pearson distribution series. This approach involves the calculation of the first four moments of the permutation distribution. We propose a novel recursive method to derive these moments theoretically and analytically without any permutation. Experimental results using different test statistics are demonstrated using simulated data and real data. The proposed strategy takes advantage of nonparametric permutation tests and parametric Pearson distribution approximation to achieve both accuracy and efficiency. 1 In t ro d u c t i o n Permutation tests are flexible nonparametric alternatives to parametric tests in small samples, or when the distribution of a test statistic is unknown or mathematically intractable. In permutation tests, except exchangeability, no other statistical assumptions are required. The p-values can be obtained by using the permutation distribution. Permutation tests are appealing in many biomedical studies, which often have limited observations with unknown distribution. They have been used successfully in structural MR image analysis [1, 2, 3], in functional MR image analysis [4], and in 3D face analysis [5]. There are three common approaches to construct the permutation distribution [6, 7, 8]: (1) exact permutation enumerating all possible arrangements; (2) approximate permutation based on random sampling from all possible permutations; (3) approximate permutation using the analytical moments of the exact permutation distribution under the null hypothesis. The main disadvantage of the exact permutation is the computational cost, due to the factorial increase in the number of permutations with the increasing number of subjects. The second technique often gives inflated type I errors caused by random sampling. When a large number of repeated tests are needed, the random permutation strategy is also computationally expensive to achieve satisfactory accuracy. Regarding the third approach, the exact permutation distribution may not have moments or moments with tractability. In most applications, it is not the existence but the derivation of moments that limits the third approach. To the best of our knowledge, there is no systematic and efficient way to derive the moments of the permutation distribution. Recently, Zhou [3] proposed a solution by converting the permutation of data to that of the statistic coefficients that are symmetric to the permutation. Since the test statistic coefficients usually have simple presentations, it is easier to track the permutation of the test statistic coefficients than that of data. However, this method requires the derivation of the permutation for each specific test statistic, which is not accessible to practical users. In this paper, we propose a novel strategy by employing a general theoretical method to derive the moments of the permutation distribution of any weighted v-statistics, for both univariate and multivariate data. We note that any moments of the permutation distribution for weighted v-statistics [9] can be considered as a summation of the product of data function term and index function term over a high dimensional index set and all possible permutations. Our key idea is to divide the whole index set into several permutation equivalent (see Definition 2) index subsets such that the summation of the data/index function term over all permutations is invariant within each subset and can be calculated without conducting any permutation. Then we can obtain the moments by summing up several subtotals. The proposed method can be extended to equivalent weighted v-statistics by replacing them with monotonic weighted v-statistics. This is due to the fact that only the order of test statistics of all permutations matters for obtaining the p-values, so that the monotonic weighted v-statistics shares the same p-value with the original test statistic. Given the first four moments, the permutation distribution can be well fitted by Pearson distribution series. The p-values are then obtained without conducting any real permutation. For multiple comparison of two-group difference, given the sample size n1 = 21 and n2 = 21, the number of tests m = 2,000, we need to conduct m×(n1 + n2 )!/n1 !/n2 ! 1.1×1015 permutations for the exact permutation test. Even for 20,000 random permutations per test, we still need m×20,000 4×107 permutations. Alternatively, our moments-based permutation method using Pearson distribution approximation only involves the calculation of the first four analytically-derived moments of exact permutation distributions to achieve high accuracy (see section 3). Instead of calculating test statistics in factorial scale with exact permutation, our moments-based permutation only requires computation of polynomial order. For example, the computational cost for univariate mean difference test statistic and modified multivariate Hotelling's T2 test statistics [8] are O(n) and O(n3 ), respectively, where n = n 1 + n2 . 2 M e t h o d o lo g y In this section, we shall mainly discuss how to calculate the moments of the permutation distribution for weighted v-statistics. For other test statistics, a possible solution is to replace them with their equivalent weighted v-statistics by monotonic transforms. The detailed discussion about equivalent test statistics can be found in [7, 8, 10]. 2.1 C o m p ut a t i o n a l c h a l l e n g e Let us first look at a toy example. Suppose we have a two-group univariate data x = ( x1 , L , xn1 , xn1 +1 ,L , xn1 + n2 ) , where the first n1 elements are in group A and the rest, n2 ,are in group B. For comparison of the two groups, the hypothesis is typically constructed as: H 0 : m A = mB vs. H a : m A ¹ m B , where m A , m B are the population means of the groups A n1 n i =1 i = n1 +1 and B, respectively. Define x A = å xi / n1 and xB = å xi / n2 as the sample means of two groups, where n=n1+n2. We choose the univariate group mean difference statistic, i.e., n T ( x) = x A - xB = å w(i ) xi , i =1 where the index function as the test w(i ) = 1/ n1 , if i Î {1, L , n1} and w(i ) = -1/ n2 , if i Î {n1 + 1, L, n} . Then the total number of all possible permutations of {1, L, n} is n!. To calculate the fourth moment of the permutation distribution, n n n n n 1 1 4 å ( å w(i ) xp (i ) ) = å å å å å w(i1 ) w(i2 ) w(i3 ) w(i4 )xp ( i1 ) xp ( i2 ) xp ( i3 ) xp ( i4 ) , n ! p ÎS n i =1 n ! p ÎS n i1 =1 i2 =1 i3 =1 i4 =1 where is the permutation operator and the symmetric group Sn [11] includes all distinct permutations. The above example shows that the moment calculation can be considered as a summation over all possible permutations and a large index set. It is noticeable that the computational challenge here is to go through the factorial level permutations and polynomial level indices. Ep (T 4 ( x ))= 2.2 P a r t i t i o n t h e i n de x s e t In this paper, we assume that the test statistic T can be expressed as a weighted v-statistic of n n i1 =1 id =1 degree d [9], that is, T ( x) = å L å w(i1 , L , id ) h( xi1 ,L , xid ) , where x = ( x1 , x 2 , L , x n ) T is a data with n observations, and w is a symmetric index function. h is a symmetric data function, i.e., invariant under permutation of (i1 ,L , id ) . Though the symmetry property is not required for our method, it helps reduce the computational cost. Here, each observation xk can be either univariate or multivariate. In the above toy example, d=1 and h is the identity function. Therefore, the r-th moment of the test statistic from the permutated data is: Ep (T r ( x)) = Ep ( å w(i1 ,L , id )h( xp (i1 ) ,L , xp ( id ) ))r i1 ,i2 ,L,id = Ep [ å i1(1) ,L, id (1) , r r k =1 k =1 { Õ w(i1(k ) ,L, id ( k ) ) Õ h( xp (i ( k ) ) ,L, xp (i ( k ) ) )}] . L i1( r ) ,L,id ( r ) d 1 Then we can exchange the summation order of permutations and that of indices, Ep (T r ( x)) = å i1(1) ,L, id (1) , L i1( r ) ,L,id ( r ) r r k =1 k =1 {( Õ w(i1( k ) ,L , id ( k ) )) Ep ( Õ h( xp (i ( k ) ) ,L, xp (i ( k ) ) ))}. d 1 Thus any moment of permutation distribution can be considered as a summation of the product of data function term and index function term over a high dimensional index set and all possible permutations. Since all possible permutations map any index value between 1 and n to all possible index r values from 1 to n with equal probability, Ep ( Õ h( xp (i ( k ) ) ,L , xp (i ( k ) ) )) , the summation of k =1 1 d data function over all permutations is only related to the equal/unequal relationship among indices. It is natural to divide the whole index set U = {i1 ,L , id }r = {(i1(1) , L , id (1) ), L (r ) , ( i1 , L , id (r ) r )} into the union of disjoint index subsets, in which Ep ( Õ h( xp (i ( k ) ) ,L , xp (i ( k ) ) )) k =1 1 d is invariant. Definition 1. Since h is a symmetric function, two index elements (i1 ,L , id ) and ( j1 ,L , jd ) are said to be equivalent if they are the same up to the order. For example, for d = 3, (1, 4, 5) = (1,5,4) = (4,1,5) = (4,5,1) = (5,1,4) = (5,4,1). Definition 2. Two indices {(i1(1) , L , id (1) ), L , (i1( r ) , L , id ( r ) )} and {( j1(1) , L , jd (1) ), L , ( j1( r ) , L , jd ( r ) )} are said to be permutation equivalent/ if there exists a permutation p Î Sn such that {(p (i1(1) ), L , p (id (1) )), L , (p (i1( r ) ), L , p (id ( r ) ))} = {( j1(1) , L , jd (1) ), L , ( j1( r ) , L , jd ( r ) )} . Here

3 0.63468719 159 nips-2009-Multi-Step Dyna Planning for Policy Evaluation and Control

Author: Hengshuai Yao, Shalabh Bhatnagar, Dongcui Diao, Richard S. Sutton, Csaba Szepesvári

Abstract: In this paper we introduce a multi-step linear Dyna-style planning algorithm. The key element of the multi-step linear Dyna is a multi-step linear model that enables multi-step projection of a sampled feature and multi-step planning based on the simulated multi-step transition experience. We propose two multi-step linear models. The ﬁrst iterates the one-step linear model, but is generally computationally complex. The second interpolates between the one-step model and the inﬁnite-step model (which turns out to be the LSTD solution), and can be learned efﬁciently online. Policy evaluation on Boyan Chain shows that multi-step linear Dyna learns a policy faster than single-step linear Dyna, and generally learns faster as the number of projection steps increases. Results on Mountain-car show that multi-step linear Dyna leads to much better online performance than single-step linear Dyna and model-free algorithms; however, the performance of multi-step linear Dyna does not always improve as the number of projection steps increases. Our results also suggest that previous attempts on extending LSTD for online control were unsuccessful because LSTD looks inﬁnite steps into the future, and suffers from the model errors in non-stationary (control) environments.

4 0.50901061 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization

Author: Alekh Agarwal, Martin J. Wainwright, Peter L. Bartlett, Pradeep K. Ravikumar

Abstract: Despite a large literature on upper bounds on complexity of convex optimization, relatively less attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining a understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight minimax complexity estimates for various function classes. We also discuss implications of these results for the understanding the inherent complexity of large-scale learning and estimation problems. 1

5 0.4945673 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

Author: Peter Orbanz

Abstract: We consider the general problem of constructing nonparametric Bayesian models on inﬁnite-dimensional random objects, such as functions, inﬁnite graphs or inﬁnite permutations. The problem has generated much interest in machine learning, where it is treated heuristically, but has not been studied in full generality in nonparametric Bayesian statistics, which tends to focus on models over probability distributions. Our approach applies a standard tool of stochastic process theory, the construction of stochastic processes from their ﬁnite-dimensional marginal distributions. The main contribution of the paper is a generalization of the classic Kolmogorov extension theorem to conditional probabilities. This extension allows a rigorous construction of nonparametric Bayesian models from systems of ﬁnitedimensional, parametric Bayes equations. Using this approach, we show (i) how existence of a conjugate posterior for the nonparametric model can be guaranteed by choosing conjugate ﬁnite-dimensional models in the construction, (ii) how the mapping to the posterior parameters of the nonparametric model can be explicitly determined, and (iii) that the construction of conjugate models in essence requires the ﬁnite-dimensional models to be in the exponential family. As an application of our constructive framework, we derive a model on inﬁnite permutations, the nonparametric Bayesian analogue of a model recently proposed for the analysis of rank data. 1

6 0.48996148 45 nips-2009-Beyond Convexity: Online Submodular Minimization

7 0.48659492 260 nips-2009-Zero-shot Learning with Semantic Output Codes

8 0.48564187 161 nips-2009-Nash Equilibria of Static Prediction Games

9 0.48286897 41 nips-2009-Bayesian Source Localization with the Multivariate Laplace Prior

10 0.48284286 221 nips-2009-Solving Stochastic Games

11 0.48250014 130 nips-2009-Learning from Multiple Partially Observed Views - an Application to Multilingual Text Categorization

12 0.48196095 250 nips-2009-Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference

13 0.4816128 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

14 0.48110905 40 nips-2009-Bayesian Nonparametric Models on Decomposable Graphs

15 0.48094177 255 nips-2009-Variational Inference for the Nested Chinese Restaurant Process

16 0.48039263 55 nips-2009-Compressed Least-Squares Regression

17 0.47995967 215 nips-2009-Sensitivity analysis in HMMs with application to likelihood maximization

18 0.47964296 14 nips-2009-A Parameter-free Hedging Algorithm

19 0.47835201 18 nips-2009-A Stochastic approximation method for inference in probabilistic graphical models

20 0.4779205 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields