Related papers: A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data

A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data

URL: http://arxiv.org/abs/2203.03808v1
Date: Tue, 8 Mar 2022 02:02:32 GMT
Title: A Fast Scale-Invariant Algorithm for Non-negative Least Squares with Non-negative Data
Authors: Jelena Diakonikolas, Chenghui Li, Swati Padmanabhan, Chaobing Song
Abstract summary: We show that the data itself is nonnegative as well, and we show that the nonnegativity in this case makes the problem easier. In particular, while the oracle complexity of unconstrained least squares problems necessarily scales with one of the data matrix constants, we show that nonnegative least squares problems with nonnegative data are solvable to multiplicative error.
Score: 18.81091632124107
License: http://creativecommons.org/licenses/by/4.0/
Abstract: Nonnegative (linear) least square problems are a fundamental class of problems that is well-studied in statistical learning and for which solvers have been implemented in many of the standard programming languages used within the machine learning community. The existing off-the-shelf solvers view the non-negativity constraint in these problems as an obstacle and, compared to unconstrained least squares, perform additional effort to address it. However, in many of the typical applications, the data itself is nonnegative as well, and we show that the nonnegativity in this case makes the problem easier. In particular, while the oracle complexity of unconstrained least squares problems necessarily scales with one of the data matrix constants (typically the spectral norm) and these problems are solved to additive error, we show that nonnegative least squares problems with nonnegative data are solvable to multiplicative error and with complexity that is independent of any matrix constants. The algorithm we introduce is accelerated and based on a primal-dual perspective. We further show how to provably obtain linear convergence using adaptive restart coupled with our method and demonstrate its effectiveness on large-scale data via numerical experiments.

Related papers

Learning to sample fibers for goodness-of-fit testing [0.0]
We consider the problem of constructing exact goodness-of-fit tests for discrete exponential family models. We translate the problem into a Markov decision process and demonstrate a reinforcement learning approach for learning good moves' for sampling. Our algorithm is based on an actor-critic sampling scheme, with provable convergence.
arXiv Detail & Related papers (2024-05-22T19:33:58Z)
Paired Autoencoders for Inverse Problems [3.355436702348694]
We consider the solution of nonlinear inverse problems where the forward problem is a discretization of a partial differential equation. The main computational bottleneck of typical algorithms is the direct estimation of the data misfit. We use a paired autoencoder framework as a likelihood-free estimator for inverse problems.
arXiv Detail & Related papers (2024-05-21T22:00:34Z)
Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
arXiv Detail & Related papers (2022-11-16T18:59:54Z)
A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems [0.0]
This paper focuses on the numerical computation of large-scale linearly constrained sparse group square-root Lasso problems. We propose a dual semismooth Newton (SSN) based augmented Lagrangian method (ALM) for it. Numerical experiments demonstrate the efficiency of the proposed algorithm.
arXiv Detail & Related papers (2021-11-27T12:20:43Z)
Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustness [68.97830259849086]
Most datasets only capture a simpler subproblem and likely suffer from spurious features. We study adversarial robustness - a local generalization property - to reveal hard, model-specific instances and spurious features. Unlike in other applications, where perturbation models are designed around subjective notions of imperceptibility, our perturbation models are efficient and sound. Surprisingly, with such perturbations, a sufficiently expressive neural solver does not suffer from the limitations of the accuracy-robustness trade-off common in supervised learning.
arXiv Detail & Related papers (2021-10-21T07:28:11Z)
Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
arXiv Detail & Related papers (2021-04-13T23:21:01Z)
Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
In many applications, we need algorithms which can align partially overlapping point sets are invariant to the corresponding corresponding RPM algorithm. We first show that the objective is a cubic bound function. We then utilize the convex envelopes of trilinear and bilinear monomial transformations to derive its lower bound. We next develop a branch-and-bound (BnB) algorithm which only branches over the transformation variables and runs efficiently.
arXiv Detail & Related papers (2021-01-19T04:24:23Z)
Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
arXiv Detail & Related papers (2020-12-29T04:08:38Z)
Matrix-wise $\ell_0$-constrained Sparse Nonnegative Least Squares [22.679160149512377]
Nonnegative least squares problems with multiple right-hand sides (MNNLS) arise in models that rely on additive linear combinations. We introduce a novel formulation for sparse MNNLS, with a matrix-wise sparsity constraint. We show that our proposed two-step approach provides more accurate results than state-of-the-art sparse codings applied both column-wise and globally.
arXiv Detail & Related papers (2020-11-22T17:21:16Z)
Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
arXiv Detail & Related papers (2020-08-05T17:52:10Z)
Consistency analysis of bilevel data-driven learning in inverse problems [1.0705399532413618]
We consider the adaptive learning of the regularization parameter from data by means of optimization. We demonstrate how to implement our framework on linear inverse problems. Online numerical schemes are derived using the gradient descent method.
arXiv Detail & Related papers (2020-07-06T12:23:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.