We consider the problem of estimating a good maximizer of a black-box function given noisy examples. We propose to fit a new type of function called a global optimization network (GON), defined as any composition of an invertible function and a unimodal function, whose unique global maximizer can be inferred in $\mathcal{O}(D)$ time, and used as the estimate. As an example way to construct GON functions, and interesting in its own right, we give new results for specifying multi-dimensional unimodal functions using lattice models with linear inequality constraints. We extend to conditional GONs that find a global maximizer conditioned on specified inputs of other dimensions. Experiments show the GON maximizers are statistically significantly better predictions than those produced by convex fits, GPR, or DNNs, and form more reasonable predictions for real-world problems.

We propose new multi-input shape constraints across four intuitive categories: complements, diminishers, dominance, and unimodality constraints. We show these shape constraints can be checked and even enforced when training machine-learned models for linear models, generalized additive models, and the nonlinear function class of multi-layer lattice models. Real-world experiments illustrate how the different shape constraints can be used to increase explainability and improve regularization, especially for non-IID train-test distribution shift.

Set functions predict a label from a permutation-invariant variable-size collection of feature vectors. We propose making set functions more understandable and regularized by capturing domain knowledge through shape constraints. We show how prior work in monotonic constraints can be adapted to set functions, and then propose two new shape constraints designed to generalize the conditioning role of weights in a weighted mean. We show how one can train standard functions and set functions that satisfy these shape constraints with a deep lattice network. We propose a nonlinear estimation strategy we call the semantic feature engine that uses set functions with the proposed shape constraints to estimate labels for compound sparse categorical features. Experiments on real-world data show the achieved accuracy is similar to deep sets or deep neural networks, but provides guarantees on the model behavior, which makes it easier to explain and debug.

A reverse concatenation coding scheme for storage systems in which the information is encoded first by a modulation (constraint) code and then by a systematic error-correcting code is considered. In this scheme, the output of the modulation coding stage has certain positions left “unconstrained”-in the sense that any way of filling them with bits results in a sequence that satisfies the constraint. These positions are then used to store the parity-check bits of the error-correcting code so that the result is a valid constrained sequence. The tradeoff function defines the maximum overall rate of the encoding scheme for a given density of unconstrained positions. This function is determined for two families of RLL constraints: RLL(d, ∞) and RLL(d, 2d+2). For RLL(d, 2d+2), a curious dichotomy in the shape of the tradeoff function between different ranges of values of d is shown to exist.

A reverse concatenation coding scheme for storage systems in which the information is encoded first by a modulation (constraint) code and then by a systematic error-correcting code is considered. In this scheme, the output of the modulation coding stage has certain positions left “unconstrained” in the sense that any way of filling them with bits results in a sequence that satisfies the constraint. These positions are then used to store the parity-check bits of the error-correcting code so that the result is a valid constrained sequence. The tradeoff function defines the maximum overall rate of the encoding scheme for a given density of unconstrained positions. This function is determined for two families of run length limited (RLL) constraints: $\mathrm{RLL}(d,\infty)$ and $\mathrm{RLL}(d,2d+2)$. For $\mathrm{RLL}(d,2d+2)$, a curious dichotomy in the shape of the tradeoff function between different ranges of values of d is shown to exist.

A method for computing lower bounds on capacities of two-dimensional (2D) constraints having a symmetric presentation in either the horizontal or the vertical direction is presented. The method is a generalization of the method of Calkin and Wilf (SIAMJ. Discrete Math., 1998). Previous best lower bounds on capacities of certain constraints are improved using the method. It is also shown how this method, as well as their method for computing upper bounds on the capacity, can be applied to constraints which are not of finite-type. Additionally, capacities of two families of multidimensional constraints are given exactly.

A method for computing lower bounds on capacities of 2-dimensional constraints having a symmetric presentation in either the horizontal or the vertical direction is presented. The method is a generalization of the method of Calkin and Wilf (SIAM J. Discrete Math., 1998). Previous best lower bounds on capacities of certain constraints are improved using the method. It is also shown how this method, as well as their method for computing upper bounds on the capacity, can be applied to constraints which are not of finite-type. Additionally, capacities of 2 families of multi-dimensional constraints are given exactly.

The maximum insertion rate of a one-dimensional constrained system over a finite alphabet is defined to be the maximum density of positions that can be freely, and independently, filled in with arbitrary symbols of the alphabet and still satisfy the constraint. In this paper, this concept is extended to higher dimensional constraints, that is, to constraints on D-dimensional arrays defined by imposing a 1-dimensional constraint in each dimension. We give a simple upper bound on the D-dimensional maximum insertion rate in terms of the individual 1-dimensional maximum insertion rate. For D-dimensional constraints defined by imposing the same 1-dimensional constraint in each dimension, we show that the D-dimensional maximum insertion rate is the same as the 1-dimensional maximum insertion rate. In this case (called the isotropic or, sometimes, symmetric case), we show that the maximum insertion rate is a lower bound on the limiting D-dimensional capacity as D tends to infinity. Finally, we show that in the case of a finite memory constraint, when the maximum insertion rate is zero, the D-dimensional capacity decays exponentially fast to zero.

Let F be a finite field and b be a positive integer. A construction is presented of codes over the alphabet F/sup b/ with the following three properties: i) the codes are maximum-distance separable (MDS) over F/sup b/, ii) they are linear over F, and iii) they have systematic generator and parity-check matrices over F with the smallest possible number of nonzero entries. Furthermore, for the case F=GF(2), the construction is the longest possible among all codes that satisfy properties i)-iii).