← All setups

Confidence Guarantees for Quadratic Minimization

Descriptions may be stale. Consult the linked Lean sources.

Confidence Guarantees for Quadratic Minimization

We consider minimizing f(x)=12Ea∼ν[⟨a,x−x⋆⟩2] over x∈R2, where ν is a probability distribution and x⋆∈R2 is an unknown minimizer. In the Euclidean norm, ∥a∥2≤L holds ν-almost surely for L>0, and a given point x0 satisfies ∥x0−x⋆∥≤R for R>0. Each oracle call at x returns ⟨a,x−x⋆⟩a using a fresh independent sample from ν. For ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ.

The optimization problem is minx∈R2f(x). We use the standard Euclidean inner product and its induced norm. The algorithm receives only L and x0; the parameters R, ε, and δ may enter the oracle-call budget but are not algorithm inputs.

Our assumptions:

Assumption 1 (Population quadratic and initial distance). There exist a Borel probability distribution ν on R2 and a point x⋆∈R2 such that f(x)=12Ea∼ν[⟨a,x−x⋆⟩2],x∈R2,∥a∥2≤L,ν-almost surely,∥x0−x⋆∥≤R. In particular, f is a convex quadratic and f(x⋆)=0 is its global minimum.

Assumption 2 (Independent stochastic gradient samples). The sample sequence (ak)k≥0 consists of measurable, mutually independent random vectors with common distribution ν. It is independent of the algorithm’s randomness. At call k, a query x∈R2 receives g(x,ak)=⟨ak,x−x⋆⟩ak.

Queries may be made anywhere in R2. After the allotted oracle calls, the output x¯∈R2 must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the sample sequence and the algorithm’s independent randomness.

Results

    Lean setup