A Screening Strategy for Structured Optimization Involving Nonconvex $\ell_{q,p}$ Regularization

• URL: http://arxiv.org/abs/2208.02161v1
• Date: Tue, 2 Aug 2022 10:01:49 GMT
• Title: A Screening Strategy for Structured Optimization Involving Nonconvex $\ell_{q,p}$ Regularization
• Authors: Tiange Li, Xiangyu Yang and Hao Wang
• Abstract summary: We develop a rule strategy to improve the computational efficiency in solving structured optimization involving nonell_qp$ regularization. We prove that our rule can remove all inactive variables in a finite number of iterations of the IRL1 method. Numerical experiments illustrate the efficiency of our screening rule strategy compared with several state-of-the-art algorithms.
• Score: 5.522202658637732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we develop a simple yet effective screening rule strategy to improve the computational efficiency in solving structured optimization involving nonconvex $\ell_{q,p}$ regularization. Based on an iteratively reweighted $\ell_1$ (IRL1) framework, the proposed screening rule works like a preprocessing module that potentially removes the inactive groups before starting the subproblem solver, thereby reducing the computational time in total. This is mainly achieved by heuristically exploiting the dual subproblem information during each iteration.Moreover, we prove that our screening rule can remove all inactive variables in a finite number of iterations of the IRL1 method. Numerical experiments illustrate the efficiency of our screening rule strategy compared with several state-of-the-art algorithms.

Related papers

• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation [0.135975510645475]
  In this work, we derive safe screening rules that can be used to discard inessential samples. The new tests are much faster to compute, especially for problems involving a parameter space of high dimension. We show how an existing homotopy algorithm to compute the regularization path of the lasso method can be reparametrized with respect to the squared $ell_$-penalty.
  arXiv  Detail & Related papers  (2023-10-13T08:10:46Z)
• Iterative Reweighted Least Squares Networks With Convergence Guarantees for Solving Inverse Imaging Problems [12.487990897680422]
  We present a novel optimization strategy for image reconstruction tasks under analysis-based image regularization. We parameterize such regularizers using potential functions that correspond to weighted extensions of the $ell_pp$-vector and $mathcalS_pp$ Schatten-matrix quasi-norms. We show that thanks to the convergence guarantees of our proposed minimization strategy, such optimization can be successfully performed with a memory-efficient implicit back-propagation scheme.
  arXiv  Detail & Related papers  (2023-08-10T17:59:46Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  optimization of the Area Under the Precision-Recall Curve (AUPRC) is a crucial problem for machine learning. In this work, we present the first trial in the single-dependent generalization of AUPRC optimization. Experiments on three image retrieval datasets on speak to the effectiveness and soundness of our framework.
  arXiv  Detail & Related papers  (2022-09-27T09:06:37Z)
• Globally Convergent Policy Search over Dynamic Filters for Output Estimation [64.90951294952094]
  We introduce the first direct policy search algorithm convex which converges to the globally optimal $textitdynamic$ filter. We show that informativity overcomes the aforementioned degeneracy.
  arXiv  Detail & Related papers  (2022-02-23T18:06:20Z)
• Learning to solve TV regularized problems with unrolled algorithms [18.241062505073234]
  Total Variation (TV) is a popular regularization strategy that promotes piece-wise constant signals. We develop and characterize two approaches to do so, describe their benefits and limitations, and discuss the regime where they can actually improve over iterative procedures.
  arXiv  Detail & Related papers  (2020-10-19T14:19:02Z)
• Alternating Direction Method of Multipliers for Quantization [15.62692130672419]
  We study the performance of the Alternating Direction Method of Multipliers for Quantization ($texttADMM-Q$) algorithm. We develop a few variants of $texttADMM-Q$ that can handle inexact update rules. We empirically evaluate the efficacy of our proposed approaches.
  arXiv  Detail & Related papers  (2020-09-08T01:58:02Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  Ordered $L_1$ (OWL) regularized regression is a new regression analysis for high-dimensional sparse learning. Proximal gradient methods are used as standard approaches to solve OWL regression. We propose the first safe screening rule for OWL regression by exploring the order of the primal solution with the unknown order structure.
  arXiv  Detail & Related papers  (2020-06-29T23:35:53Z)
• Safe Screening Rules for $\ell_0$-Regression [3.04585143845864]
  The screening rules can be computed from a convex relaxation solution in linear time. Experiments on real and synthetic data indicate that, on average, 76% of the variables can be fixed to their optimal values.
  arXiv  Detail & Related papers  (2020-04-19T06:07:09Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.