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

161 nips-2009-Nash Equilibria of Static Prediction Games

Source: pdf

Author: Michael Brückner, Tobias Scheffer

Abstract: The standard assumption of identically distributed training and test data is violated when an adversary can exercise some control over the generation of the test data. In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will ﬁnd the equilibrial prediction models. In a case study, we explore properties of Nash-equilibrial prediction models for email spam ﬁltering empirically. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 de Abstract The standard assumption of identically distributed training and test data is violated when an adversary can exercise some control over the generation of the test data. [sent-5, score-0.246]

2 In a prediction game, a learner produces a predictive model while an adversary may alter the distribution of input data. [sent-6, score-0.399]

3 We study single-shot prediction games in which the cost functions of learner and adversary are not necessarily antagonistic. [sent-7, score-0.616]

4 We identify conditions under which the prediction game has a unique Nash equilibrium, and derive algorithms that will ﬁnd the equilibrial prediction models. [sent-8, score-0.278]

5 In a variety of applications, however, data at application time are generated by an adversary whose interests are in conﬂict with those of the learner. [sent-11, score-0.264]

6 An adversarial interaction between learner and data generator can be modeled as a single-shot game in which one player controls the predictive model whereas the other player exercises some control over the distribution of the input data. [sent-13, score-0.55]

7 The minimax strategy minimizes the costs under the worst possible move of the opponent. [sent-15, score-0.417]

8 This strategy is motivated for an opponent whose goal is to inﬂict the highest possible costs on the learner; it can also be applied when no information about the interests of the adversary is available. [sent-16, score-0.522]

9 Similarly, minimax solutions to classiﬁcation games in which the adversary deletes input features or performs a feature transformation have been studied [3, 4, 5]. [sent-23, score-0.587]

10 These studies show that the minimax solution outperforms a learner that naively minimizes the costs on the training data without taking the adversary into account. [sent-24, score-0.79]

11 When rational opponents aim at minimizing their personal costs, then the minimax solution is overly pessimistic. [sent-25, score-0.273]

12 A Nash equilibrium is a pair of actions chosen such that no player gains a beneﬁt by unilaterally selecting a different action. [sent-26, score-0.506]

13 If a game has a unique Nash equilibrium, it is the strongest available concept of an optimal strategy in a game against a rational opponent. [sent-27, score-0.37]

14 If, however, multiple equilibria exist and the players choose their action according to distinct ones, then the resulting combination may be arbitrarily disadvantageous for either player. [sent-28, score-0.277]

15 1 We study games in which both players – learner and adversary – have cost functions that consist of data-dependent loss and regularizer. [sent-30, score-0.879]

16 As an example, consider that a spam ﬁlter may minimize the error rate whereas a spam sender may aim at maximizing revenue solicited by spam emails. [sent-32, score-0.525]

17 We study the existence of a unique Nash equilibrium and derive an algorithm that ﬁnds it under deﬁned conditions in Section 3. [sent-37, score-0.497]

18 For this case, we derive an algorithm that ﬁnds a unique Nash equilibrium whenever it exists. [sent-39, score-0.476]

19 2 Modeling the Game We study prediction games between a learner (v = +1) and an adversary (v = −1). [sent-41, score-0.49]

20 Static or single-shot game means that players make decisions simultaneously; neither player has information about the opponent’s decisions. [sent-43, score-0.426]

21 Inﬁnite refers to continuous cost functions that leave players with inﬁnitely many strategies to choose from. [sent-44, score-0.29]

22 Simultaneously, the adversary chooses a transformation function φa−1 that maps any input matrix X to an altered matrix φa−1 (X). [sent-51, score-0.289]

23 This transformation induces a transition from input distribution q to test distribution qtest with q(X, y) = n qtest (φa−1 (X), y) = i=1 qtest (φa−1 (X)i , yi ). [sent-52, score-0.312]

24 For instance, in spam ﬁltering it is appropriate to constrain A−1 such that perturbation matrices contain zero vectors for non-spam messages; this reﬂects that spammers can only alter spam messages. [sent-60, score-0.351]

25 Each player has an individual loss function v (y , y) where y is the value of decision function ha+1 and y is the true label. [sent-62, score-0.25]

26 Section 4 will discuss antagonistic loss functions +1 = − −1 . [sent-63, score-0.331]

27 For instance, a learner may minimize the zero-one loss whereas the adversary may focus on the lost revenue. [sent-65, score-0.498]

28 Both players aim at minimizing their loss over the test distribution qtest . [sent-66, score-0.365]

29 But, since q and consequently qtest are unknown, the cost functions are regularized empirical loss functions over the sample φa−1 (X) which reﬂects test distribution qtest . [sent-67, score-0.474]

30 n θv (av , a−v ) = v (ha+1 (φa−1 (X)i ), yi ) + Ω av (1) i=1 Each player’s cost function depends on the opponent’s parameter. [sent-71, score-0.34]

31 The minimax solution arg minav maxa−v θv (av , a−v ) minimizes the costs under the worst possible move of the opponent. [sent-73, score-0.438]

32 This solution is optimal for a malicious opponent whose goal is to inﬂict maximally high costs on the learner. [sent-74, score-0.276]

33 In absence of any information on the opponent’s goals, the minimax solution still gives the lowest upper bound on the learner’s costs over all possible strategies of the opponent. [sent-75, score-0.382]

34 If both players – learner and adversary – behave rationally in the sense of minimizing their personal costs, then the Nash equilibrium is the strongest available concept of an optimal choice of av . [sent-76, score-1.197]

35 A 2 Nash equilibrium is deﬁned as a pair of actions a∗ = [a∗ , a∗ ] such that no player can beneﬁt +1 −1 from changing the strategy unilaterally. [sent-77, score-0.531]

36 v −v −v (2) av ∈Av The Nash equilibrium has several catches. [sent-79, score-0.608]

37 Firstly, if the adversary behaves irrationally in the sense of inﬂicting high costs on the other player at the expense of incurring higher personal costs, then choosing an action according to the Nash equilibrium may result in higher costs than the minimax solution. [sent-80, score-1.377]

38 Secondly, a game may not have an equilibrium point. [sent-81, score-0.512]

39 If an equilibrium point exists, the game may thirdly possess multiple equilibria. [sent-82, score-0.512]

40 If a∗ = [a∗ , a∗ ] and a = [a+1 , a−1 ] are distinct +1 −1 equilibria, and each player decides to act according to one of them, then a combination [a∗ , a−v ] v may be a poor joint strategy and may give rise to higher costs than a worst-case solution. [sent-83, score-0.332]

41 However, if a unique Nash equilibrium exists and both players seek to minimize their individual costs, then the Nash equilibrium is guaranteed to be the optimal move. [sent-84, score-0.997]

42 3 Solution for Convex Loss Functions In this section, we study the existence of a unique Nash equilibrium of prediction games with cost functions as in Equation 1. [sent-85, score-0.695]

43 We derive an algorithm that identiﬁes the unique equilibrium if sufﬁcient conditions are met. [sent-86, score-0.476]

44 Both loss functions are, however, required to be convex and twice differentiable, and we assume strictly convex regularizers Ωav such as the l2 -norm regularizer. [sent-88, score-0.406]

45 Player- and instance-speciﬁc costs may be attached to the loss functions; however, we omit such cost factors for greater notational harmony. [sent-89, score-0.358]

46 This section’s main result is that if both loss functions are monotonic in y with different monotonicities – that is, one is monotonically increasing, and one is decreasing for any ﬁxed y – then the game has a unique Nash equilibrium that can be found efﬁciently. [sent-90, score-0.781]

47 Let the cost functions be deﬁned as in Equation 1 with strictly convex regularizers Ωav , let action spaces Av be nonempty, compact, and convex subsets of ﬁnite-dimensional Euclidean spaces. [sent-92, score-0.415]

48 If for any ﬁxed y, both loss functions v (y , y) are monotonic in y ∈ R with distinct monotonicity, convex in y , and twice differentiable in y , then a unique Nash equilibrium exists. [sent-93, score-0.776]

49 The players’ regularizers Ωav are strictly convex, and both loss functions v (ha+1 (φa−1 (X)i ), yi ) are convex and twice differentiable in av ∈ Av for any ﬁxed a−v ∈ A−v . [sent-95, score-0.645]

50 As each player has an own nonempty, compact, and convex action space Av , Theorem 2 of [7] applies as well; that is, if function σr (a) = rθ+1 (a+1 , a−1 ) + (1 − r)θ−1 (a+1 , a−1 ) (3) is diagonally strictly convex in a for some ﬁxed 0 < r < 1, then a unique Nash equilibrium exists. [sent-98, score-0.803]

51 (5) We want to show that Jr (a) is positive deﬁnite for some ﬁxed r if both loss functions v (y , y) have distinct monotonicity and are convex in y . [sent-101, score-0.268]

52 According to Theorem 1, a unique Nash equilibrium exists for suitable loss functions such as the squared hinge loss, logistic loss, etc. [sent-177, score-0.653]

53 Intuitively, Ψrv (a, b) quantiﬁes the weighted sum of the relative cost savings that the players can enjoy by changing from strategy av to strategy bv while their opponent continues to play a−v . [sent-179, score-0.616]

54 By these deﬁnitions, a∗ is a Nash equilibrium if, and only if, Vrv (a∗ ) is a global minimum of the value function with Vrv (a∗ ) = 0 for any ﬁxed weights r+1 = r and r−1 = 1 − r, where 0 < r < 1. [sent-181, score-0.378]

55 The weights rv are ﬁxed scaling factors of the players’ objectives which do not affect the Nash equilibrium in Equation 2; however, these weights ensure the main condition of Corollary 3. [sent-184, score-0.449]

56 5: Find maximal step size tk ∈ {2−l : l ∈ N} with Vrv (ak + tk dk ) ≤ Vrv (ak ) − tk dk 2 . [sent-194, score-0.368]

57 Convergence follows from the fact that if in the k-th iteration dk = 0, then ak is a Nash equilibrium which is unique according to Theorem 1. [sent-198, score-0.679]

58 If dk = 0, then dk is a descent direction of Vrv at position ak . [sent-199, score-0.303]

59 4 Solution for Antagonistic Loss Functions Algorithm 1 is guaranteed to identify the unique equilibrium if the loss functions are convex, twice differentiable, and of distinct monotonicities. [sent-203, score-0.673]

60 We will now study the case in which the learner’s cost function is continuous and convex, and the adversary’s loss function is antagonistic to the learner’s loss, that is, +1 = − −1 . [sent-204, score-0.382]

61 In this setting, a unique Nash equilibrium cannot be guaranteed to exist because the adversary’s cost function is not necessarily strictly convex. [sent-207, score-0.571]

62 The symmetry of the loss functions simpliﬁes the players’ cost functions in Equation 1 to n θ+1 (a+1 , a−1 ) = +1 (ha+1 (φa−1 (X)i ), yi ) + Ωa+1 , (15) i=1 n θ−1 (a−1 , a+1 ) = − +1 (ha+1 (φa−1 (X)i ), yi ) + Ωa−1 . [sent-209, score-0.36]

63 (16) i=1 Even though the loss functions are antagonistic, the cost functions in Equations 15 and 16 are not, unless the player’s regularizers are antagonistic as well. [sent-210, score-0.524]

64 However, according to Theorem 2, if the game has a unique Nash equilibrium, then this equilibrium is a minimax solution of the zero-sum game deﬁned by the joint cost function of Equation 17. [sent-212, score-1.025]

65 If the game with cost functions θ+1 and θ−1 deﬁned in Equations 15 and 16 has a unique Nash equilibrium a∗ , then this equilibrium also satisﬁes a∗ = arg mina+1 maxa−1 θ0 (a+1 , a−1 ) where θ0 (a+1 , a−1 ) = n i=1 +1 (ha+1 (φa−1 (X)i ), yi ) + Ωa+1 − Ωa−1 . [sent-214, score-1.149]

