Which Directions Matter? Sparse Design for Affine Robust Optimization
2026-06-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how to choose specific directions of uncertainty when creating robust machine learning models that face unknown changes or errors. They focus on picking a limited set of these directions from a dictionary, ensuring the resulting problem is easier to solve. Their method uses data to pick directions that cover important changes, like gradients or known shifts, and they prove their approach is mathematically efficient and near-optimal. They also offer guarantees on performance loss and ways to adjust their method for new data. This helps make models that remain reliable even when conditions change.
Robust optimizationUncertainty setsAtomic uncertaintySupport functionSubmodular optimizationGreedy algorithmBudget constraintsAdversarial perturbationsAffine objectivesOut-of-sample control
Authors
Pedro Chumpitaz-Flores, My Duong, Juan S. Borrero, Kaixun Hua
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.