skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 10:00 PM ET on Friday, December 8 until 2:00 AM ET on Saturday, December 9 due to maintenance. We apologize for the inconvenience.


Title: Strong Rules for Discarding Predictors in Lasso-Type Problems
Summary

We consider rules for discarding predictors in lasso regression and related problems, for computational efficiency. El Ghaoui and his colleagues have proposed ‘SAFE’ rules, based on univariate inner products between each predictor and the outcome, which guarantee that a coefficient will be 0 in the solution vector. This provides a reduction in the number of variables that need to be entered into the optimization. We propose strong rules that are very simple and yet screen out far more predictors than the SAFE rules. This great practical improvement comes at a price: the strong rules are not foolproof and can mistakenly discard active predictors, i.e. predictors that have non-zero coefficients in the solution. We therefore combine them with simple checks of the Karush–Kuhn–Tucker conditions to ensure that the exact solution to the convex problem is delivered. Of course, any (approximate) screening method can be combined with the Karush–Kuhn–Tucker conditions to ensure the exact solution; the strength of the strong rules lies in the fact that, in practice, they discard a very large number of the inactive predictors and almost never commit mistakes. We also derive conditions under which they are foolproof. Strong rules provide substantial savings in computational time for a variety of statistical optimization problems.

 
more » « less
NSF-PAR ID:
10401328
Author(s) / Creator(s):
; ; ; ; ; ;
Publisher / Repository:
Oxford University Press
Date Published:
Journal Name:
Journal of the Royal Statistical Society Series B: Statistical Methodology
Volume:
74
Issue:
2
ISSN:
1369-7412
Page Range / eLocation ID:
p. 245-266
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. null (Ed.)
    This paper is devoted to the development of a continuum theory for materials having granular microstructure and accounting for some dissipative phenomena like damage and plasticity. The continuum description is constructed by means of purely mechanical concepts, assuming expressions of elastic and dissipation energies as well as postulating a hemi-variational principle, without incorporating any additional postulate like flow rules. Granular micromechanics is connected kinematically to the continuum scale through Piola's ansatz. Mechanically meaningful objective kinematic descriptors aimed at accounting for grain-grain relative displacements in finite deformations are proposed. Karush-Kuhn-Tucker (KKT) type conditions, providing evolution equations for damage and plastic variables associated to grain-grain interactions, are derived solely from the fundamental postulates. Numerical experiments have been performed to investigate the applicability of the model. Cyclic loading-unloading histories have been considered to elucidate the material-hysteretic features of the continuum, which emerge from simple grain-grain interactions. We also assess the competition between damage and plasticity, each having an effect on the other. Further, the evolution of the load-free shape is shown not only to assess the plastic behavior, but also to make tangible the point that, in the proposed approach, plastic strain is found to be intrinsically compatible with the existence of a placement function. 
    more » « less
  2. We consider the problem of designing a feedback controller that guides the input and output of a linear time-invariant system to a minimizer of a convex optimization problem. The system is subject to an unknown disturbance, piecewise constant in time, which shifts the feasible set defined by the system equilibrium constraints. Our proposed design combines proportional-integral control with gradient feedback, and enforces the Karush-Kuhn-Tucker optimality conditions in steady-state without incorporating dual variables into the controller. We prove that the input and output variables achieve optimality in steady-state, and provide a stability criterion based on absolute stability theory. The effectiveness of our approach is illustrated on a simple example system. 
    more » « less
  3. Symbol-level precoding (SLP) based on the concept of constructive interference (CI) is shown to be superior to traditional block-level precoding (BLP), however at the cost of a symbol-by-symbol optimization during the precoding design. In this paper, we propose a CI-based block-level precoding (CI-BLP) scheme for the downlink transmission of a multi-user multiple-input single-output (MU-MISO) communication system, where we design a constant precoding matrix to a block of symbol slots to exploit CI for each symbol slot simultaneously. A single optimization problem is formulated to maximize the minimum CI effect over the entire block, thus reducing the computational cost of traditional SLP as the optimization problem only needs to be solved once per block. By leveraging the Karush-Kuhn-Tucker (KKT) conditions and the dual problem formulation, the original optimization problem is finally shown to be equivalent to a quadratic programming (QP) over a simplex. Numerical results validate our derivations and exhibit superior performance for the proposed CI-BLP scheme over traditional BLP and SLP methods, thanks to the relaxed block-level power constraint. 
    more » « less
  4. We consider the problem of designing a feedback controller that guides the input and output of a linear time-invariant system to a minimizer of a convex optimization problem. The system is subject to an unknown disturbance that determines the feasible set defined by the system equilibrium constraints. Our proposed design enforces the Karush-Kuhn-Tucker optimality conditions in steady-state without incorporating dual variables into the controller. We prove that the input and output variables achieve optimality in equilibrium and outline two procedures for designing controllers that stabilize the closed-loop system. We explore key ideas through simple examples and simulations. 
    more » « less
  5. null (Ed.)
    Abstract We study a 1-dimensional discrete signal denoising problem that consists of minimizing a sum of separable convex fidelity terms and convex regularization terms, the latter penalize the differences of adjacent signal values. This problem generalizes the total variation regularization problem. We provide here a unified approach to solve the problem for general convex fidelity and regularization functions that is based on the Karush–Kuhn–Tucker optimality conditions. This approach is shown here to lead to a fast algorithm for the problem with general convex fidelity and regularization functions, and a faster algorithm if, in addition, the fidelity functions are differentiable and the regularization functions are strictly convex. Both algorithms achieve the best theoretical worst case complexity over existing algorithms for the classes of objective functions studied here. Also in practice, our C++ implementation of the method is considerably faster than popular C++ nonlinear optimization solvers for the problem. 
    more » « less