On the implementation of LIR: the case of simple linear regression with interval data

This paper considers the problem of simple linear regression with interval-censored data. That is, \(n\) pairs of intervals are observed instead of the \(n\) pairs of precise values for the two variables (dependent and independent). Each of these intervals is closed but possibly unbounded, and contains the corresponding (unobserved) value of the dependent or independent variable. The goal of the regression is to describe the relationship between (the precise values of) these two variables by means of a linear function. Likelihood-based Imprecise Regression (LIR) is a recently introduced, very general approach to regression for imprecisely observed quantities. The result of a LIR analysis is in general set-valued: it consists of all regression functions that cannot be excluded on the basis of likelihood inference. These regression functions are said to be undominated. Since the interval data can be unbounded, a robust regression method is necessary. Hence, we consider the robust LIR method based on the minimization of the residuals’ quantiles. For this method, we prove that the set of all the intercept-slope pairs corresponding to the undominated regression functions is the union of finitely many polygons. We give an exact algorithm for determining this set (i.e., for determining the set-valued result of the robust LIR analysis), and show that it has worst-case time complexity \(O(n^{3}\log n)\) . We have implemented this exact algorithm as part of the R package linLIR.     

Robust and efficient variable selection for semiparametric partially linear varying coefficient model based on modal regression

Semiparametric partially linear varying coefficient models (SPLVCM) are frequently used in statistical modeling. With high-dimensional covariates both in parametric and nonparametric part for SPLVCM, sparse modeling is often considered in practice. In this paper, we propose a new estimation and variable selection procedure based on modal regression, where the nonparametric functions are approximated by $B$ -spline basis. The outstanding merit of the proposed variable selection procedure is that it can achieve both robustness and efficiency by introducing an additional tuning parameter (i.e., bandwidth $h$ ). Its oracle property is also established for both the parametric and nonparametric part. Moreover, we give the data-driven bandwidth selection method and propose an EM-type algorithm for the proposed method. Monte Carlo simulation study and real data example are conducted to examine the finite sample performance of the proposed method. Both the simulation results and real data analysis confirm that the newly proposed method works very well.     

A Parallel Splitting Method for Separable Convex Programs

In this paper, we propose a new parallel splitting augmented Lagrangian method for solving the nonlinear programs where the objective function is separable with three operators and the constraint is linear. The method is an improvement of the method of He (Comput. Optim. Appl., 2(42):195–212, 2009), where we generate a predictor using the same parallel splitting augmented Lagrangian scheme as that in He (Comput. Optim. Appl., 2(42):195–212, 2009), while adopting a new strategy to get the next iterate. Under the mild assumptions of convexity of the underlying mappings and the non-emptiness of the solution set, we prove that the proposed algorithm is globally convergent. We apply the new method in the area of image processing and to solve some quadratic programming problems. The preliminary numerical results indicate that the new method is efficient.     

Block splitting for distributed optimization

This paper describes a general purpose method for solving convex optimization problems in a distributed computing environment. In particular, if the problem data includes a large linear operator or matrix $A$ , the method allows for handling each sub-block of $A$ on a separate machine. The approach works as follows. First, we define a canonical problem form called graph form, in which we have two sets of variables related by a linear operator $A$ , such that the objective function is separable across these two sets of variables. Many types of problems are easily expressed in graph form, including cone programs and a wide variety of regularized loss minimization problems from statistics, like logistic regression, the support vector machine, and the lasso. Next, we describe graph projection splitting, a form of Douglas–Rachford splitting or the alternating direction method of multipliers, to solve graph form problems serially. Finally, we derive a distributed block splitting algorithm based on graph projection splitting. In a statistical or machine learning context, this allows for training models exactly with a huge number of both training examples and features, such that each processor handles only a subset of both. To the best of our knowledge, this is the only general purpose method with this property. We present several numerical experiments in both the serial and distributed settings.     

Convex Modeling of Interactions With Strong Heredity

We consider the task of fitting a regression model involving interactions among a potentially large set of covariates, in which we wish to enforce strong heredity. We propose FAMILY, a very general framework for this task. Our proposal is a generalization of several existing methods, such as VANISH, hierNet, the all-pairs lasso, and the lasso using only main effects. It can be formulated as the solution to a convex optimization problem, which we solve using an efficient alternating directions method of multipliers (ADMM) algorithm. This algorithm has guaranteed convergence to the global optimum, can be easily specialized to any convex penalty function of interest, and allows for a straightforward extension to the setting of generalized linear models. We derive an unbiased estimator of the degrees of freedom of FAMILY, and explore its performance in a simulation study and on an HIV sequence dataset. Supplementary materials for this article are available online.     

ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals

In this article, we propose an algorithm, nesta-lasso, for the lasso problem, i.e., an underdetermined linear least-squares problem with a 1-norm constraint on the solution. We prove under the assumption of the restricted isometry property (rip) and a sparsity condition on the solution, that nesta-lasso is guaranteed to be almost always locally linearly convergent. As in the case of the algorithm nesta, proposed by Becker, Bobin, and Candès, we rely on Nesterov’s accelerated proximal gradient method, which takes $O(\sqrt {1/\varepsilon })$ iterations to come within $\varepsilon > 0$ of the optimal value. We introduce a modification to Nesterov’s method that regularly updates the prox-center in a provably optimal manner. The aforementioned linear convergence is in part due to this modification. In the second part of this article, we attempt to solve the basis pursuit denoising (bpdn) problem (i.e., approximating the minimum 1-norm solution to an underdetermined least squares problem) by using nesta-lasso in conjunction with the Pareto root-finding method employed by van den Berg and Friedlander in their spgl1 solver. The resulting algorithm is called parnes. We provide numerical evidence to show that it is comparable to currently available solvers.     

Estimates of the solutions of two-point boundary-value problems for systems of first-order integrodifferential equations and the method of lines

One proves theorems on the estimates of the solutions of the systems of first-order integrodifferential equations with the boundary conditions On the basis of these theorems, one suggests a method for estimating the norms of integrodifferential equations by the method of the lines for the solutions of the periodic boundary-value problems for second-order integrodifferential equations of parabolic type. On the basis of the established theorem, on the solvability and on the estimate of the solution of the nonlinear equation $$Tx + F\left( x \right) = 0$$ in a Banach space X, where T is a linear unbounded operator, one investigates the convergence of the method of lines for solving the periodic boundary-value problem for a second-order nonlinear integrodifferential equation of parabolic type.     

On the properties of Sard kernels and multiple error estimates for bounded linear functionals of bivariate functions with application to non-product cubature

Each Sard kernels theorem supplies multiple error estimates for a bounded linear functional, provided the underlying multivariate function is sufficiently smooth. The error estimation due to Sard generally concerns the $L_1$ -norms of Sard kernels and the supremum norms of different partial derivatives of a given function. This article presents a verified method for computing Sard error constants. To assist the verified computation, we examine relevant properties of Sard kernels for general bounded linear functionals of bivariate functions. The derived $L_1$ -norms, together with interval Taylor arithmetic, make the multiple error estimates possible. We demonstrate the flexibility and superiority of Sard kernels method by different numerical examples that concern non-product cubature for bivariate functions.     

An Extragradient-Based Alternating Direction Method for Convex Minimization

In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processing and other fields have the structure that while one of the two functions has an easy proximal mapping, the other function is smoothly convex but does not have an easy proximal mapping. Therefore, the classical alternating direction methods cannot be applied. To deal with the difficulty, we propose in this paper an alternating direction method based on extragradients. Under the assumption that the smooth function has a Lipschitz continuous gradient, we prove that the proposed method returns an \(\epsilon \)-optimal solution within \(O(1/\epsilon )\) iterations. We apply the proposed method to solve a new statistical model called fused logistic regression. Our numerical experiments show that the proposed method performs very well when solving the test problems. We also test the performance of the proposed method through solving the lasso problem arising from statistics and compare the result with several existing efficient solvers for this problem; the results are very encouraging.     

Alexander duality in experimental designs

If $F$ is a full factorial design and $D$ is a fraction of $F$ , then for a given monomial ordering, the algebraic method gives a saturated polynomial basis for $D$ which can be used for regression. Consider now an algebraic basis for the complementary fraction of $D$ in $F$ , built under the same monomial ordering. We show that the basis for the complementary fraction is the Alexander dual of the first basis, constructed by shifting monomial exponents. For designs with two levels, the Alexander dual uses the traditional definition for simplicial complexes, while for designs with more than two levels, the dual is constructed with respect to the basis for the design $F$ . This yields various new constructions for designs, where the basis and linear aberration can easily be read from the duality.     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

Linear Transformations and Reduction Formulas for the Gelfand Hypergeometric Functions Associated with the Grassmannians $$G_{2,4} $$ and $$G_{3,6} $$

We show that the Gelfand hypergeometric functions associated with the Grassmannians $G_{2,4} $ and $G_{3,6} $ with some special relations imposed on the parameters can be represented in terms of hypergeometric series of a simpler form. In particular, a function associated with the Grassmannian $G_{2,4} $ (the case of three variables) can be represented (depending on the form of the additional conditions on the parameters of the series) in terms of the Horn series $H_2 ,G_2 $ , of the Appell functions $F_1 ,F_2 ,F_3 $ and of the Gauss functions $F_1^2 $ , while the functions associated with the Grassmannian $G_{3,6} $ (the case of four variables) can be represented in terms of the series $G_2 ,F_1 ,F_2 ,F_3 $ and $F_1^2 $ . The relation between certain formulas and the Gelfand--Graev--Retakh reduction formula is discussed. Combined linear transformations and universal elementary reduction rules underlying the method were implemented by a computer program developed by the authors on the basis of the computer algebra system Maple V-4.     

