nips nips2008 nips2008-13 knowledge-graph by maker-knowledge-mining

13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

Source: pdf

Author: Sanmay Das, Malik Magdon-Ismail

Abstract: We study the proﬁt-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. The sequential decision problem is hard to solve because the state space is a function. We demonstrate that the belief state is well approximated by a Gaussian distribution. We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the ﬁrst optimal sequential market-making algorithm in an established model. The algorithm leads to a surprising insight: an optimal monopolist can provide more liquidity than perfectly competitive market-makers in periods of extreme uncertainty, because a monopolist is willing to absorb initial losses in order to learn a new valuation rapidly so she can extract higher proﬁts later. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract We study the proﬁt-maximization problem of a monopolistic market-maker who sets two-sided prices in an asset market. [sent-5, score-0.338]

2 We prove a key monotonicity property of the Gaussian state update which makes the problem tractable, yielding the ﬁrst optimal sequential market-making algorithm in an established model. [sent-8, score-0.167]

3 1 Introduction Designing markets to achieve certain goals is gaining renewed importance with the prevalence of many novel markets, ranging from prediction markets [13] to markets for e-services [11]. [sent-10, score-0.36]

4 These markets tend to be thin (illiquid) when they ﬁrst appear. [sent-11, score-0.144]

5 Similarly, when a market shock occurs to the value of an instrument on a ﬁnancial exchange, thousands of speculative traders suddenly possess new valuations on the basis of which they would like to trade. [sent-12, score-0.721]

6 Periods of uncertainty, like those following a shock, are also periods of illiquidity, so trading may be sparse right after a shock. [sent-13, score-0.19]

7 People do not want to trade in thin markets, and yet, having many people trading is what creates liquidity. [sent-15, score-0.251]

8 Market-makers are responsible for providing liquidity and maintaining order on the exchange. [sent-18, score-0.19]

9 For example, the NYSE designates a single monopolist specialist (marketmaker) for each stock, while the NASDAQ allows multiple market-makers to compete. [sent-19, score-0.217]

10 Should they employ a single monopolistic market-maker or multiple competitive market-makers? [sent-22, score-0.135]

11 A monopolist market maker attempts to maximize expected discounted profits, while competitive (non-colluding) market makers may only expect zero proﬁt, since any proﬁts should be wiped out by competition. [sent-25, score-1.273]

12 Therefore, one would expect markets with competitive marketmakers to be of better quality. [sent-26, score-0.173]

13 For 1 example, the NYSE’s promotional literature used to tout the beneﬁts of a monopolist for “maintaining a fair and orderly market” in the face of market shocks [6]. [sent-31, score-0.595]

14 The main challenge to formally analyzing this question is the complexity of the monopolistic market maker’s sequential decision problem. [sent-32, score-0.529]

15 The market maker, when setting bid and ask prices, is plagued by a heavily path dependent exploitation-exploration dilema. [sent-33, score-0.88]

16 There is a tradeoff between setting the prices to extract maximum proﬁt from the next trade versus setting the prices to get as much information about the new value of the instrument so as to generate larger proﬁts from future trades. [sent-34, score-0.618]

17 We present the ﬁrst such solution within an established model of market making. [sent-36, score-0.405]

18 We show the surprising fact that a monopolist market maker leads to higher market liquidity in periods of extreme market shock than does a zero-proﬁt competitive market maker. [sent-37, score-2.326]

19 In various single period settings, it has been shown that monopolists can sometimes provide greater liquidity [6] by averaging expected proﬁts across different trade sizes. [sent-38, score-0.275]

20 We show for the ﬁrst time that this can hold true with ﬁxed trade sizes in a multi-period setting, because the market-maker is willing to take losses following a shock in order to learn the new valuation more quickly. [sent-39, score-0.375]

21 Suppose an instrument has just begun trading in a market where different people have different beliefs about its value. [sent-43, score-0.684]

22 These shares should trade at prices that reﬂect the probability that the event will occur: if the outcome pays off $100, the shares should trade at about $55 if the aggregate public belief is 55% that the event will occur. [sent-45, score-0.484]

23 Similarly, the price of a stock should reﬂect the aggregate public belief about future cash ﬂows associated with a company. [sent-46, score-0.18]

