nips nips2013 nips2013-26 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jacob Abernethy, Satyen Kale
Abstract: We consider the design of strategies for market making in an exchange. A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data. 1
Reference: text
sentIndex sentText sentNum sentScore
1 com Abstract We consider the design of strategies for market making in an exchange. [sent-6, score-0.589]
2 A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. [sent-7, score-1.866]
3 Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. [sent-8, score-1.302]
4 We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. [sent-9, score-0.589]
5 We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. [sent-10, score-0.359]
6 We run a set of experiments showing favorable performance on recent real-world stock price data. [sent-11, score-0.418]
7 1 Introduction When a trader enters a market, say a stock or commodity market, with the desire to buy or sell a certain quantity of an asset, how is this trader guaranteed to find a counterparty to agree to transact at a reasonable price? [sent-12, score-0.71]
8 This is not a problem in a liquid market, with a deep pool of traders ready to buy or sell at any time, but in a thin market the lack of counterparties can be troublesome. [sent-13, score-0.735]
9 A rushed trader may even be willing to transact at a worse price in exchange for immediate execution. [sent-14, score-0.591]
10 This is where a market maker (MM) can be quite useful. [sent-15, score-0.499]
11 A MM is any agent that participates in a market by offering to both buy and sell the underlying asset at any time. [sent-16, score-0.693]
12 The act of market making has both potential benefits and risks. [sent-18, score-0.482]
13 For one, the MM bears the risk of transacting with better-informed traders that may know much more about the movement of the asset’s price, and in such scenarios the MM can take on a large inventory of shares that it may have to offload at a worse price. [sent-19, score-0.416]
14 On the positive side, the MM can profit as a result of the bid-ask spread, the difference between the MM’s buy price and sell price. [sent-20, score-0.518]
15 In other words, if the MM buys 100 shares of a stock from one trader at a price of p, and then immediately sells 100 shares of stock to another trader at a price of p + , the MM records a profit of 100 . [sent-21, score-1.598]
16 This describes the central goal of a profitable market making strategy: minimize the inventory risk of large movements in the price while simultaneously aiming to benefit from the bid-ask spread. [sent-22, score-0.938]
17 The MM strategy has a state, which is the current inventory or holdings, receives as input order and price data, and must decide what quantities and at what prices to offer in the market. [sent-23, score-0.612]
18 In the present paper we assume that the MM interacts with a continuous double auction via an order book, and the MM can place both market and limit orders to the order book. [sent-24, score-0.551]
19 , one needs to assume that the underlying price process exhibits a mean reverting behavior to guarantee profit. [sent-29, score-0.329]
20 We begin by proposing a class of market making strategies, parameterized by the choice of bid-ask spread and liquidity, and we establish a data-dependent expression for the profit and loss of each strategy at the end of a sequence of price fluctuations. [sent-31, score-0.951]
21 In particular, we assume the MM is given an exogenously-specified price time series that is revealed online. [sent-33, score-0.329]
22 We also assume that the MM is able to make and cancel orders after every price fluctuation. [sent-34, score-0.394]
23 Using these structural properties we prove the following main result of this paper: Theorem 1 There is an online learning algorithm, that, under a bounded price volatility assumption p (see Defintion 1) has O( T ) regret after T trading periods to the best spread-based strategy. [sent-42, score-0.625]
24 Experimental simulations of our online learning algorithms with real-world price data suggest that this approach is quite promising; our algorithm frequently performs nearly as well as the best strategy, and is often superior. [sent-43, score-0.329]
25 Related Work Perhaps the most popular model to study market making has been the GlostenMilgrom model [11]. [sent-45, score-0.482]
26 In this setting the market is facilitated by a specialist, a monopolistic market maker that acts as the middle man for all trades. [sent-46, score-0.948]
27 The key technique was a method to design an automated market maker, and there has been much work on facilitating this using mechanisms based on shares (i. [sent-51, score-0.643]
28 The key difference between the present paper and the work on designing prediction markets is that our techniques are solely focused on profit and risk, and not on other issues like price discovery or information aggregation. [sent-55, score-0.379]
29 Recent work by Della Penna and Reid [19] considered market making as a the multi-armed bandit problem, and this is a notable exception where profit was the focus. [sent-56, score-0.482]
30 This “non-stochastic” approach we take to the market making problem echos many of the ideas of Cover’s results on Universal Portfolio algorithms [20], an area that has received much followup work [16, 15, 14, 3, 7] given its robustness to adversarially-chosen price fluctuations. [sent-57, score-0.811]
31 2 The Market Execution Framework We now present our market model formally. [sent-60, score-0.449]
32 We assume that all events in the market take place at discrete points in time throughout this day. [sent-62, score-0.449]
33 At each time period t a 2 market price pt is announced to the world. [sent-63, score-1.175]
34 In a typical stock exchange this price will be rounded to a discrete value; historically stock prices were quoted in 1 ’s of a dollar, although now they are quoted 8 in pennies. [sent-64, score-0.746]
35 For simplicity we assume there are two types of trades that can be executed, and each will change the cash and holdings at the following time period. [sent-74, score-0.337]
36 Then the trading strategy can execute any subset of the following two actions: • Market Order: At time t the posted price is pt and the trader executes a trade of X shares, with X 2 R. [sent-76, score-1.106]
37 In this case we update the cash as Ct+1 Ct+1 pt X and Ht+1 Ht+1 + X. [sent-77, score-0.499]
38 Note that if X < 0 then this is a short sale in which case the trader’s cash increases1 • Limit Order: Before time period t, the trader submits a demand schedule Lt : ⇧ ! [sent-78, score-0.5]
39 For every price p 2 ⇧ with p < pt 1 , the value Lt (p) is the number of shares the trader would like to buy at a price of p. [sent-80, score-1.454]
40 For every p > pt 1 the value Lt (p) is the number of shares the trader would like to sell at a price of p. [sent-81, score-1.138]
41 One should interpret a limit order in terms of “posting shares to the order book”: these shares are up for sale (and/or purchase) but the order will only be executed if the price moves. [sent-82, score-0.821]
42 In round t the posted price becomes pt and it is assumed that all shares offered at any price between pt 1 and pt are transacted. [sent-83, score-1.936]
43 More specifically, we have two cases: – If pt > pt 1 then for each p 2 ⇧ with pt 1 < p pt we update Ct+1 Ct+1 + pLt (p) and Ht+1 Ht+1 Lt (p); – Else if pt < pt 1 then for each p 2 ⇧ with pt p < pt 1 we update Ct+1 Ct+1 pLt (p) and Ht+1 Ht+1 + Lt (p). [sent-84, score-2.616]
44 It is worth noting market orders are quite different from limit orders. [sent-85, score-0.551]
45 A limit order is a passive action in the market, the trader simply states that he would be willing to trade a number of shares at a range of different prices. [sent-86, score-0.464]
46 But if the market does not move then no transactions occur. [sent-87, score-0.449]
47 The market order is a much more direct action to take, the transaction is guaranteed to execute at the current market price. [sent-88, score-0.965]
48 The market order has the downside that the trader does not get to specify the price at which he would like to trade, contrary to the limit order. [sent-89, score-1.002]
49 Roughly speaking, an MM strategy will generally interact with the market via limit orders, since the MM is simply hoping to profit from liquidity provision. [sent-90, score-0.649]
50 But the MM may at times have to place market orders to balance inventory to control risk. [sent-91, score-0.62]
51 We include one more piece of notation, the value of the strategy’s portfolio Vt+1 at the end of time period t, which can be defined explicitly in terms of the cash, holdings, and current market price: Vt+1 := Ct+1 + pt Ht+1 . [sent-92, score-0.897]
52 In other words, Vt+1 is the amount of cash the strategy would have if it liquidated all holdings at the current market price. [sent-93, score-0.835]
53 (1) The trader pays neither transaction fees nor borrowing costs when his cash balance is negative. [sent-96, score-0.397]
54 (2) Market orders are executed at exactly the posted market price, without “slippage” of any kind. [sent-97, score-0.574]
55 This suggests that the market is very liquid relative to the actions of the MM. [sent-98, score-0.474]
56 (3) The market allows the buying and selling of fractional shares. [sent-99, score-0.512]
57 But for the purpose of accounting it is perfectly reasonably to record cash in this way, assuming that the strategy ends up holdings at 0. [sent-101, score-0.386]
58 3 (4) The price sequence is “exogenously” determined, meaning that the trades we make do not affect the current and future prices. [sent-102, score-0.38]
59 We leave it for future work to consider the setting with a non-exogenous price process. [sent-104, score-0.329]
60 That is, for any p not lying between pt 1 to pt it is assumed that the Lt (p) untransacted shares at price p are removed from the order book. [sent-106, score-1.177]
61 3 Spread-based Strategies In this section we present a class of simple market making strategies which we refer to as spreadbased strategies since they maintain a fixed bid-ask spread throughout. [sent-108, score-0.736]
62 We consider market making strategies parameterized by a window size b 2 { , 2 , . [sent-113, score-0.663]
63 For some fixed liquidity density parameter ↵, it submits a buy order of ↵ shares at every price p 2 ⇧ such that p < at and a sell order ↵ shares at every price p 2 ⇧ such that p > at + b. [sent-119, score-1.327]
64 Depending on the price in the trading period pt , the strategy adjusts the next window by the smallest amount necessary to include pt . [sent-120, score-1.3]
65 Algorithm 1 Spread-Based Strategy S(b) 1: Receive parameters b > 0, liquidity density ↵ > 0, inital price p1 as input. [sent-121, score-0.392]
66 , T do 3: Observe market price pt 4: If pt < at then at+1 pt 5: Else If pt > at + b then at+1 pt b 6: Else at+1 at 7: Submit limit order Lt+1 : Lt+1 (p) = 0 if p 2 [at+1 , at+1 + b], else Lt+1 (p) = ↵. [sent-126, score-2.473]
67 8: end for The intuition behind a spread-based strategy is that the MM waits for the price to deviate in such a way that it leaves the window [at , at + b]. [sent-127, score-0.503]
68 Let’s say the price suddenly drops below at and we get pt = at k for some positive integer k such that k < b. [sent-128, score-0.656]
69 On the following round the MM updates his limit order Lt+1 to offer to sell ↵ shares at each of the price levels at + b (k 1) , at + b (k 2) , . [sent-134, score-0.729]
70 This gives a natural matching between shares that were bought and shares that are offered for sale, with the sale price being exactly b higher than the purchased price. [sent-138, score-0.815]
71 If, at a later time t0 > t, the price rises so that pt0 at + b + then all shares bought previously are sold at a profit of kb↵. [sent-139, score-0.58]
72 We now give a very useful lemma, that essentially shows that we can calculate the profit and loss of a spread-based strategy on two factors: (a) how much the spread window moves throughout the trading period, and (b) how far away the final price is from the initial price. [sent-140, score-0.616]
73 The main idea is given in the intuitive explanation above: we can match pairs of shares that are bought 4 and sold at prices that are b apart, thus registering a profit of b for each such pair. [sent-145, score-0.328]
74 Since for every unit price change, the strategies trade ↵/ shares, in the rest of the paper, without loss of generality, we may assume that ↵ = 1 and = 1 (by appropriately changing the unit of currency). [sent-151, score-0.462]
75 P ROOF :[Sketch] This is easy to prove by induction on t, via a simple case analysis on where pt lies in relation to the windows [a0 , a0 + b0 ] and [at , at + b]. [sent-159, score-0.327]
76 P ROOF :[Sketch] Again using case analysis on where pt lies in relation to the window [at , at + b], we can show that Ht + at is an invariant. [sent-161, score-0.401]
77 2 Definition 1 ( -bounded volatility) A price sequence p1 , p2 , . [sent-166, score-0.329]
78 , pT is said to have volatility if for all t 2, we have |pt pt 1 | . [sent-169, score-0.369]
79 -bounded We assume from now that the price sequence has -bounded volatility. [sent-170, score-0.329]
80 For every b 2 B, at the end of time period t, let its inventory be Ht+1 (b), cash value be Ct+1 (b), and total value be Vt+1 (b). [sent-173, score-0.348]
81 Then for any strategy S(b), we have |(Vt+1 (b) Vt (b)) (H(pt pt 1 ))| G. [sent-178, score-0.427]
82 P ROOF :[Sketch] Since |pt pt 1 | , each strategy trades at most shares, at prices between pt 1 and pt . [sent-180, score-1.209]
83 Treat every strategy S(b) as an expert and run a regret minimizing algorithm for learning with expert advice (such as Multiplicative Weights [18] or FollowThe-Perturbed-Leader [17]). [sent-186, score-0.372]
84 In each round, the meta-algorithm restores the inventory of each strategy to the correct state by additionally buying or selling enough shares so that its inventory is exactly what it would have been had it run the different strategies with their present weights throughout. [sent-188, score-0.676]
85 Algorithm 2 Low regret meta-algorithm 1: Run every strategy S(b) in parallel so that at the end of each time period t, all trades made by the strategies and the vectors Ht+1 , Ct+1 and Vt+1 2 RN can be computed. [sent-190, score-0.48]
86 , T do 4: Execute any market orders from the previous period at the current market price pt so that the inventory now equals Ht · wt . [sent-196, score-1.976]
87 5: Execute any limit orders from the previous period: a wt weighted combination of the limit orders of the strategies S(b). [sent-198, score-0.492]
88 The holdings change to Ht+1 · wt , and the cash value changes by (Ct+1 Ct ) · wt . [sent-199, score-0.648]
89 8: Place a market order to buy Ht+1 ·(wt+1 wt ) shares in the next period, and a wt+1 weighted combination of the limit orders of the strategies S(b). [sent-202, score-1.121]
90 9: end for We now prove the following bound on the regret of the algorithm based on the regret of the underlying algorithm A. [sent-203, score-0.304]
91 Theorem 2 Assume that the price sequence has algorithm is bounded by -bounded volatity. [sent-205, score-0.358]
92 PT P ROOF : The regret bound for A implies that t=1 (Vt+1 Vt ) · wt maxb2B VT (b) Regret(A). [sent-207, score-0.333]
93 2 t=1 kwt 2 Lemma 5 In round t, the change in total value of the meta-algorithm equals (Vt+1 Furthermore, |Ht · (wt wt Vt ) · wt + Ht · (wt 1 )(pt 1 pt )| G 2 kwt wt 1 )(pt 1 pt ). [sent-210, score-1.467]
94 The second bound is obtained by noting that all the Ht (b)’s are within B of each other by Corollary 1, and thus |Ht · (wt wt 1 )| Bkwt wt 1 k1 , and |pt 1 pt | by the bounded volatility assumption. [sent-213, score-0.76]
95 1 A low regret algorithm based on Mutiplicative Weights Now we give a low regret algorithm based on the classic Multiplicative Weights (MW) algorithm [18]. [sent-215, score-0.304]
96 The multiplicative update rule, wt+1 (b) = wt (b) exp(⌘t (Vt+1 (b) Vt (b)))/Zt , and the fact that by Lemma 4, the range of the entries of Vt+1 Vt is bounded by 2G implies that kwt+1 wt k1 4⌘t G. [sent-229, score-0.416]
97 Standard analysis for the regret of the MW algorithm then gives the stated regret bound for MMMW. [sent-230, score-0.304]
98 2 5 Experiments We conducted experiments with stock price data obtained from http://www. [sent-246, score-0.418]
99 Bid, ask and transaction prices in a specialist market with heterogeneously informed traders. [sent-413, score-0.621]
100 Logarithmic market scoring rules for modular combinatorial information aggregation. [sent-421, score-0.449]
wordName wordTfidf (topN-words)
[('market', 0.449), ('price', 0.329), ('pt', 0.327), ('ht', 0.209), ('shares', 0.194), ('mm', 0.19), ('trader', 0.187), ('wt', 0.181), ('vt', 0.179), ('cash', 0.172), ('regret', 0.152), ('mmmw', 0.144), ('mmfpl', 0.115), ('holdings', 0.114), ('strategies', 0.107), ('inventory', 0.106), ('roof', 0.105), ('sell', 0.101), ('kwt', 0.101), ('strategy', 0.1), ('ct', 0.093), ('pro', 0.09), ('stock', 0.089), ('hpq', 0.089), ('buy', 0.088), ('lt', 0.088), ('prices', 0.077), ('msft', 0.076), ('window', 0.074), ('trading', 0.073), ('traders', 0.072), ('wmt', 0.072), ('period', 0.07), ('round', 0.068), ('orders', 0.065), ('liquidity', 0.063), ('quoted', 0.057), ('specialist', 0.057), ('asset', 0.055), ('portfolio', 0.051), ('trades', 0.051), ('markets', 0.05), ('maker', 0.05), ('sketch', 0.044), ('sale', 0.042), ('volatility', 0.042), ('expert', 0.042), ('spread', 0.04), ('transaction', 0.038), ('fpl', 0.038), ('limit', 0.037), ('advice', 0.036), ('bought', 0.035), ('posted', 0.035), ('kalai', 0.034), ('book', 0.033), ('commerce', 0.033), ('selling', 0.033), ('lemma', 0.033), ('making', 0.033), ('universal', 0.03), ('days', 0.03), ('buying', 0.03), ('stocks', 0.03), ('execute', 0.029), ('bounded', 0.029), ('cents', 0.029), ('counterparty', 0.029), ('exogenously', 0.029), ('glosten', 0.029), ('penna', 0.029), ('plt', 0.029), ('submits', 0.029), ('transact', 0.029), ('finance', 0.028), ('money', 0.027), ('exchange', 0.026), ('trade', 0.026), ('multiplicative', 0.025), ('ftl', 0.025), ('cent', 0.025), ('liquid', 0.025), ('portfolios', 0.025), ('executed', 0.025), ('chakraborty', 0.023), ('della', 0.023), ('mw', 0.023), ('wortman', 0.023), ('movement', 0.023), ('else', 0.023), ('rounded', 0.022), ('investor', 0.022), ('sold', 0.022), ('risk', 0.021), ('purchased', 0.021), ('willing', 0.02), ('electronic', 0.019), ('kale', 0.019), ('purchase', 0.019), ('payoff', 0.019)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999928 26 nips-2013-Adaptive Market Making via Online Learning
Author: Jacob Abernethy, Satyen Kale
Abstract: We consider the design of strategies for market making in an exchange. A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data. 1
2 0.24361813 139 nips-2013-How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal
Author: Jacob Abernethy, Peter Bartlett, Rafael Frongillo, Andre Wibisono
Abstract: We consider a popular problem in finance, option pricing, through the lens of an online learning game between Nature and an Investor. In the Black-Scholes option pricing model from 1973, the Investor can continuously hedge the risk of an option by trading the underlying asset, assuming that the asset’s price fluctuates according to Geometric Brownian Motion (GBM). We consider a worst-case model, in which Nature chooses a sequence of price fluctuations under a cumulative quadratic volatility constraint, and the Investor can make a sequence of hedging decisions. Our main result is to show that the value of our proposed game, which is the “regret” of hedging strategy, converges to the Black-Scholes option price. We use significantly weaker assumptions than previous work—for instance, we allow large jumps in the asset price—and show that the Black-Scholes hedging strategy is near-optimal for the Investor even in this non-stochastic framework. 1
3 0.18034297 89 nips-2013-Dimension-Free Exponentiated Gradient
Author: Francesco Orabona
Abstract: I present a new online learning algorithm that extends the exponentiated gradient framework to infinite dimensional spaces. My analysis shows that the algorithm is implicitly able to estimate the L2 norm of the unknown competitor, U , achieving √ a regret bound of the order of O(U log(U T + 1)) T ), instead of the standard √ O((U 2 + 1) T ), achievable without knowing U . For this analysis, I introduce novel tools for algorithms with time-varying regularizers, through the use of local smoothness. Through a lower bound, I also show that the algorithm is optimal up to log(U T ) term for linear and Lipschitz losses. 1
4 0.17945343 2 nips-2013-(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
Author: Abhradeep Guha Thakurta, Adam Smith
Abstract: We give differentially private algorithms for a large class of online learning algorithms, in both the full information and bandit settings. Our algorithms aim to minimize a convex loss function which is a sum of smaller convex loss terms, one for each data point. To design our algorithms, we modify the popular mirror descent approach, or rather a variant called follow the approximate leader. The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work (due to Dwork, Naor, Pitassi and Rothblum (2010) and Jain, Kothari and Thakurta (2012)). In many cases, our algorithms (in both settings) match the dependence on the input length, T , of the optimal nonprivate regret bounds up to logarithmic factors in T . Our algorithms require logarithmic space and update time. 1
5 0.17387985 325 nips-2013-The Pareto Regret Frontier
Author: Wouter M. Koolen
Abstract: Performance guarantees for online learning algorithms typically take the form of regret bounds, which express that the cumulative loss overhead compared to the best expert in hindsight is small. In the common case of large but structured expert sets we typically wish to keep the regret especially small compared to simple experts, at the cost of modest additional overhead compared to more complex others. We study which such regret trade-offs can be achieved, and how. We analyse regret w.r.t. each individual expert as a multi-objective criterion in the simple but fundamental case of absolute loss. We characterise the achievable and Pareto optimal trade-offs, and the corresponding optimal strategies for each sample size both exactly for each finite horizon and asymptotically. 1
6 0.17329165 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives
8 0.14264834 230 nips-2013-Online Learning with Costly Features and Labels
9 0.13414349 175 nips-2013-Linear Convergence with Condition Number Independent Access of Full Gradients
10 0.12548412 191 nips-2013-Minimax Optimal Algorithms for Unconstrained Linear Optimization
11 0.12471783 159 nips-2013-Learning Prices for Repeated Auctions with Strategic Buyers
12 0.12219607 253 nips-2013-Prior-free and prior-dependent regret bounds for Thompson Sampling
13 0.096626475 231 nips-2013-Online Learning with Switching Costs and Other Adaptive Adversaries
14 0.086853951 125 nips-2013-From Bandits to Experts: A Tale of Domination and Independence
15 0.086042553 280 nips-2013-Robust Data-Driven Dynamic Programming
16 0.085913636 273 nips-2013-Reinforcement Learning in Robust Markov Decision Processes
17 0.085055426 106 nips-2013-Eluder Dimension and the Sample Complexity of Optimistic Exploration
18 0.080485448 299 nips-2013-Solving inverse problem of Markov chain with partial observations
19 0.066977136 137 nips-2013-High-Dimensional Gaussian Process Bandits
20 0.062497135 7 nips-2013-A Gang of Bandits
topicId topicWeight
[(0, 0.138), (1, -0.113), (2, 0.182), (3, -0.171), (4, 0.008), (5, -0.068), (6, -0.014), (7, 0.046), (8, 0.097), (9, 0.052), (10, -0.02), (11, -0.017), (12, 0.061), (13, -0.058), (14, 0.026), (15, 0.036), (16, 0.024), (17, -0.078), (18, -0.054), (19, -0.023), (20, -0.084), (21, -0.045), (22, -0.109), (23, 0.0), (24, 0.05), (25, 0.031), (26, -0.099), (27, -0.033), (28, -0.066), (29, -0.055), (30, 0.044), (31, 0.037), (32, 0.015), (33, -0.027), (34, -0.131), (35, 0.003), (36, 0.101), (37, -0.051), (38, -0.044), (39, 0.005), (40, -0.074), (41, 0.083), (42, -0.059), (43, -0.1), (44, -0.108), (45, 0.2), (46, 0.084), (47, -0.077), (48, 0.149), (49, 0.13)]
simIndex simValue paperId paperTitle
same-paper 1 0.97604686 26 nips-2013-Adaptive Market Making via Online Learning
Author: Jacob Abernethy, Satyen Kale
Abstract: We consider the design of strategies for market making in an exchange. A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data. 1
2 0.80707127 159 nips-2013-Learning Prices for Repeated Auctions with Strategic Buyers
Author: Kareem Amin, Afshin Rostamizadeh, Umar Syed
Abstract: Inspired by real-time ad exchanges for online display advertising, we consider the problem of inferring a buyer’s value distribution for a good when the buyer is repeatedly interacting with a seller through a posted-price mechanism. We model the buyer as a strategic agent, whose goal is to maximize her long-term surplus, and we are interested in mechanisms that maximize the seller’s long-term revenue. We define the natural notion of strategic regret — the lost revenue as measured against a truthful (non-strategic) buyer. We present seller algorithms that are no(strategic)-regret when the buyer discounts her future surplus — i.e. the buyer prefers showing advertisements to users sooner rather than later. We also give a lower bound on strategic regret that increases as the buyer’s discounting weakens and shows, in particular, that any seller algorithm will suffer linear strategic regret if there is no discounting. 1
3 0.76223916 139 nips-2013-How to Hedge an Option Against an Adversary: Black-Scholes Pricing is Minimax Optimal
Author: Jacob Abernethy, Peter Bartlett, Rafael Frongillo, Andre Wibisono
Abstract: We consider a popular problem in finance, option pricing, through the lens of an online learning game between Nature and an Investor. In the Black-Scholes option pricing model from 1973, the Investor can continuously hedge the risk of an option by trading the underlying asset, assuming that the asset’s price fluctuates according to Geometric Brownian Motion (GBM). We consider a worst-case model, in which Nature chooses a sequence of price fluctuations under a cumulative quadratic volatility constraint, and the Investor can make a sequence of hedging decisions. Our main result is to show that the value of our proposed game, which is the “regret” of hedging strategy, converges to the Black-Scholes option price. We use significantly weaker assumptions than previous work—for instance, we allow large jumps in the asset price—and show that the Black-Scholes hedging strategy is near-optimal for the Investor even in this non-stochastic framework. 1
4 0.57716471 325 nips-2013-The Pareto Regret Frontier
Author: Wouter M. Koolen
Abstract: Performance guarantees for online learning algorithms typically take the form of regret bounds, which express that the cumulative loss overhead compared to the best expert in hindsight is small. In the common case of large but structured expert sets we typically wish to keep the regret especially small compared to simple experts, at the cost of modest additional overhead compared to more complex others. We study which such regret trade-offs can be achieved, and how. We analyse regret w.r.t. each individual expert as a multi-objective criterion in the simple but fundamental case of absolute loss. We characterise the achievable and Pareto optimal trade-offs, and the corresponding optimal strategies for each sample size both exactly for each finite horizon and asymptotically. 1
5 0.50530016 2 nips-2013-(Nearly) Optimal Algorithms for Private Online Learning in Full-information and Bandit Settings
Author: Abhradeep Guha Thakurta, Adam Smith
Abstract: We give differentially private algorithms for a large class of online learning algorithms, in both the full information and bandit settings. Our algorithms aim to minimize a convex loss function which is a sum of smaller convex loss terms, one for each data point. To design our algorithms, we modify the popular mirror descent approach, or rather a variant called follow the approximate leader. The technique leads to the first nonprivate algorithms for private online learning in the bandit setting. In the full information setting, our algorithms improve over the regret bounds of previous work (due to Dwork, Naor, Pitassi and Rothblum (2010) and Jain, Kothari and Thakurta (2012)). In many cases, our algorithms (in both settings) match the dependence on the input length, T , of the optimal nonprivate regret bounds up to logarithmic factors in T . Our algorithms require logarithmic space and update time. 1
6 0.49384278 311 nips-2013-Stochastic Convex Optimization with Multiple Objectives
7 0.48652264 230 nips-2013-Online Learning with Costly Features and Labels
8 0.48334989 280 nips-2013-Robust Data-Driven Dynamic Programming
9 0.44768861 112 nips-2013-Estimation Bias in Multi-Armed Bandit Algorithms for Search Advertising
10 0.43327919 191 nips-2013-Minimax Optimal Algorithms for Unconstrained Linear Optimization
11 0.41152626 175 nips-2013-Linear Convergence with Condition Number Independent Access of Full Gradients
12 0.39218092 227 nips-2013-Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions
13 0.38070613 125 nips-2013-From Bandits to Experts: A Tale of Domination and Independence
14 0.38043416 89 nips-2013-Dimension-Free Exponentiated Gradient
15 0.37530446 235 nips-2013-Online learning in episodic Markovian decision processes by relative entropy policy search
16 0.34726626 270 nips-2013-Regret based Robust Solutions for Uncertain Markov Decision Processes
17 0.34582794 273 nips-2013-Reinforcement Learning in Robust Markov Decision Processes
18 0.33754411 231 nips-2013-Online Learning with Switching Costs and Other Adaptive Adversaries
19 0.3152037 253 nips-2013-Prior-free and prior-dependent regret bounds for Thompson Sampling
20 0.30048349 137 nips-2013-High-Dimensional Gaussian Process Bandits
topicId topicWeight
[(2, 0.023), (16, 0.046), (33, 0.125), (34, 0.04), (41, 0.011), (49, 0.021), (56, 0.072), (70, 0.021), (85, 0.074), (89, 0.041), (91, 0.373), (93, 0.039), (95, 0.017)]
simIndex simValue paperId paperTitle
same-paper 1 0.76081932 26 nips-2013-Adaptive Market Making via Online Learning
Author: Jacob Abernethy, Satyen Kale
Abstract: We consider the design of strategies for market making in an exchange. A market maker generally seeks to profit from the difference between the buy and sell price of an asset, yet the market maker also takes exposure risk in the event of large price movements. Profit guarantees for market making strategies have typically required certain stochastic assumptions on the price fluctuations of the asset in question; for example, assuming a model in which the price process is mean reverting. We propose a class of “spread-based” market making strategies whose performance can be controlled even under worst-case (adversarial) settings. We prove structural properties of these strategies which allows us to design a master algorithm which obtains low regret relative to the best such strategy in hindsight. We run a set of experiments showing favorable performance on recent real-world stock price data. 1
2 0.62021452 196 nips-2013-Modeling Overlapping Communities with Node Popularities
Author: Prem Gopalan, Chong Wang, David Blei
Abstract: We develop a probabilistic approach for accurate network modeling using node popularities within the framework of the mixed-membership stochastic blockmodel (MMSB). Our model integrates two basic properties of nodes in social networks: homophily and preferential connection to popular nodes. We develop a scalable algorithm for posterior inference, based on a novel nonconjugate variant of stochastic variational inference. We evaluate the link prediction accuracy of our algorithm on nine real-world networks with up to 60,000 nodes, and on simulated networks with degree distributions that follow a power law. We demonstrate that the AMP predicts significantly better than the MMSB. 1
3 0.6152876 25 nips-2013-Adaptive Anonymity via $b$-Matching
Author: Krzysztof M. Choromanski, Tony Jebara, Kui Tang
Abstract: The adaptive anonymity problem is formalized where each individual shares their data along with an integer value to indicate their personal level of desired privacy. This problem leads to a generalization of k-anonymity to the b-matching setting. Novel algorithms and theory are provided to implement this type of anonymity. The relaxation achieves better utility, admits theoretical privacy guarantees that are as strong, and, most importantly, accommodates a variable level of anonymity for each individual. Empirical results confirm improved utility on benchmark and social data-sets.
4 0.4465647 159 nips-2013-Learning Prices for Repeated Auctions with Strategic Buyers
Author: Kareem Amin, Afshin Rostamizadeh, Umar Syed
Abstract: Inspired by real-time ad exchanges for online display advertising, we consider the problem of inferring a buyer’s value distribution for a good when the buyer is repeatedly interacting with a seller through a posted-price mechanism. We model the buyer as a strategic agent, whose goal is to maximize her long-term surplus, and we are interested in mechanisms that maximize the seller’s long-term revenue. We define the natural notion of strategic regret — the lost revenue as measured against a truthful (non-strategic) buyer. We present seller algorithms that are no(strategic)-regret when the buyer discounts her future surplus — i.e. the buyer prefers showing advertisements to users sooner rather than later. We also give a lower bound on strategic regret that increases as the buyer’s discounting weakens and shows, in particular, that any seller algorithm will suffer linear strategic regret if there is no discounting. 1
5 0.41876891 206 nips-2013-Near-Optimal Entrywise Sampling for Data Matrices
Author: Dimitris Achlioptas, Zohar S. Karnin, Edo Liberty
Abstract: We consider the problem of selecting non-zero entries of a matrix A in order to produce a sparse sketch of it, B, that minimizes A B 2 . For large m n matrices, such that n m (for example, representing n observations over m attributes) we give sampling distributions that exhibit four important properties. First, they have closed forms computable from minimal information regarding A. Second, they allow sketching of matrices whose non-zeros are presented to the algorithm in arbitrary order as a stream, with O 1 computation per non-zero. Third, the resulting sketch matrices are not only sparse, but their non-zero entries are highly compressible. Lastly, and most importantly, under mild assumptions, our distributions are provably competitive with the optimal offline distribution. Note that the probabilities in the optimal offline distribution may be complex functions of all the entries in the matrix. Therefore, regardless of computational complexity, the optimal distribution might be impossible to compute in the streaming model. 1
6 0.4186908 285 nips-2013-Robust Transfer Principal Component Analysis with Rank Constraints
7 0.41645956 232 nips-2013-Online PCA for Contaminated Data
8 0.41549024 332 nips-2013-Tracking Time-varying Graphical Structure
10 0.4121744 233 nips-2013-Online Robust PCA via Stochastic Optimization
11 0.41176343 288 nips-2013-Scalable Influence Estimation in Continuous-Time Diffusion Networks
12 0.41144067 335 nips-2013-Transfer Learning in a Transductive Setting
13 0.41033864 291 nips-2013-Sensor Selection in High-Dimensional Gaussian Trees with Nuisances
14 0.40968609 350 nips-2013-Wavelets on Graphs via Deep Learning
15 0.40934342 45 nips-2013-BIG & QUIC: Sparse Inverse Covariance Estimation for a Million Variables
16 0.40878046 207 nips-2013-Near-optimal Anomaly Detection in Graphs using Lovasz Extended Scan Statistic
17 0.40867081 168 nips-2013-Learning to Pass Expectation Propagation Messages
18 0.40839821 304 nips-2013-Sparse nonnegative deconvolution for compressive calcium imaging: algorithms and phase transitions
19 0.40747178 300 nips-2013-Solving the multi-way matching problem by permutation synchronization
20 0.40728608 82 nips-2013-Decision Jungles: Compact and Rich Models for Classification