Logarithmic Regret for parameter-free Online Logistic Regression
This provides a parameter-free algorithm with logarithmic regret for online logistic regression, addressing optimization in adversarial environments, though it is incremental as it builds on existing EKF methods.
The paper tackles online logistic regression by introducing the Semi-Online Step (SOS) algorithm, proving an O(log(n)) regret bound in adversarial settings, and extends this to the Extended Kalman Filter (EKF) with similar bounds in constant dynamics and well-specified models.
We consider online optimization procedures in the context of logistic regression, focusing on the Extended Kalman Filter (EKF). We introduce a second-order algorithm close to the EKF, named Semi-Online Step (SOS), for which we prove a O(log(n)) regret in the adversarial setting, paving the way to similar results for the EKF. This regret bound on SOS is the first for such parameter-free algorithm in the adversarial logistic regression. We prove for the EKF in constant dynamics a O(log(n)) regret in expectation and in the well-specified logistic regression model.