24 It is well-known that markets are good at aggregating information into prices, but different market structures possess different qualities in this regard. [sent-47, score-0.525]

25 We are concerned with the properties of dealer markets, in which prices are set by one or more market-makers responsible for providing liquidity by taking one side of every trade. [sent-48, score-0.416]

26 Market-making has been studied extensively in the theoretical market microstructure literature [8, 7, for example], but only recently has the dynamic multi-period problem gained attention [2, 3]. [sent-49, score-0.466]

27 In our models, we measure liquidity using the bid-ask spread, or alternatively the probability that a trade will occur. [sent-55, score-0.275]

28 The dynamic behavior of the spread gives insight into the price discovery process. [sent-57, score-0.221]

29 The market-maker sets bid and ask prices at each trading period1 and when a trader arrives she has the option of buying or selling at those prices, or of not executing a trade. [sent-60, score-0.966]

30 Within this same framework, one can formulate the decision problem for a monopolist market-maker who maximizes her total discounted proﬁt as a reinforcement learning problem. [sent-63, score-0.254]

31 The market maker’s state is her belief about the instrument value, and her action is to set bid and ask prices. [sent-64, score-1.124]

32 The market maker’s actions must trade off proﬁt taking (exploitation) with price discovery (exploration). [sent-65, score-0.582]

33 1 The MM is willing to buy at the bid price and sell at the ask price. [sent-66, score-0.684]

34 2 The complexity of the sequential problem arises from the complexity of the state space and the fact that the action space is continuous. [sent-67, score-0.132]

35 The state of the market-maker must represent her belief about the true value of the asset being traded. [sent-68, score-0.177]

36 Even if we assume a Gaussian prior for the market-maker’s belief as well as for the beliefs of all the traders, the market-maker’s beliefs quickly become a complex product of error functions, and the exact dynamic programming problem becomes intractable. [sent-71, score-0.121]

37 We solve the Bellman equation for the optimal sequential market maker within the framework of Gaussian state space evolution, a close approximation to the true state space evolution. [sent-72, score-0.753]

38 Thus, our ﬁrst contribution is a complete solution to the optimal sequential market making problem within a Gaussian update framework. [sent-77, score-0.514]

39 Our second contribution relates to the phenomenological implications for market behavior. [sent-78, score-0.432]

40 We obtain the surprising result that in periods of extreme shock, when the market maker has large uncertainty relative to the traders, the monopolist provides greater liquidity than competitive zero-proﬁt market-makers. [sent-79, score-0.992]

41 The monopolist increases liquidity, possibly taking short term losses, in order to learn more quickly, and in doing so offers the better social outcome. [sent-80, score-0.21]

42 Of course, once the monopolist has adapted to the shock, she equilibrates at a higher bid ask spread than the the corresponding zero-proﬁt market maker with the same beliefs. [sent-81, score-1.285]

43 1 The Model and the Sequential Decision Problem Market Model At time 0, a shock occurs causing an instrument to attain value V which will be held ﬁxed through time (we consider one instrument in the market). [sent-83, score-0.357]

44 This could represent a real market shock to a stock value (change in public beliefs), an IPO, or the introduction of a new contract in a prediction market. [sent-84, score-0.608]

45 We assume that trading is divided into a sequence of discrete trading time steps, each time step corresponding to the arrival of a trader. [sent-86, score-0.284]

46 The market-maker (M M ), at each time step t ≥ 0, sets bid and ask prices bt ≤ at at which she is willing to respectively buy and sell one unit. [sent-88, score-1.062]

47 The trader decides whether to trade at either the bid or ask prices depending on the value of wt . [sent-96, score-0.947]

48 The trader will buy at at if wt > at (she thinks the instrument is undervalued), sell at bt if wt < bt (she thinks the instrument is overvalued) and do nothing otherwise. [sent-97, score-1.045]

49 M M receives a signal xt ∈ {+1, 0, −1} indicating whether the trader bought, did nothing or sold. [sent-98, score-0.173]

50 In perfect competition, the MM is pushed to setting bid and ask prices that yield zero expected proﬁt. [sent-102, score-0.697]

