Logarithmic Regret in Multisecretary and Online Linear Programs with Continuous Valuations

I use empirical processes to study how the shadow prices of a linear program that allocates an endowment of n β ∈ R m resources to n customers behave as n → ∞ . I show the shadow prices (i) adhere to a concentration of measure, (ii) converge to a multivariate normal under central-limit-theorem scaling, and (iii) have a variance that decreases like Θ ( 1 / n ) . I use these results to prove that the expected regret in an online linear program is Θ ( log n ) , both when the customer variable distribution is known upfront and must be learned on the fly. This result tightens the sharpest known upper bound from O ( log n log log n ) to O ( log n ) , and it extends the Ω ( log n ) lower bound known for single-dimensional problems to the multidimensional setting. I illustrate my new techniques with a simple analysis of a multisecretary problem.