Temporal Accelerated Quadratic — Quadratic Minimization with Temporal Discrepancy
Descriptions may be stale. Consult the linked Lean sources.
Quadratic Minimization with Temporal Discrepancy · Lean proof
Quadratic
Minimization with Temporal Discrepancy
We consider minimizing on a real
Hilbert space , where is bounded and linear and . For constants , assume for
every . A given starting
point satisfies , where . At call , the oracle returns , with fixed errors whose partial sums have norm at
most . For , the goal is an output
satisfying
almost surely under , the law of
the algorithm’s randomness.
The optimization problem is The norm is induced by the inner product on , and denotes the Hilbert-space adjoint of
. The algorithm receives only
, , , and ; the discrepancy bound , initial objective bound , and tolerance may enter the oracle-call
budget but are not algorithm inputs.
Our assumptions:
Assumption 1 (Quadratic structure). The objective
and its gradient are where is a bounded linear operator satisfying In particular, is the unique minimizer and .
Assumption 2 (Initial objective bound). The given
starting point satisfies
Assumption 3 (Temporal discrepancy). There is a
fixed deterministic sequence in such that the oracle reply at call
, for any query , is Its
cumulative error satisfies with the empty sum equal to zero.
After the allotted oracle calls, the output must satisfy
Proved result
OracleTemplate.Convergence LongTails.Setups.QuadraticTemporalDiscrepancy.spec OracleTemplate.TemporalDiscrepancy.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.