66 As a consequence of Theorem 2, we can identify the unique Nash equilibrium of the game with cost functions θ+1 and θ−1 , if it exists, by ﬁnding the minimax solution of the game with joint cost function θ0 . [sent-216, score-1.151]

67 The minimax solution is given by a∗ +1 = arg min max θ0 (a+1 , a−1 ). [sent-217, score-0.248]

68 It identiﬁes the unique Nash equilibrium of a game with antagonistic loss functions, if it exists, by ﬁnding the minimax solution of the game with joint cost function θ0 . [sent-222, score-1.308]

69 +1 5: Find maximal step size tk ∈ {2−l : l ∈ N} with θ0 (ak + tk dk , ak ) ≤ θ0 (ak , ak ) − −1 +1 −1 +1 tk dk 2 . [sent-227, score-0.658]

70 +1 8: until ak − ak−1 ≤ +1 +1 6: A minimax solution arg mina+1 maxa−1 θ+1 (a+1 , a−1 ) of the learner’s cost function minimizes the learner’s costs when playing against the most malicious opponent; for instance, Invar-SVM [4] ﬁnds such a solution. [sent-230, score-0.682]

71 By contrast, the minimax solution arg mina+1 maxa−1 θ0 (a+1 , a−1 ) of the joint cost function as deﬁned in Equation 17 constitutes a Nash equilibrium of the game with cost functions θ+1 and θ−1 , deﬁned in Equations 15 and 16. [sent-231, score-0.964]

72 It minimizes the costs for each of two players that seek their personal advantage. [sent-232, score-0.403]

73 5 Experiments We study the problem of email spam ﬁltering where the learner tries to identify spam emails while the adversary conceals spam messages in order to penetrate the ﬁlter. [sent-234, score-1.16]

74 Our goal is to explore the relative strengths and weaknesses of the proposed Nash models for antagonistic and non-antagonistic loss functions and existing baseline methods. [sent-235, score-0.331]

75 We use the logistic loss as the learner’s loss function +1 (h(x), y) = log(1 + e−yh(x) ) for the Minimax and the Nash model. [sent-263, score-0.272]

76 Consequently, the adversary’s loss for the Minimax solution is the negative loss of the learner. [sent-264, score-0.266]

77 In the Nash model, we choose −1 (h(x), y) = log(1 + eyh(x) ) which is a convex approximation of the adversary’s zero-one loss, that is, correct predictions by the learner incur high costs for the adversary. [sent-265, score-0.34]

78 For spam emails xi , we impose box constraints − 2 xi ≤ a−1,i ≤ 2 xi on the adversary’s parameters; for non-spam we set a−1,i = 0. [sent-267, score-0.362]

79 That is, the spam sender can only transform spam emails. [sent-268, score-0.363]

80 We use l2 -norm regularizers for both players, that is, Ωav = λv av 2 where 2 2 λv is the regularization parameter of player v. [sent-272, score-0.425]

81 We use two email corpora: the ﬁrst contains 65,000 publicly available emails received between 2000 and 2002 from the Enron corpus, the SpamAssassin corpus, Bruce Guenter’s spam trap, and several mailing lists. [sent-274, score-0.411]

82 The second contains 40,000 private emails received between 2000 and 2007. [sent-275, score-0.259]

83 Recall that Minimax refers to the Nash equilibrium for antagonistic loss functions found by solving the minimax problem for the joint cost function (Algorithm 2). [sent-294, score-0.989]

84 In this setting, loss functions – but not cost functions – are antagonistic; hence, Nash cannot gain an advantage over Minimax. [sent-295, score-0.296]

85 Regular SVM and logistic regression are faster than the game models; the game models behave comparably. [sent-297, score-0.296]

86 1 10,000 20,000 t emails received after training future 100 400 1,600 number of training emails 6,200 Figure 2: Left, center: AUC evaluated into the future after training on past. [sent-306, score-0.4]

