February 2021 - Various modeling techniques are used to predict the capacity fade of Li-ion batteries. Algebraic reduced-order models, which are inherently interpretable and computationally fast, are ideal for use in battery controllers, technoeconomic models, and multi-objective optimizations. For Li-ion batteries with graphite anodes, solid-electrolyte-interphase (SEI) growth on the graphite surface dominates fade. This fade is often modeled using physically informed equations, such as square-root of time for predicting solvent-diffusion limited SEI growth, and Arrhenius and Tafel-like equations predicting the temperature and state-of-charge rate dependencies. In some cases, completely empirical relationships are proposed. However, statistical validation is rarely conducted to evaluate model optimality, and only a handful of possible models are usually investigated. This article demonstrates a novel procedure for automatically identifying reduced-order degradation models from millions of algorithmically generated equations via bi-level optimization and symbolic regression. Identified models are statistically validated using cross-validation, sensitivity analysis, and uncertainty quantification via bootstrapping. On a LiFePO4/Graphite cell calendar aging data set, automatically identified models utilizing square-root, power law, stretched exponential, and sigmoidal functions result in greater accuracy and lower uncertainty than models identified by human experts, and demonstrate that previously known physical relationships can be empirically "rediscovered" using machine learning.