The (1+1) Elitist Black-Box Complexity of LeadingOnes View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2018-05

AUTHORS

Carola Doerr, Johannes Lengler

ABSTRACT

One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us to understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the Ω(nlogn) lower bound for unary unbiased algorithms on functions with a unique global optimum (Lehre and Witt in Algorithmica 64:623–642, 2012), which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, such non-trivial lower bounds are very rare in the existing literature on black-box optimization and therefore remain to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is Ω(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order nloglogn (Afshani et al. in Lecture notes in computer science, vol 8066, pp 1–11. Springer, New York, 2013). The Ω(n2) lower bound does not rely on the fact that elitist black-box algorithms are not allowed to make use of absolute fitness values. In contrast, we show that even if absolute fitness values are revealed to the otherwise elitist algorithm, it cannot significantly profit from this additional information. Our result thus shows that for LeadingOnes the memory-restriction, together with the selection requirement, has a substantial impact on the best possible performance. More... »

PAGES

1579-1603

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-017-0304-6

DOI

http://dx.doi.org/10.1007/s00453-017-0304-6

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "CNRS and Sorbonne Universit\u00e9s, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Doerr", 
        "givenName": "Carola", 
        "id": "sg:person.010360414373.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Swiss Federal Institute of Technology in Zurich", 
          "id": "https://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "Institute for Theoretical Computer Science, ETH Z\u00fcrich, Z\u00fcrich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lengler", 
        "givenName": "Johannes", 
        "id": "sg:person.01104137534.89", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104137534.89"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-15844-5_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000452291", 
          "https://doi.org/10.1007/978-3-642-15844-5_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1967654.1967669", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006048249"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2463372.2463480", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018985918"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(01)00182-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019717336"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-40273-9_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021394801", 
          "https://doi.org/10.1007/978-3-642-40273-9_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2739480.2754678", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022158020"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-35533-2_18", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037135703", 
          "https://doi.org/10.1007/978-3-642-35533-2_18"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-004-1177-z", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040195428", 
          "https://doi.org/10.1007/s00224-004-1177-z"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2908812.2908922", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045850838"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9616-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045973415", 
          "https://doi.org/10.1007/s00453-012-9616-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00453-012-9684-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048445835", 
          "https://doi.org/10.1007/s00453-012-9684-9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00224-012-9438-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051006109", 
          "https://doi.org/10.1007/s00224-012-9438-8"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2739480.2754654", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1053304664"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tevc.2012.2202241", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061605104"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1239/jap/1110381369", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064441978"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/sfcs.1977.24", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086173273"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511814075", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098701235"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-05", 
    "datePublishedReg": "2018-05-01", 
    "description": "One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us to understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the \u03a9(nlogn) lower bound for unary unbiased algorithms on functions with a unique global optimum (Lehre and Witt in Algorithmica 64:623\u2013642, 2012), which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, such non-trivial lower bounds are very rare in the existing literature on black-box optimization and therefore remain to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is \u03a9(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order nloglogn (Afshani et al. in Lecture notes in computer science, vol 8066, pp 1\u201311. Springer, New York, 2013). The \u03a9(n2) lower bound does not rely on the fact that elitist black-box algorithms are not allowed to make use of absolute fitness values. In contrast, we show that even if absolute fitness values are revealed to the otherwise elitist algorithm, it cannot significantly profit from this additional information. Our result thus shows that for LeadingOnes the memory-restriction, together with the selection requirement, has a substantial impact on the best possible performance.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-017-0304-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "80"
      }
    ], 
    "name": "The (1+1) Elitist Black-Box Complexity of LeadingOnes", 
    "pagination": "1579-1603", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "70c56a621457e18f81032ad249fd8f60c4d12a378b978168f3b0cc0cdc10ec3b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-017-0304-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1084022154"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-017-0304-6", 
      "https://app.dimensions.ai/details/publication/pub.1084022154"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:25", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000362_0000000362/records_87106_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-017-0304-6"
  }
]
 

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/s00453-017-0304-6'

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/s00453-017-0304-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0304-6'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-017-0304-6'


 

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