87 Accuracy (40,000 Private Emails) SVM SVM with costs LogReg LogReg with costs Invar-SVM Minimax Nash Nash with costs 44 43 42 41 40 39 38 70 0. [sent-310, score-0.474]

88 Our model reﬂects that an email service provider may delete detected spam emails after a latency period whereas other emails incur storage costs c+1,i proportional to their ﬁle size. [sent-319, score-0.826]

89 The spam sender’s costs are c−1,i = 1 for all spam instances and c−1,i = 0 for all non-spam instances. [sent-320, score-0.482]

90 The classiﬁer threshold balances a trade-off between non-spam recall (fraction of legitimate emails delivered) and storage costs. [sent-321, score-0.257]

91 Invar-SVM and Minimax cannot reﬂect differing costs for learner and adversary in their optimization criteria and therefore perform worse. [sent-326, score-0.534]

92 6 Conclusion We studied games in which each player’s cost function consists of a data-dependent loss and a regularizer. [sent-328, score-0.27]

93 A learner produces a linear model while an adversary chooses a transformation matrix to be added to the data matrix. [sent-329, score-0.419]

94 It minimizes the costs of each of two players that aim for their highest personal beneﬁt. [sent-332, score-0.403]

95 We derive an algorithm that identiﬁes the equilibrium under these conditions. [sent-333, score-0.399]

96 For the case of antagonistic loss functions with arbitrary regularizers a unique Nash equilibrium may or may not exist. [sent-334, score-0.853]

97 We derive an algorithm that ﬁnds the unique Nash equilibrium, if it exists, by solving a minimax problem on a newly derived joint cost function. [sent-335, score-0.378]

98 In a setting with player- and instance-speciﬁc costs, the Nash model for non-antagonistic loss functions excels because this setting is poorly modeled with antagonistic loss functions. [sent-338, score-0.453]

99 Existence and uniqueness of equilibrium points for concave n-person games. [sent-372, score-0.378]

100 Relaxation methods for generalized Nash equilibrium problems with inexact line search. [sent-375, score-0.378]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('nash', 0.522), ('equilibrium', 0.378), ('adversary', 0.246), ('av', 0.23), ('minimax', 0.202), ('emails', 0.2), ('vrv', 0.171), ('players', 0.164), ('spam', 0.162), ('antagonistic', 0.161), ('costs', 0.158), ('ak', 0.145), ('game', 0.134), ('learner', 0.13), ('player', 0.128), ('loss', 0.122), ('ha', 0.103), ('dk', 0.079), ('logreg', 0.079), ('qtest', 0.079), ('cost', 0.078), ('unique', 0.077), ('opponent', 0.075), ('auc', 0.073), ('rv', 0.071), ('games', 0.07), ('regularizers', 0.067), ('tk', 0.064), ('jr', 0.059), ('private', 0.059), ('action', 0.058), ('storage', 0.057), ('maxa', 0.056), ('convex', 0.052), ('email', 0.049), ('personal', 0.049), ('functions', 0.048), ('transformation', 0.043), ('nonempty', 0.042), ('sender', 0.039), ('svm', 0.039), ('strictly', 0.038), ('jacobian', 0.037), ('equation', 0.034), ('equilibria', 0.034), ('minimizes', 0.032), ('ict', 0.032), ('yi', 0.032), ('mina', 0.032), ('summand', 0.03), ('adversarial', 0.03), ('differentiable', 0.029), ('logistic', 0.028), ('messages', 0.028), ('perturbation', 0.027), ('twice', 0.027), ('chronologically', 0.026), ('deletes', 0.026), ('maxb', 0.026), ('strategy', 0.025), ('corpus', 0.025), ('amir', 0.025), ('monotonicity', 0.025), ('public', 0.025), ('arg', 0.024), ('nds', 0.023), ('danskin', 0.023), ('potsdam', 0.023), ('choon', 0.023), ('hui', 0.023), ('prediction', 0.023), ('solution', 0.022), ('sam', 0.022), ('spaces', 0.022), ('monotonic', 0.022), ('distinct', 0.021), ('derive', 0.021), ('laurent', 0.021), ('chronological', 0.021), ('malicious', 0.021), ('study', 0.021), ('compact', 0.021), ('theorem', 0.021), ('consequently', 0.02), ('ltering', 0.02), ('lanckriet', 0.02), ('globerson', 0.02), ('diagonally', 0.02), ('gert', 0.02), ('scheffer', 0.02), ('execution', 0.019), ('static', 0.019), ('eigenvalues', 0.019), ('regards', 0.019), ('bv', 0.019), ('ghaoui', 0.019), ('maximal', 0.018), ('teo', 0.018), ('interests', 0.018), ('bk', 0.018)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 161 nips-2009-Nash Equilibria of Static Prediction Games

