OpenFrontiers
Join
← Back to the index
OP-1239OpenOptimization

The mathematics of artificial intelligence · 2022-opt-26

Optimization Theory, Algorithms, and Complexity · ICM 2022: The mathematics of artificial intelligence

MSC 90C · Mathematical programming

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let m,d,q,p∈Nm,d,q,p\in\mathbb N. Let {(x(i),y(i))}i=1m⊆Rd×Rq\{(x^{(i)},y^{(i)})\}_{i=1}^{m}\subseteq\mathbb R^d\times\mathbb R^q be a finite training set, and let Φθ:Rd→Rq\Phi_\theta:\mathbb R^d\to\mathbb R^q be the realization of a fixed deep feed-forward neural-network architecture whose trainable weights and biases are collected in θ∈Rp\theta\in\mathbb R^p. For a specified loss function L:Rq×Rq→R\mathscr L:\mathbb R^q\times\mathbb R^q\to\mathbb R, define the empirical-risk objective

F(θ)=1m∑i=1mL ⁣(Φθ(x(i)),y(i)).F(\theta)=\frac1m\sum_{i=1}^{m}\mathscr L\!\left(\Phi_\theta(x^{(i)}),y^{(i)}\right).

Given randomly sampled nonempty mini-batches Bk⊆{1,…,m}B_k\subseteq\{1,\ldots,m\} and step sizes ηk>0\eta_k>0, stochastic gradient descent generates

θk+1=θk−ηk 1∣Bk∣∑i∈Bk∇θL ⁣(Φθk(x(i)),y(i)).\theta_{k+1} =\theta_k-\eta_k\,\frac1{|B_k|} \sum_{i\in B_k}\nabla_\theta\mathscr L\!\left(\Phi_{\theta_k}(x^{(i)}),y^{(i)}\right).

Determine verifiable hypotheses on the training data, network architecture and activation functions, loss function, initialization, step-size sequence, and mini-batch sampling law under which, despite the nonconvexity of FF, the iterates (θk)k≥0(\theta_k)_{k\geq0} converge in a specified probabilistic sense to a local minimizer θ∗\theta_* and satisfy an explicit, quantitatively small bound on the optimization error

F(θ∗)−inf⁡θ∈RpF(θ).F(\theta_*)-\inf_{\theta\in\mathbb R^p}F(\theta).

Under those hypotheses, characterize mathematically the mechanism by which stochastic mini-batch sampling favors such local minimizers over local minimizers having substantially larger optimization error.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

Let d∈Nd\in\mathbb N, let a,b∈Ra,b\in\mathbb R with a≤ba\leq b, let μ\mu be a finite Borel measure on [a,b]d[a,b]^d, and let f:[a,b]d→Rf:[a,b]^d\to\mathbb R be bounded and measurable. Let σ:R→R\sigma:\mathbb R\to\mathbb R be locally bounded and measurable, and assume that σ\sigma is discriminatory for μ\mu: whenever a measurable function φ:[a,b]d→R\varphi:[a,b]^d\to\mathbb R belongs to L1(μ)L^1(\mu) and

∫[a,b]dσ(⟨w,x⟩+c)φ(x) dμ(x)=0for every w∈Rd and c∈R,\int_{[a,b]^d}\sigma(\langle w,x\rangle+c)\varphi(x)\,d\mu(x)=0 \quad\text{for every }w\in\mathbb R^d\text{ and }c\in\mathbb R,

then φ=0\varphi=0 μ\mu-almost everywhere. For h∈N0h\in\mathbb N_0, define

Ih=inf⁡c,vi,bi∈R, wi∈Rd∫[a,b]d(c+∑i=1hviσ(⟨wi,x⟩+bi)−f(x))2dμ(x),I_h=\inf_{c,v_i,b_i\in\mathbb R,\,w_i\in\mathbb R^d} \int_{[a,b]^d} \left(c+\sum_{i=1}^{h}v_i\sigma(\langle w_i,x\rangle+b_i)-f(x)\right)^2d\mu(x),

and let

K=inf⁡({h∈N0:Ih=0}∪{∞}).\mathcal K=\inf\bigl(\{h\in\mathbb N_0:I_h=0\}\cup\{\infty\}\bigr).

Prove that Ih+1<IhI_{h+1}<I_h for every h∈N0h\in\mathbb N_0 with h<Kh<\mathcal K.

Source reference: Arnulf Jentzen and Adrian Riekert, “Non-convergence to Global Minimizers for Adam and Stochastic Gradient Descent Optimization and Constructions of Local Minimizers in the Training of Artificial Neural Networks,” SIAM/ASA Journal on Uncertainty Quantification 13(3) (2025), 1294–1333, Conjecture 3.13. DOI: https://doi.org/10.1137/24M1639464.

Question 2

Let N,d,D∈NN,d,D\in\mathbb N with D>ND>N, let (xi,yi)∈Rd×R(x_i,y_i)\in\mathbb R^d\times\mathbb R for i∈[N]={1,…,N}i\in[N]=\{1,\ldots,N\}, and let f:RD×Rd→Rf:\mathbb R^D\times\mathbb R^d\to\mathbb R be twice continuously differentiable in its first variable. Define

Li(θ)=12(f(θ,xi)−yi)2,L(θ)=1N∑i=1NLi(θ),L_i(\theta)=\frac12\bigl(f(\theta,x_i)-y_i\bigr)^2, \qquad L(\theta)=\frac1N\sum_{i=1}^N L_i(\theta),

and the interpolation manifold

M={θ∈RD:f(θ,xi)=yi for every i∈[N]}.M=\{\theta\in\mathbb R^D:f(\theta,x_i)=y_i\text{ for every }i\in[N]\}.

Assume that {∇θf(θ,xi):i∈[N]}\{\nabla_\theta f(\theta,x_i):i\in[N]\} is linearly independent for every θ∈M\theta\in M. Fix η>0\eta>0, let ξ1,ξ2,…\xi_1,\xi_2,\ldots be independent and uniform on [N][N], and consider

Θn+1=Gη,ξn+1(Θn),Gη,i(θ)=θ−η∇Li(θ),\Theta_{n+1}=G_{\eta,\xi_{n+1}}(\Theta_n), \qquad G_{\eta,i}(\theta)=\theta-\eta\nabla L_i(\theta),

where the law of Θ0\Theta_0 is equivalent to Lebesgue measure on RD\mathbb R^D. Assume that every Gη,iG_{\eta,i} and the full-gradient map Gη(θ)=θ−η∇L(θ)G_\eta(\theta)=\theta-\eta\nabla L(\theta) is nonsingular in the measure-theoretic sense that the preimage of every Lebesgue-null set is Lebesgue-null.

For θ∗∈M\theta_*\in M, put

N(θ∗)=span⁡{∇θf(θ∗,xi):i∈[N]}\mathcal N(\theta_*)=\operatorname{span}\{\nabla_\theta f(\theta_*,x_i):i\in[N]\}

and define its top transverse Lyapunov exponent by

λ(θ∗)=lim⁡n→∞1n E ⁣[log⁡∥DGη,ξn(θ∗)⋯DGη,ξ1(θ∗)∣N(θ∗)∥].\lambda(\theta_*)= \lim_{n\to\infty}\frac1n\, \mathbb E\!\left[ \log\left\| DG_{\eta,\xi_n}(\theta_*)\cdots DG_{\eta,\xi_1}(\theta_*) \big|_{\mathcal N(\theta_*)} \right\| \right].

Call θ∗\theta_* regular if

∥∇θf(θ∗,xi)∥2∉{1/η,2/η}for every i∈[N],\|\nabla_\theta f(\theta_*,x_i)\|^2\notin\{1/\eta,2/\eta\} \quad\text{for every }i\in[N],

and there is no nonempty proper subset A⊂[N]A\subset[N] such that

∇θf(θ∗,xi)⋅∇θf(θ∗,xj)=0for all i∈A and j∈[N]∖A.\nabla_\theta f(\theta_*,x_i)\cdot\nabla_\theta f(\theta_*,x_j)=0 \quad\text{for all }i\in A\text{ and }j\in[N]\setminus A.

Define Θlim\Theta_{\mathrm{lim}} to be lim⁡n→∞Θn\lim_{n\to\infty}\Theta_n if this limit exists and lies in MM, and a cemetery state otherwise. For a regular θ∗∈M\theta_*\in M satisfying λ(θ∗)=0\lambda(\theta_*)=0, determine whether θ∗\theta_* must belong to the support of Θlim\Theta_{\mathrm{lim}}, meaning that

P(Θlim∈U)>0\mathbb P(\Theta_{\mathrm{lim}}\in U)>0

for every relatively open neighborhood UU of θ∗\theta_* in MM; if not, characterize additional verifiable conditions that decide whether it belongs to this support.

Source reference: Dennis Chemnitz and Maximilian Engel, “Characterizing Dynamical Stability of Stochastic Gradient Descent in Overparameterized Learning,” Journal of Machine Learning Research 26(134) (2025), 1–46, Remark 2.3 following Theorem B. arXiv:2407.20209; https://www.jmlr.org/papers/v26/24-1547.html.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

