# Optimization Algorithms

[Sci-hub!](https://sci-hub.se/)
[Chasing Convex Bodies Optimally (Sel21)](https://arxiv.org/pdf/1905.11968.pdf)
[Chasing Convex Bodies with Linear Competitive Ratio (AGGT21)](https://arxiv.org/pdf/1905.11877.pdf)

- [BKL+18](https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.91) (Tau)
- Choosing Steiner for each $K_t$
- $O(min(d, \sqrt{d\log T}))$
- [ABC+19](https://arxiv.org/pdf/1806.08865.pdf) (LTF)
- $O(d\log d)$
- [BLLS19](https://arxiv.org/pdf/1811.00887.pdf) (LF) (November 5, 2018)
- [Sit14](https://arxiv.org/pdf/1110.6600.pdf) (WP)
- [FL93](https://www.cs.huji.ac.il/~nati/PAPERS/convex_body_chasing.pdf)
- [BBE17](https://arxiv.org/pdf/1707.05527.pdf)
- - -

- [Smoothed Online Convex Optimization in High Dimensions
via Online Balanced Descent](https://arxiv.org/pdf/1803.10366.pdf)
- [Chasing Convex Bodies Optimally](https://arxiv.org/pdf/1905.11968.pdf)
- [BKL+18: Chasing Nested Convex Bodies Nearly Optimally](https://epubs.siam.org/doi/pdf/10.1137/1.9781611975994.91)

- - -

- [Online Mirror Descent](https://sudeepraja.github.io/OMD/)

## Backup

1. [CONTRACTING PROXIMAL METHODS FOR SMOOTH CONVEX OPTIMIZATION](https://epubs.siam.org/doi/pdf/10.1137/19M130769X)
1. [The Complexity of Gradient Descent: CLS = PPAD ∩ PLS](https://sci-hub.se/https://dl.acm.org/doi/10.1145/3406325.3451052)
1. [An overview of gradient descent optimization algorithms](https://arxiv.org/abs/1609.04747)
1. [An Online Algorithm for Maximum-Likelihood Quantum State Tomography](https://arxiv.org/pdf/2012.15498.pdf)
1. [AN INEXACT PROXIMAL POINT ALGORITHM FOR NONMONOTONE EQUILIBRIUM PROBLEMS IN BANACH SPACES](https://projecteuclid.org/journals/taiwanese-journal-of-mathematics/volume-17/issue-6/AN-INEXACT-PROXIMAL-POINT-ALGORITHM-FOR-NONMONOTONE-EQUILIBRIUM-PROBLEMS-IN/10.11650/tjm.17.2013.3266.full)

- - -

1. Introduction
2. Background (introduced by FL93) (WP)
- relations with other problems
4. First upper bound (BLLS19) (LF)
- solving strategy
5. Nested case
- introduction (Tau)
- greedy (ABC+19) (Tau)
- binary lifting & centroid (ABC+19) (LTF)
- centroid is not good enough (BBE17)
- Steiner point (BKL+20) (Tau)
- a lower bound (BKL+20) (Tau)
6. General case
- greedy approach is not competitive (FL93) (LF)
- Explain that Steiner point & binary lifting is still good. (Sel21) (WP)
- Special case: Euclidean norm (AGGT21) (LTF)
- an algorithm to approximate Steiner point
7. Conclusion
8. Reference