Author: Michael Brückner, Tobias Scheffer

2 0.27262634 221 nips-2009-Solving Stochastic Games

Author: Liam M. Dermed, Charles L. Isbell

Abstract: Solving multi-agent reinforcement learning problems has proven difﬁcult because of the lack of tractable algorithms. We provide the ﬁrst approximation algorithm which solves stochastic games with cheap-talk to within absolute error of the optimal game-theoretic solution, in time polynomial in 1/ . Our algorithm extends Murray’s and Gordon’s (2007) modiﬁed Bellman equation which determines the set of all possible achievable utilities; this provides us a truly general framework for multi-agent learning. Further, we empirically validate our algorithm and ﬁnd the computational cost to be orders of magnitude less than what the theory predicts. 1

3 0.23928241 232 nips-2009-Strategy Grafting in Extensive Games

Author: Kevin Waugh, Nolan Bard, Michael Bowling

Abstract: Extensive games are often used to model the interactions of multiple agents within an environment. Much recent work has focused on increasing the size of an extensive game that can be feasibly solved. Despite these improvements, many interesting games are still too large for such techniques. A common approach for computing strategies in these large games is to ﬁrst employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size. This abstract game is then solved and the resulting strategy is played in the original game. Most top programs in recent AAAI Computer Poker Competitions use this approach. The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games. These larger abstract games have more expressive strategy spaces and therefore contain better strategies. In this paper we present a new method for computing strategies in large games. This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve. We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justiﬁcation for the resulting improvement. 1

4 0.17299151 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

Author: Marc Lanctot, Kevin Waugh, Martin Zinkevich, Michael Bowling

Abstract: Sequential decision-making with multiple agents and imperfect information is commonly modeled as an extensive game. One efﬁcient method for computing Nash equilibria in large, zero-sum, imperfect information games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-speciﬁc augmentation involving chance outcome sampling. In this paper, we describe a general family of domain-independent CFR sample-based algorithms called Monte Carlo counterfactual regret minimization (MCCFR) of which the original and poker-speciﬁc versions are special cases. We start by showing that MCCFR performs the same regret updates as CFR on expectation. Then, we introduce two sampling schemes: outcome sampling and external sampling, showing that both have bounded overall regret with high probability. Thus, they can compute an approximate equilibrium using self-play. Finally, we prove a new tighter bound on the regret for the original CFR algorithm and relate this new bound to MCCFR’s bounds. We show empirically that, although the sample-based algorithms require more iterations, their lower cost per iteration can lead to dramatically faster convergence in various games. 1

5 0.12139 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Author: Samuel R. Bulò, Marcello Pelillo

Abstract: Hypergraph clustering refers to the process of extracting maximally coherent groups from a set of objects using high-order (rather than pairwise) similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a user-deﬁned number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this paper, we provide a radically different perspective to the problem. In contrast to the classical approach, we attempt to provide a meaningful formalization of the very notion of a cluster and we show that game theory offers an attractive and unexplored perspective that serves well our purpose. Speciﬁcally, we show that the hypergraph clustering problem can be naturally cast into a non-cooperative multi-player “clustering game”, whereby the notion of a cluster is equivalent to a classical game-theoretic equilibrium concept. From the computational viewpoint, we show that the problem of ﬁnding the equilibria of our clustering game is equivalent to locally optimizing a polynomial function over the standard simplex, and we provide a discrete-time dynamics to perform this optimization. Experiments are presented which show the superiority of our approach over state-of-the-art hypergraph clustering techniques.

