Statistical learning theory · Optimization & optimizers / Open question
Fast Logistic Learning with Optimal Regret
Even a convex linear prediction model can have a gap between statistically optimal learning and an implementation whose cost scales gently with the data stream. Efficiency payoff: Obtain optimal online log-loss guarantees without expensive posterior integration or a large comparator-norm penalty.
Seed catalog · Showing the bundled record.
Problem statement
An online learner observes , , predicts , then observes . Can it achieve expected log-loss regret against every logistic predictor of norm at most , with total computation on -bit rational inputs? Predictions may be improper. Obtain a near-linear-in- algorithm with only polylogarithmic norm dependence, or a computational lower bound.
Assumptions and scope
- Regret subtracts min_{||w||<=B} sum_t log(1+exp(-y_t w^T x_t)) from the learner's cumulative Bernoulli log loss. The learner sees x_t before predicting; an adaptive non-anticipating adversary may use the past but not the learner's fresh internal random bits.
- The learner may output any probability rather than one common linear model, so proper-learning lower bounds do not apply automatically. Computational precision must make cumulative numerical loss error bounded; access to exact posterior samples or log-concave integrals is not free.
- Report dimension, input-bit, memory and failure-probability dependence. The target excludes a power of T or B hidden in a sampling subroutine; any weaker runtime/regret improvement must state what overhead remains.
What would settle it?
The stated statistical guarantee with near-linear total time and polylogarithmic B dependence, or an explicit computational obstruction. Polynomial-time improper learning or linear-in-B regret alone is an established weaker baseline.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Foster et al. already remove exponential norm dependence. Jézéquel et al. give fast per-round updates with a linear B regret factor; the 2026 mixture-of-sigmoids result sharply improves the cost of near-optimal regret to a reported O(B^3 T^5). This stricter joint resource target is an editorial formulation, not a claim that improper logistic learning remains impossible. This is an editorial, source-motivated research target. The preliminary review through 2026-11-20 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Foster et al. — Logistic Regression: The Importance of Being Improper ↗partial theory · source checked 2026-11-20
Primary and scholarly abstracts checked: improper prediction already removes exponential comparator-norm dependence, with near-optimal regret and a costly implementation. The old possibility question is resolved.
- Jézéquel, Gaillard and Rudi — Efficient Improper Learning for Online Logistic Regression ↗partial theory · source checked 2026-11-20
Scholarly abstract checked: O(d^2) per-round work with a linear-in-B regret factor. Fast improper prediction already exists; the remaining target asks for logarithmic norm dependence at low computation.
- Di Gennaro, Chakraborty and Zhivotovskiy — Efficient Logistic Regression with Mixture of Sigmoids ↗partial theory · source checked 2026-11-20
Scholarly abstract checked: near-optimal O(d log(Bn)) regret with O(B^3 n^5) reported total complexity, substantially improving older bounds; separable-data geometric adaptation also analyzed. Polynomial-time feasibility is not open.