Tight Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Monotone Variational Inequalities View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-07-02

AUTHORS

Guoyong Gu, Junfeng Yang

ABSTRACT

This paper considers the relaxed proximal point algorithm for solving monotone variational inequality problems, and our main contribution is the establishment of a tight ergodic sublinear convergence rate. First, the tight or exact worst-case convergence rate is computed using the performance estimation framework. It is observed that this numerical bound asymptotically coincides with the best-known existing rate, whose tightness is not clear. This implies that, without further assumptions, sublinear convergence rate is likely the best achievable rate for the relaxed proximal point algorithm. Motivated by the numerical result, a concrete example is constructed, which provides a lower bound on the exact worst-case convergence rate. This lower bound coincides with the numerical bound computed via the performance estimation framework, leading us to conjecture that the lower bound provided by the example is exactly the tight worse-case rate, which is then verified theoretically. We thus have established an ergodic sublinear complexity rate that is tight in terms of both the sublinear order and the constants involved. More... »

PAGES

1-15

References to SciGraph publications

  • 2016-10-14. On the worst-case complexity of the gradient method with exact line search for smooth strongly convex functions in OPTIMIZATION LETTERS
  • 2015-10-17. Optimized first-order methods for smooth convex minimization in MATHEMATICAL PROGRAMMING
  • 2016-05-17. Smooth strongly convex interpolation and exact worst-case performance of first-order methods in MATHEMATICAL PROGRAMMING
  • 2018-05-10. Exact Worst-Case Convergence Rates of the Proximal Gradient Method for Composite Convex Minimization in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2016-02-16. An optimal variant of Kelley’s cutting-plane method in MATHEMATICAL PROGRAMMING
  • 2004. Finite-Dimensional Variational Inequalities and Complementarity Problems in NONE
  • 2020-07-09. On the convergence rate of the Halpern-iteration in OPTIMIZATION LETTERS
  • 2007-06-19. Primal-dual subgradient methods for convex problems in MATHEMATICAL PROGRAMMING
  • 2013-11-09. Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems: a unified approach in COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
  • 2020-10-30. Optimizing the Efficiency of First-Order Methods for Decreasing the Gradient of Smooth Convex Functions in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2013-03-23. Performance of first-order methods for smooth convex minimization: a novel approach in MATHEMATICAL PROGRAMMING
  • 2017. Convex Analysis and Monotone Operator Theory in Hilbert Spaces in NONE
  • 2016-10-05. On the Convergence Analysis of the Optimized Gradient Method in JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
  • 2021-03-23. Accelerated proximal point method for maximally monotone operators in MATHEMATICAL PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10957-022-02058-3

    DOI

    http://dx.doi.org/10.1007/s10957-022-02058-3

    DIMENSIONS

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


    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/09", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Engineering", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0906", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Electrical and Electronic Engineering", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Nanjing University, 210093, Nanjing, China", 
              "id": "http://www.grid.ac/institutes/grid.41156.37", 
              "name": [
                "Department of Mathematics, Nanjing University, 210093, Nanjing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Gu", 
            "givenName": "Guoyong", 
            "id": "sg:person.013653377411.69", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013653377411.69"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Nanjing University, 210093, Nanjing, China", 
              "id": "http://www.grid.ac/institutes/grid.41156.37", 
              "name": [
                "Department of Mathematics, Nanjing University, 210093, Nanjing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Junfeng", 
            "id": "sg:person.01221404563.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221404563.36"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-319-48311-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084688822", 
              "https://doi.org/10.1007/978-3-319-48311-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-013-0653-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000652377", 
              "https://doi.org/10.1007/s10107-013-0653-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-020-01770-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1132216534", 
              "https://doi.org/10.1007/s10957-020-01770-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11590-016-1087-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052065725", 
              "https://doi.org/10.1007/s11590-016-1087-4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10589-013-9616-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049661773", 
              "https://doi.org/10.1007/s10589-013-9616-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-015-0949-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026197562", 
              "https://doi.org/10.1007/s10107-015-0949-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-018-1298-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1103925104", 
              "https://doi.org/10.1007/s10957-018-1298-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10957-016-1018-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037939592", 
              "https://doi.org/10.1007/s10957-016-1018-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11590-020-01617-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1129136851", 
              "https://doi.org/10.1007/s11590-020-01617-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-007-0149-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016713895", 
              "https://doi.org/10.1007/s10107-007-0149-x"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/b97544", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029291821", 
              "https://doi.org/10.1007/b97544"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-021-01643-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1136616128", 
              "https://doi.org/10.1007/s10107-021-01643-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-016-0985-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025240589", 
              "https://doi.org/10.1007/s10107-016-0985-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10107-016-1009-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047457386", 
              "https://doi.org/10.1007/s10107-016-1009-3"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2022-07-02", 
        "datePublishedReg": "2022-07-02", 
        "description": "This paper considers the relaxed proximal point algorithm for solving monotone variational inequality problems, and our main contribution is the establishment of a tight ergodic sublinear convergence rate. First, the tight or exact worst-case convergence rate is computed using the performance estimation framework. It is observed that this numerical bound asymptotically coincides with the best-known existing rate, whose tightness is not clear. This implies that, without further assumptions, sublinear convergence rate is likely the best achievable rate for the relaxed proximal point algorithm. Motivated by the numerical result, a concrete example is constructed, which provides a lower bound on the exact worst-case convergence rate. This lower bound coincides with the numerical bound computed via the performance estimation framework, leading us to conjecture that the lower bound provided by the example is exactly the tight worse-case rate, which is then verified theoretically. We thus have established an ergodic sublinear complexity rate that is tight in terms of both the sublinear order and the constants involved.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10957-022-02058-3", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8128190", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.8132337", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1044187", 
            "issn": [
              "0022-3239", 
              "1573-2878"
            ], 
            "name": "Journal of Optimization Theory and Applications", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }
        ], 
        "keywords": [
          "performance estimation framework", 
          "estimation framework", 
          "numerical results", 
          "convergence rate", 
          "point algorithm", 
          "main contribution", 
          "algorithm", 
          "rate", 
          "achievable rate", 
          "example", 
          "further assumptions", 
          "order", 
          "sublinear convergence rate", 
          "results", 
          "problem", 
          "tightness", 
          "framework", 
          "constants", 
          "terms", 
          "concrete examples", 
          "assumption", 
          "worst-case rate", 
          "best achievable rate", 
          "complexity rate", 
          "contribution", 
          "coincide", 
          "inequality problem", 
          "variational inequalities", 
          "inequality", 
          "worst-case convergence rate", 
          "establishment", 
          "proximal point algorithm", 
          "variational inequality problem", 
          "monotone variational inequalities", 
          "monotone variational inequality problems", 
          "relaxed proximal point algorithm", 
          "paper", 
          "sublinear order"
        ], 
        "name": "Tight Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Monotone Variational Inequalities", 
        "pagination": "1-15", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1149183588"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10957-022-02058-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10957-022-02058-3", 
          "https://app.dimensions.ai/details/publication/pub.1149183588"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T16:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_940.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10957-022-02058-3"
      }
    ]
     

    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/s10957-022-02058-3'

    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/s10957-022-02058-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02058-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10957-022-02058-3'


     

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

    156 TRIPLES      21 PREDICATES      74 URIs      52 LITERALS      4 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10957-022-02058-3 schema:about anzsrc-for:09
    2 anzsrc-for:0906
    3 schema:author N7d4e36a718c04d9d9b0f4814e8e97863
    4 schema:citation sg:pub.10.1007/978-3-319-48311-5
    5 sg:pub.10.1007/b97544
    6 sg:pub.10.1007/s10107-007-0149-x
    7 sg:pub.10.1007/s10107-013-0653-0
    8 sg:pub.10.1007/s10107-015-0949-3
    9 sg:pub.10.1007/s10107-016-0985-7
    10 sg:pub.10.1007/s10107-016-1009-3
    11 sg:pub.10.1007/s10107-021-01643-0
    12 sg:pub.10.1007/s10589-013-9616-x
    13 sg:pub.10.1007/s10957-016-1018-7
    14 sg:pub.10.1007/s10957-018-1298-1
    15 sg:pub.10.1007/s10957-020-01770-2
    16 sg:pub.10.1007/s11590-016-1087-4
    17 sg:pub.10.1007/s11590-020-01617-9
    18 schema:datePublished 2022-07-02
    19 schema:datePublishedReg 2022-07-02
    20 schema:description This paper considers the relaxed proximal point algorithm for solving monotone variational inequality problems, and our main contribution is the establishment of a tight ergodic sublinear convergence rate. First, the tight or exact worst-case convergence rate is computed using the performance estimation framework. It is observed that this numerical bound asymptotically coincides with the best-known existing rate, whose tightness is not clear. This implies that, without further assumptions, sublinear convergence rate is likely the best achievable rate for the relaxed proximal point algorithm. Motivated by the numerical result, a concrete example is constructed, which provides a lower bound on the exact worst-case convergence rate. This lower bound coincides with the numerical bound computed via the performance estimation framework, leading us to conjecture that the lower bound provided by the example is exactly the tight worse-case rate, which is then verified theoretically. We thus have established an ergodic sublinear complexity rate that is tight in terms of both the sublinear order and the constants involved.
    21 schema:genre article
    22 schema:isAccessibleForFree false
    23 schema:isPartOf sg:journal.1044187
    24 schema:keywords achievable rate
    25 algorithm
    26 assumption
    27 best achievable rate
    28 coincide
    29 complexity rate
    30 concrete examples
    31 constants
    32 contribution
    33 convergence rate
    34 establishment
    35 estimation framework
    36 example
    37 framework
    38 further assumptions
    39 inequality
    40 inequality problem
    41 main contribution
    42 monotone variational inequalities
    43 monotone variational inequality problems
    44 numerical results
    45 order
    46 paper
    47 performance estimation framework
    48 point algorithm
    49 problem
    50 proximal point algorithm
    51 rate
    52 relaxed proximal point algorithm
    53 results
    54 sublinear convergence rate
    55 sublinear order
    56 terms
    57 tightness
    58 variational inequalities
    59 variational inequality problem
    60 worst-case convergence rate
    61 worst-case rate
    62 schema:name Tight Ergodic Sublinear Convergence Rate of the Relaxed Proximal Point Algorithm for Monotone Variational Inequalities
    63 schema:pagination 1-15
    64 schema:productId N4e170edd9fc04137ac94a0a253e8bf06
    65 N8d93606364634d889613b8d874ab50e6
    66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1149183588
    67 https://doi.org/10.1007/s10957-022-02058-3
    68 schema:sdDatePublished 2022-09-02T16:08
    69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    70 schema:sdPublisher N373c702e7cbe4c52bb7c3c3af314204d
    71 schema:url https://doi.org/10.1007/s10957-022-02058-3
    72 sgo:license sg:explorer/license/
    73 sgo:sdDataset articles
    74 rdf:type schema:ScholarlyArticle
    75 N373c702e7cbe4c52bb7c3c3af314204d schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 N4e170edd9fc04137ac94a0a253e8bf06 schema:name dimensions_id
    78 schema:value pub.1149183588
    79 rdf:type schema:PropertyValue
    80 N7d4e36a718c04d9d9b0f4814e8e97863 rdf:first sg:person.013653377411.69
    81 rdf:rest Nba751a307a4b445ebee573c5d6281ec0
    82 N8d93606364634d889613b8d874ab50e6 schema:name doi
    83 schema:value 10.1007/s10957-022-02058-3
    84 rdf:type schema:PropertyValue
    85 Nba751a307a4b445ebee573c5d6281ec0 rdf:first sg:person.01221404563.36
    86 rdf:rest rdf:nil
    87 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Engineering
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:0906 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Electrical and Electronic Engineering
    92 rdf:type schema:DefinedTerm
    93 sg:grant.8128190 http://pending.schema.org/fundedItem sg:pub.10.1007/s10957-022-02058-3
    94 rdf:type schema:MonetaryGrant
    95 sg:grant.8132337 http://pending.schema.org/fundedItem sg:pub.10.1007/s10957-022-02058-3
    96 rdf:type schema:MonetaryGrant
    97 sg:journal.1044187 schema:issn 0022-3239
    98 1573-2878
    99 schema:name Journal of Optimization Theory and Applications
    100 schema:publisher Springer Nature
    101 rdf:type schema:Periodical
    102 sg:person.01221404563.36 schema:affiliation grid-institutes:grid.41156.37
    103 schema:familyName Yang
    104 schema:givenName Junfeng
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01221404563.36
    106 rdf:type schema:Person
    107 sg:person.013653377411.69 schema:affiliation grid-institutes:grid.41156.37
    108 schema:familyName Gu
    109 schema:givenName Guoyong
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013653377411.69
    111 rdf:type schema:Person
    112 sg:pub.10.1007/978-3-319-48311-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084688822
    113 https://doi.org/10.1007/978-3-319-48311-5
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/b97544 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029291821
    116 https://doi.org/10.1007/b97544
    117 rdf:type schema:CreativeWork
    118 sg:pub.10.1007/s10107-007-0149-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1016713895
    119 https://doi.org/10.1007/s10107-007-0149-x
    120 rdf:type schema:CreativeWork
    121 sg:pub.10.1007/s10107-013-0653-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000652377
    122 https://doi.org/10.1007/s10107-013-0653-0
    123 rdf:type schema:CreativeWork
    124 sg:pub.10.1007/s10107-015-0949-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026197562
    125 https://doi.org/10.1007/s10107-015-0949-3
    126 rdf:type schema:CreativeWork
    127 sg:pub.10.1007/s10107-016-0985-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025240589
    128 https://doi.org/10.1007/s10107-016-0985-7
    129 rdf:type schema:CreativeWork
    130 sg:pub.10.1007/s10107-016-1009-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047457386
    131 https://doi.org/10.1007/s10107-016-1009-3
    132 rdf:type schema:CreativeWork
    133 sg:pub.10.1007/s10107-021-01643-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1136616128
    134 https://doi.org/10.1007/s10107-021-01643-0
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/s10589-013-9616-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1049661773
    137 https://doi.org/10.1007/s10589-013-9616-x
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/s10957-016-1018-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037939592
    140 https://doi.org/10.1007/s10957-016-1018-7
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/s10957-018-1298-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103925104
    143 https://doi.org/10.1007/s10957-018-1298-1
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/s10957-020-01770-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1132216534
    146 https://doi.org/10.1007/s10957-020-01770-2
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/s11590-016-1087-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052065725
    149 https://doi.org/10.1007/s11590-016-1087-4
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/s11590-020-01617-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1129136851
    152 https://doi.org/10.1007/s11590-020-01617-9
    153 rdf:type schema:CreativeWork
    154 grid-institutes:grid.41156.37 schema:alternateName Department of Mathematics, Nanjing University, 210093, Nanjing, China
    155 schema:name Department of Mathematics, Nanjing University, 210093, Nanjing, China
    156 rdf:type schema:Organization
     




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


    ...