6 0.11307919 48 nips-2009-Bootstrapping from Game Tree Search

7 0.085083209 144 nips-2009-Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness

8 0.065877445 14 nips-2009-A Parameter-free Hedging Algorithm

9 0.065220587 208 nips-2009-Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

10 0.063696675 116 nips-2009-Information-theoretic lower bounds on the oracle complexity of convex optimization

11 0.060348798 220 nips-2009-Slow Learners are Fast

12 0.059954785 3 nips-2009-AUC optimization and the two-sample problem

13 0.05640059 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

14 0.055496138 173 nips-2009-Nonparametric Greedy Algorithms for the Sparse Learning Problem

15 0.055206433 11 nips-2009-A General Projection Property for Distribution Families

16 0.054952648 98 nips-2009-From PAC-Bayes Bounds to KL Regularization

17 0.052301671 176 nips-2009-On Invariance in Hierarchical Models

18 0.05165533 157 nips-2009-Multi-Label Prediction via Compressed Sensing

19 0.045105845 136 nips-2009-Learning to Rank by Optimizing NDCG Measure

20 0.044786215 230 nips-2009-Statistical Consistency of Top-k Ranking

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.13), (1, 0.111), (2, 0.081), (3, -0.098), (4, -0.118), (5, 0.039), (6, -0.064), (7, -0.061), (8, 0.088), (9, -0.016), (10, -0.212), (11, -0.34), (12, -0.207), (13, -0.117), (14, 0.013), (15, -0.204), (16, -0.042), (17, -0.01), (18, 0.029), (19, -0.007), (20, 0.02), (21, 0.015), (22, -0.008), (23, -0.004), (24, 0.006), (25, 0.037), (26, 0.001), (27, -0.02), (28, -0.061), (29, -0.001), (30, 0.026), (31, 0.024), (32, 0.004), (33, 0.058), (34, 0.03), (35, -0.01), (36, -0.06), (37, -0.016), (38, 0.031), (39, 0.004), (40, -0.028), (41, -0.018), (42, 0.007), (43, 0.05), (44, -0.059), (45, 0.075), (46, -0.036), (47, -0.028), (48, 0.016), (49, -0.023)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.94589859 161 nips-2009-Nash Equilibria of Static Prediction Games

Author: Michael Brückner, Tobias Scheffer

2 0.92209291 232 nips-2009-Strategy Grafting in Extensive Games

Author: Kevin Waugh, Nolan Bard, Michael Bowling

3 0.80036908 221 nips-2009-Solving Stochastic Games

Author: Liam M. Dermed, Charles L. Isbell

4 0.77881432 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

Author: Marc Lanctot, Kevin Waugh, Martin Zinkevich, Michael Bowling

5 0.56718516 9 nips-2009-A Game-Theoretic Approach to Hypergraph Clustering

Author: Samuel R. Bulò, Marcello Pelillo

6 0.51163667 48 nips-2009-Bootstrapping from Game Tree Search

7 0.2926597 11 nips-2009-A General Projection Property for Distribution Families

8 0.28486907 14 nips-2009-A Parameter-free Hedging Algorithm

9 0.27138874 144 nips-2009-Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness

10 0.24537134 75 nips-2009-Efficient Large-Scale Distributed Training of Conditional Maximum Entropy Models

11 0.24415621 60 nips-2009-Convergent Temporal-Difference Learning with Arbitrary Smooth Function Approximation

12 0.23566365 234 nips-2009-Streaming k-means approximation

13 0.23333442 220 nips-2009-Slow Learners are Fast

14 0.22934082 76 nips-2009-Efficient Learning using Forward-Backward Splitting

15 0.22214282 3 nips-2009-AUC optimization and the two-sample problem

