• Estimate Bias of larger steps (learning rate)
• cf. Simon (Heidelberg) work?

Operatornorm for Changing Learning rate

Basis change matrices do not cancel out

Ideas

• Piecewise constant learning rate?
• Basis change matrices are maybe similar enough, add basis change for iteration n and bound the difference between basis change n+1 and change n
  • somehow surgically remove the basis change differences from the
    product without forcing a product of operator norms

1. Start out gd from n points -> distribution
2. split one point in random distribution around point occasionally during training
   -> tree (too many branches for parallelization)
   -> branch cutting based on current height (evolutionary algorithm).
   Tree has independent strands so we can apply SGD proof (for mathematical proof
   pretend cutting does not exist) then apply culling to full tree.

Tree might approximate uniform distribution over all parameters?

• smoothes loss (fulfill assumptions for convergence proofs)
• gaussian kernel -> random shift of the measurement location

Start with a lot of smoothing, slowly reduce -> wide minima? global optimization?

cf. https://arxiv.org/abs/2011.02009 (go back through references)

https://link.springer.com/content/pdf/10.1007/s11222-021-10016-8.pdf
https://arxiv.org/pdf/1309.3116.pdf

Convergence? Martingale theory

https://math.stackexchange.com/questions/4306820/convergence-behavior-of-sequence-with-diminishing-contraction

when eigenvectors are the standard basis (sec 4.1)

Markov index process? Cf. https://arxiv.org/abs/2112.03754

In high dimension random vectors are likely orthogonal (cf. https://math.stackexchange.com/questions/995623/why-are-randomly-drawn-vectors-nearly-perpendicular-in-high-dimensions/4307960#4307960)

Can this justify ada-heuristics? I.e. orthogonal to most except for a small subset which has likely a different eigenvalue distribution within than all the eigenvalues? E.g. two dimensional: it is likely that a random vector has more of one standard basis component than the other. So if the standard basis vectors where the eigenvectors, this random vector would have more of one eigenvalue than the other in some sense. So the ada heuristics would capture some of that probably?

Try on quadratic functions

Talk to Martin about this

The estimating sequences approach can be used in a stochastic setting assuming strong convexity. (lem: SGD bound with noise)

• true model: linear
• sample gaussian input points
• add gaussian noise to outputs

fit overparametrized polynomials. SGD should be more robust than least squares regression. Did not work so far. Figure out why

-> diagonal hessian? fast optimization?

• Deriving convolution from first principles
• https://arxiv.org/abs/1805.05533

Instead of the upper bound, use second order approximation and reorder for the directional derivative. Estimate directional derivative and use that instead of lipschitz constant.

Regularization? (bound third derivative?, levenberg-marquart?)

• classic case
• stochastic case