In the first, most general, variant of GD-FixedPoint
\(\phi \)  is given by an arbitrary well-behaved arithmetic circuit with \(\lbrace +,-,\times ,\times \zeta ,\max ,\min ,>\rbrace \)  gates, where \(\times \zeta \)  denotes multiplication by a constant. \(\max ,\min \)  gates are not smooth and \(>\)  gate is not even continuous, but it is promisedTo make the problem total, the algorithm may either return a solution or a certificate that this promise is violated; however the \(\cap \) -complete instances [1]} always satisfy the promise, so it suffices to prove hardness for this special case. that \(\nabla \phi \)  is defined and \(\alpha \) -Lipschitz in the \(\ell _2 - \ell _2\)  sense (the parameter \(\alpha \)  is given as an input to the algorithm).
The well-behaved desideratum restricts that the number \(\times \)  gates on any input-output path is at most logarithmic (in the size of the circuit). This desideratum is important to avoid doubly-exponential numbers from repeated squaring. See [1]} for a detailed discussion.
