Simple gradient methods often converge at a fast, geometric rate on problems like sparse logistic regression or group-sparse least squares, even though these problems lack the curvature (strong convexity) that classical theory needs to promise such speed. Optimization theory explains this with error bounds: inequalities saying that, near the set of solutions, the distance to that set is at most a constant $\kappa$ times a quantity the solver can compute, such as the length of a proximal gradient step. When an error bound holds, linear convergence follows. When it fails, the theory predicts a slowdown to sublinear rates. A large body of this theory has never been checked on real data. Several key papers contain no experiments at all, and the constants they rely on are treated as unknowable for realistic losses.
We propose to turn the error bound from an assumption into a measured quantity. For an important class of problems, the solution set can be computed exactly enough to measure the distance to it, so the ratio between distance and residual can be traced across real datasets. We use this measurement to test the theory's sharpest predictions: whether the bound holds, its constant, its exponent, and the radius inside which it applies. The flagship test is the $\ell_{1,p}$ phase transition. Theory says first-order methods converge linearly for $p \in [1,2] \cup \{\infty\}$ and sublinearly for $p \in (2,\infty)$, and this has only been confirmed on synthetic data. The question is whether that boundary is visible on high-dimensional benchmarks or is hidden by finite precision and practical solver heuristics.
Core Claim
Our claim is that a single problem-level measurement, an empirical error-bound profile, predicts convergence behavior across different solvers better than fitting each solver's convergence curve separately. The profile records how the ratio $\mathrm{dist}(x,X^*)/r(x)$ behaves as the residual $r(x)$ shrinks. If the ratio stays bounded, the measured $\kappa$ should set the linear rate of proximal gradient, block coordinate descent and their accelerated variants, and the scale where the ratio stabilizes should mark where burn-in ends. If the ratio grows like a power of $1/r$, as predicted for $p>2$, every solver should slow down in the same way. If this holds, it gives the field a way to validate claims that so far exist only as theorems. If it fails, because measured constants do not transfer across solvers, then error-bound constants are less useful in practice than the theory implies, and that negative result is also worth knowing.
Why the Distance Is Computable
The obstacle that kept error bounds unmeasured is that the solution set $X^*$ is usually not a single point, so "distance to the solution" is not the distance to a reference solution. For composite problems $F(x) = h(Ax) + g(x)$, where $h$ is strictly convex (least squares, logistic loss) and $g$ is a convex regularizer, there is useful structure. The fitted values $y^* = Ax^*$ and the gradient $\nabla h(y^*)$ are the same for every solution. The solution set is therefore exactly the convex set of points $x$ with $Ax = y^*$ that also satisfy the optimality condition for $g$ at the fixed dual vector $-A^\top \nabla h(y^*)$. This invariance underlies the proofs in ℓ_{1,p}-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods (Zhou et al., which derive the phase transition from Lipschitz properties of the optimality mapping) and in On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems (Zhang, Jiang and Luo, which prove a local error bound for sparse group Lasso with fewer samples than features and report no experiments).
We reuse this invariance as a measurement tool. First, we solve to very high accuracy with a long accelerated run in extended precision to obtain $y^*$ and the dual vector. Then we compute $\mathrm{dist}(x,X^*)$ for any query point $x$ by solving a projection problem onto that convex set. The residual is the proximal gradient step length
$$r(x) = \|x - \mathrm{prox}_{\alpha g}(x - \alpha \nabla f(x))\|,$$
where $\alpha$ is the step size and $f = h \circ A$. The empirical modulus at residual scale $s$ is the largest observed ratio $\mathrm{dist}(x,X^*)/r(x)$ among sampled points with $r(x) \approx s$. Because it is a maximum over samples, it is a certified lower bound on the true local $\kappa$. We sample points two ways: along solver trajectories, and by random perturbations of solutions in directions tangent and normal to $X^*$. Perturbation sampling probes worst-case directions that trajectories may never visit. The fitted log-log slope of distance against residual estimates the Hölder exponent studied in Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence and Restarting Frank-Wolfe: Faster Rates under Hölderian Error Bounds. Both papers show that this exponent controls rates but never measure it.
Research Program
The first component is the measurement tool itself. We validate it on synthetic instances where the solution set and $\kappa$ are known in closed form, and we check that the estimates are stable across random seeds and across the precision of the reference solve.
The second component is the phase-transition audit. We run $\ell_{1,p}$-regularized logistic regression and least squares with $p \in \{1, 1.5, 2, 3, 4, \infty\}$ on rcv1_binary (RCV1: A New Benchmark Collection for Text Categorization Research), real-sim, E2006-tfidf and E2006-log1p. Groups come from two sources: feature clustering, and random partitions as a control. For each setting we record the error-bound profile and the convergence of proximal gradient, block coordinate gradient descent, accelerated proximal gradient with adaptive restart, and the error-bound-adaptive method from Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions. That paper benchmarks on the same LIBSVM datasets under $\ell_1$ regularization but never varies $p$ and never measures the bound. The specific question is whether, at the tolerances practitioners use (relative suboptimality around $10^{-6}$ to $10^{-10}$), the $p>2$ ratio grows enough to matter, or whether acceleration and restarts hide the predicted slowdown.
The third component is the first empirical test of the sparse group Lasso bound in the regime with fewer samples than features. We use the same datasets subsampled to that regime, together with colon-cancer (62 examples, 2,000 features). The theorem in that paper is purely local, so measuring the radius where the ratio stabilizes is the substantive new information.
The fourth component addresses the open question in A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates. That paper ran LoPGD on colon-cancer metric learning with a hand-chosen epoch schedule because the exponent $\theta$ could not be derived. We estimate $\theta$ for this problem using a suboptimality-based profile that does not require a unique solution, measuring distance to the nearest of several independently computed high-accuracy solutions as an upper estimate. We then ask whether a schedule set from the measured $\theta$ matches or improves on the hand-tuned one. This component is secondary because the distance computation here is only approximate, and we will report it as such.
Neural collapse, studied in Linear Convergence Analysis of Neural Collapse with Unconstrained Features, has a solution manifold that is also computable. It is a natural follow-up, but we keep it out of scope so the main test stays clean.
Baselines
The naive reference point is per-solver curve fitting. For each solver we fit the slope of log suboptimality against iteration and treat that slope as "the rate." This is what an experimental section normally reports, and it requires no theory. Our measurement must beat it on transfer. We fit slopes on proximal gradient at one step size, then predict the rates of proximal gradient at other step sizes, block coordinate descent, and accelerated variants. We compare these predictions with the ones obtained by plugging the measured $\kappa$ and the known smoothness constant into the contraction factors given by error-bound theory. Both predictors get the same proximal gradient trajectories as input, so the comparison is fair. Our approach wins if the $\kappa$-based predictions fall within a factor of two of the observed rates across solvers more often than the slope-transfer predictions do.
The theory-only baseline is the analytic constant. For polyhedral cases, such as $p \in \{1,\infty\}$, Hoffman-type bounds of the kind used in Global Error Bounds and Linear Convergence for Gradient-Based Algorithms for Trend Filtering and ℓ1-Convex Clustering give computable but typically very loose constants. We report the gap between analytic and measured $\kappa$. A gap of several orders of magnitude would quantify, for the first time on real data, how conservative these theorems are.
The strongest existing method for actually solving these problems without knowing the constants is the family of parameter-free restart schemes: ASA from Yang et al. (2018), RASSG from Yang et al. (2016), and Wolfe-gap restarts from Restarting Frank-Wolfe. We run each with its published default settings and a matched tuning budget of the same number of grid points we allow for tuning step sizes elsewhere, on the same data and hardware. We found no reported number on Lacuna for any of these methods on $\ell_{1,p}$ problems with $p>2$, or on rcv1/real-sim/E2006 rates as numerical values; the papers present those results only in figures. The only reported head-to-head numbers in the file are on colon-cancer metric learning. There, LoPGD reached objective 0.0405 in 1.89 hours with 8 projections, while standard projected gradient descent reached 0.0879 after more than 57 hours and 8,000 projections (A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates). A schedule set from our measured $\theta$ beats LoPGD if it reaches 0.0405 with no more projections or less wall-clock time. Matching it would still be informative, because it would show the hand-tuned schedule was close to what the geometry implies.
Two ablations isolate the key ingredient. The first replaces the true distance to the solution set with distance to a single reference solution, which is what one would naively do. This shows whether the solution-set projection matters: on problems with non-unique solutions, the naive version should overestimate $\kappa$ and wrongly predict slow convergence. The second ablation uses trajectory samples only, without perturbations, to test whether solvers' paths alone reveal the worst-case constant.
Why not just…?
Why not just plot convergence curves and read off the rates? For a single solver on a single problem, that works, and we do not claim otherwise. The threat is real: if fitted slopes transfer across solvers as well as measured $\kappa$ does, our measurement adds nothing beyond plots. The cross-solver transfer experiment settles this directly. What curve fitting cannot do is distinguish between two causes of slow convergence: the error bound fails, or the solver is poorly configured. It also cannot locate where burn-in ends. Both questions are central to the $p>2$ test.
Why not just use parameter-free restart methods and ignore the constants? For solving problems, these methods are often the right choice. ASA and RASSG were built precisely because the constants are unknown, and Kerdreux et al. report robustness to the restart parameter. But adaptivity hides diagnosis. A restart scheme that runs fast on $p=3$ tells us nothing about whether the theorem's failure is practically irrelevant or whether the scheme compensates for it. Our experiments compare restart methods on both sides of the phase boundary, so we can see whether they absorb the predicted slowdown.
Why not just compute the constants analytically, as the theory papers do? Analytic constants exist only for polyhedral or specially structured cases. Even there, Hoffman-type constants are known to be loose, and Yang et al. explicitly could not derive $\theta$ for their metric-learning problem. The analytic-versus-measured comparison in our baselines quantifies this looseness instead of assuming it.
Decisive Checks
The idea succeeds if three things happen. Measured profiles show a bounded ratio for $p \le 2$ and a growing ratio for $p \in \{3,4\}$ on at least the rcv1 and E2006 datasets. Proximal gradient and block coordinate descent slow down where and when the profile predicts. And $\kappa$-based rate predictions transfer across solvers better than slope fitting does. The idea is falsified as a practical tool, though the result would still be an informative negative one, under either of two outcomes. One is that the $p>2$ ratio stays bounded down to $10^{-10}$ suboptimality on real data, which would mean the theorem's failure is invisible at practical precision. The other is that measured $\kappa$ predicts rates no better than per-solver slopes. We will release the measurement code and all profiles, so purely theoretical error-bound results can be checked on real data in the future.
References
- \(\ell_{1, p}\)-Norm Regularization: Error Bounds and Convergence Rate Analysis of First-Order Methods
- On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems
- Stochastic Convex Optimization: Faster Local Growth Implies Faster Global Convergence
- Restarting Frank-Wolfe: Faster Rates Under Hölderian Error Bounds
- RCV1: A New Benchmark Collection for Text Categorization Research
- Fast Rates of ERM and Stochastic Approximation: Adaptive to Error Bound Conditions
- A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
- Linear Convergence Analysis of Neural Collapse with Unconstrained Features
- Global Error Bounds and Linear Convergence for Gradient-Based Algorithms for Trend Filtering and 𝓁 1 -Convex Clustering.
- Restarting Frank-Wolfe