128 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-017-0304-6 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd6a58e44ba3f43428f408c0fafa4a476
4 schema:citation sg:pub.10.1007/978-3-642-15844-5_1
5 sg:pub.10.1007/978-3-642-35533-2_18
6 sg:pub.10.1007/978-3-642-40273-9_1
7 sg:pub.10.1007/s00224-004-1177-z
8 sg:pub.10.1007/s00224-012-9438-8
9 sg:pub.10.1007/s00453-012-9616-8
10 sg:pub.10.1007/s00453-012-9684-9
11 https://doi.org/10.1016/s0304-3975(01)00182-7
12 https://doi.org/10.1017/cbo9780511814075
13 https://doi.org/10.1109/sfcs.1977.24
14 https://doi.org/10.1109/tevc.2012.2202241
15 https://doi.org/10.1145/1967654.1967669
16 https://doi.org/10.1145/2463372.2463480
17 https://doi.org/10.1145/2739480.2754654
18 https://doi.org/10.1145/2739480.2754678
19 https://doi.org/10.1145/2908812.2908922
20 https://doi.org/10.1239/jap/1110381369
21 schema:datePublished 2018-05
22 schema:datePublishedReg 2018-05-01
23 schema:description One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized search heuristics. Complementing classical runtime analysis, black-box models help us to understand how algorithmic choices such as the population size, the variation operators, or the selection rules influence the optimization time. One example for such a result is the Ω(nlogn) lower bound for unary unbiased algorithms on functions with a unique global optimum (Lehre and Witt in Algorithmica 64:623–642, 2012), which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack of analyzing techniques, such non-trivial lower bounds are very rare in the existing literature on black-box optimization and therefore remain to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is Ω(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order nloglogn (Afshani et al. in Lecture notes in computer science, vol 8066, pp 1–11. Springer, New York, 2013). The Ω(n2) lower bound does not rely on the fact that elitist black-box algorithms are not allowed to make use of absolute fitness values. In contrast, we show that even if absolute fitness values are revealed to the otherwise elitist algorithm, it cannot significantly profit from this additional information. Our result thus shows that for LeadingOnes the memory-restriction, together with the selection requirement, has a substantial impact on the best possible performance.
24 schema:genre research_article
25 schema:inLanguage en
26 schema:isAccessibleForFree true
27 schema:isPartOf N415c8f057e4c4d93aaf8e46f8534055f
28 Na173a77434ff418a86bf8653dd7d43af
29 sg:journal.1047644
30 schema:name The (1+1) Elitist Black-Box Complexity of LeadingOnes
31 schema:pagination 1579-1603
32 schema:productId N9d5c7873009a48b689a6464fee412d7c
33 Nc75c0df2e9a946d0a5979bfc08417e14
34 Nf25c72bf295a49bcaf8e813e3f417609
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084022154
36 https://doi.org/10.1007/s00453-017-0304-6
37 schema:sdDatePublished 2019-04-11T12:25
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Ne721b5c11ef8427b98438dd36ac827b9
40 schema:url https://link.springer.com/10.1007%2Fs00453-017-0304-6
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N415c8f057e4c4d93aaf8e46f8534055f schema:volumeNumber 80
45 rdf:type schema:PublicationVolume
46 N7de49d4bcf9946a9bebdf217560895e0 rdf:first sg:person.01104137534.89
47 rdf:rest rdf:nil
48 N9d5c7873009a48b689a6464fee412d7c schema:name readcube_id
49 schema:value 70c56a621457e18f81032ad249fd8f60c4d12a378b978168f3b0cc0cdc10ec3b
50 rdf:type schema:PropertyValue
51 Na173a77434ff418a86bf8653dd7d43af schema:issueNumber 5
52 rdf:type schema:PublicationIssue
53 Nc75c0df2e9a946d0a5979bfc08417e14 schema:name dimensions_id
54 schema:value pub.1084022154
55 rdf:type schema:PropertyValue
56 Nccea3308583741f0b665508a8d8d8482 schema:name CNRS and Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005, Paris, France
57 rdf:type schema:Organization
58 Nd6a58e44ba3f43428f408c0fafa4a476 rdf:first sg:person.010360414373.45
59 rdf:rest N7de49d4bcf9946a9bebdf217560895e0
60 Ne721b5c11ef8427b98438dd36ac827b9 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 Nf25c72bf295a49bcaf8e813e3f417609 schema:name doi
63 schema:value 10.1007/s00453-017-0304-6
64 rdf:type schema:PropertyValue
65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
66 schema:name Information and Computing Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
69 schema:name Computation Theory and Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1047644 schema:issn 0178-4617
72 1432-0541
73 schema:name Algorithmica
74 rdf:type schema:Periodical
75 sg:person.010360414373.45 schema:affiliation Nccea3308583741f0b665508a8d8d8482
76 schema:familyName Doerr
77 schema:givenName Carola
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010360414373.45
79 rdf:type schema:Person
80 sg:person.01104137534.89 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
81 schema:familyName Lengler
82 schema:givenName Johannes
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01104137534.89
84 rdf:type schema:Person
85 sg:pub.10.1007/978-3-642-15844-5_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000452291
86 https://doi.org/10.1007/978-3-642-15844-5_1
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/978-3-642-35533-2_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037135703
89 https://doi.org/10.1007/978-3-642-35533-2_18
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/978-3-642-40273-9_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021394801
92 https://doi.org/10.1007/978-3-642-40273-9_1
93 rdf:type schema:CreativeWork
94 sg:pub.10.1007/s00224-004-1177-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1040195428
95 https://doi.org/10.1007/s00224-004-1177-z
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/s00224-012-9438-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051006109
98 https://doi.org/10.1007/s00224-012-9438-8
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/s00453-012-9616-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045973415
101 https://doi.org/10.1007/s00453-012-9616-8
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/s00453-012-9684-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048445835
104 https://doi.org/10.1007/s00453-012-9684-9
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0304-3975(01)00182-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019717336
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1017/cbo9780511814075 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098701235
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1109/sfcs.1977.24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086173273
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1109/tevc.2012.2202241 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061605104
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1145/1967654.1967669 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006048249
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1145/2463372.2463480 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018985918
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1145/2739480.2754654 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053304664
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/2739480.2754678 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022158020
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/2908812.2908922 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045850838
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1239/jap/1110381369 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064441978
125 rdf:type schema:CreativeWork
126 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
127 schema:name Institute for Theoretical Computer Science, ETH Zürich, Zürich, Switzerland
128 rdf:type schema:Organization
 




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


...