Minimization with Bounded Temporal Discrepancy
Descriptions may be stale. Consult the linked Lean sources.
Minimization with Bounded Temporal Discrepancy
We consider minimizing a twice continuously differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Strong convexity and smoothness). The
function
Assumption 2 (Lipschitz Hessian). The Hessian
Assumption 3 (Bounded temporal discrepancy). There
is a fixed deterministic sequence
Assumption 4 (Initial objective gap). There exists
Queries may be made at any point of
Results
On a finite-dimensional real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) NonlinearTemporalAcceleration
(Ours) |
|||
| (2) Restarted, batched AGD+ (Cohen et al. 2018); Derived bound from Lemma 3.2 and Eq. (3.2). | (1): noise cost For |
(1) needs Lipschitz
Hessian and known |
|
| (3) Quadratic dilation
reduction (Schmidt
et al. 2011), Prop. 4; specialization to |
(1): scope extends from
quadratics to nonlinear Hessian-Lipschitz objectives. The dilation
reduction requires affine gradients. Matches known acceleration when
|
(1) at |
Abbr: