Which Directions Matter? Sparse Design for Affine Robust Optimization

Pedro Chumpitaz-Flores, My Duong, Juan S. Borrero, Kaixun Hua
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:1327-1356, 2026.

Abstract

Robust machine learning and optimization rely on the uncertainty model choice. We investigate which uncertainty directions a model must cover when defined by a finite dictionary and a budget constraint. Selecting a subset forms an atomic uncertainty set with a closed form support function, yielding tractable robust programs for affine objectives. We propose a data-driven selection rule based on a coverage objective over evaluation directions, including gradients, adversarial perturbations, or shifts observed on held out data. We prove this objective is monotone and submodular, supporting a greedy method with a $(1-1/e)$ approximation guarantee and a matching hardness barrier. We also provide a certificate bounding the loss from the selected subset and a radius calibration rule with out-of-sample control.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-chumpitaz-flores26a, title = {Which Directions Matter? {Sparse} Design for Affine Robust Optimization}, author = {Chumpitaz-Flores, Pedro and Duong, My and Borrero, Juan S. and Hua, Kaixun}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {1327--1356}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/chumpitaz-flores26a/chumpitaz-flores26a.pdf}, url = {https://proceedings.mlr.press/v337/chumpitaz-flores26a.html}, abstract = {Robust machine learning and optimization rely on the uncertainty model choice. We investigate which uncertainty directions a model must cover when defined by a finite dictionary and a budget constraint. Selecting a subset forms an atomic uncertainty set with a closed form support function, yielding tractable robust programs for affine objectives. We propose a data-driven selection rule based on a coverage objective over evaluation directions, including gradients, adversarial perturbations, or shifts observed on held out data. We prove this objective is monotone and submodular, supporting a greedy method with a $(1-1/e)$ approximation guarantee and a matching hardness barrier. We also provide a certificate bounding the loss from the selected subset and a radius calibration rule with out-of-sample control.} }
Endnote
%0 Conference Paper %T Which Directions Matter? Sparse Design for Affine Robust Optimization %A Pedro Chumpitaz-Flores %A My Duong %A Juan S. Borrero %A Kaixun Hua %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-chumpitaz-flores26a %I PMLR %P 1327--1356 %U https://proceedings.mlr.press/v337/chumpitaz-flores26a.html %V 337 %X Robust machine learning and optimization rely on the uncertainty model choice. We investigate which uncertainty directions a model must cover when defined by a finite dictionary and a budget constraint. Selecting a subset forms an atomic uncertainty set with a closed form support function, yielding tractable robust programs for affine objectives. We propose a data-driven selection rule based on a coverage objective over evaluation directions, including gradients, adversarial perturbations, or shifts observed on held out data. We prove this objective is monotone and submodular, supporting a greedy method with a $(1-1/e)$ approximation guarantee and a matching hardness barrier. We also provide a certificate bounding the loss from the selected subset and a radius calibration rule with out-of-sample control.
APA
Chumpitaz-Flores, P., Duong, M., Borrero, J.S. & Hua, K.. (2026). Which Directions Matter? Sparse Design for Affine Robust Optimization. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:1327-1356 Available from https://proceedings.mlr.press/v337/chumpitaz-flores26a.html.

Related Material