Federated Minimax Optimization with Client Heterogeneity Article Swipe
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2302.04249
Minimax optimization has seen a surge in interest with the advent of modern applications such as GANs, and it is inherently more challenging than simple minimization. The difficulty is exacerbated by the training data residing at multiple edge devices or \textit{clients}, especially when these clients can have heterogeneous datasets and local computation capabilities. We propose a general federated minimax optimization framework that subsumes such settings and several existing methods like Local SGDA. We show that naive aggregation of heterogeneous local progress results in optimizing a mismatched objective function -- a phenomenon previously observed in standard federated minimization. To fix this problem, we propose normalizing the client updates by the number of local steps undertaken between successive communication rounds. We analyze the convergence of the proposed algorithm for classes of nonconvex-concave and nonconvex-nonconcave functions and characterize the impact of heterogeneous client data, partial client participation, and heterogeneous local computations. Our analysis works under more general assumptions on the intra-client noise and inter-client heterogeneity than so far considered in the literature. For all the function classes considered, we significantly improve the existing computation and communication complexity results. Experimental results support our theoretical claims.
Related Topics
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2302.04249
- https://arxiv.org/pdf/2302.04249
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4320342275
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4320342275Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2302.04249Digital Object Identifier
- Title
-
Federated Minimax Optimization with Client HeterogeneityWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-02-08Full publication date if available
- Authors
-
Pranay Sharma, Rohan Panda, Gauri JoshiList of authors in order
- Landing page
-
https://arxiv.org/abs/2302.04249Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2302.04249Direct 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/2302.04249Direct OA link when available
- Concepts
-
Minimax, Computer science, Computation, Minification, Mathematical optimization, Convergence (economics), Enhanced Data Rates for GSM Evolution, Function (biology), Algorithm, Artificial intelligence, Mathematics, Programming language, Evolutionary biology, Economics, Biology, Economic growthTop 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/W4320342275 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2302.04249 |
| ids.doi | https://doi.org/10.48550/arxiv.2302.04249 |
| ids.openalex | https://openalex.org/W4320342275 |
| fwci | |
| type | preprint |
| title | Federated Minimax Optimization with Client Heterogeneity |
| 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.9977999925613403 |
| 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/T10273 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9740999937057495 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1705 |
| topics[1].subfield.display_name | Computer Networks and Communications |
| topics[1].display_name | IoT and Edge/Fog Computing |
| topics[2].id | https://openalex.org/T11478 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9735999703407288 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Caching and Content Delivery |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C149728462 |
| concepts[0].level | 2 |
| concepts[0].score | 0.856255292892456 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q751319 |
| concepts[0].display_name | Minimax |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.792488694190979 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C45374587 |
| concepts[2].level | 2 |
| concepts[2].score | 0.7206307649612427 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q12525525 |
| concepts[2].display_name | Computation |
| concepts[3].id | https://openalex.org/C147764199 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5924367904663086 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q6865248 |
| concepts[3].display_name | Minification |
| concepts[4].id | https://openalex.org/C126255220 |
| concepts[4].level | 1 |
| concepts[4].score | 0.5371435880661011 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[4].display_name | Mathematical optimization |
| concepts[5].id | https://openalex.org/C2777303404 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5243844389915466 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q759757 |
| concepts[5].display_name | Convergence (economics) |
| concepts[6].id | https://openalex.org/C162307627 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5103067755699158 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q204833 |
| concepts[6].display_name | Enhanced Data Rates for GSM Evolution |
| concepts[7].id | https://openalex.org/C14036430 |
| concepts[7].level | 2 |
| concepts[7].score | 0.5077782273292542 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q3736076 |
| concepts[7].display_name | Function (biology) |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.2794169783592224 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C154945302 |
| concepts[9].level | 1 |
| concepts[9].score | 0.21620261669158936 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[9].display_name | Artificial intelligence |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.12338045239448547 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C199360897 |
| concepts[11].level | 1 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[11].display_name | Programming language |
| concepts[12].id | https://openalex.org/C78458016 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q840400 |
| concepts[12].display_name | Evolutionary biology |
| concepts[13].id | https://openalex.org/C162324750 |
| concepts[13].level | 0 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q8134 |
| concepts[13].display_name | Economics |
| concepts[14].id | https://openalex.org/C86803240 |
| concepts[14].level | 0 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q420 |
| concepts[14].display_name | Biology |
| concepts[15].id | https://openalex.org/C50522688 |
| concepts[15].level | 1 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q189833 |
| concepts[15].display_name | Economic growth |
| keywords[0].id | https://openalex.org/keywords/minimax |
| keywords[0].score | 0.856255292892456 |
| keywords[0].display_name | Minimax |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.792488694190979 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/computation |
| keywords[2].score | 0.7206307649612427 |
| keywords[2].display_name | Computation |
| keywords[3].id | https://openalex.org/keywords/minification |
| keywords[3].score | 0.5924367904663086 |
| keywords[3].display_name | Minification |
| keywords[4].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[4].score | 0.5371435880661011 |
| keywords[4].display_name | Mathematical optimization |
| keywords[5].id | https://openalex.org/keywords/convergence |
| keywords[5].score | 0.5243844389915466 |
| keywords[5].display_name | Convergence (economics) |
| keywords[6].id | https://openalex.org/keywords/enhanced-data-rates-for-gsm-evolution |
| keywords[6].score | 0.5103067755699158 |
| keywords[6].display_name | Enhanced Data Rates for GSM Evolution |
| keywords[7].id | https://openalex.org/keywords/function |
| keywords[7].score | 0.5077782273292542 |
| keywords[7].display_name | Function (biology) |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.2794169783592224 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[9].score | 0.21620261669158936 |
| keywords[9].display_name | Artificial intelligence |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.12338045239448547 |
| keywords[10].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2302.04249 |
| 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/2302.04249 |
| 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/2302.04249 |
| locations[1].id | doi:10.48550/arxiv.2302.04249 |
| 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 | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| 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.2302.04249 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5028196076 |
| authorships[0].author.orcid | https://orcid.org/0009-0007-8027-7913 |
| authorships[0].author.display_name | Pranay Sharma |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Sharma, Pranay |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5058974480 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Rohan Panda |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Panda, Rohan |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5067441201 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-6372-9697 |
| authorships[2].author.display_name | Gauri Joshi |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Joshi, Gauri |
| 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://arxiv.org/pdf/2302.04249 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Federated Minimax Optimization with Client Heterogeneity |
| 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.9977999925613403 |
| 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/W2016058626, https://openalex.org/W2474724840, https://openalex.org/W2895916002, https://openalex.org/W1814049089, https://openalex.org/W1977348009, https://openalex.org/W2369683208, https://openalex.org/W2084836983, https://openalex.org/W1530911128, https://openalex.org/W1555347637, https://openalex.org/W2362133437 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2302.04249 |
| 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/2302.04249 |
| 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/2302.04249 |
| primary_location.id | pmh:oai:arXiv.org:2302.04249 |
| 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/2302.04249 |
| 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/2302.04249 |
| publication_date | 2023-02-08 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 4, 55, 84, 89 |
| abstract_inverted_index.-- | 88 |
| abstract_inverted_index.To | 97 |
| abstract_inverted_index.We | 53, 72, 118 |
| abstract_inverted_index.as | 15 |
| abstract_inverted_index.at | 35 |
| abstract_inverted_index.by | 30, 107 |
| abstract_inverted_index.in | 6, 82, 93, 166 |
| abstract_inverted_index.is | 19, 28 |
| abstract_inverted_index.it | 18 |
| abstract_inverted_index.of | 11, 77, 110, 122, 128, 137 |
| abstract_inverted_index.on | 155 |
| abstract_inverted_index.or | 39 |
| abstract_inverted_index.so | 163 |
| abstract_inverted_index.we | 101, 175 |
| abstract_inverted_index.For | 169 |
| abstract_inverted_index.Our | 148 |
| abstract_inverted_index.The | 26 |
| abstract_inverted_index.all | 170 |
| abstract_inverted_index.and | 17, 49, 65, 130, 133, 144, 159, 181 |
| abstract_inverted_index.can | 45 |
| abstract_inverted_index.far | 164 |
| abstract_inverted_index.fix | 98 |
| abstract_inverted_index.for | 126 |
| abstract_inverted_index.has | 2 |
| abstract_inverted_index.our | 188 |
| abstract_inverted_index.the | 9, 31, 104, 108, 120, 123, 135, 156, 167, 171, 178 |
| abstract_inverted_index.data | 33 |
| abstract_inverted_index.edge | 37 |
| abstract_inverted_index.have | 46 |
| abstract_inverted_index.like | 69 |
| abstract_inverted_index.more | 21, 152 |
| abstract_inverted_index.seen | 3 |
| abstract_inverted_index.show | 73 |
| abstract_inverted_index.such | 14, 63 |
| abstract_inverted_index.than | 23, 162 |
| abstract_inverted_index.that | 61, 74 |
| abstract_inverted_index.this | 99 |
| abstract_inverted_index.when | 42 |
| abstract_inverted_index.with | 8 |
| abstract_inverted_index.GANs, | 16 |
| abstract_inverted_index.Local | 70 |
| abstract_inverted_index.SGDA. | 71 |
| abstract_inverted_index.data, | 140 |
| abstract_inverted_index.local | 50, 79, 111, 146 |
| abstract_inverted_index.naive | 75 |
| abstract_inverted_index.noise | 158 |
| abstract_inverted_index.steps | 112 |
| abstract_inverted_index.surge | 5 |
| abstract_inverted_index.these | 43 |
| abstract_inverted_index.under | 151 |
| abstract_inverted_index.works | 150 |
| abstract_inverted_index.advent | 10 |
| abstract_inverted_index.client | 105, 139, 142 |
| abstract_inverted_index.impact | 136 |
| abstract_inverted_index.modern | 12 |
| abstract_inverted_index.number | 109 |
| abstract_inverted_index.simple | 24 |
| abstract_inverted_index.Minimax | 0 |
| abstract_inverted_index.analyze | 119 |
| abstract_inverted_index.between | 114 |
| abstract_inverted_index.claims. | 190 |
| abstract_inverted_index.classes | 127, 173 |
| abstract_inverted_index.clients | 44 |
| abstract_inverted_index.devices | 38 |
| abstract_inverted_index.general | 56, 153 |
| abstract_inverted_index.improve | 177 |
| abstract_inverted_index.methods | 68 |
| abstract_inverted_index.minimax | 58 |
| abstract_inverted_index.partial | 141 |
| abstract_inverted_index.propose | 54, 102 |
| abstract_inverted_index.results | 81, 186 |
| abstract_inverted_index.rounds. | 117 |
| abstract_inverted_index.several | 66 |
| abstract_inverted_index.support | 187 |
| abstract_inverted_index.updates | 106 |
| abstract_inverted_index.analysis | 149 |
| abstract_inverted_index.datasets | 48 |
| abstract_inverted_index.existing | 67, 179 |
| abstract_inverted_index.function | 87, 172 |
| abstract_inverted_index.interest | 7 |
| abstract_inverted_index.multiple | 36 |
| abstract_inverted_index.observed | 92 |
| abstract_inverted_index.problem, | 100 |
| abstract_inverted_index.progress | 80 |
| abstract_inverted_index.proposed | 124 |
| abstract_inverted_index.residing | 34 |
| abstract_inverted_index.results. | 184 |
| abstract_inverted_index.settings | 64 |
| abstract_inverted_index.standard | 94 |
| abstract_inverted_index.subsumes | 62 |
| abstract_inverted_index.training | 32 |
| abstract_inverted_index.algorithm | 125 |
| abstract_inverted_index.federated | 57, 95 |
| abstract_inverted_index.framework | 60 |
| abstract_inverted_index.functions | 132 |
| abstract_inverted_index.objective | 86 |
| abstract_inverted_index.complexity | 183 |
| abstract_inverted_index.considered | 165 |
| abstract_inverted_index.difficulty | 27 |
| abstract_inverted_index.especially | 41 |
| abstract_inverted_index.inherently | 20 |
| abstract_inverted_index.mismatched | 85 |
| abstract_inverted_index.optimizing | 83 |
| abstract_inverted_index.phenomenon | 90 |
| abstract_inverted_index.previously | 91 |
| abstract_inverted_index.successive | 115 |
| abstract_inverted_index.undertaken | 113 |
| abstract_inverted_index.aggregation | 76 |
| abstract_inverted_index.assumptions | 154 |
| abstract_inverted_index.challenging | 22 |
| abstract_inverted_index.computation | 51, 180 |
| abstract_inverted_index.considered, | 174 |
| abstract_inverted_index.convergence | 121 |
| abstract_inverted_index.exacerbated | 29 |
| abstract_inverted_index.literature. | 168 |
| abstract_inverted_index.normalizing | 103 |
| abstract_inverted_index.theoretical | 189 |
| abstract_inverted_index.Experimental | 185 |
| abstract_inverted_index.applications | 13 |
| abstract_inverted_index.characterize | 134 |
| abstract_inverted_index.inter-client | 160 |
| abstract_inverted_index.intra-client | 157 |
| abstract_inverted_index.optimization | 1, 59 |
| abstract_inverted_index.capabilities. | 52 |
| abstract_inverted_index.communication | 116, 182 |
| abstract_inverted_index.computations. | 147 |
| abstract_inverted_index.heterogeneity | 161 |
| abstract_inverted_index.heterogeneous | 47, 78, 138, 145 |
| abstract_inverted_index.minimization. | 25, 96 |
| abstract_inverted_index.significantly | 176 |
| abstract_inverted_index.participation, | 143 |
| abstract_inverted_index.\textit{clients}, | 40 |
| abstract_inverted_index.nonconvex-concave | 129 |
| abstract_inverted_index.nonconvex-nonconcave | 131 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |