← All AI/ML open problems

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.

OpenEditorially scopedSpecified modelCompiled 2026-11-20

Seed catalog · Showing the bundled record.

Problem statement

An online learner observes xt∈Rdx_t\in\mathbb R^d, ∥xt∥2≤1\|x_t\|_2\leq1, predicts pt∈(0,1)p_t\in(0,1), then observes yt∈{−1,1}y_t\in\{-1,1\}. Can it achieve expected log-loss regret ERT≤Cdlog⁡(1+BT)\mathbb E R_T\leq C d\log(1+BT) against every logistic predictor of norm at most B≥1B\geq1, with total computation T poly⁡(d,b,log⁡T,log⁡B)T\,\operatorname{poly}(d,b,\log T,\log B) on bb-bit rational inputs? Predictions may be improper. Obtain a near-linear-in-TT 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

  1. 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.

  2. 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.

  3. 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.