Sparse trace norm regularization

We study the problem of estimating multiple predictive functions from a dictionary of basis functions in the nonparametric regression setting. Our estimation scheme assumes that each predictive function can be estimated in the form of a linear combination of the basis functions. By assuming that the coefficient matrix admits a sparse low-rank structure, we formulate the function estimation problem as a convex program regularized by the trace norm and the \(\ell _1\) -norm simultaneously. We propose to solve the convex program using the accelerated gradient (AG) method; we also develop efficient algorithms to solve the key components in AG. In addition, we conduct theoretical analysis on the proposed function estimation scheme: we derive a key property of the optimal solution to the convex program; based on an assumption on the basis functions, we establish a performance bound of the proposed function estimation scheme (via the composite regularization). Simulation studies demonstrate the effectiveness and efficiency of the proposed algorithms.     

Nonlinear superharmonic functions and supersolutions

Due to the lack of representation formulas for superharmonic functions associated with p-harmonic equations ${-\nabla \cdot(|\nabla u|^{p-2}\nabla u) = \mu}$ and their generalizations ${-\nabla \cdot A(x,\nabla u) = \mu}$ ,where ${A(x,\nabla u) \cdot \nabla u \approx | \nabla u |^{p}}$ , the interplay between nonlinear superharmonic functions and supersolutions is more important than in the linear case. Using the recent result of Kilpeläinen et. al., we establish sufficient and necessary conditions in terms of the Riesz measure μ that a p-superharmonic function is an ordinary weak supersolution. As an example we consider p-superharmonic solutions of the Poisson-type equation ${-\nabla \cdot A(x,\nabla u) = f(x)}$ .     

Approximation of Boolean functions to Schaefer’s classes

We consider an algorithm for transferring Boolean functions to function classes for which the generalized satisfiability problem is solvable in polynomial time (Schaefer??s classes). For the case where an initial function is represented as a truth-table, it is proved that the complexity of the algorithm is $ {l^2} + l\,\log_2^2(l) $ , where l is the input length.     

A discontinuous Galerkin scheme for front propagation with obstacles

We are interested in front propagation problems in the presence of obstacles. We extend a previous work (Bokanowski et al. SIAM J Sci Comput 33(2):923–938, 2011), to propose a simple and direct discontinuous Galerkin (DG) method adapted to such front propagation problems. We follow the formulation of Bokanowski et al. (SIAM J Control Optim 48(7):4292–4316, (2010)), leading to a level set formulation driven by $\min (u_t + H(x,\nabla u), u-g(x))=0$ , where $g(x)$ is an obstacle function. The DG scheme is motivated by the variational formulation when the Hamiltonian $H$ is a linear function of $\nabla u$ , corresponding to linear convection problems in the presence of obstacles. The scheme is then generalized to nonlinear equations, written in an explicit form. Stability analysis is performed for the linear case with Euler forward, a Heun scheme and a Runge-Kutta third order time discretization using the technique proposed in Zhang and Shu (SIAM J Numer Anal 48:1038–1063, 2010). Several numerical examples are provided to demonstrate the robustness of the method. Finally, a narrow band approach is considered in order to reduce the computational cost.     

Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation

We present two linearization-based algorithms for mixed-integer nonlinear programs (MINLPs) having a convex continuous relaxation. The key feature of these algorithms is that, in contrast to most existing linearization-based algorithms for convex MINLPs, they do not require the continuous relaxation to be defined by convex nonlinear functions. For example, these algorithms can solve to global optimality MINLPs with constraints defined by quasiconvex functions. The first algorithm is a slightly modified version of the LP/NLP-based branch-and-bouund \((\text{ LP/NLP-BB })\) algorithm of Quesada and Grossmann, and is closely related to an algorithm recently proposed by Bonami et al. (Math Program 119:331–352, 2009). The second algorithm is a hybrid between this algorithm and nonlinear programming based branch-and-bound. Computational experiments indicate that the modified LP/NLP-BB method has comparable performance to LP/NLP-BB on instances defined by convex functions. Thus, this algorithm has the potential to solve a wider class of MINLP instances without sacrificing performance.     

The k-error linear complexity distribution for 2^n-periodic binary sequences

The linear complexity and the \(k\) -error linear complexity of a sequence have been used as important security measures for key stream sequence strength in linear feedback shift register design. By using the sieve method of combinatorics, we investigate the \(k\) -error linear complexity distribution of \(2^n\) -periodic binary sequences in this paper based on Games–Chan algorithm. First, for \(k=2,3\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences (with linear complexity less than \(2^n\) ) are characterized. Second, for \(k=3,4\) , the complete counting functions for the \(k\) -error linear complexity of \(2^n\) -periodic binary sequences with linear complexity \(2^n\) are presented. Third, as a consequence of these results, the counting functions for the number of \(2^n\) -periodic binary sequences with the \(k\) -error linear complexity for \(k = 2\) and \(3\) are obtained.