The problem is unresolved. No result found gives, for a practically representative class of finite-data deep feed-forward networks, one verifiable set of hypotheses that simultaneously proves convergence of the stated mini-batch SGD iterates to a local minimizer, bounds that minimizer's empirical-risk gap, and explains why mini-batch randomness selects it over higher-loss local minima. Existing results establish important but non-exhaustive regimes or mechanisms.

  • Gitta Kutyniok, “The Mathematics of Artificial Intelligence,” Proceedings of the International Congress of Mathematicians 2022, vol. 7, 2022, pp. 5118–5139, DOI 10.4171/ICM2022/141. Section 5 poses this question as one of seven key problems; Section 3.2 emphasizes that the nonconvex stochastic setting is much less understood than approximation theory.

  • Benjamin Fehrman, Benjamin Gess, and Arnulf Jentzen, “Convergence Rates for the Stochastic Gradient Descent Method for Non-Convex Objective Functions,” Journal of Machine Learning Research 21(136), 2020, pp. 1–48, arXiv:1904.01517. The paper proves quantitative local convergence to a manifold of minima for smooth objectives when initialization is already in a suitable attracting neighborhood, with growing mini-batches controlling departures from that neighborhood. It does not show that neural-network SGD reaches such a neighborhood or that the reached minimum has small global optimization error.

  • Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song, “A Convergence Theory for Deep Learning via Over-Parameterization,” Proceedings of the 36th International Conference on Machine Learning, PMLR 97, 2019, pp. 242–252, direct URL. For sufficiently wide ReLU fully connected, convolutional, and residual networks, nondegenerate inputs, random initialization, and specified losses and hyperparameters, the paper proves polynomial-time convergence of SGD to zero training error (with linear convergence for regression). This gives a zero-gap guarantee in an overparameterized, near-initialization regime, but it avoids rather than characterizes selection among local minima of different objective values.

  • Bobby Kleinberg, Yuanzhi Li, and Yang Yuan, “An Alternative View: When Does SGD Escape Local Minima?,” Proceedings of the 35th International Conference on Machine Learning, PMLR 80, 2018, pp. 2698–2707, arXiv:1802.06175. Their main theorem shows that SGD approaches and remains near a desired point with constant probability when a noise-smoothed gradient field satisfies a global one-point-convexity condition. This rigorously exhibits convolutional smoothing as a possible escape mechanism, but the required condition is only checked empirically for neural-network landscapes and does not yield the requested general neural-network hypotheses.

  • Itay Safran and Ohad Shamir, “Spurious Local Minima are Common in Two-Layer ReLU Neural Networks,” Proceedings of the 35th International Conference on Machine Learning, PMLR 80, 2018, pp. 4433–4441, direct URL. A computer-assisted proof constructs spurious local minima for realizable Gaussian teacher-student problems with 6≤k≤206\leq k\leq20, and experiments find substantial attraction probabilities. Thus benign landscapes cannot be assumed without additional architecture, data, or initialization conditions.

  • Thang Do, Sonja Hannibal, and Arnulf Jentzen, “Non-convergence to Global Minimizers in Data Driven Supervised Deep Learning: Adam and Stochastic Gradient Descent Optimization Provably Fail to Converge to Global Minimizers in the Training of Deep Neural Networks with ReLU Activation,” Journal of Mathematical Analysis and Applications, 2026, article 130724, DOI 10.1016/j.jmaa.2026.130724. For broad classes of ReLU deep networks and SGD-type optimizers, it proves that high-probability convergence to global minimizers fails, with failure probability tending exponentially to one as width or depth grows. The authors explicitly note that success could instead mean convergence to strictly suboptimal levels close to the infimum; their result does not establish that remaining possibility or its selection mechanism.

  • Dennis Chemnitz and Maximilian Engel, “Characterizing Dynamical Stability of Stochastic Gradient Descent in Overparameterized Learning,” Journal of Machine Learning Research 26(134), 2025, pp. 1–46, direct URL. A characteristic Lyapunov exponent is proved to determine whether SGD can accumulate at a given global minimum. This rigorously advances minima selection in interpolating models, but it distinguishes stability among global minima rather than showing preference for local minima with smaller empirical-risk gaps.

Consequently, the strongest positive theorems either assume special overparameterized geometry, start locally near a favorable minimum, or analyze idealized smoothing/stability. The remaining gap is the requested unified, checkable theory for deep-network mini-batch SGD that both controls the value of the selected suboptimal local minimum and derives the preference over worse local minima from the actual stochastic-gradient sampling law.

References
  1. [1]ICM Conjectures · 2022-opt-26 link
  2. [2]ICM 2022: The mathematics of artificial intelligence link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.