Quantum Algorithms for Projection-Free Sparse Convex Optimization

Jianhao He, John C.S. Lui · 2025

Read Quantum Algorithms for Projection-Free Sparse Convex Optimization by Jianhao He, John C.S. Lui (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-08543.txt.

Introduction

Jianhao He and John Lui give quantum algorithms for sparse optimization in twenty twenty-five. The problem is projection-free convex optimization with sparsity constraints. It covers many tasks in machine learning and data science. The authors treat both vector and matrix domains.

For vectors, two quantum algorithms find near-optimal solutions with fewer queries than the best classical method. The savings reach a factor tied to the square root of the dimension, or even the full dimension. For matrices under nuclear norm constraints, two more algorithms speed up the update step. Their gains also scale with dimension. Sparsity here means most entries stay zero, which keeps solutions simple. Readers get quantum speedups for a workhorse optimization family.

Catalog record

CREATORJianhao He, John C.S. Lui
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-08543

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Algorithms for Projection-Free Sparse Convex Optimization Jianhao He, John C.S. Lui Abstract This paper considers the projection-free sparse convex optimization problem for the vector domain and the matrix domain, which covers a large number of important applications in machine learning and data science. For the vector domain 𝒟 ⊂ ℝ d \mathcal{D}\subset\mathbb{R}^{d} , we propose two quantum algorithms for sparse constraints that finds a ε \varepsilon -optimal solution with the query complexity of O ⁡ ( d / ε ) O(\sqrt{d}/\varepsilon) and O ⁡ ( 1 / ε ) O(1/\varepsilon) by using the function value oracle, reducing a factor of O ⁡ ( d ) O(\sqrt{d}) and O ⁡ ( d ) O(d) over the best classical algorithm, respectively, where d d is the dimension. For the matrix domain 𝒟 ⊂ ℝ d × d \mathcal{D}\subset\mathbb{R}^{d\times d} , we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to O ~ ​ ( r ​ d / ε 2 ) \tilde{O}(rd/\varepsilon^{2}) and O ~ ​ ( r ​ d / ε 3 ) \tilde{O}(\sqrt{r}d/\varepsilon^{3}) for computing the update step, reducing at least a factor of O ⁡ ( d ) O(\sqrt{d}) over the best classical algorithm, where r r is the rank of the gradient matrix. Our algorithms show quantum advantages in projection-free sparse convex optimization problems as they outperform the optimal classical methods in dependence on the dimension d d . 1 Introduction In this paper, we consider the following constrained optimization problem of the form \min_{\bm{x}\in\mathcal{D}}f(\bm{x}), (1) such objective covers many important application in operations research and machine learning. We are interested in the case where 1) the objective function f is convex and continuously differentiable, and 2) the domain \mathcal{D}\subset\mathbb{R}^{d} is a feasible set that is convex, and the dimension d is high. Typical instances of such high-dimensional optimization problems include multiclass classification, multitask learning, matrix learning, network systems and many more [ 27 , 33 , 34 , 39 , 21 , 80 , 30 , 35 ] . As an example, for the matrix completion, the optimization problem to be solved is as follows: \displaystyle\min_{X\in\mathbb{R}^{m\times n},\norm{X}_{\tr}\leq r}\sum_{(i,j)\in\Omega}(X_{i,j}-Y_{i,j})^{2}, (2) where X is the matrix to be recovered, \Omega denotes the observed elements, Y_{i,j} is the observed known value at position (i,j) , and \norm{X}_{\tr}\leq r represents the trace norm (nuclear norm) constraint. Compared with unconstrained convex optimization problems, optimizing Equation 1 involves handling constraints, which introduces new challenges. A straightforward method for optimizing Equation 1 is the projected gradient descent approach [ 53 ] . This method first takes a step in the gradient direction and then performs the projection to satisfy the constraint. However, in practice, the dimensions of the feasible set can be very large, leading to prohibitively high computational complexity. For example, when solving Equation 2 , the projection step involves performing a singular value decomposition (SVD), whose time complexity is O(mn\min\{m,n\}) ( O(d^{3}) for X\in\mathbb{R}^{d\times d} ). Compared to the projected gradient descent approach, the Frank-Wolfe (FW) method (also known as the conditional gradient method) is more efficient when dealing with structured constrainted optimization problems. Rather than performing projections, it solves a computationally efficient linear sub-problem to ensure that the solution lies within the feasible set \mathcal{D} . When solving Equation 2 , the time complexity of the Frank-Wolfe method is O(mn) ( O(d^{2}) for X\in\mathbb{R}^{d\times d} ), which is significantly lower than the complexity of SVD-based projections. Since the Frank-Wolfe method is efficient for optimizing many difficult machine learning problems, such as low-rank constrained problems and sparsity-constrained problems, it has attracted significant attention and has been applied to solving Equation 3 and many of its variants. Despite the efficiency of FW in handling structured constraints, it still incurs significant computational overhead when dealing with high-dimensional problems. The bottleneck of the computation is the linear subproblem over \mathcal{D} , which is either assumed to have efficient implementation or simply follows existing classical oracles, such as [ 22 , 39 , 27 ] . The overhead of these oracles, however, grows linearly or superlinearly in terms of dimension d . Recently, quantum computing has emerged as a promising new paradigm to accelerate a large number of important optimization problems, e.g., combinatorial optimization [ 29 , 3 , 23 , 24 , 60 , 76 , 65 , 38 ] , linear programming [ 45 , 55 , 68 , 4 ] , second-order cone programming [ 49 , 48 , 46 ] , quadratic programming [ 44 ] , polynomial optimization [ 64 ] , semi-definite optimization [ 45 , 67 , 10 , 9 , 69 ] , convex optimization [ 70 , 14 , 81 ] , nonconvex optimization [ 78 , 19 ] , stochastic optimization [ 66 ] online optimization [ 37 , 36 , 57 ] , multi-arm bandit [ 13 , 72 , 56 , 71 ] . We aim to take a thorough investigation on whether quantum computing can accelerate FW algorithms, and in particular the linear sub-problem over structured constraints regarding dimension d . We aim to answer the following question: Can one utilize quantum techniques to accelerate Frank-Wolfe algorithms in terms of dimension d ? Chen et al. gave an initial answer to this question [ 17 ] . They considered the linear regression problem with explicit functional form where the closed form of gradient is provided. Given the precomputed matrix factors of the closed-form objective function stored in specific data structures, they leveraged HHL-based algorithms to accelerate matrix multiplications in calculating the closed-form gradient, leading to a upper bound of O\left(\sqrt{d}/\varepsilon^{2}\right) . In this work, we consider a more general problem where the objective function is a smooth convex function accessible only through a function value oracle, and then we consider a more general constraint conditions ( the latent group norm ball ) to enhance the theoretical framework’s applicability. Besides, we also consider the case of matrix feasible set, under different assumptions. To our best knowledge, we are the first one to consider accelerating the matrix case of the FW algorithm by quantum computing. Contributions. We give a systematic study on how to accelerate FW algorithms when \mathcal{D} is either a vector domain \mathbb{R}^{d} , or a matrix domain \mathbb{R}^{d\times d} subject to various structured constraints. Note that our findings can be applied to non-square matrices, we express our results using square matrices for simplicity of presentation (Remark 1 ). We summarize our contributions as follows. For the vector domain \mathcal{D}\subset\mathbb{R}^{d} : • We propose the quantum Frank-Wolfe algorithm for the projection-free sparse convex optimization problem under \ell_{1} norm constraints (Theorem 1 ) and the d -dimensional simplex \Delta_{d} (Theorem 2 ). We achieve a query complexity of \widetilde{O}(\sqrt{d}/\varepsilon) in finding an \varepsilon -optimal solution using the function value oracle, reducing a factor of O(\sqrt{d}) over the optimal classical algorithm. Furthermore, if the objective function is a Lipschitz continuous function, we prove that the query complexity can be reduced to O(1/\epsilon) by employing the bounded-error Jordan quantum gradient estimation algorithm, at the cost of more qubits and additional gates (Theorem 5 ). In addition, we consider the generalization to latent group norm constraints (Theorem 6 ) and achieve

Read the complete text