Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs
Phase diagram showing achievable time complexity for different batch sizes and algorithms.
$\ell$ is the information exponent (or leap index) of the target.
It requires Python 3.10 or later (not tested on Python later than 3.11).
git submodule update --init --recursive # install boostmath
pip install -r requirements.txt
pip install -e giant-learning --no-binary :all:
As the paper, our code is divided into two parts:
- Time Complexity Analysis at initialization: This part is implemented in the notebook
time-complexity.ipynb. - Exact Asymptotic ODEs: This part is implemented in the notebook
exact-asymptotic.ipynb.
In the folder mathematica/ you can find the Mathematica notebook used to derive the explicit ODEs for the exact asymptotic analysis.