On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Khaled Elbassioni , Kazuhisa Makino , Kurt Mehlhorn , Fahimeh Ramezani

ABSTRACT

Given two bounded convex sets X ⊆ ℝm and Y ⊆ ℝn, specified by membership oracles, and a continuous convex-concave function F:X×Y → ℝ, we consider the problem of computing an ε-approximate saddle point, that is, a pair (x*,y*) ∈ X×Y such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sup_{y\in Y} F(x^*,y)\le \inf_{x\in X}F(x,y^*)+\varepsilon .$\end{document} Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm for computing an ε-approximate saddle point for matrix games, that is, when F is bilinear and the sets X and Y are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an ε-approximate saddle point can be computed using O*(n + m) random samples from log-concave distributions over the convex sets X and Y. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when ε ∈ (0,1) is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. A full version of this paper can be found at http://arxiv.org/abs/1301.5290. More... »

PAGES

65-76

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-38768-5_8

DOI

http://dx.doi.org/10.1007/978-3-642-38768-5_8

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1011598011


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Masdar Institute of Science and Technology, Abu Dhabi, UAE", 
          "id": "http://www.grid.ac/institutes/grid.440568.b", 
          "name": [
            "Masdar Institute of Science and Technology, Abu Dhabi, UAE"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Elbassioni", 
        "givenName": "Khaled", 
        "id": "sg:person.012561735335.16", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graduate School of Information Science and Technology, University of Tokyo, 113-8656, Tokyo, Japan", 
          "id": "http://www.grid.ac/institutes/grid.26999.3d", 
          "name": [
            "Graduate School of Information Science and Technology, University of Tokyo, 113-8656, Tokyo, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Makino", 
        "givenName": "Kazuhisa", 
        "id": "sg:person.07741653331.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "id": "sg:person.011757371347.43", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany", 
          "id": "http://www.grid.ac/institutes/grid.419528.3", 
          "name": [
            "Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ramezani", 
        "givenName": "Fahimeh", 
        "id": "sg:person.011016565440.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Given two bounded convex sets X\u2009\u2286\u2009\u211dm and Y\u2009\u2286\u2009\u211dn, specified by membership oracles, and a continuous convex-concave function F:X\u00d7Y\u2009\u2192\u2009\u211d, we consider the problem of computing an \u03b5-approximate saddle point, that is, a pair (x*,y*)\u2009\u2208\u2009X\u00d7Y such that \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\sup_{y\\in Y} F(x^*,y)\\le \\inf_{x\\in X}F(x,y^*)+\\varepsilon .$\\end{document} Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm for computing an \u03b5-approximate saddle point for matrix games, that is, when F is bilinear and the sets X and Y are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant \u201cwidth\u201d, an \u03b5-approximate saddle point can be computed using O*(n\u2009+\u2009m) random samples from log-concave distributions over the convex sets X and Y. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when \u03b5\u2009\u2208\u2009(0,1) is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. A full version of this paper can be found at http://arxiv.org/abs/1301.5290.", 
    "editor": [
      {
        "familyName": "Du", 
        "givenName": "Ding-Zhu", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Guochuan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-38768-5_8", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-38767-8", 
        "978-3-642-38768-5"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "approximate saddle point", 
      "saddle point", 
      "convex sets", 
      "fictitious play", 
      "log-concave distributions", 
      "set X", 
      "polynomial time algorithm", 
      "general case", 
      "membership oracle", 
      "matrix games", 
      "main tool", 
      "function f", 
      "simple algorithm", 
      "X\u00d7Y", 
      "algorithm", 
      "Khachiyan", 
      "approximation", 
      "problem", 
      "simplices", 
      "convex", 
      "bilinear", 
      "full version", 
      "point", 
      "set", 
      "Grigoriadis", 
      "width", 
      "oracle", 
      "version", 
      "distribution", 
      "random sample", 
      "function", 
      "results", 
      "pairs", 
      "tool", 
      "cases", 
      "game", 
      "variants", 
      "combination", 
      "consequences", 
      "samples", 
      "play", 
      "paper", 
      "method"
    ], 
    "name": "On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets", 
    "pagination": "65-76", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011598011"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-38768-5_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-38768-5_8", 
      "https://app.dimensions.ai/details/publication/pub.1011598011"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_406.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-38768-5_8"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38768-5_8'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38768-5_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38768-5_8'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-38768-5_8'


 

This table displays all metadata directly associated to this object as RDF triples.

134 TRIPLES      22 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-38768-5_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf0eb9e89a7b64ceaa75123734c11c857
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description Given two bounded convex sets X ⊆ ℝm and Y ⊆ ℝn, specified by membership oracles, and a continuous convex-concave function F:X×Y → ℝ, we consider the problem of computing an ε-approximate saddle point, that is, a pair (x*,y*) ∈ X×Y such that \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\sup_{y\in Y} F(x^*,y)\le \inf_{x\in X}F(x,y^*)+\varepsilon .$\end{document} Grigoriadis and Khachiyan (1995), based on a randomized variant of fictitious play, gave a simple algorithm for computing an ε-approximate saddle point for matrix games, that is, when F is bilinear and the sets X and Y are simplices. In this paper, we extend their method to the general case. In particular, we show that, for functions of constant “width”, an ε-approximate saddle point can be computed using O*(n + m) random samples from log-concave distributions over the convex sets X and Y. As a consequence, we obtain a simple randomized polynomial-time algorithm that computes such an approximation faster than known methods for problems with bounded width and when ε ∈ (0,1) is a fixed, but arbitrarily small constant. Our main tool for achieving this result is the combination of the randomized fictitious play with the recently developed results on sampling from convex sets. A full version of this paper can be found at http://arxiv.org/abs/1301.5290.
7 schema:editor Nea6668402b3643c3b743682122c7c1e5
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N46f8ca68519043a3b0845f54f38bc416
11 schema:keywords Grigoriadis
12 Khachiyan
13 X×Y
14 algorithm
15 approximate saddle point
16 approximation
17 bilinear
18 cases
19 combination
20 consequences
21 convex
22 convex sets
23 distribution
24 fictitious play
25 full version
26 function
27 function f
28 game
29 general case
30 log-concave distributions
31 main tool
32 matrix games
33 membership oracle
34 method
35 oracle
36 pairs
37 paper
38 play
39 point
40 polynomial time algorithm
41 problem
42 random sample
43 results
44 saddle point
45 samples
46 set
47 set X
48 simple algorithm
49 simplices
50 tool
51 variants
52 version
53 width
54 schema:name On Randomized Fictitious Play for Approximating Saddle Points over Convex Sets
55 schema:pagination 65-76
56 schema:productId Na9f48342b9cd43638aa2dde4134452cf
57 Nf579744a649f43688f1ddc9db11c2e58
58 schema:publisher N39082b9866284c35b30d90f4dd1f6c05
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011598011
60 https://doi.org/10.1007/978-3-642-38768-5_8
61 schema:sdDatePublished 2022-10-01T06:58
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher Ne7614cda205d4a9a98faa13cbb7f7ff9
64 schema:url https://doi.org/10.1007/978-3-642-38768-5_8
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N14c46dd040724ea798a673e0a039b721 schema:familyName Zhang
69 schema:givenName Guochuan
70 rdf:type schema:Person
71 N1bed7abd63684401828aaafc858cb816 rdf:first sg:person.011016565440.58
72 rdf:rest rdf:nil
73 N39082b9866284c35b30d90f4dd1f6c05 schema:name Springer Nature
74 rdf:type schema:Organisation
75 N46f8ca68519043a3b0845f54f38bc416 schema:isbn 978-3-642-38767-8
76 978-3-642-38768-5
77 schema:name Computing and Combinatorics
78 rdf:type schema:Book
79 N47173d52cd7b4173823fe395f5e6177c rdf:first sg:person.011757371347.43
80 rdf:rest N1bed7abd63684401828aaafc858cb816
81 N4e6cd3a2eccd4ca592a9f6d6e20c1f87 schema:familyName Du
82 schema:givenName Ding-Zhu
83 rdf:type schema:Person
84 N85a95f2c5e0e448f984b474c6b7b0473 rdf:first N14c46dd040724ea798a673e0a039b721
85 rdf:rest rdf:nil
86 Na35f96fe1ec742eb810fb545c953a9c5 rdf:first sg:person.07741653331.03
87 rdf:rest N47173d52cd7b4173823fe395f5e6177c
88 Na9f48342b9cd43638aa2dde4134452cf schema:name doi
89 schema:value 10.1007/978-3-642-38768-5_8
90 rdf:type schema:PropertyValue
91 Ne7614cda205d4a9a98faa13cbb7f7ff9 schema:name Springer Nature - SN SciGraph project
92 rdf:type schema:Organization
93 Nea6668402b3643c3b743682122c7c1e5 rdf:first N4e6cd3a2eccd4ca592a9f6d6e20c1f87
94 rdf:rest N85a95f2c5e0e448f984b474c6b7b0473
95 Nf0eb9e89a7b64ceaa75123734c11c857 rdf:first sg:person.012561735335.16
96 rdf:rest Na35f96fe1ec742eb810fb545c953a9c5
97 Nf579744a649f43688f1ddc9db11c2e58 schema:name dimensions_id
98 schema:value pub.1011598011
99 rdf:type schema:PropertyValue
100 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
101 schema:name Information and Computing Sciences
102 rdf:type schema:DefinedTerm
103 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
104 schema:name Computation Theory and Mathematics
105 rdf:type schema:DefinedTerm
106 sg:person.011016565440.58 schema:affiliation grid-institutes:grid.419528.3
107 schema:familyName Ramezani
108 schema:givenName Fahimeh
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011016565440.58
110 rdf:type schema:Person
111 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
112 schema:familyName Mehlhorn
113 schema:givenName Kurt
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
115 rdf:type schema:Person
116 sg:person.012561735335.16 schema:affiliation grid-institutes:grid.440568.b
117 schema:familyName Elbassioni
118 schema:givenName Khaled
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012561735335.16
120 rdf:type schema:Person
121 sg:person.07741653331.03 schema:affiliation grid-institutes:grid.26999.3d
122 schema:familyName Makino
123 schema:givenName Kazuhisa
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07741653331.03
125 rdf:type schema:Person
126 grid-institutes:grid.26999.3d schema:alternateName Graduate School of Information Science and Technology, University of Tokyo, 113-8656, Tokyo, Japan
127 schema:name Graduate School of Information Science and Technology, University of Tokyo, 113-8656, Tokyo, Japan
128 rdf:type schema:Organization
129 grid-institutes:grid.419528.3 schema:alternateName Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
130 schema:name Max Planck Institute for Informatics, Campus E1 4, 66123, Saarbrucken, Germany
131 rdf:type schema:Organization
132 grid-institutes:grid.440568.b schema:alternateName Masdar Institute of Science and Technology, Abu Dhabi, UAE
133 schema:name Masdar Institute of Science and Technology, Abu Dhabi, UAE
134 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...