Confidence Guarantees for Quadratic Minimization
Descriptions may be stale. Consult the linked Lean sources.
Confidence
Guarantees for Quadratic Minimization
We consider minimizing over , where is a probability distribution and
is an
unknown minimizer. In the Euclidean norm, holds -almost surely for , and a given point satisfies for . Each oracle call at returns using a
fresh independent sample from .
For and , the goal is a measurable
output satisfying with
probability at least .
The optimization problem is We use the
standard Euclidean inner product and its induced norm. The algorithm
receives only and ; the parameters , , 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 and a point such that In particular, is a convex quadratic and is its global minimum.
Assumption 2 (Independent stochastic gradient
samples). The sample sequence consists of measurable,
mutually independent random vectors with common distribution . It is independent of the algorithm’s
randomness. At call , a query
receives
Queries may be made anywhere in . After the allotted oracle
calls, the output must be measurable
and satisfy
where is the joint law of the
sample sequence and the algorithm’s independent randomness.
Results
Lean setup