Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality Article Swipe
Yan Yu Hu
,
Zhao Peng
,
Zhou, Zhi-Hua
·
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2511.06597
YOU?
·
· 2025
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2511.06597
In this work, we study offline convex optimization with smooth objectives, where the classical Nesterov's Accelerated Gradient (NAG) method achieves the optimal accelerated convergence. Extensive research has aimed to understand NAG from various perspectives, and a recent line of work approaches this from the viewpoint of online learning and online-to-batch conversion, emphasizing the role of optimistic online algorithms for acceleration. In this work, we contribute to this perspective by proposing novel optimistic online-to-batch conversions that incorporate optimism theoretically into the analysis, thereby significantly simplifying the online algorithm design while preserving the optimal convergence rates. Specifically, we demonstrate the effectiveness of our conversions through the following results: (i) when combined with simple online gradient descent, our optimistic conversion achieves the optimal accelerated convergence; (ii) our conversion also applies to strongly convex objectives, and by leveraging both optimistic online-to-batch conversion and optimistic online algorithms, we achieve the optimal accelerated convergence rate for strongly convex and smooth objectives, for the first time through the lens of online-to-batch conversion; (iii) our optimistic conversion can achieve universality to smoothness -- applicable to both smooth and non-smooth objectives without requiring knowledge of the smoothness coefficient -- and remains efficient as non-universal methods by using only one gradient query in each iteration. Finally, we highlight the effectiveness of our optimistic online-to-batch conversions by a precise correspondence with NAG.
Related Topics
Concepts
Mathematical optimization
Smoothness
Computer science
Regular polygon
Universality (dynamical systems)
Convergence (economics)
Rate of convergence
Convex optimization
Mathematics
Algorithm
Applied mathematics
Online algorithm
Offline learning
Convex function
Dissimilation
Simple (philosophy)
Line search
Optimization problem
Perspective (graphical)
Matching (statistics)
Gradient method
Efficient algorithm
Gradient descent
Metadata
- Type
- preprint
- Landing Page
- https://doi.org/10.48550/arxiv.2511.06597
- OA Status
- green
- OpenAlex ID
- https://openalex.org/W7105004742
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W7105004742Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2511.06597Digital Object Identifier
- Title
-
Optimistic Online-to-Batch Conversions for Accelerated Convergence and UniversalityWork title
- Type
-
preprintOpenAlex work type
- Publication year
-
2025Year of publication
- Publication date
-
2025-11-10Full publication date if available
- Authors
-
Yan Yu Hu, Zhao Peng, Zhou, Zhi-HuaList of authors in order
- Landing page
-
https://doi.org/10.48550/arxiv.2511.06597Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://doi.org/10.48550/arxiv.2511.06597Direct OA link when available
- Concepts
-
Mathematical optimization, Smoothness, Computer science, Regular polygon, Universality (dynamical systems), Convergence (economics), Rate of convergence, Convex optimization, Mathematics, Algorithm, Applied mathematics, Online algorithm, Offline learning, Convex function, Dissimilation, Simple (philosophy), Line search, Optimization problem, Perspective (graphical), Matching (statistics), Gradient method, Efficient algorithm, Gradient descentTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
Full payload
| id | https://openalex.org/W7105004742 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2511.06597 |
| ids.doi | https://doi.org/10.48550/arxiv.2511.06597 |
| ids.openalex | https://openalex.org/W7105004742 |
| fwci | |
| type | preprint |
| title | Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C126255220 |
| concepts[0].level | 1 |
| concepts[0].score | 0.6354796886444092 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[0].display_name | Mathematical optimization |
| concepts[1].id | https://openalex.org/C102634674 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5881940126419067 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q868473 |
| concepts[1].display_name | Smoothness |
| concepts[2].id | https://openalex.org/C41008148 |
| concepts[2].level | 0 |
| concepts[2].score | 0.5626344680786133 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[2].display_name | Computer science |
| concepts[3].id | https://openalex.org/C112680207 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5602629780769348 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q714886 |
| concepts[3].display_name | Regular polygon |
| concepts[4].id | https://openalex.org/C183992945 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5370355844497681 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q2495574 |
| concepts[4].display_name | Universality (dynamical systems) |
| concepts[5].id | https://openalex.org/C2777303404 |
| concepts[5].level | 2 |
| concepts[5].score | 0.47731125354766846 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q759757 |
| concepts[5].display_name | Convergence (economics) |
| concepts[6].id | https://openalex.org/C57869625 |
| concepts[6].level | 3 |
| concepts[6].score | 0.4253866672515869 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q1783502 |
| concepts[6].display_name | Rate of convergence |
| concepts[7].id | https://openalex.org/C157972887 |
| concepts[7].level | 3 |
| concepts[7].score | 0.38846078515052795 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q463359 |
| concepts[7].display_name | Convex optimization |
| concepts[8].id | https://openalex.org/C33923547 |
| concepts[8].level | 0 |
| concepts[8].score | 0.3825438916683197 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[8].display_name | Mathematics |
| concepts[9].id | https://openalex.org/C11413529 |
| concepts[9].level | 1 |
| concepts[9].score | 0.3713816702365875 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[9].display_name | Algorithm |
| concepts[10].id | https://openalex.org/C28826006 |
| concepts[10].level | 1 |
| concepts[10].score | 0.3581197261810303 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q33521 |
| concepts[10].display_name | Applied mathematics |
| concepts[11].id | https://openalex.org/C196921405 |
| concepts[11].level | 2 |
| concepts[11].score | 0.334991455078125 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q786431 |
| concepts[11].display_name | Online algorithm |
| concepts[12].id | https://openalex.org/C2780490138 |
| concepts[12].level | 3 |
| concepts[12].score | 0.32833006978034973 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q7079636 |
| concepts[12].display_name | Offline learning |
| concepts[13].id | https://openalex.org/C145446738 |
| concepts[13].level | 3 |
| concepts[13].score | 0.3177259564399719 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q319913 |
| concepts[13].display_name | Convex function |
| concepts[14].id | https://openalex.org/C80316690 |
| concepts[14].level | 2 |
| concepts[14].score | 0.31718289852142334 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q755669 |
| concepts[14].display_name | Dissimilation |
| concepts[15].id | https://openalex.org/C2780586882 |
| concepts[15].level | 2 |
| concepts[15].score | 0.30589231848716736 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q7520643 |
| concepts[15].display_name | Simple (philosophy) |
| concepts[16].id | https://openalex.org/C85522705 |
| concepts[16].level | 3 |
| concepts[16].score | 0.2882642447948456 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q3278015 |
| concepts[16].display_name | Line search |
| concepts[17].id | https://openalex.org/C137836250 |
| concepts[17].level | 2 |
| concepts[17].score | 0.28565773367881775 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q984063 |
| concepts[17].display_name | Optimization problem |
| concepts[18].id | https://openalex.org/C12713177 |
| concepts[18].level | 2 |
| concepts[18].score | 0.2787061333656311 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q1900281 |
| concepts[18].display_name | Perspective (graphical) |
| concepts[19].id | https://openalex.org/C165064840 |
| concepts[19].level | 2 |
| concepts[19].score | 0.26859304308891296 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q1321061 |
| concepts[19].display_name | Matching (statistics) |
| concepts[20].id | https://openalex.org/C115680565 |
| concepts[20].level | 2 |
| concepts[20].score | 0.26076388359069824 |
| concepts[20].wikidata | https://www.wikidata.org/wiki/Q5977448 |
| concepts[20].display_name | Gradient method |
| concepts[21].id | https://openalex.org/C3018263672 |
| concepts[21].level | 2 |
| concepts[21].score | 0.26069003343582153 |
| concepts[21].wikidata | https://www.wikidata.org/wiki/Q1296251 |
| concepts[21].display_name | Efficient algorithm |
| concepts[22].id | https://openalex.org/C153258448 |
| concepts[22].level | 3 |
| concepts[22].score | 0.26044508814811707 |
| concepts[22].wikidata | https://www.wikidata.org/wiki/Q1199743 |
| concepts[22].display_name | Gradient descent |
| keywords[0].id | https://openalex.org/keywords/smoothness |
| keywords[0].score | 0.5881940126419067 |
| keywords[0].display_name | Smoothness |
| keywords[1].id | https://openalex.org/keywords/regular-polygon |
| keywords[1].score | 0.5602629780769348 |
| keywords[1].display_name | Regular polygon |
| keywords[2].id | https://openalex.org/keywords/universality |
| keywords[2].score | 0.5370355844497681 |
| keywords[2].display_name | Universality (dynamical systems) |
| keywords[3].id | https://openalex.org/keywords/convergence |
| keywords[3].score | 0.47731125354766846 |
| keywords[3].display_name | Convergence (economics) |
| keywords[4].id | https://openalex.org/keywords/rate-of-convergence |
| keywords[4].score | 0.4253866672515869 |
| keywords[4].display_name | Rate of convergence |
| keywords[5].id | https://openalex.org/keywords/convex-optimization |
| keywords[5].score | 0.38846078515052795 |
| keywords[5].display_name | Convex optimization |
| keywords[6].id | https://openalex.org/keywords/online-algorithm |
| keywords[6].score | 0.334991455078125 |
| keywords[6].display_name | Online algorithm |
| keywords[7].id | https://openalex.org/keywords/offline-learning |
| keywords[7].score | 0.32833006978034973 |
| keywords[7].display_name | Offline learning |
| language | |
| locations[0].id | doi:10.48550/arxiv.2511.06597 |
| 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 | |
| locations[0].version | |
| locations[0].raw_type | article |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://doi.org/10.48550/arxiv.2511.06597 |
| indexed_in | datacite |
| authorships[0].author.id | https://openalex.org/A2499081064 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Yan Yu Hu |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Yan, Yu-Hu |
| authorships[0].is_corresponding | True |
| authorships[1].author.id | https://openalex.org/A2102656079 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-2420-5567 |
| authorships[1].author.display_name | Zhao Peng |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Zhao, Peng |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A4225911639 |
| authorships[2].author.orcid | |
| authorships[2].author.display_name | Zhou, Zhi-Hua |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Zhou, Zhi-Hua |
| authorships[2].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://doi.org/10.48550/arxiv.2511.06597 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-11-12T00:00:00 |
| display_name | Optimistic Online-to-Batch Conversions for Accelerated Convergence and Universality |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-12T23:15:19.534421 |
| primary_topic | |
| cited_by_count | 0 |
| locations_count | 1 |
| best_oa_location.id | doi:10.48550/arxiv.2511.06597 |
| 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 | |
| best_oa_location.version | |
| best_oa_location.raw_type | article |
| 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 | https://doi.org/10.48550/arxiv.2511.06597 |
| primary_location.id | doi:10.48550/arxiv.2511.06597 |
| 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 | |
| primary_location.version | |
| primary_location.raw_type | article |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://doi.org/10.48550/arxiv.2511.06597 |
| publication_date | 2025-11-10 |
| publication_year | 2025 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 35, 216 |
| abstract_inverted_index.-- | 174, 189 |
| abstract_inverted_index.In | 0, 60 |
| abstract_inverted_index.as | 193 |
| abstract_inverted_index.by | 68, 132, 196, 215 |
| abstract_inverted_index.in | 202 |
| abstract_inverted_index.of | 38, 45, 54, 99, 162, 185, 210 |
| abstract_inverted_index.to | 28, 65, 127, 172, 176 |
| abstract_inverted_index.we | 3, 63, 95, 142, 206 |
| abstract_inverted_index.(i) | 106 |
| abstract_inverted_index.NAG | 30 |
| abstract_inverted_index.and | 34, 48, 131, 138, 152, 179, 190 |
| abstract_inverted_index.can | 169 |
| abstract_inverted_index.for | 58, 149, 155 |
| abstract_inverted_index.has | 26 |
| abstract_inverted_index.one | 199 |
| abstract_inverted_index.our | 100, 114, 123, 166, 211 |
| abstract_inverted_index.the | 12, 20, 43, 52, 79, 84, 90, 97, 103, 118, 144, 156, 160, 186, 208 |
| abstract_inverted_index.(ii) | 122 |
| abstract_inverted_index.NAG. | 220 |
| abstract_inverted_index.also | 125 |
| abstract_inverted_index.both | 134, 177 |
| abstract_inverted_index.each | 203 |
| abstract_inverted_index.from | 31, 42 |
| abstract_inverted_index.into | 78 |
| abstract_inverted_index.lens | 161 |
| abstract_inverted_index.line | 37 |
| abstract_inverted_index.only | 198 |
| abstract_inverted_index.rate | 148 |
| abstract_inverted_index.role | 53 |
| abstract_inverted_index.that | 74 |
| abstract_inverted_index.this | 1, 41, 61, 66 |
| abstract_inverted_index.time | 158 |
| abstract_inverted_index.when | 107 |
| abstract_inverted_index.with | 8, 109, 219 |
| abstract_inverted_index.work | 39 |
| abstract_inverted_index.(NAG) | 17 |
| abstract_inverted_index.(iii) | 165 |
| abstract_inverted_index.aimed | 27 |
| abstract_inverted_index.first | 157 |
| abstract_inverted_index.novel | 70 |
| abstract_inverted_index.query | 201 |
| abstract_inverted_index.study | 4 |
| abstract_inverted_index.using | 197 |
| abstract_inverted_index.where | 11 |
| abstract_inverted_index.while | 88 |
| abstract_inverted_index.work, | 2, 62 |
| abstract_inverted_index.convex | 6, 129, 151 |
| abstract_inverted_index.design | 87 |
| abstract_inverted_index.method | 18 |
| abstract_inverted_index.online | 46, 56, 85, 111, 140 |
| abstract_inverted_index.rates. | 93 |
| abstract_inverted_index.recent | 36 |
| abstract_inverted_index.simple | 110 |
| abstract_inverted_index.smooth | 9, 153, 178 |
| abstract_inverted_index.achieve | 143, 170 |
| abstract_inverted_index.applies | 126 |
| abstract_inverted_index.methods | 195 |
| abstract_inverted_index.offline | 5 |
| abstract_inverted_index.optimal | 21, 91, 119, 145 |
| abstract_inverted_index.precise | 217 |
| abstract_inverted_index.remains | 191 |
| abstract_inverted_index.thereby | 81 |
| abstract_inverted_index.through | 102, 159 |
| abstract_inverted_index.various | 32 |
| abstract_inverted_index.without | 182 |
| abstract_inverted_index.Finally, | 205 |
| abstract_inverted_index.Gradient | 16 |
| abstract_inverted_index.achieves | 19, 117 |
| abstract_inverted_index.combined | 108 |
| abstract_inverted_index.descent, | 113 |
| abstract_inverted_index.gradient | 112, 200 |
| abstract_inverted_index.learning | 47 |
| abstract_inverted_index.optimism | 76 |
| abstract_inverted_index.research | 25 |
| abstract_inverted_index.results: | 105 |
| abstract_inverted_index.strongly | 128, 150 |
| abstract_inverted_index.Extensive | 24 |
| abstract_inverted_index.algorithm | 86 |
| abstract_inverted_index.analysis, | 80 |
| abstract_inverted_index.classical | 13 |
| abstract_inverted_index.efficient | 192 |
| abstract_inverted_index.following | 104 |
| abstract_inverted_index.highlight | 207 |
| abstract_inverted_index.knowledge | 184 |
| abstract_inverted_index.proposing | 69 |
| abstract_inverted_index.requiring | 183 |
| abstract_inverted_index.viewpoint | 44 |
| abstract_inverted_index.Nesterov's | 14 |
| abstract_inverted_index.algorithms | 57 |
| abstract_inverted_index.applicable | 175 |
| abstract_inverted_index.approaches | 40 |
| abstract_inverted_index.contribute | 64 |
| abstract_inverted_index.conversion | 116, 124, 137, 168 |
| abstract_inverted_index.iteration. | 204 |
| abstract_inverted_index.leveraging | 133 |
| abstract_inverted_index.non-smooth | 180 |
| abstract_inverted_index.objectives | 181 |
| abstract_inverted_index.optimistic | 55, 71, 115, 135, 139, 167, 212 |
| abstract_inverted_index.preserving | 89 |
| abstract_inverted_index.smoothness | 173, 187 |
| abstract_inverted_index.understand | 29 |
| abstract_inverted_index.Accelerated | 15 |
| abstract_inverted_index.accelerated | 22, 120, 146 |
| abstract_inverted_index.algorithms, | 141 |
| abstract_inverted_index.coefficient | 188 |
| abstract_inverted_index.convergence | 92, 147 |
| abstract_inverted_index.conversion, | 50 |
| abstract_inverted_index.conversion; | 164 |
| abstract_inverted_index.conversions | 73, 101, 214 |
| abstract_inverted_index.demonstrate | 96 |
| abstract_inverted_index.emphasizing | 51 |
| abstract_inverted_index.incorporate | 75 |
| abstract_inverted_index.objectives, | 10, 130, 154 |
| abstract_inverted_index.perspective | 67 |
| abstract_inverted_index.simplifying | 83 |
| abstract_inverted_index.convergence. | 23 |
| abstract_inverted_index.convergence; | 121 |
| abstract_inverted_index.optimization | 7 |
| abstract_inverted_index.universality | 171 |
| abstract_inverted_index.Specifically, | 94 |
| abstract_inverted_index.acceleration. | 59 |
| abstract_inverted_index.effectiveness | 98, 209 |
| abstract_inverted_index.non-universal | 194 |
| abstract_inverted_index.perspectives, | 33 |
| abstract_inverted_index.significantly | 82 |
| abstract_inverted_index.theoretically | 77 |
| abstract_inverted_index.correspondence | 218 |
| abstract_inverted_index.online-to-batch | 49, 72, 136, 163, 213 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |