Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization Article Swipe

PDF

Ronak Mehta , Jelena Diakonikolas , Zaïd Harchaoui ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2403.10763

We consider the penalized distributionally robust optimization (DRO) problem with a closed, convex uncertainty set, a setting that encompasses learning using $f$-DRO and spectral/$L$-risk minimization. We present Drago, a stochastic primal-dual algorithm that combines cyclic and randomized components with a carefully regularized primal update to achieve dual variance reduction. Owing to its design, Drago enjoys a state-of-the-art linear convergence rate on strongly convex-strongly concave DRO problems with a fine-grained dependency on primal and dual condition numbers. Theoretical results are supported by numerical benchmarks on regression and classification tasks.

Related Topics

Concepts

Dual (grammatical number) Mathematical optimization Computer science Robust optimization Optimization algorithm Algorithm Mathematics Art Literature

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2403.10763
PDF: https://arxiv.org/pdf/2403.10763
OA Status: green
Related Works: 10
OpenAlex ID: https://openalex.org/W4393023566

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4393023566

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2403.10763

Digital Object Identifier
Title: Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-03-16

Full publication date if available
Authors: Ronak Mehta, Jelena Diakonikolas, Zaïd Harchaoui

List of authors in order
Landing page: https://arxiv.org/abs/2403.10763

Publisher landing page
PDF URL: https://arxiv.org/pdf/2403.10763

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2403.10763