51 2 State Space The state space for the MM is determined by MM’s belief about the value V , described by a density function pt at time step t. [sent-110, score-0.334]

52 The MM decides on actions (bid and ask prices) (bt , at ) based on pt . [sent-111, score-0.36]

53 The MM receives signal xt ∈ {+1, 0, −1} as to whether the trader bought, sold, or did nothing. [sent-112, score-0.173]

54 Let qt (V ; bt , at ) be the probability of receiving signal xt given bid and ask (bt , at ), conditioned on V . [sent-113, score-0.953]

55 The Bayesian update to pt is then given by pt+1 (v) = ∞ t pt (v) qt (v;bt ,at ) , where the normalization constant At = −∞ dv pt (v)qt (v; bt , at ). [sent-115, score-1.181]

56 3 t qτ (v;bτ ,aτ ) τ =1 Aτ Solving for Market Maker Prices Let bt ≤ at , and let rt be the expected proﬁt at time t. [sent-117, score-0.311]

57 The expected discounted return is then R = ∞ t t=0 γ rt where 0 < γ < 1 is the discount factor. [sent-118, score-0.152]

58 We can compute ∞ rt as rt = −∞ dv vF (−v) (pt (v + bt ) + pt (at − v)). [sent-120, score-0.681]

59 rt decomposes into two terms which can ask bid be identiﬁed as the bid and ask side proﬁts, rt = rt (bt ) + rt (at ). [sent-121, score-1.206]

60 In perfect competition, M M should not be expecting any proﬁt on either the bid or ask side. [sent-122, score-0.475]

61 This is because if the contrary were true, a competing MM could place bid or ask prices so as to obtain less proﬁt, wiping out M M ’s advantage. [sent-123, score-0.677]

62 Hence the M M will set bid and ask prices such that bid ask rt (bt ) = 0 and rt (at ) = 0. [sent-125, score-1.28]

63 For the typical case of well behaved distributions pt (v) and F , the bid and ask returns display a single maximum. [sent-128, score-0.713]

64 When γ is large, the expected discounted return R could be signiﬁcantly higher than the myopic return. [sent-131, score-0.233]

65 The only reason to do this is if choosing a sub-optimal short term strategy will lead to a signiﬁcant decrease in the uncertainty in V (which translates to a narrowing of the probability distribution pt (v)). [sent-133, score-0.211]

66 The problem is heavily path dependent with the number of paths being exponential in the number of trading periods. [sent-137, score-0.142]

67 010 Probability Z α−βx dx x · N (x) = p 1 + β2 Figure 1: Gaussian state update (dashed) versus Figure 2: Gaussian integrals and normalization true state update (solid) illustrating that the Gaus- constants used in the derivation of the DP and sian approximation is valid. [sent-156, score-0.19]

68 Thus, forcing the MM to maintain a Gaussian belief over the true value at each time t should give a good approximation to the true state space evolution, and the resulting optimal actions should closely match the true optimal actions. [sent-160, score-0.227]

69 The value function is independent of µt (hence dependent only on σt ), and the optimal action is of the form bt = µt − δt , at = µt + δt . [sent-162, score-0.34]

70 + − The normalization constant A(z + , z − ) is given in Figure 2, and zt and zt are respectively 2 +∞, at , bt and at , bt , −∞ when xt = +1, 0, −1. [sent-170, score-0.641]

71 The updates µt+1 and σt+1 are obtained from Ept+1 [V ] = dv vpt+1 (v) and Ept+1 [V 2 ] = dv v 2 pt+1 (v). [sent-171, score-0.19]

72 The expectation is with respect to the future state σt+1 , which depends directly on the trade outcome xt ∈ {−1, 0, +1}. [sent-185, score-0.194]

73 We deﬁne ρt = σt /σ and q = δt /σ 1 + ρ2 , where at = µt + δt and t bt = µt − δt . [sent-186, score-0.247]

74 When x = 0, ∗ ∗ the myopic and optimal M M coincide, and so we have that V (0) = 2q (1−Φ(q )) , where q ∗ = 1−γ q ∗ (0) ≈ 0. [sent-192, score-0.207]

75 Note that if we only maximize the ﬁrst term in the value function, we obtain the myopic action q myp (ρ), satisfying the ﬁxed point equation: q myp = myp (1 + ρ2 ) 1−Φ(q ) ) . [sent-194, score-0.38]

76 There is a similarly elegant solution for the zero-proﬁt MM under the Gaussian t N (q myp assumption, obtained by setting rt = 0, yielding the ﬁxed point equation: q zero = 10 standard ﬁxed point iterations are sufﬁcient to solve these equations accurately. [sent-195, score-0.138]

77 1+ρ2 1−Φ(q zero ) t Experimental Results First, we validate the Gaussian approximation by simulating a market as follows. [sent-197, score-0.447]

78 Each simulation consists of 100 trading periods at which point discounted returns become negligible. [sent-200, score-0.23]

79 At each trading step t, a new trader arrives with a valuation wt ∼ N (V, 1) (Gaussian with mean V and variance 1). [sent-201, score-0.4]

80 In each simulation, the market-maker’s state updates are given by the Gaussian approximation (2), (3), according to which she sets bid and ask prices. [sent-203, score-0.555]

81 The trader at time-step t trades by comparing wt to bt , at . [sent-204, score-0.412]

82 4 (b) Bid-ask spreads as a function of the MM information disadvantage ρ indicating that once ρ exceeds about 1. [sent-225, score-0.144]

83 Myopic Zero Profit 5 10 15 20 Time Step t 25 30 35 (c) Realized average return as a function of time: the monopolist is willing to take signiﬁcant short term loss to improve future proﬁts as a result of better price discovery. [sent-229, score-0.349]

84 If the real world conformed to the MM’s belief, a new value Vt would be drawn from N (µt , σt ) at each trading period t, and then the trader would receive a sample wt ∼ N (Vt , 1). [sent-233, score-0.363]

85 Figure 3(a) also demonstrates that the optimal signiﬁcantly outperforms the myopic market-maker. [sent-238, score-0.207]

86 Some phenomenological properties of the market are shown in Figure 4. [sent-240, score-0.432]

87 3 For a starting MM information disadvantage of ρ = 3, the optimal MM initially has signiﬁcantly lower spread, even compared with the zero proﬁt market-maker. [sent-241, score-0.137]

88 The reason for this outcome is illustrated in Figure 3(c) where we see that the optimal market maker is offering lower spreads and taking on signiﬁcant initial loss to be compensated later by signiﬁcant proﬁts due to better price discovery. [sent-242, score-0.691]

89 At equilibrium the optimal MM’s spread and the myopic spread are equal, as expected. [sent-243, score-0.425]

90 4 Discussion Our solution to the Bellman equation for the optimal monopolistic MM leads to the striking conclusion that the optimal MM is willing to take early losses by offering lower spreads in order to make signiﬁcantly higher proﬁts later (Figures 3(b,c) and 4). [sent-244, score-0.356]

91 This is quantitative evidence that the optimal MM offers more liquidity than a zero-proﬁt MM after a market shock, especially when the MM is at a large information disadvantage. [sent-245, score-0.636]

92 Competition may actually impede the price discovery process, since the market makers would have no incentive to take early losses for better price discovery – competitive pricing is not necessarily informationally efﬁcient (there are quicker ways for the market to “learn” a new valuation). [sent-247, score-1.184]

93 3 With both zero-proﬁt and optimal MMs we reproduce one of the key ﬁndings of Das [3]: the market exhibits a two-regime behavior. [sent-248, score-0.446]

94 Price jumps are immediately followed by a regime of high spreads (the pricediscovery regime), and then when the market-maker learns the new valuation, the market settles into an equilibrium regime of lower spreads (the efﬁcient market regime). [sent-249, score-1.01]

95 Figure 4: Realized market properties based on simulating the three MMs. [sent-266, score-0.405]

96 When the state is a probability distribution, updated according to independent events, we expect the Gaussian approximation to closely match the real state evolution. [sent-268, score-0.138]

97 While this paper presents a stylized model, simple trading models have been shown to produce rich market behavior in many cases (for example, [5]). [sent-270, score-0.547]

98 The results presented here are an example of the kinds of insights that can be be gained from studying market properties in these models while approaching agent decision problems from the perspective of machine learning. [sent-271, score-0.405]

99 Insider trading, liquidity, and the role of the monopolist specialist. [sent-326, score-0.19]

100 Bid, ask and transaction prices in a specialist market with heterogeneously informed traders. [sent-335, score-0.783]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('market', 0.405), ('mm', 0.327), ('bid', 0.326), ('bt', 0.247), ('pt', 0.211), ('prices', 0.202), ('liquidity', 0.19), ('monopolist', 0.19), ('qt', 0.18), ('myopic', 0.166), ('ask', 0.149), ('trading', 0.142), ('profit', 0.122), ('trader', 0.122), ('pro', 0.122), ('markets', 0.12), ('shock', 0.119), ('spread', 0.109), ('instrument', 0.109), ('maker', 0.106), ('dv', 0.095), ('trade', 0.085), ('bellman', 0.083), ('monopolistic', 0.082), ('disadvantage', 0.076), ('price', 0.071), ('das', 0.068), ('nasdaq', 0.068), ('spreads', 0.068), ('traders', 0.068), ('valuation', 0.068), ('rt', 0.064), ('realized', 0.063), ('willing', 0.061), ('state', 0.058), ('asset', 0.054), ('ept', 0.054), ('glosten', 0.054), ('makers', 0.054), ('myp', 0.054), ('competitive', 0.053), ('xt', 0.051), ('periods', 0.048), ('zt', 0.048), ('belief', 0.045), ('wt', 0.043), ('gaussian', 0.043), ('losses', 0.042), ('sequential', 0.042), ('microstructure', 0.041), ('milgrom', 0.041), ('nyse', 0.041), ('pricing', 0.041), ('sell', 0.041), ('vpt', 0.041), ('stock', 0.041), ('optimal', 0.041), ('discounted', 0.04), ('world', 0.036), ('buy', 0.036), ('vf', 0.036), ('ts', 0.036), ('regime', 0.032), ('action', 0.032), ('beliefs', 0.028), ('amyp', 0.027), ('behaved', 0.027), ('bmyp', 0.027), ('bought', 0.027), ('darley', 0.027), ('phenomenological', 0.027), ('profits', 0.027), ('rensselaer', 0.027), ('sanmay', 0.027), ('specialist', 0.027), ('troy', 0.027), ('return', 0.027), ('dy', 0.026), ('rhs', 0.026), ('update', 0.026), ('arrives', 0.025), ('maximizes', 0.024), ('conveyed', 0.024), ('dealer', 0.024), ('polytechnic', 0.024), ('quotes', 0.024), ('thinks', 0.024), ('thin', 0.024), ('public', 0.023), ('competition', 0.022), ('shares', 0.022), ('approximation', 0.022), ('discount', 0.021), ('equation', 0.021), ('discovery', 0.021), ('value', 0.02), ('zero', 0.02), ('abstracts', 0.02), ('dynamic', 0.02), ('social', 0.02)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999946 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

Author: Sanmay Das, Malik Magdon-Ismail

2 0.12262097 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs

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

Abstract: Our setting is a Partially Observable Markov Decision Process with continuous state, observation and action spaces. Decisions are based on a Particle Filter for estimating the belief state given past observations. We consider a policy gradient approach for parameterized policy optimization. For that purpose, we investigate sensitivity analysis of the performance measure with respect to the parameters of the policy, focusing on Finite Difference (FD) techniques. We show that the naive FD is subject to variance explosion because of the non-smoothness of the resampling procedure. We propose a more sophisticated FD method which overcomes this problem and establish its consistency. 1

3 0.10614365 206 nips-2008-Sequential effects: Superstition or rational behavior?

Author: Angela J. Yu, Jonathan D. Cohen

Abstract: In a variety of behavioral tasks, subjects exhibit an automatic and apparently suboptimal sequential effect: they respond more rapidly and accurately to a stimulus if it reinforces a local pattern in stimulus history, such as a string of repetitions or alternations, compared to when it violates such a pattern. This is often the case even if the local trends arise by chance in the context of a randomized design, such that stimulus history has no real predictive power. In this work, we use a normative Bayesian framework to examine the hypothesis that such idiosyncrasies may reﬂect the inadvertent engagement of mechanisms critical for adapting to a changing environment. We show that prior belief in non-stationarity can induce experimentally observed sequential effects in an otherwise Bayes-optimal algorithm. The Bayesian algorithm is shown to be well approximated by linear-exponential ﬁltering of past observations, a feature also apparent in the behavioral data. We derive an explicit relationship between the parameters and computations of the exact Bayesian algorithm and those of the approximate linear-exponential ﬁlter. Since the latter is equivalent to a leaky-integration process, a commonly used model of neuronal dynamics underlying perceptual decision-making and trial-to-trial dependencies, our model provides a principled account of why such dynamics are useful. We also show that parameter-tuning of the leaky-integration process is possible, using stochastic gradient descent based only on the noisy binary inputs. This is a proof of concept that not only can neurons implement near-optimal prediction based on standard neuronal dynamics, but that they can also learn to tune the processing parameters without explicitly representing probabilities. 1

4 0.092825674 57 nips-2008-Deflation Methods for Sparse PCA

Author: Lester W. Mackey

Abstract: In analogy to the PCA setting, the sparse PCA problem is often solved by iteratively alternating between two subtasks: cardinality-constrained rank-one variance maximization and matrix deﬂation. While the former has received a great deal of attention in the literature, the latter is seldom analyzed and is typically borrowed without justiﬁcation from the PCA context. In this work, we demonstrate that the standard PCA deﬂation procedure is seldom appropriate for the sparse PCA setting. To rectify the situation, we ﬁrst develop several deﬂation alternatives better suited to the cardinality-constrained context. We then reformulate the sparse PCA optimization problem to explicitly reﬂect the maximum additional variance objective on each round. The result is a generalized deﬂation procedure that typically outperforms more standard techniques on real-world datasets. 1

5 0.06804245 195 nips-2008-Regularized Policy Iteration

Author: Amir M. Farahmand, Mohammad Ghavamzadeh, Shie Mannor, Csaba Szepesvári

Abstract: In this paper we consider approximate policy-iteration-based reinforcement learning algorithms. In order to implement a ﬂexible function approximation scheme we propose the use of non-parametric methods with regularization, providing a convenient way to control the complexity of the function approximator. We propose two novel regularized policy iteration algorithms by adding L2 -regularization to two widely-used policy evaluation methods: Bellman residual minimization (BRM) and least-squares temporal difference learning (LSTD). We derive efﬁcient implementation for our algorithms when the approximate value-functions belong to a reproducing kernel Hilbert space. We also provide ﬁnite-sample performance bounds for our algorithms and show that they are able to achieve optimal rates of convergence under the studied conditions. 1

6 0.0493237 154 nips-2008-Nonparametric Bayesian Learning of Switching Linear Dynamical Systems

7 0.048992328 19 nips-2008-An Empirical Analysis of Domain Adaptation Algorithms for Genomic Sequence Analysis

8 0.048133206 74 nips-2008-Estimating the Location and Orientation of Complex, Correlated Neural Activity using MEG

9 0.047880083 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms

10 0.046486739 241 nips-2008-Transfer Learning by Distribution Matching for Targeted Advertising

11 0.045830835 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs

12 0.04366336 244 nips-2008-Unifying the Sensory and Motor Components of Sensorimotor Adaptation

13 0.043302238 223 nips-2008-Structure Learning in Human Sequential Decision-Making

14 0.042522293 170 nips-2008-Online Optimization in X-Armed Bandits

15 0.04164717 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

16 0.040895686 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

17 0.039033983 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

18 0.036172278 97 nips-2008-Hierarchical Fisher Kernels for Longitudinal Data

19 0.035554525 196 nips-2008-Relative Margin Machines

20 0.035361003 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.105), (1, 0.096), (2, -0.023), (3, -0.021), (4, -0.02), (5, 0.091), (6, 0.016), (7, 0.089), (8, 0.07), (9, -0.037), (10, -0.006), (11, -0.058), (12, -0.011), (13, -0.036), (14, 0.039), (15, -0.006), (16, 0.001), (17, -0.049), (18, -0.019), (19, -0.033), (20, 0.025), (21, -0.05), (22, -0.081), (23, 0.022), (24, -0.015), (25, 0.05), (26, 0.026), (27, -0.012), (28, 0.017), (29, 0.064), (30, -0.064), (31, -0.002), (32, -0.012), (33, 0.001), (34, -0.022), (35, -0.032), (36, 0.047), (37, -0.051), (38, 0.013), (39, 0.066), (40, -0.044), (41, -0.109), (42, 0.081), (43, -0.033), (44, 0.045), (45, 0.08), (46, 0.003), (47, 0.082), (48, 0.086), (49, 0.031)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.92732704 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

Author: Sanmay Das, Malik Magdon-Ismail

2 0.66980129 206 nips-2008-Sequential effects: Superstition or rational behavior?

Author: Angela J. Yu, Jonathan D. Cohen

3 0.59607553 57 nips-2008-Deflation Methods for Sparse PCA

Author: Lester W. Mackey

4 0.55375195 154 nips-2008-Nonparametric Bayesian Learning of Switching Linear Dynamical Systems

Author: Alan S. Willsky, Erik B. Sudderth, Michael I. Jordan, Emily B. Fox

Abstract: Many nonlinear dynamical phenomena can be effectively modeled by a system that switches among a set of conditionally linear dynamical modes. We consider two such models: the switching linear dynamical system (SLDS) and the switching vector autoregressive (VAR) process. Our nonparametric Bayesian approach utilizes a hierarchical Dirichlet process prior to learn an unknown number of persistent, smooth dynamical modes. We develop a sampling algorithm that combines a truncated approximation to the Dirichlet process with efﬁcient joint sampling of the mode and state sequences. The utility and ﬂexibility of our model are demonstrated on synthetic data, sequences of dancing honey bees, and the IBOVESPA stock index.

5 0.55358785 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs

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

6 0.49615419 141 nips-2008-Multi-Agent Filtering with Infinitely Nested Beliefs

7 0.49462172 242 nips-2008-Translated Learning: Transfer Learning across Different Feature Spaces

8 0.39899167 195 nips-2008-Regularized Policy Iteration

9 0.3955321 19 nips-2008-An Empirical Analysis of Domain Adaptation Algorithms for Genomic Sequence Analysis

10 0.36277589 112 nips-2008-Kernel Measures of Independence for non-iid Data

11 0.36173049 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

12 0.35641131 187 nips-2008-Psychiatry: Insights into depression through normative decision-making models

13 0.351217 33 nips-2008-Bayesian Model of Behaviour in Economic Games

14 0.34246671 25 nips-2008-An interior-point stochastic approximation method and an L1-regularized delta rule

15 0.33598226 186 nips-2008-Probabilistic detection of short events, with application to critical care monitoring

16 0.32708085 211 nips-2008-Simple Local Models for Complex Dynamical Systems

17 0.32488245 241 nips-2008-Transfer Learning by Distribution Matching for Targeted Advertising

18 0.3242338 7 nips-2008-A computational model of hippocampal function in trace conditioning

19 0.31535909 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms

20 0.31199738 70 nips-2008-Efficient Inference in Phylogenetic InDel Trees

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.046), (7, 0.038), (12, 0.032), (15, 0.012), (21, 0.44), (28, 0.152), (57, 0.035), (59, 0.022), (63, 0.026), (71, 0.024), (77, 0.035), (83, 0.027), (84, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.75309205 13 nips-2008-Adapting to a Market Shock: Optimal Sequential Market-Making

Author: Sanmay Das, Malik Magdon-Ismail

2 0.74396688 46 nips-2008-Characterizing response behavior in multisensory perception with conflicting cues

Author: Rama Natarajan, Iain Murray, Ladan Shams, Richard S. Zemel

Abstract: We explore a recently proposed mixture model approach to understanding interactions between conﬂicting sensory cues. Alternative model formulations, differing in their sensory noise models and inference methods, are compared based on their ﬁt to experimental data. Heavy-tailed sensory likelihoods yield a better description of the subjects’ response behavior than standard Gaussian noise models. We study the underlying cause for this result, and then present several testable predictions of these models. 1

3 0.62267214 153 nips-2008-Nonlinear causal discovery with additive noise models

Author: Patrik O. Hoyer, Dominik Janzing, Joris M. Mooij, Jan R. Peters, Bernhard Schölkopf

Abstract: The discovery of causal relationships between a set of observed variables is a fundamental problem in science. For continuous-valued data linear acyclic causal models with additive noise are often used because these models are well understood and there are well-known methods to ﬁt them to data. In reality, of course, many causal relationships are more or less nonlinear, raising some doubts as to the applicability and usefulness of purely linear methods. In this contribution we show that the basic linear framework can be generalized to nonlinear models. In this extended framework, nonlinearities in the data-generating process are in fact a blessing rather than a curse, as they typically provide information on the underlying causal system and allow more aspects of the true data-generating mechanisms to be identiﬁed. In addition to theoretical results we show simulations and some simple real data experiments illustrating the identiﬁcation power provided by nonlinearities. 1

4 0.56453258 134 nips-2008-Mixed Membership Stochastic Blockmodels

Author: Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing

Abstract: In many settings, such as protein interactions and gene regulatory networks, collections of author-recipient email, and social networks, the data consist of pairwise measurements, e.g., presence or absence of links between pairs of objects. Analyzing such data with probabilistic models requires non-standard assumptions, since the usual independence or exchangeability assumptions no longer hold. In this paper, we introduce a class of latent variable models for pairwise measurements: mixed membership stochastic blockmodels. Models in this class combine a global model of dense patches of connectivity (blockmodel) with a local model to instantiate node-speciﬁc variability in the connections (mixed membership). We develop a general variational inference algorithm for fast approximate posterior inference. We demonstrate the advantages of mixed membership stochastic blockmodel with applications to social networks and protein interaction networks. 1

5 0.4334259 48 nips-2008-Clustering via LP-based Stabilities

Author: Nikos Komodakis, Nikos Paragios, Georgios Tziritas

Abstract: A novel center-based clustering algorithm is proposed in this paper. We ﬁrst formulate clustering as an NP-hard linear integer program and we then use linear programming and the duality theory to derive the solution of this optimization problem. This leads to an efﬁcient and very general algorithm, which works in the dual domain, and can cluster data based on an arbitrary set of distances. Despite its generality, it is independent of initialization (unlike EM-like methods such as K-means), has guaranteed convergence, can automatically determine the number of clusters, and can also provide online optimality bounds about the quality of the estimated clustering solutions. To deal with the most critical issue in a centerbased clustering algorithm (selection of cluster centers), we also introduce the notion of stability of a cluster center, which is a well deﬁned LP-based quantity that plays a key role to our algorithm’s success. Furthermore, we also introduce, what we call, the margins (another key ingredient in our algorithm), which can be roughly thought of as dual counterparts to stabilities and allow us to obtain computationally efﬁcient approximations to the latter. Promising experimental results demonstrate the potentials of our method.

6 0.41485694 86 nips-2008-Finding Latent Causes in Causal Networks: an Efficient Approach Based on Markov Blankets

7 0.38983926 108 nips-2008-Integrating Locally Learned Causal Structures with Overlapping Variables

8 0.38382766 217 nips-2008-Sparsity of SVMs that use the epsilon-insensitive loss

9 0.37191734 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions

10 0.37187427 195 nips-2008-Regularized Policy Iteration

11 0.37048408 135 nips-2008-Model Selection in Gaussian Graphical Models: High-Dimensional Consistency of \boldmath$\ell 1$-regularized MLE

12 0.36881205 231 nips-2008-Temporal Dynamics of Cognitive Control

13 0.36877272 50 nips-2008-Continuously-adaptive discretization for message-passing algorithms

14 0.36800265 40 nips-2008-Bounds on marginal probability distributions

15 0.36710134 162 nips-2008-On the Design of Loss Functions for Classification: theory, robustness to outliers, and SavageBoost

16 0.36686644 49 nips-2008-Clusters and Coarse Partitions in LP Relaxations

17 0.3659482 84 nips-2008-Fast Prediction on a Tree

18 0.36578882 107 nips-2008-Influence of graph construction on graph-based clustering measures

19 0.3656942 101 nips-2008-Human Active Learning

20 0.36563766 196 nips-2008-Relative Margin Machines