← All setups

Chi-Square Constrained Robust Optimization

Descriptions may be stale. Consult the linked Lean sources.

Chi-Square Constrained Robust Optimization

We minimize a robust objective F over a closed convex set C in a separable real Hilbert space E. Here F(x) is the worst expected sample loss under nonnegative densities relative to a probability law ν, with mean one and chi-square divergence at most ρ>0. Sample losses are jointly measurable, convex and bounded on C, with jointly measurable bounded subgradients. Each oracle call returns the projection of the query onto C, together with its loss and subgradient evaluated using one fresh independent sample from ν. Given ε>0, the goal is a measurable feasible output x¯ with E[F(x¯)−F(x⋆)]≤ε, where x⋆ minimizes F on C and expectation includes sampling and algorithm randomness.

Let Ξ be a measurable sample space carrying the probability measure ν. Write ℓ:E×Ξ→R for the sample loss and g:E×Ξ→E for its supplied subgradient. Define the density class Wρ={w:Ξ→R measurable:w(ξ)≥0 for every ξ,w∈L2(ν),Eξ∼ν[w(ξ)]=1,12Eξ∼ν[(w(ξ)−1)2]≤ρ}. The objective and optimization problem are F(x)=supw∈WρEξ∼ν[w(ξ)ℓ(x,ξ)],minx∈CF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, Ξ, ρ>0, G>0, B>0, R≥0, ε>0, and a given point x0∈E; the instance consists of C, ν, ℓ, and g, accessed through the oracle described below.

Our assumptions:

Assumption 1 (Feasible set and projection). The set C⊆E is closed and convex, and x0∈C. There is a measurable map ΠC:E→C satisfying ⟨y−ΠC(y),u−ΠC(y)⟩≤0,y∈E,u∈C.

Assumption 2 (Sample losses and subgradients). The maps ℓ and g are jointly measurable. For every ξ∈Ξ and x,y∈C, ℓ(x,ξ)+⟨g(x,ξ),y−x⟩≤ℓ(y,ξ),0≤ℓ(x,ξ)≤B,∥g(x,ξ)∥≤G.

Assumption 3 (Initial distance). There exists x⋆∈C such that F(x⋆)≤F(x)for every x∈C,∥x0−x⋆∥≤R.

Queries may be made at any y∈E. At call k≥0, the oracle returns (ΠC(y), ℓ(ΠC(y),ξk), g(ΠC(y),ξk)). The sample variables (ξk)k≥0 are measurable, mutually independent, and each has law ν. The loss and subgradient in a reply use the same sample. Any algorithm randomness is independent of the entire sample sequence.

After the allotted calls, the output x¯ must be measurable and belong to C for every realization. Its objective gap must be integrable and satisfy EP[F(x¯)−F(x⋆)]≤ε, where P is the joint law of the samples and the algorithm’s randomness.

Results

Let X be a nonempty closed convex subset of a complete, second-countable real inner-product space with its Borel measurable structure. The population law P0 is arbitrary. Jointly measurable losses and subgradients satisfy 0≤ℓ(x;ξ)≤B, convex subgradient inequalities on X, and ∥g(x;ξ)∥≤G. A minimizer x⋆∈X satisfies ∥x0−x⋆∥≤R, with x0∈X, ρ,G,B,ε>0 and R≥0. Each IID oracle call returns projection onto X, loss, and subgradient. Define L(x)=sup{∫wℓ(x;ξ)dP0:w≥0, w∈L2(P0), ∫wdP0=1, 12∫(w−1)2dP0≤ρ}. The target is a measurable feasible output x^ with ∫[L(x^(ω))−L(x⋆)]dP(ω)≤ε under the IID sampling law P.

Comparison for ChiSquareConstrainedDro.
Result Oracle complexity Novelty Limitations
(1) ChiSquareBracketedDro (Ours) (⋆⋆⋆) (review) O([1+(1+ρ)G2R2ε2+(1+ρ)2B2ρε2]Λ2) IID calls, including selection; deterministic budget.
(2) (Levy et al. 2020), Theorem 4 and subsequent selection O([1+G2R2(ρB+εlog⁡(B/ε))ε3]Γ2) sampled loss/subgradient calls; 0<ε<B. Call bound holds with probability ≥1−ε/B. (1): at ρ≥1, GR=B, costs O(ρB2ε−2Λ2) versus O(ρB3ε−3Γ2) for ε≪B. Scope: initial-distance bound replaces diameter bound. Deterministic budget includes selection. (1) loses for ρ≪min{B2/(G2R2),εB/(GR)} through B2/(ρε2). For ρ≥1, gain requires ε≲G2R2B/(G2R2+B2), up to logarithms.

Abbr: Λ=log(2+(1+ρ)Bρε); Γ=1+log⁡(1+ρB/ε2); ρ is the χ2 radius; G bounds subgradient norms; B bounds losses; R bounds initial distance (diameter for (2)). ≲ and ≪ describe comparison regimes; rate gains are up to logarithmic factors.

Levy, Daniel, Yair Carmon, John C. Duchi, and Aaron Sidford. 2020. Large-Scale Methods for Distributionally Robust Optimization. https://doi.org/10.48550/arXiv.2010.05893.

Lean setup