教你用贪心算法选关键方向，逼近最优解。
论文提出一种基于有限字典和预算约束的不确定性方向选择方法，将选定子集构成原子不确定性集，并推导出闭式支撑函数，使仿射目标的鲁棒优化可解。该方法通过数据驱动规则覆盖评估方向（如梯度、对抗扰动和留出数据偏移），并证明目标函数是单调且子模的，支持贪心算法达到(1-1/e)近似保证，同时给出匹配的难度下界。此外，论文提供选定子集损失的上界证书，以及带样本外控制的半径校准规则。
Which Directions Matter? Sparse Design for Affine Robust Optimization
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.