First-order and KKT conditions
\[\nabla f(x^\star) + \textstyle\sum_i \lambda_i \nabla g_i(x^\star) + A^\top \nu = 0,\quad \lambda_i \ge
0,\quad \lambda_i g_i(x^\star) = 0\]
For a convex problem \(\min f(x)\) subject to \(g_i(x) \le 0,\ Ax = b\) under Slater's condition, plus primal
feasibility. Unconstrained: an interior local minimum of a differentiable \(f\) has \(\nabla f(x^\star) = 0\).
- Gives
- Turns "which solution?" into algebra, and often reveals an implicit regularizer.
- Costs
-
Differentiability and a constraint qualification; sufficiency needs convexity or another global argument.
- Wrong tool when
-
The problem is non-convex: a stationary point need not be a minimum, and KKT says nothing about which one the
dynamics pick.
Strong-convexity sensitivity
\[\sup_x \lVert \nabla f(x) - \nabla \tilde f(x) \rVert \le \varepsilon \;\Longrightarrow\; \lVert \tilde
x^\star - x^\star \rVert \le \frac{\varepsilon}{\mu}\]
For differentiable, \(\mu\)-strongly convex \(f\), with \(x^\star = \arg\min f\) and \(\tilde x^\star = \arg\min
\tilde f\).
- Gives
- A direct bound on how far the parameters move.
- Costs
- A unique minimizer and curvature \(\mu > 0\), at least on the region that matters.
- Wrong tool when
- Minima are flat or overparameterized, or symmetries make Euclidean parameter distance meaningless.
Uniform objective perturbation
\[\sup_x \lvert f(x) - \tilde f(x) \rvert \le \delta \;\Longrightarrow\; \lVert \tilde x^\star - x^\star \rVert
\le 2\sqrt{\delta/\mu}\]
For \(\mu\)-strongly convex \(f\).
- Gives
- Stability when you can compare only function values, not gradients.
- Costs
- Strong convexity and a uniform approximation on the relevant domain.
- Wrong tool when
-
You do know the gradient perturbation; the previous tool gives the sharper \(\mathcal{O}(\varepsilon/\mu)\).
Implicit function theorem and influence functions
\[\left.\frac{d\theta^\star_\epsilon}{d\epsilon}\right|_{0} = -H^{-1}\, \partial_\epsilon F(\theta^\star,
\epsilon)\big|_{0}, \qquad \text{upweighting } z:\ \frac{d\theta^\star}{d\epsilon} = -H^{-1}\nabla_\theta
\ell(z, \theta^\star)\]
With \(F(\theta, \epsilon) = \nabla_\theta R(\theta, \epsilon)\), \(F(\theta^\star, 0) = 0\) and \(H =
\partial_\theta F(\theta^\star, 0)\) invertible.
- Gives
- The first-order effect of reweighting or deleting data, or of changing a hyperparameter.
- Costs
- Local differentiability and a nonsingular Hessian; the answer holds only for small \(\epsilon\).
- Wrong tool when
- The Hessian is singular, the perturbation is large, or the optimum is non-smooth.
Contraction mappings
\[d(x_t, x^\star) \le q^t\, d(x_0, x^\star), \qquad 0 \le q < 1\]
If \(T\) is a \(q\)-contraction on a complete metric space, it has a unique fixed point \(x^\star\).
- Gives
- Uniqueness, convergence to the equilibrium and its sensitivity, all at once.
- Costs
- A genuine contraction on an invariant complete set.
- Wrong tool when
-
The dynamics are only non-expansive, or have large neutral directions, as in most neural-network training.
Kurdyka–Łojasiewicz (KL) inequality
\[\varphi'\big(f(x) - f(x^\star)\big)\, \operatorname{dist}\big(0, \partial f(x)\big) \ge 1 \quad \text{near }
x^\star\]
With \(\varphi(0) = 0\) and \(\varphi' > 0\); exponent \(1/2\) corresponds to \(\varphi(s) = c\sqrt{s}\).
- Gives
-
Convergence of descent methods and, with exponent \(1/2\) at the minimizers, a local error bound: distance to
the set of minimizers in non-convex problems, where no unique optimum exists.
- Costs
-
Losses built from analytic or semialgebraic pieces have the KL property with some exponent; the
exponent \(1/2\) and the neighborhood are extra assumptions. The bound is to a set, not a single point.
- Wrong tool when
- It is asserted abstractly with no link to the actual architecture or loss.