Direct OA link when available
Concepts: Dual (grammatical number), Mathematical optimization, Computer science, Robust optimization, Optimization algorithm, Algorithm, Mathematics, Art, Literature

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4393023566
doi	https://doi.org/10.48550/arxiv.2403.10763
ids.doi	https://doi.org/10.48550/arxiv.2403.10763
ids.openalex	https://openalex.org/W4393023566
fwci
type	preprint
title	Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T11814
topics[0].field.id	https://openalex.org/fields/22
topics[0].field.display_name	Engineering
topics[0].score	0.9465000033378601
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2209
topics[0].subfield.display_name	Industrial and Manufacturing Engineering
topics[0].display_name	Advanced Manufacturing and Logistics Optimization
topics[1].id	https://openalex.org/T10876
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.9210000038146973
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2207
topics[1].subfield.display_name	Control and Systems Engineering
topics[1].display_name	Fault Detection and Control Systems
topics[2].id	https://openalex.org/T10791
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9194999933242798
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2207
topics[2].subfield.display_name	Control and Systems Engineering
topics[2].display_name	Advanced Control Systems Optimization
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C2780980858
concepts[0].level	2
concepts[0].score	0.7087341547012329
concepts[0].wikidata	https://www.wikidata.org/wiki/Q110022
concepts[0].display_name	Dual (grammatical number)
concepts[1].id	https://openalex.org/C126255220
concepts[1].level	1
concepts[1].score	0.6066780090332031
concepts[1].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[1].display_name	Mathematical optimization
concepts[2].id	https://openalex.org/C41008148
concepts[2].level	0
concepts[2].score	0.5820461511611938
concepts[2].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[2].display_name	Computer science
concepts[3].id	https://openalex.org/C193254401
concepts[3].level	2
concepts[3].score	0.5725851058959961
concepts[3].wikidata	https://www.wikidata.org/wiki/Q2160088
concepts[3].display_name	Robust optimization
concepts[4].id	https://openalex.org/C2987595161
concepts[4].level	2
concepts[4].score	0.49276497960090637
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[4].display_name	Optimization algorithm
concepts[5].id	https://openalex.org/C11413529
concepts[5].level	1
concepts[5].score	0.45991435647010803
concepts[5].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[5].display_name	Algorithm
concepts[6].id	https://openalex.org/C33923547
concepts[6].level	0
concepts[6].score	0.21480852365493774
concepts[6].wikidata	https://www.wikidata.org/wiki/Q395
concepts[6].display_name	Mathematics
concepts[7].id	https://openalex.org/C142362112
concepts[7].level	0
concepts[7].score	0.0
concepts[7].wikidata	https://www.wikidata.org/wiki/Q735
concepts[7].display_name	Art
concepts[8].id	https://openalex.org/C124952713
concepts[8].level	1
concepts[8].score	0.0
concepts[8].wikidata	https://www.wikidata.org/wiki/Q8242
concepts[8].display_name	Literature
keywords[0].id	https://openalex.org/keywords/dual
keywords[0].score	0.7087341547012329
keywords[0].display_name	Dual (grammatical number)
keywords[1].id	https://openalex.org/keywords/mathematical-optimization
keywords[1].score	0.6066780090332031
keywords[1].display_name	Mathematical optimization
keywords[2].id	https://openalex.org/keywords/computer-science
keywords[2].score	0.5820461511611938
keywords[2].display_name	Computer science
keywords[3].id	https://openalex.org/keywords/robust-optimization
keywords[3].score	0.5725851058959961
keywords[3].display_name	Robust optimization
keywords[4].id	https://openalex.org/keywords/optimization-algorithm
keywords[4].score	0.49276497960090637
keywords[4].display_name	Optimization algorithm
keywords[5].id	https://openalex.org/keywords/algorithm
keywords[5].score	0.45991435647010803
keywords[5].display_name	Algorithm
keywords[6].id	https://openalex.org/keywords/mathematics
keywords[6].score	0.21480852365493774
keywords[6].display_name	Mathematics
language	en
locations[0].id	pmh:oai:arXiv.org:2403.10763
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/2403.10763
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/2403.10763
locations[1].id	doi:10.48550/arxiv.2403.10763
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.2403.10763
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5001083519
authorships[0].author.orcid
authorships[0].author.display_name	Ronak Mehta
authorships[0].author_position	first
authorships[0].raw_author_name	Mehta, Ronak
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5076054793
authorships[1].author.orcid	https://orcid.org/0000-0003-3439-0310
authorships[1].author.display_name	Jelena Diakonikolas
authorships[1].author_position	middle
authorships[1].raw_author_name	Diakonikolas, Jelena
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5010613767
authorships[2].author.orcid	https://orcid.org/0000-0003-1186-1343
authorships[2].author.display_name	Zaïd Harchaoui
authorships[2].author_position	last
authorships[2].raw_author_name	Harchaoui, Zaid
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/2403.10763
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2024-03-21T00:00:00
display_name	Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T11814
primary_topic.field.id	https://openalex.org/fields/22
primary_topic.field.display_name	Engineering
primary_topic.score	0.9465000033378601
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2209
primary_topic.subfield.display_name	Industrial and Manufacturing Engineering
primary_topic.display_name	Advanced Manufacturing and Logistics Optimization
related_works	https://openalex.org/W3005017983, https://openalex.org/W2205708137, https://openalex.org/W3182145356, https://openalex.org/W3212504317, https://openalex.org/W1988872022, https://openalex.org/W2224558845, https://openalex.org/W4366549320, https://openalex.org/W4287863136, https://openalex.org/W3028487898, https://openalex.org/W3173431235
cited_by_count	0
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2403.10763
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/2403.10763
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/2403.10763
primary_location.id	pmh:oai:arXiv.org:2403.10763
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/2403.10763
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/2403.10763
publication_date	2024-03-16
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	10, 15, 28, 39, 55, 67
abstract_inverted_index.We	0, 25
abstract_inverted_index.by	80
abstract_inverted_index.on	60, 70, 83
abstract_inverted_index.to	44, 50
abstract_inverted_index.DRO	64
abstract_inverted_index.and	22, 35, 72, 85
abstract_inverted_index.are	78
abstract_inverted_index.its	51
abstract_inverted_index.the	2
abstract_inverted_index.dual	46, 73
abstract_inverted_index.rate	59
abstract_inverted_index.set,	14
abstract_inverted_index.that	17, 32
abstract_inverted_index.with	9, 38, 66
abstract_inverted_index.(DRO)	7
abstract_inverted_index.Drago	53
abstract_inverted_index.Owing	49
abstract_inverted_index.using	20
abstract_inverted_index.Drago,	27
abstract_inverted_index.convex	12
abstract_inverted_index.cyclic	34
abstract_inverted_index.enjoys	54
abstract_inverted_index.linear	57
abstract_inverted_index.primal	42, 71
abstract_inverted_index.robust	5
abstract_inverted_index.tasks.	87
abstract_inverted_index.update	43
abstract_inverted_index.$f$-DRO	21
abstract_inverted_index.achieve	45
abstract_inverted_index.closed,	11
abstract_inverted_index.concave	63
abstract_inverted_index.design,	52
abstract_inverted_index.present	26
abstract_inverted_index.problem	8
abstract_inverted_index.results	77
abstract_inverted_index.setting	16
abstract_inverted_index.combines	33
abstract_inverted_index.consider	1
abstract_inverted_index.learning	19
abstract_inverted_index.numbers.	75
abstract_inverted_index.problems	65
abstract_inverted_index.strongly	61
abstract_inverted_index.variance	47
abstract_inverted_index.algorithm	31
abstract_inverted_index.carefully	40
abstract_inverted_index.condition	74
abstract_inverted_index.numerical	81
abstract_inverted_index.penalized	3
abstract_inverted_index.supported	79
abstract_inverted_index.benchmarks	82
abstract_inverted_index.components	37
abstract_inverted_index.dependency	69
abstract_inverted_index.randomized	36
abstract_inverted_index.reduction.	48
abstract_inverted_index.regression	84
abstract_inverted_index.stochastic	29
abstract_inverted_index.Theoretical	76
abstract_inverted_index.convergence	58
abstract_inverted_index.encompasses	18
abstract_inverted_index.primal-dual	30
abstract_inverted_index.regularized	41
abstract_inverted_index.uncertainty	13
abstract_inverted_index.fine-grained	68
abstract_inverted_index.optimization	6
abstract_inverted_index.minimization.	24
abstract_inverted_index.classification	86
abstract_inverted_index.convex-strongly	62
abstract_inverted_index.distributionally	4
abstract_inverted_index.state-of-the-art	56
abstract_inverted_index.spectral/$L$-risk	23
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile