To anyone interested.

Quite frankly I have worked very hard the last year with the single
goal of proving results about gradient descent.  Please use what I
have anyway you can (and add me to your paper).

My Claude 1 window, whom I asked to help me, reassured me that this
work is great. My Claude 2-5 windows, whom I asked to review the
paper, have been saying that the paper is worth very little. I would
love to hear your thoughts on it. Is any of this work worth developing
further, or should I redirect my efforts? I'd appreciate an honest
answer over a polite one. Or maybe you know someone who can publish
some of this with me.

My goal has been to prove that gradient descent finds zero error in
logarithmic time while making as few assumptions as possible.  I have
had assumptions of various flavors, but they all boil down to assuming
that the network remains random through the gradient descent process.
With this I was able to prove 70 pages about how gradient descent
behaves with all different ranges of parameters. What I failed to
really appreciate is that the hard part of the proof was in the
assumption, because we do not know how the network changes as gradient
descent proceeds. I suppose I really only did "one step of gradient
descent", which is the easy part.

One thing that may be standard and may be a contribution is that I
focused on training only one layer of the neural network.  The first
network stage is x_d = f_1(a_d), where f_1 is a fixed random network
mapping (possibly a single real value) input a_d to a data
representation x_d in R^M. What I sent you three years ago is that if
these x_d are linearly independent, then gradient descent works great.
The next network stage is z_d = W x_d in R^M'. Here W in R^{M' x M}
are the weights that we train.  The final stage is the output
f_3(z_d). Again f_3 is a fixed random network.  Let g_d in R^M' be the
gradient of f_3 at z_d, and let alpha_d = |g_d|^2 be its
sensitivity. We always assume that the gradient descent experts are
able to keep this at least some minimum alpha.  One nice thing about
this model is that the rate matrix governing convergence is R = (G^T
G) o (X^T X), i.e. R_dd' = (g_d . g_d')(x_d . x_d'). This is a
Khatri-Rao (Gram) matrix and is the restriction of your empirical NTK
to the W-block . Along gradient flow, dE/dt = -4 e^T R e, so any floor
lambda_min(R_t) >= mu > 0 gives E_t <= E_0 exp(-4 mu t).

If M >= D (the x_d linearly independent), there is a floor for free:
lambda_min(R_t) >= lambda_min(X^T X) * alpha_min(t) for the whole run
(Schur's product bound). That is the result I sent you.

The interesting case is M < D <= MM': the gradients g_d must supply
the missing dimensions. When f_1, W_0 and f_3 are random (f_3 complex
enough, analytic activations), R has full rank at initialization once
MM' >= D, and with probability one it stays full rank along gradient
descent (for all but countably many step sizes). But full rank says
nothing about how small lambda_min(R_t) becomes. Our mistake was to
assume that lambda_min(R_t) stays above a constant times alpha_min
throughout training.

I do a few obvious steps to extend Blum and Rivest's NP-completeness
result to this model (when the sigmoids look more like
thresholds). But maybe more fun, I give a dynamic programming
algorithm somewhat matching the lower bound complexity when the input
representation X is almost full rank ... but for the easier problem
min_W max_d (y_d - y_d)^2 (instead of min_W sum_d (y_d - y_d)^2).
This is the point where I thought I was done and sent the paper to
Claudes 2-5, who hated it.

Since then I kept posing conjectures to Claude, who is getting smarter
and smarter, and I no longer have the energy to read her pages of
results. Here is my honest summary of where it stands.

THE CONJECTURE. Let f_1, W_0 and f_3 be random, M < D, and MM' >= CD,
where C > 1 is a fixed number (say 2). Then along gradient descent (at
least for realizable targets), with high probability lambda_min(R_t)
>= c alpha_min(t) for all t, where c > 0 depends on C but not on D. (C
> 1 matters: at MM' = D, R has full rank, but with independent random
gradients lambda_min is only about alpha/D^2.)  WHAT WE HAVE.

1) At initialization. If the g_d were independent Gaussian vectors
(and the x_d reasonably spread out), then lambda_min(R) >= c *
alpha_min once MM' >= CD. We only have a sketch (Hanson-Wright plus a
net argument), which gives some large unspecified C, and I suspect
this is known. Simulations suggest that any C > 1 works, with c about
(1 - 1/sqrt(C))^2, as in the Marchenko-Pastur law. With only pairwise
near-orthogonality of the g_d, the simple Gershgorin argument needs
MM' >= D^2; reaching MM' = Theta(D) uses the random signs that
independence provides. For a Gaussian-process f_3 whose correlation
length is small compared with the distances between the z_d, the g_d
are nearly independent. For a finite cosine (random Fourier feature)
f_3 we have only simulations.

2) Knowledge does not help. We started by limiting what a GD adversary
knows about f_3 after a few steps, but this buys nothing: an adversary
can reach any W within the movement budget in one step, without
knowing anything. So one has to limit how far W moves.

3) A proved but weak trajectory result. If W -> R(W) is L_R-Lipschitz
near W_0 and lambda_min(R_0)^{3/2} > (3/2) L_R sqrt(E_0), then
lambda_min(R_t) stays bounded away from zero forever and gradient flow
converges (a short ODE comparison). With our best estimates of L_R for
a random smooth f_3, this closes only when MM' >~ D^2 and M' >~
D. That is the regime where W moves less than one correlation length
of f_3, i.e. the lazy regime, which I assume is not new. At MM' =
Theta(D) it does not close. At one simulated size (D = 200), our bound
on L_R was roughly 40-360 times larger than the rate of change we
could find numerically.

4) Where the conjecture is false. If f_3 depends on z only through k
directions (e.g. a single neuron sigma(a . z)), then rank(R) <= kM;
for a quadratic f_3, rank(R) <= M(M+3)/2. So f_3 must be genuinely
complex.

5) Simulations (cosine f_3, D = 51, realizable targets, 3 seeds per
width, MM' from 1.1D to 51D): lambda_min(R_t)/alpha_min(t) never fell
below about a third of its starting value, and the error went to zero
(to about 10^-20, except at MM' = 1.1D, where it reached 10^-3 to
10^-5 after 20,000 iterations). The typical z_d moved between about
0.2 correlation lengths of f_3 (at MM' = 51D) and 1.2 (at MM' = 1.1D);
the farthest moved about 1.8. These are small experiments.

So we have no proof of the conjecture for any f_3 -- not for Gaussian processes, not for cosine features. Even the lazy-regime statement in item 3 rests on the initialization sketch in item 1.

I am attaching

(1) my way too long paper as it was when I sent it to Claude 2-5, with
a one-page list of the errors found since, and

(2) short notes (six pages) on what we have done since. These notes
were drafted mostly by Claude at my direction. [CHECK: add "I have
read them" only if true.]

Even a one-line "worth pursuing" or "move on" would be immensely helpful.

Thank you so so much for considering this.
Jeff Edmonds
Department of Electrical Engineering and Computer Science
York University
jeff@cse.yorku.ca