More Like this

1. Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

   https://doi.org/10.1007/s10107-023-01966-0  

   He, Ziyu ; Han, Shaoning ; Gómez, Andrés ; Cui, Ying ; Pang, Jong-Shi ( May 2023 , Mathematical Programming)

   This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$${\ell }_0$-path” where the discontinuous$$\ell _0$$${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$${\ell }_1$-path” where the$$\ell _1$$${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$${\ell }_1$-function aims to enhance the$$\ell _1$$${\ell }_1$-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$${\ell }_1$-path. Our study of the capped$$\ell _1$$${\ell }_1$-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$${\ell }_0$-path and the$$\ell _1$$${\ell }_1$-path. Indeed, while the$$\ell _0$$${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$${\ell }_1$-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.

    

   more » « less
2. Semileptonic form factors for $$B\rightarrow D^*\ell \nu $$ at nonzero recoil from $$2+1$$-flavor lattice QCD: Fermilab Lattice and MILC Collaborations

   https://doi.org/10.1140/epjc/s10052-022-10984-9  

   Bazavov, A. ; DeTar, C. E. ; Du, D. ; El-Khadra, A. X. ; Gámiz, E. ; Gelzer, Z. ; Gottlieb, S. ; Heller, U. M. ; Kronfeld, A. S. ; Laiho, J. ; et al ( December 2022 , The European Physical Journal C)

   We present the first unquenched lattice-QCD calculation of the form factors for the decay$$B\rightarrow D^*\ell \nu $$$B\to D^{\ast }\ell \nu$at nonzero recoil. Our analysis includes 15 MILC ensembles with$$N_f=2+1$$$N_f=2+1$flavors of asqtad sea quarks, with a strange quark mass close to its physical mass. The lattice spacings range from$$a\approx 0.15$$$a\approx 0.15$fm down to 0.045 fm, while the ratio between the light- and the strange-quark masses ranges from 0.05 to 0.4. The valencebandcquarks are treated using the Wilson-clover action with the Fermilab interpretation, whereas the light sector employs asqtad staggered fermions. We extrapolate our results to the physical point in the continuum limit using rooted staggered heavy-light meson chiral perturbation theory. Then we apply a model-independent parametrization to extend the form factors to the full kinematic range. With this parametrization we perform a joint lattice-QCD/experiment fit using several experimental datasets to determine the CKM matrix element$$|V_{cb}|$$$|V_{\mathrm{cb}}|$. We obtain$$\left| V_{cb}\right| = (38.40 \pm 0.68_{\text {th}} \pm 0.34_{\text {exp}} \pm 0.18_{\text {EM}})\times 10^{-3}$$$\left(V_{\mathrm{cb}}\right)=(38.40\pm 0.{68}_{\text{th}}\pm 0.{34}_{\text{exp}}\pm 0.{18}_{\text{EM}})\times {10}^{-3}$. The first error is theoretical, the second comes from experiment and the last one includes electromagnetic and electroweak uncertainties, with an overall$$\chi ^2\text {/dof} = 126/84$$${\chi }^2\text{/dof}=126/84$, which illustrates the tensions between the experimental data sets, and between theory and experiment. This result is in agreement with previous exclusive determinations, but the tension with the inclusive determination remains. Finally, we integrate the differential decay rate obtained solely from lattice data to predict$$R(D^*) = 0.265 \pm 0.013$$$R\left(D^{\ast }\right)=0.265\pm 0.013$, which confirms the current tension between theory and experiment.

    

   more » « less
3. Sparse representation of vectors in lattices and semigroups

   https://doi.org/10.1007/s10107-021-01657-8  

   Aliev, Iskander ; Averkov, Gennadiy ; De Loera, Jesús A. ; Oertel, Timm ( May 2021 , Mathematical Programming)

   We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the$$\ell _0$$${\ell }_0$-norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$${\ell }_0$-norm of solutions to systems$$A\varvec{x}=\varvec{b}$$$Ax=b$, where$$A\in \mathbb {Z}^{m\times n}$$$A\in Z^{m\times n}$,$${\varvec{b}}\in \mathbb {Z}^m$$$b\in Z^m$and$$\varvec{x}$$$x$is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\ell _0$$${\ell }_0$-norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\mathbb {R}$$$R$, to other subdomains such as$$\mathbb {Z}$$$Z$. We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.

    

   more » « less
4. Measurement of the mass dependence of the transverse momentum of lepton pairs in Drell–Yan production in proton–proton collisions at $$\sqrt{s} = 13\,\text {Te\hspace{-.08em}V} $$

   https://doi.org/10.1140/epjc/s10052-023-11631-7  

   Tumasyan, A. ; Adam, W. ; Andrejkovic, J. W. ; Bergauer, T. ; Chatterjee, S. ; Dragicevic, M. ; Valle, A. Escalante ; Frühwirth, R. ; Jeitler, M. ; Krammer, N. ; et al ( July 2023 , The European Physical Journal C)

   The double differential cross sections of the Drell–Yan lepton pair ($$\ell ^+\ell ^-$$${\ell }^{+}{\ell }^{-}$, dielectron or dimuon) production are measured as functions of the invariant mass$$m_{\ell \ell }$$$m_{\ell \ell }$, transverse momentum$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, and$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$. The$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$observable, derived from angular measurements of the leptons and highly correlated with$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, is used to probe the low-$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$region in a complementary way. Dilepton masses up to 1$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$are investigated. Additionally, a measurement is performed requiring at least one jet in the final state. To benefit from partial cancellation of the systematic uncertainty, the ratios of the differential cross sections for various$$m_{\ell \ell }$$$m_{\ell \ell }$ranges to those in the Z mass peak interval are presented. The collected data correspond to an integrated luminosity of 36.3$$\,\text {fb}^{-1}$$${\text{fb}}^{-1}$of proton–proton collisions recorded with the CMS detector at the LHC at a centre-of-mass energy of 13$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$. Measurements are compared with predictions based on perturbative quantum chromodynamics, including soft-gluon resummation.

    

   more » « less
5. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less