A Central Limit Theorem for Algorithmic Estimator of Saddle Point Article Swipe
Abhishek Roy
,
Yi-An Ma
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2306.06305
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2306.06305
In this work, we study the asymptotic randomness of an algorithmic estimator of the saddle point of a globally convex-concave and locally strongly-convex strongly-concave objective. Specifically, we show that the averaged iterates of a Stochastic Extra-Gradient (SEG) method for a Saddle Point Problem (SPP) converges almost surely to the saddle point and follows a Central Limit Theorem (CLT) with optimal covariance under martingale-difference noise and the state(decision)-dependent Markov noise. To ensure the stability of the algorithm dynamics under the state-dependent Markov noise, we propose a variant of SEG with truncated varying sets. Interestingly, we show that a state-dependent Markovian data sequence can cause Stochastic Gradient Descent Ascent (SGDA) to diverge even if the target objective is strongly-convex strongly-concave. The main novelty of this work is establishing a CLT for SEG for a stochastic SPP, especially under sate-dependent Markov noise. This is the first step towards online inference of SPP with numerous potential applications including games, robust strategic classification, and reinforcement learning. We illustrate our results through numerical experiments.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2306.06305
- https://arxiv.org/pdf/2306.06305
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4380551315
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4380551315Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2306.06305Digital Object Identifier
- Title
-
A Central Limit Theorem for Algorithmic Estimator of Saddle PointWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-06-09Full publication date if available
- Authors
-
Abhishek Roy, Yi-An MaList of authors in order
- Landing page
-
https://arxiv.org/abs/2306.06305Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2306.06305Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2306.06305Direct OA link when available
- Concepts
-
Saddle point, Mathematics, Applied mathematics, Markov chain, Central limit theorem, Saddle, Mathematical optimization, Geometry, StatisticsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4380551315 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2306.06305 |
| ids.doi | https://doi.org/10.48550/arxiv.2306.06305 |
| ids.openalex | https://openalex.org/W4380551315 |
| fwci | |
| type | preprint |
| title | A Central Limit Theorem for Algorithmic Estimator of Saddle Point |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11612 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9994999766349792 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Stochastic Gradient Optimization Techniques |
| topics[1].id | https://openalex.org/T12101 |
| topics[1].field.id | https://openalex.org/fields/18 |
| topics[1].field.display_name | Decision Sciences |
| topics[1].score | 0.9990000128746033 |
| topics[1].domain.id | https://openalex.org/domains/2 |
| topics[1].domain.display_name | Social Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1803 |
| topics[1].subfield.display_name | Management Science and Operations Research |
| topics[1].display_name | Advanced Bandit Algorithms Research |
| topics[2].id | https://openalex.org/T12056 |
| topics[2].field.id | https://openalex.org/fields/26 |
| topics[2].field.display_name | Mathematics |
| topics[2].score | 0.9980000257492065 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2613 |
| topics[2].subfield.display_name | Statistics and Probability |
| topics[2].display_name | Markov Chains and Monte Carlo Methods |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2681867 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6743858456611633 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q690935 |
| concepts[0].display_name | Saddle point |
| concepts[1].id | https://openalex.org/C33923547 |
| concepts[1].level | 0 |
| concepts[1].score | 0.6463812589645386 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[1].display_name | Mathematics |
| concepts[2].id | https://openalex.org/C28826006 |
| concepts[2].level | 1 |
| concepts[2].score | 0.48358458280563354 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q33521 |
| concepts[2].display_name | Applied mathematics |
| concepts[3].id | https://openalex.org/C98763669 |
| concepts[3].level | 2 |
| concepts[3].score | 0.450736403465271 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q176645 |
| concepts[3].display_name | Markov chain |
| concepts[4].id | https://openalex.org/C166785042 |
| concepts[4].level | 2 |
| concepts[4].score | 0.44616594910621643 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q190391 |
| concepts[4].display_name | Central limit theorem |
| concepts[5].id | https://openalex.org/C2777127463 |
| concepts[5].level | 2 |
| concepts[5].score | 0.43371444940567017 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q10862618 |
| concepts[5].display_name | Saddle |
| concepts[6].id | https://openalex.org/C126255220 |
| concepts[6].level | 1 |
| concepts[6].score | 0.3592800796031952 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[6].display_name | Mathematical optimization |
| concepts[7].id | https://openalex.org/C2524010 |
| concepts[7].level | 1 |
| concepts[7].score | 0.07962650060653687 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[7].display_name | Geometry |
| concepts[8].id | https://openalex.org/C105795698 |
| concepts[8].level | 1 |
| concepts[8].score | 0.07333928346633911 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[8].display_name | Statistics |
| keywords[0].id | https://openalex.org/keywords/saddle-point |
| keywords[0].score | 0.6743858456611633 |
| keywords[0].display_name | Saddle point |
| keywords[1].id | https://openalex.org/keywords/mathematics |
| keywords[1].score | 0.6463812589645386 |
| keywords[1].display_name | Mathematics |
| keywords[2].id | https://openalex.org/keywords/applied-mathematics |
| keywords[2].score | 0.48358458280563354 |
| keywords[2].display_name | Applied mathematics |
| keywords[3].id | https://openalex.org/keywords/markov-chain |
| keywords[3].score | 0.450736403465271 |
| keywords[3].display_name | Markov chain |
| keywords[4].id | https://openalex.org/keywords/central-limit-theorem |
| keywords[4].score | 0.44616594910621643 |
| keywords[4].display_name | Central limit theorem |
| keywords[5].id | https://openalex.org/keywords/saddle |
| keywords[5].score | 0.43371444940567017 |
| keywords[5].display_name | Saddle |
| keywords[6].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[6].score | 0.3592800796031952 |
| keywords[6].display_name | Mathematical optimization |
| keywords[7].id | https://openalex.org/keywords/geometry |
| keywords[7].score | 0.07962650060653687 |
| keywords[7].display_name | Geometry |
| keywords[8].id | https://openalex.org/keywords/statistics |
| keywords[8].score | 0.07333928346633911 |
| keywords[8].display_name | Statistics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2306.06305 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2306.06305 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2306.06305 |
| locations[1].id | doi:10.48550/arxiv.2306.06305 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2306.06305 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5076362329 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-9272-6778 |
| authorships[0].author.display_name | Abhishek Roy |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Roy, Abhishek |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5041806431 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-6074-6638 |
| authorships[1].author.display_name | Yi-An Ma |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Ma, Yian |
| authorships[1].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2306.06305 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | A Central Limit Theorem for Algorithmic Estimator of Saddle Point |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11612 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9994999766349792 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Stochastic Gradient Optimization Techniques |
| related_works | https://openalex.org/W4236459141, https://openalex.org/W4205304778, https://openalex.org/W2020252434, https://openalex.org/W73248859, https://openalex.org/W2584253892, https://openalex.org/W2350324449, https://openalex.org/W1572705989, https://openalex.org/W119381072, https://openalex.org/W2034033896, https://openalex.org/W2087062149 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2306.06305 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2306.06305 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2306.06305 |
| primary_location.id | pmh:oai:arXiv.org:2306.06305 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2306.06305 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2306.06305 |
| publication_date | 2023-06-09 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 17, 33, 39, 53, 84, 96, 126, 131 |
| abstract_inverted_index.In | 0 |
| abstract_inverted_index.To | 69 |
| abstract_inverted_index.We | 161 |
| abstract_inverted_index.an | 9 |
| abstract_inverted_index.if | 111 |
| abstract_inverted_index.is | 115, 124, 140 |
| abstract_inverted_index.of | 8, 12, 16, 32, 73, 86, 121, 147 |
| abstract_inverted_index.to | 47, 108 |
| abstract_inverted_index.we | 3, 26, 82, 93 |
| abstract_inverted_index.CLT | 127 |
| abstract_inverted_index.SEG | 87, 129 |
| abstract_inverted_index.SPP | 148 |
| abstract_inverted_index.The | 118 |
| abstract_inverted_index.and | 20, 51, 64, 158 |
| abstract_inverted_index.can | 101 |
| abstract_inverted_index.for | 38, 128, 130 |
| abstract_inverted_index.our | 163 |
| abstract_inverted_index.the | 5, 13, 29, 48, 65, 71, 74, 78, 112, 141 |
| abstract_inverted_index.SPP, | 133 |
| abstract_inverted_index.This | 139 |
| abstract_inverted_index.data | 99 |
| abstract_inverted_index.even | 110 |
| abstract_inverted_index.main | 119 |
| abstract_inverted_index.show | 27, 94 |
| abstract_inverted_index.step | 143 |
| abstract_inverted_index.that | 28, 95 |
| abstract_inverted_index.this | 1, 122 |
| abstract_inverted_index.with | 58, 88, 149 |
| abstract_inverted_index.work | 123 |
| abstract_inverted_index.(CLT) | 57 |
| abstract_inverted_index.(SEG) | 36 |
| abstract_inverted_index.(SPP) | 43 |
| abstract_inverted_index.Limit | 55 |
| abstract_inverted_index.Point | 41 |
| abstract_inverted_index.cause | 102 |
| abstract_inverted_index.first | 142 |
| abstract_inverted_index.noise | 63 |
| abstract_inverted_index.point | 15, 50 |
| abstract_inverted_index.sets. | 91 |
| abstract_inverted_index.study | 4 |
| abstract_inverted_index.under | 61, 77, 135 |
| abstract_inverted_index.work, | 2 |
| abstract_inverted_index.(SGDA) | 107 |
| abstract_inverted_index.Ascent | 106 |
| abstract_inverted_index.Markov | 67, 80, 137 |
| abstract_inverted_index.Saddle | 40 |
| abstract_inverted_index.almost | 45 |
| abstract_inverted_index.ensure | 70 |
| abstract_inverted_index.games, | 154 |
| abstract_inverted_index.method | 37 |
| abstract_inverted_index.noise, | 81 |
| abstract_inverted_index.noise. | 68, 138 |
| abstract_inverted_index.online | 145 |
| abstract_inverted_index.robust | 155 |
| abstract_inverted_index.saddle | 14, 49 |
| abstract_inverted_index.surely | 46 |
| abstract_inverted_index.target | 113 |
| abstract_inverted_index.Central | 54 |
| abstract_inverted_index.Descent | 105 |
| abstract_inverted_index.Problem | 42 |
| abstract_inverted_index.Theorem | 56 |
| abstract_inverted_index.diverge | 109 |
| abstract_inverted_index.follows | 52 |
| abstract_inverted_index.locally | 21 |
| abstract_inverted_index.novelty | 120 |
| abstract_inverted_index.optimal | 59 |
| abstract_inverted_index.propose | 83 |
| abstract_inverted_index.results | 164 |
| abstract_inverted_index.through | 165 |
| abstract_inverted_index.towards | 144 |
| abstract_inverted_index.variant | 85 |
| abstract_inverted_index.varying | 90 |
| abstract_inverted_index.Gradient | 104 |
| abstract_inverted_index.averaged | 30 |
| abstract_inverted_index.dynamics | 76 |
| abstract_inverted_index.globally | 18 |
| abstract_inverted_index.iterates | 31 |
| abstract_inverted_index.numerous | 150 |
| abstract_inverted_index.sequence | 100 |
| abstract_inverted_index.Markovian | 98 |
| abstract_inverted_index.algorithm | 75 |
| abstract_inverted_index.converges | 44 |
| abstract_inverted_index.estimator | 11 |
| abstract_inverted_index.including | 153 |
| abstract_inverted_index.inference | 146 |
| abstract_inverted_index.learning. | 160 |
| abstract_inverted_index.numerical | 166 |
| abstract_inverted_index.objective | 114 |
| abstract_inverted_index.potential | 151 |
| abstract_inverted_index.stability | 72 |
| abstract_inverted_index.strategic | 156 |
| abstract_inverted_index.truncated | 89 |
| abstract_inverted_index.Stochastic | 34, 103 |
| abstract_inverted_index.asymptotic | 6 |
| abstract_inverted_index.covariance | 60 |
| abstract_inverted_index.especially | 134 |
| abstract_inverted_index.illustrate | 162 |
| abstract_inverted_index.objective. | 24 |
| abstract_inverted_index.randomness | 7 |
| abstract_inverted_index.stochastic | 132 |
| abstract_inverted_index.algorithmic | 10 |
| abstract_inverted_index.applications | 152 |
| abstract_inverted_index.establishing | 125 |
| abstract_inverted_index.experiments. | 167 |
| abstract_inverted_index.Specifically, | 25 |
| abstract_inverted_index.reinforcement | 159 |
| abstract_inverted_index.Extra-Gradient | 35 |
| abstract_inverted_index.Interestingly, | 92 |
| abstract_inverted_index.convex-concave | 19 |
| abstract_inverted_index.sate-dependent | 136 |
| abstract_inverted_index.classification, | 157 |
| abstract_inverted_index.state-dependent | 79, 97 |
| abstract_inverted_index.strongly-convex | 22, 116 |
| abstract_inverted_index.strongly-concave | 23 |
| abstract_inverted_index.strongly-concave. | 117 |
| abstract_inverted_index.martingale-difference | 62 |
| abstract_inverted_index.state(decision)-dependent | 66 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |