analiza aiqbench
This theoretical paper examines when distributionally robust optimization (DRO), a common way to hedge against distribution shift, yields decisions that are suboptimal in regret for least-squares regression. It shows DRO can fall short of the minimax rate by dimension-dependent factors in some settings, and that minimax regret optimization and spectral-norm regularization attain the optimal rate. For ML practitioners, the practical takeaway is that robust training objectives are not automatically the best choice under Wasserstein perturbations, and the choice depends on problem structure such as effective rank.
Regret-Optimal Wasserstein-Robust Linear Regression
arXiv:2610.42109v1 Announce Type: cross Abstract: Distributionally robust optimization (DRO) minimizes worst-case risk under distributional uncertainty, but its decisions can be suboptimal in terms of their excess risk, or regret. We study this gap for multivariate least-squares regression, assuming that the observed source law and unknown target law differ by an adversarial 2-Wasserstein perturbation of size $\varepsilon$. We first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $\kappa$. Here, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(\kappa \varepsilon^2)$. For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem has bounded residual effective rank. On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors. Fortunately, we prove that two alternative procedures, minimax regret optimization (MRO) and spectral-norm regularization (SNR), attain the minimax rate. We derive an exact convex reformulation of MRO and an accelerated proximal algorithm for SNR, along with high-probability finite-sample guarantees. We support these theoretical results with numerical experiments separating the performance of MRO and SNR from DRO.
Abstract:Distributionally robust optimization (DRO) minimizes worst-case risk under distributional uncertainty, but its decisions can be suboptimal in terms of their excess risk, or regret. We study this gap for multivariate least-squares regression, assuming that the observed source law and unknown target law differ by an adversarial 2-Wasserstein perturbation of size $\varepsilon$. We first identify the asymptotic complexity of robust decision-making in the $\varepsilon \to 0$ limit, characterized by a problem-specific condition number $\kappa$. Here, a wide spectrum of simple algorithms, including DRO, achieve the instance-optimal rate of $O(\kappa \varepsilon^2)$. For fixed $\varepsilon > 0$, we prove that DRO still achieves the minimax rate if the problem has bounded residual effective rank. On the other hand, we identify significant failure modes where DRO is provably suboptimal by dimension-dependent factors. Fortunately, we prove that two alternative procedures, minimax regret optimization (MRO) and spectral-norm regularization (SNR), attain the minimax rate. We derive an exact convex reformulation of MRO and an accelerated proximal algorithm for SNR, along with high-probability finite-sample guarantees. We support these theoretical results with numerical experiments separating the performance of MRO and SNR from DRO.
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2610.42109 [stat.ML]
(or arXiv:2610.42109v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2610.42109 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 285 cuvinte