nips nips2012 nips2012-161 knowledge-graph by maker-knowledge-mining

161 nips-2012-Interpreting prediction markets: a stochastic approach

Source: pdf

Author: Nicolas D. Penna, Mark D. Reid, Rafael M. Frongillo

Abstract: We strengthen recent connections between prediction markets and learning by showing that a natural class of market makers can be understood as performing stochastic mirror descent when trader demands are sequentially drawn from a ﬁxed distribution. This provides new insights into how market prices (and price paths) may be interpreted as a summary of the market’s belief distribution by relating them to the optimization problem being solved. In particular, we show that under certain conditions the stationary point of the stochastic process of prices generated by the market is equal to the market’s Walrasian equilibrium of classic market analysis. Together, these results suggest how traditional market making mechanisms might be replaced with general purpose learning algorithms while still retaining guarantees about their behaviour. 1 Introduction and literature review This paper is part of an ongoing line of research, spanning several authors, into formal connections between markets and machine learning. In [5] an equivalence is shown between the theoretically popular prediction market makers based on sequences of proper scoring rules and follow the regularised leader, a form of no-regret online learning. By modelling the traders that demand the assets the market maker is oﬀering we are able to extend the equivalence to stochastic mirror decent. The dynamics of wealth transfer is studied in [3], for a sequence of markets between agents that behave as Kelly bettors (i.e. have log utilities), and an equivalence to stochastic gradient decent is analysed. More broadly, [9, 2] have analysed how a wide range of machine learning models can be implemented in terms of market equilibria. The literature on the interpretation of prediction market prices [7, 11] has had the goal of relating the equilibrium prices to the distribution of the beliefs of traders. More recent work [8] has looked at a stochastic model, and studied the behavior of simple agents sequentially interacting with the market. We continue this latter path of research, motivated by the observation that the equilibrium price may be a poor predictor of the behavior in a volitile prediction market. As such, we seek a more detailed understanding of the market than the equilibrium point – we would like to know what the “stationary distribution” of the price is, as time goes to inﬁnity. 1 As is standard in the literature, we assume a ﬁxed (product) distribution over traders’ beliefs and wealth. Our model features an automated market maker, following the framework of [1] is becoming a standard framework in the ﬁeld. We obtain two results. First, we prove that under certain conditions the stationary point of our stochastic process deﬁned by the market maker and a belief distribution of traders converges to the Walrasian equilibrium of the market as the market liquidity increases. This result, stated in Theorem 1, is general in the sense that only technical convergence conditions are placed on the demand functions of the traders – as such, we believe it is a generalisation of the stochastic result of [8] to cases where agents are are not limited to linear demands, and leave this precise connection to future work. Second, we show in Corollary 1 that when traders are Kelly bettors, the resulting stochastic market process is equivalent to stochastic mirror descent; see e.g. [6]. This result adds to the growing literature which relates prediction markets, and automated market makers in general, to online learning; see e.g. [1], [5], [3] . This connection to mirror descent seems to suggest that the prices in a prediction market at any given time may be meaningless, as the ﬁnal point in stochastic mirror descent often has poor convergence guarantees. However, standard results suggest that a prudent way to form a “consensus estimate” from a prediction market is to average the prices. The average price, assuming our market model is reasonable, is provably close to the stationary price. In Section 5 we give a natural example that exhibits this behavior. Beyond this, however, Theorem 2 gives us insight into the relationship between the market liquidity and the convergence of prices; in particular it suggests that we should increase liquidity at a rate √ of t if we wish the price to settle down at the right rate. 2 Model Our market model will follow the automated market maker framework of [1]. We will equip our market maker with a strictly convex function C : Rn → R which is twice continuously diﬀerentiable. For brevity we will write ϕ := C. The outcome space is Ω, and the contracts are determined by a payoﬀ function φ : Ω → Rn such that Π := ϕ(Rn ) = ConvHull(φ(Ω)). That is, the derivative space Π of C (the “instantaneous prices”) must be the convex hull of the payoﬀs. A trader purchasing shares at the current prices π ∈ Rn pays C(ϕ−1 (π) + r) − C(ϕ−1 (π)) for the bundle of contracts r ∈ Rn . Note that our dependence solely on π limits our model slightly, since in general the share space (domain of C) may contain more information than the current prices (cf. [1]). The bundle r is determined by an agent’s demand function d(C, π) which speciﬁes the bundle to buy given the price π and the cost function C. Our market dynamics are the following. The market maker posts the current price πt , and at each time t = 1 . . . T , a trader is chosen with demand function d drawn i.i.d. from some demand distribution D. Intuitively, these demands are parameterized by latent variables such as the agent’s belief p ∈ ∆Ω and total wealth W . The price is then updated to πt+1 = ϕ(ϕ−1 (πt ) + d(C, πt )). (1) After update T , the outcome is revealed and payout φ(ω)i is given for each contract i ∈ {1, . . . , n}. 3 Stationarity and equilibrium We ﬁrst would like to relate our stochastic model (1) to the standard notion of market equilibrium from the Economics literature, which we call the Walrasian equilibrium to avoid confusion. Here prices are ﬁxed, and the equilibrium price is one that clears the market, meaning that the sum of the demands r is 0 ∈ Rn . In fact, we will show that the stationary point of our process approaches the Walrasian equilibrium point as the liquidity of the market approaches inﬁnity. 2 First, we must add a liquidity parameter to our market. Following the LMSR (the cost function C(s) = b ln i esi /b ), we deﬁne Cb (s) := b C(s/b). (2) This transformation of a convex function is called a perspective function and is known to preserve convexity [4]. Observe that ϕb (s) := Cb (s) = C(s/b) = ϕ(s/b), meaning that the price under Cb at s is the same as the price under C at s/b. As with the LMSR, we call b the liquidity parameter ; this terminology is justiﬁed by noting that one deﬁnition of liquidity, 1/λmax 2 Cb (s) = b/λmax 2 C(s/b) (cf. [1]). In the following, we will consider the limit as b → ∞. Second, in order to connect to the Walrasian equilibrium, we need a notion of a ﬁxed-price demand function: if a trader has demand d(C, ·) given C, what would the same trader’s demand be under a market where prices are ﬁxed and do not “change” during a trade? For the sake of generality, we restrict our allowable demand functions to the ones for which the limit d(F, π) := lim d(Cb , π) (3) b→∞ exists; this demand d(F, ·) will be the corresponding ﬁxed-price demand for d. We now deﬁne the Walrasion equilibrium point π ∗ , which is simply the price at which the market clears when traders have demands distributed by D. Formally, this is the following condition:1 d(F, π ∗ ) dD(d) = 0 (4) D Note that 0 ∈ Rn ; the demand for each contract should be balanced. s The stationary point of our stochastic process, on the other hand, is the price πb for which the expected price ﬂuctuation is 0. Formally, we have s s E [∆(πb , d(Cb , πb ))] = 0, (5) d∼D where ∆(π, d) := ϕ(ϕ−1 (π) + d) − π is the price ﬂuctuation. We now consider the limit of our stochastic process as the market liquidity approaches ∞. Theorem 1. Let C be a strictly convex and α-smooth2 cost function, and assume that ∂ ∂b d(Cb , π) = o(1/b) uniformly in π and all d ∈ D. If furthermore the limit (3) is uniform s in π and d, then limb→∞ πb = π ∗ . s Proof. Note that by the stationarity condition (5) we may deﬁne π ∗ and πb to be the roots of the following “excess demand” functions, respectively: Z(π) := s Zb (π) := b E [∆(π, d(Cb , π))], d(F, π) dD(d), d∼D D where we scale the latter by b so that −1 Let s = ϕ s Zb does not limit to the zero function. (π) be the current share vector. Then we have lim b∆(π, d(Cb , π)) = lim b ϕ ϕ−1 (π) + d(Cb , π)/b − π b→∞ b→∞ ϕ s + a d(C1/a , π) − π a ∂ = lim ϕ s + a d(C1/a , π) d(C1/a , π) + a ∂a d(C1/a , π) = lim a→0 a→0 = lim ϕ s+ = lim 2 b→∞ b→∞ 1 b d(Cb , π) C(s) d(Cb , π) = d(Cb , π) + 2 2 1 ∂ b ∂b d(Cb , π)(−b ) C(s) d(F, π), 1 Here and throughout we ignore technical issues of uniqueness. One may simply restrict to the class of demands for which uniqueness is satisﬁed. 2 C is α-smooth if λmax 2 C ≤ α 3 where we apply L’Hopital’s rule for the third equality. Crucially, the above limit is uniform with respect to both d ∈ D and π ∈ Π; uniformity in d is by assumption, and uniformity in π follows from α-smoothness of C, since C is dominated by a quadratic. Since the limit is uniform with respect to D, we now have s lim Zb (π) = lim b E [∆(π, d(Cb , π))] = E b→∞ b→∞ = 2 d∼D d∼D C(s) E [d(F, π)] = 2 lim b∆(π, d(Cb , π)) b→∞ C(s) Z(π). d∼D s As 2 C(s) is positive deﬁnite by assumption on C, we can conclude that limb→∞ Zb and Z share the same zeroes. Since Z has compact domain and is assumed continuous with a unique zero π ∗ , for each ∈ (0, max ) there must be some δ > 0 s.t. |Z(π)| > for all π s.t. π − π ∗ > δ (otherwise there would be a sequence of πn → π s.t. f (π ) = 0 but π = π ∗ ). s By uniform convergence there must be a B > 0 s.t. for all b > B we have Zb − Z ∞ < /2. s s In particular, for π s.t. π − π ∗ > δ, |Zb (π)| > /2. Thus, the corresponding zeros πb must ∗ s ∗ 3 be within δ of π . Hence limb→∞ πb = π . 3.1 Utility-based demands Maximum Expected Utility (MEU) demand functions are a particular kind of demand function derived by assuming a trader has some belief p ∈ ∆n over the outcomes in Ω, some wealth W ≥ 0, and a monotonically increasing utility function of money u : R → R. If such a trader buys a bundle r of contracts from a market maker with cost function C and price π, her wealth after ω occurs is Υω (C, W, π, r) := W +φ(ω)·r−[C(ϕ−1 (π)+r)−C(ϕ−1 (π))]. We ensure traders do not go into debt by requiring that traders only make demands such that this ﬁnal wealth is nonnegative: ∀ω Υω (C, π, r) ≥ 0. The set of debt-free bundles for wealth W and market C at price π is denoted S(C, W, π) := {r ∈ Rn : minω Υω (C, W, π, r) ≥ 0}. A continuous MEU demand function du (C, π) is then just the demand that maximizes a W,p trader’s expected utility subject to the debt-free constraint. That is, du (C, π) := argmax W,p E [u (Υω (C, W, π, r))] . (6) r∈S(C,W,π) ω∼p We also deﬁne a ﬁxed-price MEU demand function du (F, π) similarly, where W,p Υω (F, W, π, r) := W + φ(ω) · r − π · r and S(F, W, π) := {r ∈ Rn : minω Υω (F, W, π, r) ≥ 0} are the ﬁxed price analogues to the continuously priced versions above. Using the notation bS := {b r | r ∈ S}, the following relationships between the continuous and ﬁxed price versions of Υ, SW , and the expected utility are a consequence of the convexity of C. Their main purpose is to highlight the relationship between wealth and liquidity in MEU demands. In particular, they show that scaling up of liquidity is equivalent to a scaling down of wealth and that the continuously priced constraints and wealth functions monotonically approach the ﬁxed priced versions. Lemma 1. For any strictly convex cost function C, wealth W > 0, price π, demand r, and liquidity parameter b > 0 the following properties hold: 1. Υω (Cb , W, π, r) = b Υω (C, W/b, π, r/b); 2. S(Cb , W, π) = b S(C, W/b, π); 3. S(C, W, π) is convex for all C; 4. S(C, W, π) ⊆ S(Cb , W, π) ⊆ S(F, W, π) for all b ≥ 1. 5. For monotone utilities u, Eω∼p [u (Υω (F, W, π, r))] ≥ Eω∼p [u (Υω (C, W, π, r))]. Proof. Property (1) follows from a simple computation: Υω (Cb , W, π, r) = W + φ(ω) · r − b C(ϕ−1 (π) + r/b) + b C(ϕ−1 (π)) = b W/b + φ(ω) · (r/b) − C(ϕ−1 (π) + r/b) + C(ϕ−1 (π)) , which equals b Υω (C, W/b, π, r/b) by deﬁnition. We now can see property (2) as well: S(Cb , W, π) = {r : min b Υω (C, W/b, π, r/b) ≥ 0} = {b r : min Υω (C, W/b, π, r) ≥ 0}. ω 3 ω We thank Avraham Ruderman for a helpful discussion regarding this proof. 4 For (3), deﬁne fC,s,ω (r) = C(s + r) − C(s) − φ(ω) · r, which is the ex-post cost of purchasing bundle r. As C is convex, and fC,s,ω is a shifted and translated version of C plus a linear term, fC,s,ω is convex also. The constraint Υω (C, W, π, r) ≥ 0 then translates to fC,s,ω (r) ≤ W , and thus the set of r which satisfy the constraint is convex as a sublevel set of a convex function. Now S(C, W, π) is convex as an intersection of convex sets, proving (3). For (4) suppose r satisﬁes fC,s,ω (r) ≤ W . Note that fC,s,ω (0) = 0 always. Then by convexity we have for f := fC,s,ω we have f (r/b) = f 1 r + b−1 0 ≤ 1 f (r) + b−1 0 ≤ W/b, b b b b which implies S(C, W, π) ⊆ S(Cb , W, π) when considering (3). To complete (4) note that fC,s,ω dominates fF,s : r → (ϕ(s) − φ(ω)) · r by convexity of C: C(s + r) − C(s) ≥ C(s) · r. Finally, proof of (5) is obtained by noting that the convexity of C means that C(ϕ−1 (π) + r) − C(ϕ−1 (π)) ≥ C(ϕ−1 (π)) · r = π · r and exploting the monotonicty of u. Lemma 1 shows us that MEU demands have a lot of structure, and in particular, properties (4) and (5) suggest that they may satisfy the conditions of Theorem 1; we leave this as an open question for future work. Another interesting aspect of Lemma 1 is the relationship between markets with cost function Cb and wealths W and markets with cost function C and wealths W/b – indeed, properties (1) and (2) suggest that the liquidity limit should in some sense be equivalent to a wealth limit, in that increasing liquidity by a factor b should yield similar dynamics to decreasing the wealths by b. This would relate our model to that of [8], where the authors essentially show a wealth-limit version of Theorem 1 for a binary-outcome market where traders have linear utilities (a special case of (6)). We leave this precise connection for future work. 4 Market making as mirror descent We now explore the surprising relationship between our stochastic price update and standard stochastic optimization techniques. In particular, we will relate our model to a stochastic mirror descent of the form xt+1 = argmin{η x · F (xt ; ξ) + DR (x, xt )}, (7) x∈R where at each step ξ ∼ Ξ are i.i.d. and R is some strictly convex function. We will refer to an algorithm of the form (7) a stochastic mirror descent of f (x) := Eξ∼Ξ [F (x; ξ)]. Theorem 2. If for all d ∈ D we have some F (· ; d) : Rn → Rn such that d(R∗ , π) = − F (π; d), then the stochastic update of our model (1) is exactly a stochastic mirror descent of f (π) = Ed∼D [F (π; d)]. Proof. By standard arguments, the mirror descent update (7) can be rewritten as xt+1 = R∗ ( R(xt ) − F (xt ; ξ)), where R∗ is the conjugate dual of R. Take R = C ∗ , and let ξ = d ∼ D. By assumption, we have F (x; d) = −d(R∗ , x) = −d(C, x) for all d. As R∗ = C = ϕ, we have ϕ−1 = ( R∗ )−1 = R by duality, and thus our update becomes xt+1 = ϕ ϕ−1 (xt ) + d(C, xt ) , which exactly matches the stochastic update of our model (1). As an example, consider Kelly betters, which correspond to ﬁxed-price demands d(C, π) := dlog (F, π) with utility u(x) = log x as deﬁned in (3). A simple calculation shows that our W,p update becomes W p−π πt+1 = ϕ ϕ−1 (πt ) + , (8) π 1−π where W and p are drawn (independently) from P and W. Corollary 1. The stochastic update for ﬁxed-price Kelly betters (8) is exactly a stochastic mirror descent of f (π) = W · KL(p, π), where p and W are the means of P and W, respectively. 5 Proof. We take F (x; dlog ) = W · (KL(p, x) + H(p)). Then W,p F (x; dlog ) = W W,p −p p − 1 + x 1−x =− W p−x = −dlog (F, x). W,p x 1−x Hence, by Theorem 2 our update is a stochastic mirror descent of: f (x) := E[F (x; dlog )] = E[W p log x + W (1 − p) log(1 − x)] = W · (KL(p, x) + H(p)) , W,p which of course is equivalent to W · KL(p, x) as the entropy term does not depend on x. Note that while this last result is quite compelling, we have mixed ﬁxed-price demands with a continuous-price market model – see Section 3.1. One could interpret this combination as a model in which the market maker can only adjust the prices after a trade, according to a ﬁxed convex cost function C. This of course diﬀers from the standard model, which adjusts the price continuously during a trade. 4.1 Leveraging existing learning results Theorem 2 not only identiﬁes a fascinating connection between machine learning and our stochastic prediction market model, but it also allows us to use powerful existing techniques to make broad conclusions about the behavior of our model. Consider the following result: ≤ G2 for all p, π, and R is σ-strongly convex, then log 1 δ . Price Avg price Avg belief 0.70 In our context, Proposition 1 says that the average of the prices will be a very good estimate of the minimizer of f , which as suggested by happens to be the underlying mean belief p of the traders! Moreover, as the Kelly demands are linear in both p and W , it is easy to see from Theorem 1 that p is also the stationary point and the Walrasian equilibrium point (the latter was also shown by [11]). On the other hand, as we demonstrate next, it is not hard to come up with an example where the instantaneous price πt is quite far from the equilibrium at any given time period. 1+4 0.65 π D2 G2 η + ηT 2σ 0.60 f (π T ) ≤ min f (π) + Price of contract 1 2 0.55 F (π; p) 0.50 Proposition 1 ([6]). If with probability 1 − δ, 0 500 1000 1500 2000 Trade number Before moving to our empirical work, we make one Figure 1: Price movement for Kelly ﬁnal point. The above relationship between our betters with binomial(q = 0.6, n = 6, stochastic market model and mirror descent sheds α = 0.5) beliefs in the LMSR market light on an important question: how might an auto- with liquidity b = 10. mated market maker adjust the liquidity so that the market actually converges to the mean of the traders’ beliefs? The learning parameter η can be thought of as the inverse of the liquidity, and as such, Proposition 1 suggests that √ increasing the liquidity as t may cause the mean price to converge to the mean belief (assuming a ﬁxed underlying belief distribution). 5 Empirical work Example: biased coin Consider a classic Bayesian setting where a coin has unknown bias Pr[heads] = q, and traders have a prior β(α, α) over q (i.e., traders are α-conﬁdent that the coin is fair). Now suppose each trader independently observes n ﬂips from the coin, and updates her belief; upon seeing k heads, a trader would have posterior β(α + k, α + n − k). When presented with a prediction market with contracts for a single toss of the coin, where and contract 0 pays $1 for tails and contract 1 pays $1 for heads, a trader would purchase 6 0 20 40 60 Trades 80 100 b = 10 Instant Averaged 0.06 Loss 0.04 0.02 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged 0.00 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged Square loss of price to mean belief for State 9 b=3 0.08 b=1 0.10 Square loss of price to mean belief for State 9 0.10 0.10 Square loss of price to mean belief for State 9 0 20 40 60 Trades 80 100 0 20 40 60 80 100 Trades Figure 2: Mean square loss of average and instantaneous prices relative to the mean belief of 0.26 over 20 simulations for State 9 for b = 1 (left), b = 3 (middle), and b = 10 (right). Bars show standard deviation. contracts as if according to the mean of their posterior. Hence, the belief distribution P of the market assigns weight P(p) = n q k (1 − q)n−k to belief p = (α + k)/(2α + n), yielding k a biased mean belief of (α + nq)/(2α + n). We show a typical simulation of this market in Figure 1, where traders behave as Kelly betters in the ﬁxed-price LMSR. Clearly, after almost every trade, the market price is quite far from the equilibrium/stationary point, and hence the classical supply and demand analysis of this market yields a poor description of the actual behavior, and in particular, of the predictive quality of the price at any given time. However, the mean price is consistently close to the mean belief of the traders, which in turn is quite close to the true parameter q. Election Survey Data We now compare the quality of the running average price versus the instantaneous price as a predictor of the mean belief of a market. We do so by simulating a market maker interacting with traders with unit wealth, log utility, and beliefs drawn from a ﬁxed distribution. The belief distributions are derived from the Princeton election survey data[10]. For each of the 50 US states, participants in the survey were asked to estimate the probability that one of two possible candidates were going to win that state.4 We use these 50 sets of estimates as 50 diﬀerent empirical distributions from which to draw trader beliefs. A simulation is conﬁgured by choosing one of the 50 empirical belief distributions S, a market liquidity parameter b to deﬁne the LMSR cost function C(s) = b ln i esi /b , and an initial market position vector of (0, 0) – that is, no contracts for either outcome. A conﬁgured simulation is run for T trades. At each trade, a belief p is drawn from S uniformly and with replacement. This belief is used to determine the demand of the trader relative to the current market pricing. The trader purchase a bundle of contracts according to its demand and the market moves its position and price accordingly. The complete price path πt for t t = 1, . . . , T of the market is recorded as well as a running average price πt := 1 i=1 πt for ¯ t t = 1 . . . , T . For each of the 50 empirical belief distributions we conﬁgured 9 markets with b ∈ {1, 2, 3, 5, 10, 15, 20, 30, 50} and ran 20 independent simulations of T = 100 trades. We present a portion of the results for the empirical distributions for states 9 and 11. States 9 and 11 have, respectively, sample sizes of 2,717 and 2,709; means 0.26 and 0.9; and variances 0.04 and 0.02. These are chosen as being representative of the rest of the simulation results: State 9 with mean oﬀ-center and a spread of beliefs (high uncertainty) and State 11 with highly concentrated beliefs around a single outcome (low uncertainty). The results are summarised in Figures 2, 3, and 4. The ﬁrst show the square loss of the average and instaneous prices relative to the mean belief for high uncertainty State 9 for b = 1, 3, 10. Clearly, the average price is a much more reliable estimator of the mean belief for low liquidity (b = 1) and is only outperformed by the instaneous price for higher liquidity (b = 10), but then only early in trading. Similar plots for State 11 are shown in Figure 3 where the advantage of using the average price is signiﬁcantly diminished. 4 The original dataset contains conjunctions of wins as well as conditional statements but we only use the single variable results of the survey. 7 0 20 40 60 80 100 b = 10 Instant Averaged 0.06 Loss 0.04 0.02 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged 0.00 0.00 0.02 0.04 Loss 0.06 0.08 Instant Averaged Square loss of price to mean belief for State 11 b=3 0.08 b=1 0.10 Square loss of price to mean belief for State 11 0.10 0.10 Square loss of price to mean belief for State 11 0 20 40 Trades 60 80 100 0 20 40 Trades 60 80 100 Trades Figure 3: Mean square loss of average and instantaneous prices relative to the mean belief of 0.9 over 20 simulations for State 11 for b = 1 (left), b = 3 (middle), and b = 10 (right). Bars show standard deviation. Figure 4 shows the improvement the average price has over the instantaneous price in square loss relative to the mean belief for all liquidity settings and highlights that average prices work better in low liquidity settings, consistent with the theory. Similar trends were observed for all the other States, depending on whether they had high uncertainty – in which case average price was a much better estimator – or low uncertainty – in which case instanteous price was better. Improvement of Average over Instant Prices for State 9 Improvement of Average over Instant Prices for State 11 0.06 0.02 0.00 0.04 Loss Di fference fference -0.04 0.00 -0.06 -0.02 -0.08 10 20 100 80 80 30 40 40 30 60 Tra des b 60 Tra des 10 20 100 20 b Loss Di -0.02 0.02 40 40 20 50 50 Figure 4: An overview of the results for States 9 (left) and 11 (right). For each trade and choice of b, the vertical value shows the improvement of the average price over the instantaneous price as measure by square loss relative to the mean. 6 Conclusion and future work As noted in Section 3.1, there are several open questions with regard to maximum expected utility demands and Theorem 1, as well as the relationship between trader wealth and market liquidity. It would also be interesting to have a application of Theorem 2 to a continuousprice model, which yields a natural minimization as in Corollary 1. The equivalence to mirror decent stablished in Theorem 2 may also lead to a better understanding of the optimal manner in which a automated prediction market ought to increase liquidity so as to maximise eﬃciency. Acknowledgments This work was supported by the Australian Research Council (ARC). NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the ARC through the ICT Centre of Excellence program. The ﬁrst author was partially supported by NSF grant CC-0964033 and by a Google University Research Award. 8 References [1] J. Abernethy, Y. Chen, and J.W. Vaughan. An optimization-based framework for automated market-making. In Proceedings of the 11th ACM conference on Electronic Commerce (EC’11), 2011. [2] A. Barbu and N. Lay. An introduction to artiﬁcial prediction markets for classiﬁcation. Arxiv preprint arXiv:1102.1465, 2011. [3] A. Beygelzimer, J. Langford, and D. Pennock. Learning Performance of Prediction Markets with Kelly Bettors. 2012. [4] S. Boyd and L. Vandenberghe. Convex optimization. Cambridge University Press, 2004. [5] Y. Chen and J.W. Vaughan. A new understanding of prediction markets via no-regret learning, pages 189–198. 2010. [6] J. Duchi, S. Shalev-Shwartz, Y. Singer, and A. Tewari. Composite objective mirror descent. COLT, 2010. [7] C.F. Manski. Interpreting the predictions of prediction markets. Technical report, National Bureau of Economic Research, 2004. [8] A. Othman and T. Sandholm. When do markets with simple agents fail? In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1-Volume 1, pages 865–872. International Foundation for Autonomous Agents and Multiagent Systems, 2010. [9] A. Storkey. Machine learning markets. AISTATS, 2012. [10] G. Wang, S.R. Kulkarni, H.V. Poor, and D.N. Osherson. Aggregating large sets of probabilistic forecasts by weighted coherent adjustment. Decision Analysis, 8(2):128, 2011. [11] J. Wolfers and E. Zitzewitz. Interpreting prediction market prices as probabilities. Technical report, National Bureau of Economic Research, 2006. 9

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 au Abstract We strengthen recent connections between prediction markets and learning by showing that a natural class of market makers can be understood as performing stochastic mirror descent when trader demands are sequentially drawn from a ﬁxed distribution. [sent-9, score-1.294]

2 This provides new insights into how market prices (and price paths) may be interpreted as a summary of the market’s belief distribution by relating them to the optimization problem being solved. [sent-10, score-1.178]

3 In particular, we show that under certain conditions the stationary point of the stochastic process of prices generated by the market is equal to the market’s Walrasian equilibrium of classic market analysis. [sent-11, score-1.393]

4 Together, these results suggest how traditional market making mechanisms might be replaced with general purpose learning algorithms while still retaining guarantees about their behaviour. [sent-12, score-0.51]

5 In [5] an equivalence is shown between the theoretically popular prediction market makers based on sequences of proper scoring rules and follow the regularised leader, a form of no-regret online learning. [sent-14, score-0.599]

6 By modelling the traders that demand the assets the market maker is oﬀering we are able to extend the equivalence to stochastic mirror decent. [sent-15, score-1.262]

7 The dynamics of wealth transfer is studied in [3], for a sequence of markets between agents that behave as Kelly bettors (i. [sent-16, score-0.363]

8 More broadly, [9, 2] have analysed how a wide range of machine learning models can be implemented in terms of market equilibria. [sent-19, score-0.491]

9 The literature on the interpretation of prediction market prices [7, 11] has had the goal of relating the equilibrium prices to the distribution of the beliefs of traders. [sent-20, score-1.109]

10 We continue this latter path of research, motivated by the observation that the equilibrium price may be a poor predictor of the behavior in a volitile prediction market. [sent-22, score-0.519]

11 As such, we seek a more detailed understanding of the market than the equilibrium point – we would like to know what the “stationary distribution” of the price is, as time goes to inﬁnity. [sent-23, score-0.952]

12 Our model features an automated market maker, following the framework of [1] is becoming a standard framework in the ﬁeld. [sent-25, score-0.53]

13 First, we prove that under certain conditions the stationary point of our stochastic process deﬁned by the market maker and a belief distribution of traders converges to the Walrasian equilibrium of the market as the market liquidity increases. [sent-27, score-2.506]

14 Second, we show in Corollary 1 that when traders are Kelly bettors, the resulting stochastic market process is equivalent to stochastic mirror descent; see e. [sent-29, score-0.977]

15 This result adds to the growing literature which relates prediction markets, and automated market makers in general, to online learning; see e. [sent-32, score-0.614]

16 This connection to mirror descent seems to suggest that the prices in a prediction market at any given time may be meaningless, as the ﬁnal point in stochastic mirror descent often has poor convergence guarantees. [sent-35, score-1.177]

17 However, standard results suggest that a prudent way to form a “consensus estimate” from a prediction market is to average the prices. [sent-36, score-0.565]

18 The average price, assuming our market model is reasonable, is provably close to the stationary price. [sent-37, score-0.545]

19 Beyond this, however, Theorem 2 gives us insight into the relationship between the market liquidity and the convergence of prices; in particular it suggests that we should increase liquidity at a rate √ of t if we wish the price to settle down at the right rate. [sent-39, score-1.495]

20 2 Model Our market model will follow the automated market maker framework of [1]. [sent-40, score-1.141]

21 We will equip our market maker with a strictly convex function C : Rn → R which is twice continuously diﬀerentiable. [sent-41, score-0.691]

22 A trader purchasing shares at the current prices π ∈ Rn pays C(ϕ−1 (π) + r) − C(ϕ−1 (π)) for the bundle of contracts r ∈ Rn . [sent-45, score-0.653]

23 Note that our dependence solely on π limits our model slightly, since in general the share space (domain of C) may contain more information than the current prices (cf. [sent-46, score-0.203]

24 The bundle r is determined by an agent’s demand function d(C, π) which speciﬁes the bundle to buy given the price π and the cost function C. [sent-48, score-0.698]

25 The market maker posts the current price πt , and at each time t = 1 . [sent-50, score-0.958]

26 T , a trader is chosen with demand function d drawn i. [sent-53, score-0.434]

27 Intuitively, these demands are parameterized by latent variables such as the agent’s belief p ∈ ∆Ω and total wealth W . [sent-57, score-0.409]

28 The price is then updated to πt+1 = ϕ(ϕ−1 (πt ) + d(C, πt )). [sent-58, score-0.347]

29 3 Stationarity and equilibrium We ﬁrst would like to relate our stochastic model (1) to the standard notion of market equilibrium from the Economics literature, which we call the Walrasian equilibrium to avoid confusion. [sent-63, score-0.91]

30 Here prices are ﬁxed, and the equilibrium price is one that clears the market, meaning that the sum of the demands r is 0 ∈ Rn . [sent-64, score-0.819]

31 In fact, we will show that the stationary point of our process approaches the Walrasian equilibrium point as the liquidity of the market approaches inﬁnity. [sent-65, score-0.959]

32 2 First, we must add a liquidity parameter to our market. [sent-66, score-0.318]

33 Observe that ϕb (s) := Cb (s) = C(s/b) = ϕ(s/b), meaning that the price under Cb at s is the same as the price under C at s/b. [sent-69, score-0.694]

34 As with the LMSR, we call b the liquidity parameter ; this terminology is justiﬁed by noting that one deﬁnition of liquidity, 1/λmax 2 Cb (s) = b/λmax 2 C(s/b) (cf. [sent-70, score-0.318]

35 Second, in order to connect to the Walrasian equilibrium, we need a notion of a ﬁxed-price demand function: if a trader has demand d(C, ·) given C, what would the same trader’s demand be under a market where prices are ﬁxed and do not “change” during a trade? [sent-73, score-1.526]

36 For the sake of generality, we restrict our allowable demand functions to the ones for which the limit d(F, π) := lim d(Cb , π) (3) b→∞ exists; this demand d(F, ·) will be the corresponding ﬁxed-price demand for d. [sent-74, score-0.683]

37 We now deﬁne the Walrasion equilibrium point π ∗ , which is simply the price at which the market clears when traders have demands distributed by D. [sent-75, score-1.357]

38 Formally, this is the following condition:1 d(F, π ∗ ) dD(d) = 0 (4) D Note that 0 ∈ Rn ; the demand for each contract should be balanced. [sent-76, score-0.241]

39 s The stationary point of our stochastic process, on the other hand, is the price πb for which the expected price ﬂuctuation is 0. [sent-77, score-0.788]

40 Formally, we have s s E [∆(πb , d(Cb , πb ))] = 0, (5) d∼D where ∆(π, d) := ϕ(ϕ−1 (π) + d) − π is the price ﬂuctuation. [sent-78, score-0.347]

41 We now consider the limit of our stochastic process as the market liquidity approaches ∞. [sent-79, score-0.899]

42 Since the limit is uniform with respect to D, we now have s lim Zb (π) = lim b E [∆(π, d(Cb , π))] = E b→∞ b→∞ = 2 d∼D d∼D C(s) E [d(F, π)] = 2 lim b∆(π, d(Cb , π)) b→∞ C(s) Z(π). [sent-90, score-0.194]

43 1 Utility-based demands Maximum Expected Utility (MEU) demand functions are a particular kind of demand function derived by assuming a trader has some belief p ∈ ∆n over the outcomes in Ω, some wealth W ≥ 0, and a monotonically increasing utility function of money u : R → R. [sent-108, score-1.082]

44 If such a trader buys a bundle r of contracts from a market maker with cost function C and price π, her wealth after ω occurs is Υω (C, W, π, r) := W +φ(ω)·r−[C(ϕ−1 (π)+r)−C(ϕ−1 (π))]. [sent-109, score-1.517]

45 We ensure traders do not go into debt by requiring that traders only make demands such that this ﬁnal wealth is nonnegative: ∀ω Υω (C, π, r) ≥ 0. [sent-110, score-0.772]

46 The set of debt-free bundles for wealth W and market C at price π is denoted S(C, W, π) := {r ∈ Rn : minω Υω (C, W, π, r) ≥ 0}. [sent-111, score-0.986]

47 A continuous MEU demand function du (C, π) is then just the demand that maximizes a W,p trader’s expected utility subject to the debt-free constraint. [sent-112, score-0.459]

48 (6) r∈S(C,W,π) ω∼p We also deﬁne a ﬁxed-price MEU demand function du (F, π) similarly, where W,p Υω (F, W, π, r) := W + φ(ω) · r − π · r and S(F, W, π) := {r ∈ Rn : minω Υω (F, W, π, r) ≥ 0} are the ﬁxed price analogues to the continuously priced versions above. [sent-114, score-0.642]

49 Using the notation bS := {b r | r ∈ S}, the following relationships between the continuous and ﬁxed price versions of Υ, SW , and the expected utility are a consequence of the convexity of C. [sent-115, score-0.415]

50 Their main purpose is to highlight the relationship between wealth and liquidity in MEU demands. [sent-116, score-0.487]

51 In particular, they show that scaling up of liquidity is equivalent to a scaling down of wealth and that the continuously priced constraints and wealth functions monotonically approach the ﬁxed priced versions. [sent-117, score-0.736]

52 For any strictly convex cost function C, wealth W > 0, price π, demand r, and liquidity parameter b > 0 the following properties hold: 1. [sent-119, score-1.086]

53 This would relate our model to that of [8], where the authors essentially show a wealth-limit version of Theorem 1 for a binary-outcome market where traders have linear utilities (a special case of (6)). [sent-141, score-0.791]

54 4 Market making as mirror descent We now explore the surprising relationship between our stochastic price update and standard stochastic optimization techniques. [sent-143, score-0.672]

55 In particular, we will relate our model to a stochastic mirror descent of the form xt+1 = argmin{η x · F (xt ; ξ) + DR (x, xt )}, (7) x∈R where at each step ξ ∼ Ξ are i. [sent-144, score-0.274]

56 We will refer to an algorithm of the form (7) a stochastic mirror descent of f (x) := Eξ∼Ξ [F (x; ξ)]. [sent-148, score-0.223]

57 If for all d ∈ D we have some F (· ; d) : Rn → Rn such that d(R∗ , π) = − F (π; d), then the stochastic update of our model (1) is exactly a stochastic mirror descent of f (π) = Ed∼D [F (π; d)]. [sent-150, score-0.304]

58 As an example, consider Kelly betters, which correspond to ﬁxed-price demands d(C, π) := dlog (F, π) with utility u(x) = log x as deﬁned in (3). [sent-156, score-0.233]

59 The stochastic update for ﬁxed-price Kelly betters (8) is exactly a stochastic mirror descent of f (π) = W · KL(p, π), where p and W are the means of P and W, respectively. [sent-159, score-0.367]

60 W,p x 1−x Hence, by Theorem 2 our update is a stochastic mirror descent of: f (x) := E[F (x; dlog )] = E[W p log x + W (1 − p) log(1 − x)] = W · (KL(p, x) + H(p)) , W,p which of course is equivalent to W · KL(p, x) as the entropy term does not depend on x. [sent-163, score-0.315]

61 Note that while this last result is quite compelling, we have mixed ﬁxed-price demands with a continuous-price market model – see Section 3. [sent-164, score-0.615]

62 One could interpret this combination as a model in which the market maker can only adjust the prices after a trade, according to a ﬁxed convex cost function C. [sent-166, score-0.871]

63 This of course diﬀers from the standard model, which adjusts the price continuously during a trade. [sent-167, score-0.375]

64 1 Leveraging existing learning results Theorem 2 not only identiﬁes a fascinating connection between machine learning and our stochastic prediction market model, but it also allows us to use powerful existing techniques to make broad conclusions about the behavior of our model. [sent-169, score-0.604]

65 70 In our context, Proposition 1 says that the average of the prices will be a very good estimate of the minimizer of f , which as suggested by happens to be the underlying mean belief p of the traders! [sent-172, score-0.384]

66 Moreover, as the Kelly demands are linear in both p and W , it is easy to see from Theorem 1 that p is also the stationary point and the Walrasian equilibrium point (the latter was also shown by [11]). [sent-173, score-0.274]

67 On the other hand, as we demonstrate next, it is not hard to come up with an example where the instantaneous price πt is quite far from the equilibrium at any given time period. [sent-174, score-0.513]

68 6, n = 6, stochastic market model and mirror descent sheds α = 0. [sent-182, score-0.714]

69 5) beliefs in the LMSR market light on an important question: how might an auto- with liquidity b = 10. [sent-183, score-0.87]

70 mated market maker adjust the liquidity so that the market actually converges to the mean of the traders’ beliefs? [sent-184, score-1.446]

71 The learning parameter η can be thought of as the inverse of the liquidity, and as such, Proposition 1 suggests that √ increasing the liquidity as t may cause the mean price to converge to the mean belief (assuming a ﬁxed underlying belief distribution). [sent-185, score-0.991]

72 5 Empirical work Example: biased coin Consider a classic Bayesian setting where a coin has unknown bias Pr[heads] = q, and traders have a prior β(α, α) over q (i. [sent-186, score-0.354]

73 Now suppose each trader independently observes n ﬂips from the coin, and updates her belief; upon seeing k heads, a trader would have posterior β(α + k, α + n − k). [sent-189, score-0.47]

74 When presented with a prediction market with contracts for a single toss of the coin, where and contract 0 pays $1 for tails and contract 1 pays $1 for heads, a trader would purchase 6 0 20 40 60 Trades 80 100 b = 10 Instant Averaged 0. [sent-190, score-1.03]

75 08 Instant Averaged Square loss of price to mean belief for State 9 b=3 0. [sent-204, score-0.547]

76 10 Square loss of price to mean belief for State 9 0. [sent-206, score-0.547]

77 10 Square loss of price to mean belief for State 9 0 20 40 60 Trades 80 100 0 20 40 60 80 100 Trades Figure 2: Mean square loss of average and instantaneous prices relative to the mean belief of 0. [sent-208, score-1.06]

78 Hence, the belief distribution P of the market assigns weight P(p) = n q k (1 − q)n−k to belief p = (α + k)/(2α + n), yielding k a biased mean belief of (α + nq)/(2α + n). [sent-212, score-0.928]

79 We show a typical simulation of this market in Figure 1, where traders behave as Kelly betters in the ﬁxed-price LMSR. [sent-213, score-0.821]

80 Clearly, after almost every trade, the market price is quite far from the equilibrium/stationary point, and hence the classical supply and demand analysis of this market yields a poor description of the actual behavior, and in particular, of the predictive quality of the price at any given time. [sent-214, score-1.896]

81 However, the mean price is consistently close to the mean belief of the traders, which in turn is quite close to the true parameter q. [sent-215, score-0.536]

82 Election Survey Data We now compare the quality of the running average price versus the instantaneous price as a predictor of the mean belief of a market. [sent-216, score-0.927]

83 We do so by simulating a market maker interacting with traders with unit wealth, log utility, and beliefs drawn from a ﬁxed distribution. [sent-217, score-0.944]

84 4 We use these 50 sets of estimates as 50 diﬀerent empirical distributions from which to draw trader beliefs. [sent-220, score-0.235]

85 A simulation is conﬁgured by choosing one of the 50 empirical belief distributions S, a market liquidity parameter b to deﬁne the LMSR cost function C(s) = b ln i esi /b , and an initial market position vector of (0, 0) – that is, no contracts for either outcome. [sent-221, score-1.593]

86 This belief is used to determine the demand of the trader relative to the current market pricing. [sent-224, score-1.062]

87 The trader purchase a bundle of contracts according to its demand and the market moves its position and price accordingly. [sent-225, score-1.454]

88 , T of the market is recorded as well as a running average price πt := 1 i=1 πt for ¯ t t = 1 . [sent-229, score-0.856]

89 For each of the 50 empirical belief distributions we conﬁgured 9 markets with b ∈ {1, 2, 3, 5, 10, 15, 20, 30, 50} and ran 20 independent simulations of T = 100 trades. [sent-233, score-0.274]

90 The ﬁrst show the square loss of the average and instaneous prices relative to the mean belief for high uncertainty State 9 for b = 1, 3, 10. [sent-242, score-0.509]

91 Clearly, the average price is a much more reliable estimator of the mean belief for low liquidity (b = 1) and is only outperformed by the instaneous price for higher liquidity (b = 10), but then only early in trading. [sent-243, score-1.542]

92 Similar plots for State 11 are shown in Figure 3 where the advantage of using the average price is signiﬁcantly diminished. [sent-244, score-0.365]

93 08 Instant Averaged Square loss of price to mean belief for State 11 b=3 0. [sent-260, score-0.547]

94 10 Square loss of price to mean belief for State 11 0. [sent-262, score-0.547]

95 10 Square loss of price to mean belief for State 11 0 20 40 Trades 60 80 100 0 20 40 Trades 60 80 100 Trades Figure 3: Mean square loss of average and instantaneous prices relative to the mean belief of 0. [sent-264, score-1.06]

96 Figure 4 shows the improvement the average price has over the instantaneous price in square loss relative to the mean belief for all liquidity settings and highlights that average prices work better in low liquidity settings, consistent with the theory. [sent-267, score-1.861]

97 Similar trends were observed for all the other States, depending on whether they had high uncertainty – in which case average price was a much better estimator – or low uncertainty – in which case instanteous price was better. [sent-268, score-0.746]

98 For each trade and choice of b, the vertical value shows the improvement of the average price over the instantaneous price as measure by square loss relative to the mean. [sent-281, score-0.895]

99 1, there are several open questions with regard to maximum expected utility demands and Theorem 1, as well as the relationship between trader wealth and market liquidity. [sent-283, score-1.059]

100 The equivalence to mirror decent stablished in Theorem 2 may also lead to a better understanding of the optimal manner in which a automated prediction market ought to increase liquidity so as to maximise eﬃciency. [sent-285, score-1.05]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('market', 0.491), ('price', 0.347), ('liquidity', 0.318), ('traders', 0.25), ('trader', 0.235), ('cb', 0.233), ('prices', 0.203), ('demand', 0.199), ('wealth', 0.148), ('belief', 0.137), ('markets', 0.137), ('demands', 0.124), ('mirror', 0.12), ('maker', 0.12), ('equilibrium', 0.114), ('kelly', 0.102), ('walrasian', 0.094), ('contracts', 0.089), ('meu', 0.078), ('instant', 0.074), ('dlog', 0.069), ('zb', 0.068), ('bundle', 0.065), ('betters', 0.063), ('lmsr', 0.063), ('beliefs', 0.061), ('trades', 0.059), ('stochastic', 0.058), ('lim', 0.054), ('trade', 0.054), ('coin', 0.052), ('instantaneous', 0.052), ('agents', 0.047), ('makers', 0.047), ('priced', 0.047), ('wealths', 0.047), ('descent', 0.045), ('contract', 0.042), ('utility', 0.04), ('square', 0.04), ('australian', 0.039), ('rn', 0.039), ('automated', 0.039), ('gured', 0.038), ('prediction', 0.037), ('loss', 0.037), ('stationary', 0.036), ('convex', 0.035), ('limb', 0.034), ('heads', 0.034), ('pays', 0.033), ('limit', 0.032), ('xt', 0.032), ('utilities', 0.031), ('bettors', 0.031), ('clears', 0.031), ('fference', 0.031), ('instaneous', 0.031), ('payo', 0.031), ('tra', 0.031), ('convexity', 0.028), ('continuously', 0.028), ('esi', 0.028), ('purchasing', 0.028), ('purchase', 0.028), ('bureau', 0.028), ('interpreting', 0.027), ('state', 0.026), ('mean', 0.026), ('election', 0.025), ('di', 0.025), ('equivalence', 0.024), ('update', 0.023), ('uniformity', 0.023), ('interacting', 0.022), ('multiagent', 0.022), ('arc', 0.022), ('cost', 0.022), ('relationship', 0.021), ('nicta', 0.021), ('stationarity', 0.021), ('avg', 0.021), ('decent', 0.021), ('du', 0.021), ('poor', 0.021), ('kl', 0.02), ('averaged', 0.02), ('des', 0.02), ('theorem', 0.02), ('leave', 0.019), ('outcome', 0.019), ('relate', 0.019), ('dd', 0.019), ('suggest', 0.019), ('average', 0.018), ('economic', 0.018), ('connection', 0.018), ('simulation', 0.017), ('uncertainty', 0.017), ('strictly', 0.017)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0 161 nips-2012-Interpreting prediction markets: a stochastic approach

Author: Nicolas D. Penna, Mark D. Reid, Rafael M. Frongillo

2 0.0667511 134 nips-2012-Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

Author: Andre Wibisono, Martin J. Wainwright, Michael I. Jordan, John C. Duchi

Abstract: We consider derivative-free algorithms for stochastic optimization problems that use only noisy function values rather than gradients, analyzing their ﬁnite-sample convergence rates. We show that if pairs of function values are available, algorithms that √ gradient estimates based on random perturbations suffer a factor use of at most d in convergence rate over traditional stochastic gradient methods, where d is the problem dimension. We complement our algorithmic development with information-theoretic lower bounds on the minimax convergence rate of such problems, which show that our bounds are sharp with respect to all problemdependent quantities: they cannot be improved by more than constant factors. 1

3 0.050845951 324 nips-2012-Stochastic Gradient Descent with Only One Projection

Author: Mehrdad Mahdavi, Tianbao Yang, Rong Jin, Shenghuo Zhu, Jinfeng Yi

Abstract: Although many variants of stochastic gradient descent have been proposed for large-scale convex optimization, most of them require projecting the solution at each iteration to ensure that the obtained solution stays within the feasible domain. For complex domains (e.g., positive semideﬁnite cone), the projection step can be computationally expensive, making stochastic gradient descent unattractive for large-scale optimization problems. We address this limitation by developing novel stochastic optimization algorithms that do not need intermediate projections. Instead, only one projection at the last iteration is needed to obtain a feasible solution in the given domain. Our theoretical analysis shows that with a high probability, √ the proposed algorithms achieve an O(1/ T ) convergence rate for general convex optimization, and an O(ln T /T ) rate for strongly convex optimization under mild conditions about the domain and the objective function. 1

4 0.048476327 277 nips-2012-Probabilistic Low-Rank Subspace Clustering

Author: S. D. Babacan, Shinichi Nakajima, Minh Do

Abstract: In this paper, we consider the problem of clustering data points into lowdimensional subspaces in the presence of outliers. We pose the problem using a density estimation formulation with an associated generative model. Based on this probability model, we ﬁrst develop an iterative expectation-maximization (EM) algorithm and then derive its global solution. In addition, we develop two Bayesian methods based on variational Bayesian (VB) approximation, which are capable of automatic dimensionality selection. While the ﬁrst method is based on an alternating optimization scheme for all unknowns, the second method makes use of recent results in VB matrix factorization leading to fast and effective estimation. Both methods are extended to handle sparse outliers for robustness and can handle missing values. Experimental results suggest that proposed methods are very effective in subspace clustering and identifying outliers. 1

5 0.047141708 199 nips-2012-Link Prediction in Graphs with Autoregressive Features

Author: Emile Richard, Stephane Gaiffas, Nicolas Vayatis

Abstract: In the paper, we consider the problem of link prediction in time-evolving graphs. We assume that certain graph features, such as the node degree, follow a vector autoregressive (VAR) model and we propose to use this information to improve the accuracy of prediction. Our strategy involves a joint optimization procedure over the space of adjacency matrices and VAR matrices which takes into account both sparsity and low rank properties of the matrices. Oracle inequalities are derived and illustrate the trade-offs in the choice of smoothing parameters when modeling the joint effect of sparsity and low rank property. The estimate is computed efﬁciently using proximal methods through a generalized forward-backward agorithm. 1

6 0.046813693 288 nips-2012-Rational inference of relative preferences

7 0.046436131 45 nips-2012-Approximating Equilibria in Sequential Auctions with Incomplete Information and Multi-Unit Demand

8 0.045463707 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models

9 0.044357009 325 nips-2012-Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

10 0.041173879 227 nips-2012-Multiclass Learning with Simplex Coding

11 0.040636569 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

12 0.040088102 286 nips-2012-Random Utility Theory for Social Choice

13 0.037220452 153 nips-2012-How Prior Probability Influences Decision Making: A Unifying Probabilistic Model

14 0.035445411 143 nips-2012-Globally Convergent Dual MAP LP Relaxation Solvers using Fenchel-Young Margins

15 0.035427086 351 nips-2012-Transelliptical Component Analysis

16 0.035060011 105 nips-2012-Dynamic Pruning of Factor Graphs for Maximum Marginal Prediction

17 0.034392111 331 nips-2012-Symbolic Dynamic Programming for Continuous State and Observation POMDPs

18 0.034369621 218 nips-2012-Mixing Properties of Conditional Markov Chains with Unbounded Feature Functions

19 0.032769378 122 nips-2012-Exploration in Model-based Reinforcement Learning by Empirically Estimating Learning Progress

20 0.03216517 296 nips-2012-Risk Aversion in Markov Decision Processes via Near Optimal Chernoff Bounds

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.091), (1, -0.019), (2, 0.05), (3, 0.013), (4, 0.015), (5, 0.012), (6, -0.007), (7, 0.001), (8, -0.031), (9, 0.015), (10, -0.001), (11, -0.003), (12, -0.024), (13, 0.011), (14, 0.01), (15, -0.005), (16, 0.002), (17, -0.039), (18, -0.023), (19, 0.031), (20, -0.012), (21, -0.004), (22, -0.006), (23, 0.033), (24, -0.045), (25, -0.017), (26, 0.003), (27, 0.021), (28, 0.017), (29, 0.031), (30, 0.035), (31, 0.009), (32, -0.041), (33, 0.021), (34, 0.011), (35, 0.06), (36, 0.053), (37, 0.008), (38, 0.031), (39, 0.015), (40, -0.032), (41, -0.039), (42, 0.005), (43, -0.026), (44, -0.002), (45, 0.01), (46, 0.031), (47, -0.068), (48, -0.01), (49, 0.019)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.89527285 161 nips-2012-Interpreting prediction markets: a stochastic approach

Author: Nicolas D. Penna, Mark D. Reid, Rafael M. Frongillo

2 0.58244622 343 nips-2012-Tight Bounds on Profile Redundancy and Distinguishability

Author: Jayadev Acharya, Hirakendu Das, Alon Orlitsky

Abstract: The minimax KL-divergence of any distribution from all distributions in a collection P has several practical implications. In compression, it is called redundancy and represents the least additional number of bits over the entropy needed to encode the output of any distribution in P. In online estimation and learning, it is the lowest expected log-loss regret when guessing a sequence of random values generated by a distribution in P. In hypothesis testing, it upper bounds the largest number of distinguishable distributions in P. Motivated by problems ranging from population estimation to text classiﬁcation and speech recognition, several machine-learning and information-theory researchers have recently considered label-invariant observations and properties induced by i.i.d. distributions. A sufﬁcient statistic for all these properties is the data’s proﬁle, the multiset of the number of times each data element appears. Improving on a sequence of previous works, we show that the redundancy of the collection of distributions induced over proﬁles by length-n i.i.d. sequences is between 0.3 · n1/3 and n1/3 log2 n, in particular, establishing its exact growth power. 1

3 0.58165026 325 nips-2012-Stochastic optimization and sparse statistical recovery: Optimal algorithms for high dimensions

Author: Alekh Agarwal, Sahand Negahban, Martin J. Wainwright

Abstract: We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding a O(d/T ) convergence rate for strongly convex objectives in d dimensions and O( s(log d)/T ) convergence rate when the optimum is s-sparse. Our algorithm is based on successively solving a series of ℓ1 -regularized optimization problems using Nesterov’s dual averaging algorithm. We establish that the error of our solution after T iterations is at most O(s(log d)/T ), with natural extensions to approximate sparsity. Our results apply to locally Lipschitz losses including the logistic, exponential, hinge and least-squares losses. By recourse to statistical minimax results, we show that our convergence rates are optimal up to constants. The effectiveness of our approach is also conﬁrmed in numerical simulations where we compare to several baselines on a least-squares regression problem.

4 0.58068675 134 nips-2012-Finite Sample Convergence Rates of Zero-Order Stochastic Optimization Methods

Author: Andre Wibisono, Martin J. Wainwright, Michael I. Jordan, John C. Duchi

5 0.54688573 16 nips-2012-A Polynomial-time Form of Robust Regression

Author: Ozlem Aslan, Dale Schuurmans, Yao-liang Yu

Abstract: Despite the variety of robust regression methods that have been developed, current regression formulations are either NP-hard, or allow unbounded response to even a single leverage point. We present a general formulation for robust regression—Variational M-estimation—that uniﬁes a number of robust regression methods while allowing a tractable approximation strategy. We develop an estimator that requires only polynomial-time, while achieving certain robustness and consistency guarantees. An experimental evaluation demonstrates the effectiveness of the new estimation approach compared to standard methods. 1

6 0.53804958 217 nips-2012-Mixability in Statistical Learning

7 0.53216666 110 nips-2012-Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems

8 0.52614385 45 nips-2012-Approximating Equilibria in Sequential Auctions with Incomplete Information and Multi-Unit Demand

9 0.51998901 333 nips-2012-Synchronization can Control Regularization in Neural Systems via Correlated Noise Processes

10 0.51857686 139 nips-2012-Fused sparsity and robust estimation for linear models with unknown variance

11 0.50984442 76 nips-2012-Communication-Efficient Algorithms for Statistical Optimization

12 0.49563822 290 nips-2012-Recovery of Sparse Probability Measures via Convex Programming

13 0.49298272 288 nips-2012-Rational inference of relative preferences

14 0.49016532 96 nips-2012-Density Propagation and Improved Bounds on the Partition Function

15 0.48426312 263 nips-2012-Optimal Regularized Dual Averaging Methods for Stochastic Optimization

16 0.48280111 286 nips-2012-Random Utility Theory for Social Choice

17 0.4815287 206 nips-2012-Majorization for CRFs and Latent Likelihoods

18 0.47990781 296 nips-2012-Risk Aversion in Markov Decision Processes via Near Optimal Chernoff Bounds

19 0.47868058 262 nips-2012-Optimal Neural Tuning Curves for Arbitrary Stimulus Distributions: Discrimax, Infomax and Minimum $L p$ Loss

20 0.47364891 302 nips-2012-Scaling MPE Inference for Constrained Continuous Markov Random Fields with Consensus Optimization

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.021), (21, 0.023), (27, 0.011), (36, 0.027), (38, 0.108), (40, 0.396), (42, 0.04), (54, 0.036), (55, 0.017), (74, 0.029), (76, 0.101), (80, 0.058), (92, 0.036)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.76596522 161 nips-2012-Interpreting prediction markets: a stochastic approach

Author: Nicolas D. Penna, Mark D. Reid, Rafael M. Frongillo

2 0.40083864 162 nips-2012-Inverse Reinforcement Learning through Structured Classification

Author: Edouard Klein, Matthieu Geist, Bilal Piot, Olivier Pietquin

Abstract: This paper adresses the inverse reinforcement learning (IRL) problem, that is inferring a reward for which a demonstrated expert behavior is optimal. We introduce a new algorithm, SCIRL, whose principle is to use the so-called feature expectation of the expert as the parameterization of the score function of a multiclass classiﬁer. This approach produces a reward function for which the expert policy is provably near-optimal. Contrary to most of existing IRL algorithms, SCIRL does not require solving the direct RL problem. Moreover, with an appropriate heuristic, it can succeed with only trajectories sampled according to the expert behavior. This is illustrated on a car driving simulator. 1

3 0.3996692 38 nips-2012-Algorithms for Learning Markov Field Policies

Author: Abdeslam Boularias, Jan R. Peters, Oliver B. Kroemer

Abstract: We use a graphical model for representing policies in Markov Decision Processes. This new representation can easily incorporate domain knowledge in the form of a state similarity graph that loosely indicates which states are supposed to have similar optimal actions. A bias is then introduced into the policy search process by sampling policies from a distribution that assigns high probabilities to policies that agree with the provided state similarity graph, i.e. smoother policies. This distribution corresponds to a Markov Random Field. We also present forward and inverse reinforcement learning algorithms for learning such policy distributions. We illustrate the advantage of the proposed approach on two problems: cart-balancing with swing-up, and teaching a robot to grasp unknown objects. 1

4 0.39890048 292 nips-2012-Regularized Off-Policy TD-Learning

Author: Bo Liu, Sridhar Mahadevan, Ji Liu

Abstract: We present a novel l1 regularized off-policy convergent TD-learning method (termed RO-TD), which is able to learn sparse representations of value functions with low computational complexity. The algorithmic framework underlying ROTD integrates two key ideas: off-policy convergent gradient TD methods, such as TDC, and a convex-concave saddle-point formulation of non-smooth convex optimization, which enables ﬁrst-order solvers and feature selection using online convex regularization. A detailed theoretical and experimental analysis of RO-TD is presented. A variety of experiments are presented to illustrate the off-policy convergence, sparse feature selection capability and low computational cost of the RO-TD algorithm. 1

5 0.3982859 83 nips-2012-Controlled Recognition Bounds for Visual Learning and Exploration

Author: Vasiliy Karasev, Alessandro Chiuso, Stefano Soatto

Abstract: We describe the tradeoff between the performance in a visual recognition problem and the control authority that the agent can exercise on the sensing process. We focus on the problem of “visual search” of an object in an otherwise known and static scene, propose a measure of control authority, and relate it to the expected risk and its proxy (conditional entropy of the posterior density). We show this analytically, as well as empirically by simulation using the simplest known model that captures the phenomenology of image formation, including scaling and occlusions. We show that a “passive” agent given a training set can provide no guarantees on performance beyond what is afforded by the priors, and that an “omnipotent” agent, capable of inﬁnite control authority, can achieve arbitrarily good performance (asymptotically). In between these limiting cases, the tradeoff can be characterized empirically. 1

6 0.39772293 69 nips-2012-Clustering Sparse Graphs

7 0.39739168 61 nips-2012-Best Arm Identification: A Unified Approach to Fixed Budget and Fixed Confidence

8 0.39722916 259 nips-2012-Online Regret Bounds for Undiscounted Continuous Reinforcement Learning

9 0.39632049 186 nips-2012-Learning as MAP Inference in Discrete Graphical Models

10 0.39628184 333 nips-2012-Synchronization can Control Regularization in Neural Systems via Correlated Noise Processes

11 0.39621165 199 nips-2012-Link Prediction in Graphs with Autoregressive Features

12 0.39539289 353 nips-2012-Transferring Expectations in Model-based Reinforcement Learning

13 0.39522821 316 nips-2012-Small-Variance Asymptotics for Exponential Family Dirichlet Process Mixture Models

14 0.39521229 364 nips-2012-Weighted Likelihood Policy Search with Model Selection

15 0.39510861 358 nips-2012-Value Pursuit Iteration

16 0.39486688 335 nips-2012-The Bethe Partition Function of Log-supermodular Graphical Models

17 0.39481851 348 nips-2012-Tractable Objectives for Robust Policy Optimization

18 0.39473611 179 nips-2012-Learning Manifolds with K-Means and K-Flats

19 0.39423335 252 nips-2012-On Multilabel Classification and Ranking with Partial Feedback

20 0.39388058 153 nips-2012-How Prior Probability Influences Decision Making: A Unifying Probabilistic Model