Optimal and computationally tractable lower bounds for logistic log-likelihoods

Summary The logit transform is arguably the most popular link function beyond linear settings. Its routine use, combined with the lack of analytical solutions for optimization problems involving this transform, continues to motivate research in computational statistics. Among the directions explored, a central one has focused on the design of tractable tangent lower bounds for logistic log-likelihoods, facilitating the derivation of minorize-maximize (MM) schemes and variational Bayes (VB) approximations. However, popular approaches rely on quadratic minorizers, and it remains unclear whether tangent lower bounds sharper than quadratic ones can be obtained without sacrificing tractability. We cover this gap by introducing a novel piecewise quadratic lower bound that uniformly improves any tangent quadratic minorizer and has direct interpretation in terms of the classical generalized lasso problem. As shown empirically, this bound can accelerate current MM schemes for point estimation and yields VB approximations with higher accuracy than those based on quadratic bounds.