felixbenning / optimization-review

Masterthesis

Final version can be found here: https://arxiv.org/abs/2112.15392

Abstract

This thesis reviews numerical optimization methods with machine learning problems in mind. Since machine learning models are highly parametrized, we focus on methods suited for high dimensional optimization. We build intuition on quadratic models to figure out which methods are suited for non-convex optimization, and develop convergence proofs on convex functions for this selection of methods. With this theoretical foundation for stochastic gradient descent and momentum methods, we try to explain why the methods used commonly in the machine learning field are so successful. Besides explaining successful heuristics, the last chapter also provides a less extensive review of more theoretical methods, which are not quite as popular in practice. So in some sense this work attempts to answer the question: Why are the default Tensorflow optimizers included in the defaults?

optimization-review's Issues

momentum in stochastic setting on quadratic functions

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

SGD on overfitted polynomials

• 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

Remove iid assumption from examples

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

Convergence rate of Heuristics

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

when eigenvectors are the standard basis (sec 4.1)

Check out Convolutions on Loss

• 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)

Fouriertransform diagonalizes Convolutions?

-> diagonal hessian? fast optimization?

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

Justify eigenvectors are standard basis with High Dimensionality?

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

Heavy Tailed error in SGD

Convergence? Martingale theory

(S)LLN, CLTs Review

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

Evolutionary Branch Cutting

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?

Multi-level Monte Carlo

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

Estimating Sequences in Stochastic Setting

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

Calculation Based Backtracking

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

Krylov Subspace Descent is PCA on Hessian?

Talk to Martin about this