AI & ML
Geometry, Local Minimax Risk, and the Limits of Sample Average Approximation in Linear Stochastic Optimization
arXiv stat.TH0 views
arXiv:2611.25007v1 Announce Type: new Abstract: We study how the local geometry of a linear stochastic optimization problem determines its statistical difficulty, measured by expected decision regret. The optimal local rate is governed by how fast the support function of the feasible set grows away from its linearization at the true mean; depending on the instance, it can be $n^{-1/2}$, $n^{-1}$, $n^{-2}$, or a non-power rate, and sample average approximation (SAA) attains these rates in a Gaussian mean model. At smooth instances, SAA also attains the classical sharp local minimax constant. We then allow the data distribution to vary in a Kullback--Leibler (KL) ball of radius proportional to $1/n$ around a reference distribution $P$. The exact local minimax limit of this benchmark, which may depend on $P$, coincides with that of a Gaussian model whose local parameter set is the covariance ellipsoid of $P$. A simple coordinatewise truncated SAA rule, which does not use $P$, attains the minimax rate, and at smooth instances its constant matches the minimax constant as the neighborhood radius grows. Ordinary SAA, in contrast, can have strictly suboptimal worst-case expected regret when the local rate is fast relative to the tails of $P$, because rare tail events then dominate the expectation. The results delineate when SAA is sharply optimal, rate-optimal, or statistically suboptimal, and quantify the local price of distributional robustness.
Source:https://arxiv.org/abs/2611.25007PreviousStop Removing Stopwords: How an Inherited Preprocessing Default Distorts Legal Text-as-DataNextFunctional Estimation under Local Differential Privacy: General Lower Bounds and Applications to Entropy and Power Sums
Related posts
Why an Embedded Game Fails on Some Phones, and How to Debug It
0dev.to
Microsoft 365 vs Office 2024: The Break-Even Math
0dev.to
Master AI Evals: Build Reliable, Scalable Model Evaluation Pipelines
0dev.to
What to give someone who misses a place
0dev.to
Google is pushing OEMs against GrapheneOS and bootloader unlocking
0Hacker News
VESTA: Visual Exploration with Statistical Tool Agents
0arXiv stat.CO