16 0.21298686 189 nips-2009-Periodic Step Size Adaptation for Single Pass On-line Learning

17 0.20887537 176 nips-2009-On Invariance in Hierarchical Models

18 0.20611829 180 nips-2009-On the Convergence of the Concave-Convex Procedure

19 0.2057813 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

20 0.20304683 244 nips-2009-The Wisdom of Crowds in the Recollection of Order Information

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(24, 0.151), (25, 0.049), (35, 0.042), (36, 0.074), (39, 0.02), (47, 0.295), (58, 0.077), (61, 0.031), (71, 0.067), (81, 0.017), (86, 0.059), (91, 0.012)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.80113208 161 nips-2009-Nash Equilibria of Static Prediction Games

Author: Michael Brückner, Tobias Scheffer

2 0.65731579 252 nips-2009-Unsupervised Feature Selection for the $k$-means Clustering Problem

Author: Christos Boutsidis, Petros Drineas, Michael W. Mahoney

Abstract: We present a novel feature selection algorithm for the k-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter ϵ ∈ (0, 1), selects and appropriately rescales in an unsupervised manner Θ(k log(k/ϵ)/ϵ2 ) features from a dataset of arbitrary dimensions. We prove that, if we run any γ-approximate k-means algorithm (γ ≥ 1) on the features selected using our method, we can ﬁnd a (1 + (1 + ϵ)γ)-approximate partition with high probability. 1

3 0.65597385 46 nips-2009-Bilinear classifiers for visual recognition

Author: Hamed Pirsiavash, Deva Ramanan, Charless C. Fowlkes

Abstract: We describe an algorithm for learning bilinear SVMs. Bilinear classiﬁers are a discriminative variant of bilinear models, which capture the dependence of data on multiple factors. Such models are particularly appropriate for visual data that is better represented as a matrix or tensor, rather than a vector. Matrix encodings allow for more natural regularization through rank restriction. For example, a rank-one scanning-window classiﬁer yields a separable ﬁlter. Low-rank models have fewer parameters and so are easier to regularize and faster to score at run-time. We learn low-rank models with bilinear classiﬁers. We also use bilinear classiﬁers for transfer learning by sharing linear factors between different classiﬁcation tasks. Bilinear classiﬁers are trained with biconvex programs. Such programs are optimized with coordinate descent, where each coordinate step requires solving a convex program - in our case, we use a standard off-the-shelf SVM solver. We demonstrate bilinear SVMs on difﬁcult problems of people detection in video sequences and action classiﬁcation of video sequences, achieving state-of-the-art results in both. 1

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

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

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

5 0.57641381 221 nips-2009-Solving Stochastic Games

Author: Liam M. Dermed, Charles L. Isbell

6 0.56623703 15 nips-2009-A Rate Distortion Approach for Semi-Supervised Conditional Random Fields

7 0.56566173 181 nips-2009-Online Learning of Assignments

8 0.55745083 240 nips-2009-Sufficient Conditions for Agnostic Active Learnable

9 0.55272561 45 nips-2009-Beyond Convexity: Online Submodular Minimization

10 0.55146229 144 nips-2009-Lower bounds on minimax rates for nonparametric regression with additive sparsity and smoothness

11 0.53896725 12 nips-2009-A Generalized Natural Actor-Critic Algorithm

12 0.5343399 239 nips-2009-Submodularity Cuts and Applications

13 0.53372383 55 nips-2009-Compressed Least-Squares Regression

14 0.53138667 14 nips-2009-A Parameter-free Hedging Algorithm

15 0.5306294 94 nips-2009-Fast Learning from Non-i.i.d. Observations

16 0.52935857 156 nips-2009-Monte Carlo Sampling for Regret Minimization in Extensive Games

17 0.52723271 122 nips-2009-Label Selection on Graphs

18 0.52372748 59 nips-2009-Construction of Nonparametric Bayesian Models from Parametric Bayes Equations

19 0.52371365 20 nips-2009-A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers

20 0.51963055 91 nips-2009-Fast, smooth and adaptive regression in metric spaces