Monotonic Kronecker-Factored Lattice
Authors: William Taylor Bakst
Nobuyuki Morioka
Erez Louidor
Venue: ICLR 2021 Poster (2021)
Keywords: Theory
Regularization
Algorithms
Classification
Regression
Matrix and Tensor Factorization
Fairness
Evaluation
Efficiency
Machine Learning

Abstract: It is computationally challenging to learn flexible monotonic functions that guarantee model behavior and provide interpretability beyond a few input features, and in a time where minimizing resource use is increasingly important, we must be able to learn such models that are still efficient. In this paper we show how to effectively and efficiently learn such functions using Kronecker-Factored Lattice ($\mathrm{KFL}$), an efficient reparameterization of flexible monotonic lattice regression via Kronecker product. Both computational and storage costs scale linearly in the number of input features, which is a significant improvement over existing methods that grow exponentially. We also show that we can still properly enforce monotonicity and other shape constraints. The $\mathrm{KFL}$ function class consists of products of piecewise-linear functions, and the size of the function class can be further increased through ensembling. We prove that the function class of an ensemble of $M$ base $\mathrm{KFL}$ models strictly increases as $M$ increases up to a certain threshold. Beyond this threshold, every multilinear interpolated lattice function can be expressed. Our experimental results demonstrate that $\mathrm{KFL}$ trains faster with fewer parameters while still achieving accuracy and evaluation speeds comparable to or better than the baseline methods and preserving monotonicity guarantees on the learned model.

Published as a conference paper at ICLR 2021
MONOTONIC KRONECKER-FACTORE LATTICE
Nobuyuki Morioka, Erez Louidor; William Bakst"
Google Research
(nmorioka, erez, wbakst @ggooge.ccmm
ABSTRACT
It is computationally challenging to learn flexible monotonic functions that guaran- tee model behavior and provide interpretability beyond few input features, and in time where minimizing resource use is increasingly important, must be able to learn such models that are still efficient. In this paper we show how to effectively and efficiently learn such functions using Kronecker-Factoree Lattice (KFL), an efficient reparameterization of flexible monotonic lattice regression via Kronecker product. Both computational and storage costs scale linearly in the number of input features, which is a significant improvement over existing methods that grow exponentially. We also show that we can still properly enforce monotonicity and other shape constraints. The KFL function class consists of products of peccewise-lineal functions, and the size of the function class can be further increased through ensembling. We prove that the function class of an ensemble of . base KFL models strictly increases as M increases up to a certain threshold. Beyond this threshold, every multilinear interpolated lattice function can expressed. Our experimental results demonstrate that KFL trains faster with fewer parameters while still achieving accuracy and evaluation speeds comparable to or better than the bascline methods and preserving monotonicity guarantees on the learned model.
INTRODUCTION
Many machine learning problems have other requirements in addition to accuracy, such efficiency, storage, and interpretability. For example, the ability to learn flexible monotonic functions at scale is useful practice because machine learning practitioners often know apriori which input features positively negatively relate to the output and can incorporate these hints as inductive bias in the training to further regularize the model (Abu-Mostafa 1993) and guarantee its expected behavior on unseen examples. It is, however, computationally challenging to learn such functions efficiently. In this paper, we extend the work of interpretable monotonic lattice regression (Gupta et al., 2016) to significantly reduce computational and storage costs without compromising accuracy.
While a linear model with nonnegative coefficients able to learn simple monotonic functions, its function class is restricted. Prior works proposed non-lineat methods (Sill 1997] Dugas et al. 2009 Daniels & Velikoval 2010 Qu & Hu| (011] to learn more flexible monotonic functions, but they shown work only in limited settings of small datasets and low dimensional feature spaces. Monotonic lattice regression (Gupta et al.) 2016), an extension of lattice regression (Garcia et al.) 2012), learns an interpolated look-up table with linear inequality constraints that impose monotonicity. This has been demonstrated to work with millions of training examples and achieve competitive accuracy against, for example, random forests; however, because the number of model parameters scales exponentially in the number of input features, it is difficult to apply such models in high dimensional feature space settings. To overcome this limitation, (Canini al., (0166) incorporated ensemble learning to combine many tiny lattice models, each capturing non-linear interactions among a small random subset of features.
This paper proposes Cronecker-Factored Lattice (KFT.), novel reparameterization of monotonic lattice regression via Kronecker product to achieve significant parameter efficiency and simultancously provide guaranteed monotonicity of the learned model with respect to user- pees-preerrdbed set of input
"qqual contribution.

---

Published as a conference paper at ICLR 2021
features for user trust. Both inference and storage costs scale linearly in the number of features. Hence, it potentially allows for more features to non- non-linearly interact. Kronecker factorization has been applied to wide variety of problems including optimization (Martens & Grosse 2013 George et al. 2018 Osawa et al.) 2019), convolutional neural networks (Zhang et al. 2015). and recurrent neural networks (Jose et al. 2018), but, to the best of our knowledge, has not yet been explored to learn flexible monotonic functions.
The main contributions of this paper are: reparameterization of monotonic lattice regression to achieve linear evaluation time and storage of the resulting subclass of models, (2) proving sufficient and necessary conditions for KFL model be monotonic as well convex and nonnegative, (3) showing how the conditions for monotonicity can be efficiently imposed during training, (4) characterizing the values of M for which the capacity of the funetion class of an ensemble of M base KFL, models strictly increases and showing that with a large enough M an ensemble can express every multilinear interpolated lattice function, and (5) providing experimental results on both public and proprietary datasets that demonstrate that KFL has accuracy and evaluation speeds comparable to or better than other lattice methods while requiring less training time and fewer parameters.
NOTATION AND OVERVIEW OF MONOTONIC LATTICE REGRESSION
For n E N we denote by [n] the set {1.2..... n). For x E RD and E [D], let x[d denote the dth entry of We use ex,n to denote the one-hot vector in 1) ] where ed, = if d and [d, = O, otherwise. When n is clear from the context we write eş- For two real vectors v, w of the same length we if the respective inequality holds entrywise. We denote by 0 the zero vector in a real vector space T denote their Cartesian product and S T to denote the set of elements in S but not in T. We denote by [S] the cardinality of S. For piecewise linear function [= [0, - 1] - R whose graph has V-1 linear segments, where for .,..., V-1, the ith segment connects the points (i - 1, w w(i)) with (i, w( + 1]). See Figure for an example. Observe that for any a, 3 R and vectors w, v RV, have (: aw
denote their dot product. We write S and 2 w
whose dimension clear from the context. For two sets S and T we use
R.V. we use fpwi(a; w) denote the 1-dimensional continuous
3v) = fppi(: w) + V)pw).:v).
Symbol
Description
D
Number of features
ednn
"1-hot" n--iiennsional vector with in the dth entry
Spwl
1-dimensional piecewise linear function
fulll
Multilinear lattice function
fa
Simplex lattice function
fua
KFL function
V
D D-dimensional size of lattice
My
Set of vertices of lattice of size
Dv
Domain of a lattice model
Interpolation kernel.
0
Vector of lattice parameters
8:V;
Outer Kronecker product of vectors V;
KFL(V,M)
Class of ensembles of M KFL functions of size
r(T)
Rank of tensor
Table 1: Table of major notation
Lattice models, proposed in Garcia al. (2012) are interpolated look-up tables such that the function parameters are the function values sampled on a regular grid. They have been shown to exhibit efficient training procedures such that the resulting model is guaranteed to satisfy various types of shape constraints, including monotonicity and convexity (Gupta et al., 2016 2018 Cotter et al. 2019) without severely restricting the model class. See Figure for example.
2

---

Published as a conference paper at ICLR 2021
0.0
1.0
10
0.8
0.6
f(a]
0.5
0.5
0.4
02
0.0
0.0
0.6
Figure 1: f(x) fpwil (2; [0 0.5))
Figure 2: 2x2 multilinear interpolated lattice with four parameters defining a monotonically increasing function both dimensions.
More precisely, a D-dimensional lattice of size VEND consists of regular D-dimensional grid of look-up table vertices My {0, 1,..., V[]]-1} ... {0, 1, ...,,,.. D Thus, Vid is the number of vertices in the lattice in the dtth dimension, and the grid has [ Víd] vertices. We denote [0, V 1]. Typically. each feature is "calibrated" so that its value lies in 0. vid - 1]. using the piecewise- linear calibration technique of (Gupta et al. (0166) (see also Section 3.5). The lattice parameters are vector E MR,, where Re for each vertex E My, there is a corresponding parameter denote by 8v. The lattice model or function is obtained by interpolating the parameters using one of many possible interpolation schemes specified by an interpolation kernel $ Dv My Given + the resulting lattice model f: Dv + defined by
by Dy E IR" the domain of the lattice model given by Dy = [0. V[1] 1] x
denotes the set of vectors of length [Myl with entries indexed by My:
f(x: 0) = - (x) Σ 0 (+
(1)
vEMY
where (xxx)) denotes the entry of (x) with index v. Typically, one requires that for all u, v E My. (P(v)) 1 if v, and 0 otherwise, so that f(v) 0v. In Gupta et al. (2016) the authors present two interpolation schemes termed 'multilincar' and 'simplex' We denote the corresponding kernels by muuiillnnar and Thimplex and the resulting lattice models by fmu(;; 0) and fa(;; 0), respectively. We give the definition of 4muuttilinear here since we make use of it later, but refer the reader to (Gupta al, (216)) for the definition of simplex interpolation.
(puultiliineerxx (x)) = II (v)) VEM, JE[D]
(2)
For both multilinear and simplex interpolated lattice functions, the resulting function is increasing (resp. decreasing) given direction if and only if the function is increasing (resp. decreasing) on the grid's vertices in that direction (Gupta et al. 2016 Lemmas 1, 3). As a result, training a lattice model with these interpolation schemes respect the monotonicity constraint can be done by solving a constrained optimization problem with linear inequality constraints (Gupta et al. (016)..
Evaluating the lattice function at single point can done (22)) time for multilinear interpolation and in O(D log D) time for simplex interpolation (Gupta et al. 2016). Both interpolation schemes require OIL Vid) space for storing the parameters (assuming a constant number of bits per parameter). In the next section present sub-class of the set of multlinear- cnaltiinear-nterpolaation lattice functions, which we term KFL(V). Each function in this class can evaluated in (DD) time and requires only O V(d) space for its parameters. Moreover, like the multilinear and simplex interpolated lattiee function classes, there is a necessary and sufficient condition for a function in KFL(V) to be monotonic in subset of its inputs, and this condition can be efficiently checked. As result, one can train models in KFL(V) that are guaranteed to be monotonic in a prescribed set of features.
3

---

Published as a conference paper at ICLR 2021
3 GRROEECKE-FFCCTREE LATTICE
The Kronecker product of two matrices A = (at.)) E Rmxx and = (bxg) E 12xx is defined as the mpp nq real block matrix given by:
an
al
A B
(3)
am
B
The Kronecker product is associative and generally non-commutaiive; however, A & and & A permutation equivalent. We extend the definition of Kronecker product to vectors by regarding them as matrices with a single row or column. For s vectors V; E R", we use the notation Vg. Let I {0, ................................ R1 1} x ... x {0. .0..... Rg 1}. We index the entries
of
V1 & v by I, so that the entry with index (f1....,.a) E I is IT v,li, + 1].
The Kronecker product satisfies the mrixedproddcct property: for 4 matrices A E R=**" B E RPX9, C E R D RTx* it holds that (A @ (C D) (AC) @ (BD), where for two matrices M, N, we denote their conventional product by M.. Consequently for vectors a,c E IR" and b, E R2 holds that
(a (c d) = (a.c) @ (b d) = (a cbb.
(4)
where the rightmost equality follows since Kronecker product of scalars reduces to simple product. See (Loan 2000) for more details on Kronecker products.
We are now ready to define the class KFL(V). Let V E No and fix lattice of size V. The class KFL(V) is the subclass all multilinear interpolation lattice functions whose parameters are Kronecker products of D factors. Precisely,
KFL(V) = ( wa) : Vd wa E R.
We reparameterize the functions in KFL and use fun Wi.... wa) = fmn _ wa) to denote the function with parameters [wa]a- The following proposition shows that functions in KFL(V) are products of 1 1-dimensional piecewise linear functions. It essentially follows from the fact that $ maittilinear (x) can be expressed Kronecker product of D vectors.
Proposition Let E NP, For all WT ERI WD RDD
fun(x; w....., WD) = II f wwi (x|d; wa), for all Dv.
(5)
Proof of Proposition For E N. let L Upwe (I; 01,,) Jpwi e2
R R" be given by L (z)
[p (x; e), Let Wi...., wD be vectors satisfying the conditions in the proposition. By the definition of KFL(V), It follows from 2 that for all x E Dv we have
have fial;; Wi,..., wp)
fmll(:: & wa). Fix $ & momutiilinear
((x) & V (x(]). Therefore using we get, for all x E D..
[1, w1, WD) = Smn (x; & wa) = (& wa) (0 [x(d(x((d))
II d=1
(wa 4 (x(g))(
Now, for each d E [D] we have
wa L (x(a(() = Σ wali] wwllifoow(x(dd])e..na = fpw
[E[V|d]]
(x wa).
Substituting into 66. we obtain
It follows from Proposition I that evaluating function in KFL(V) requires evaluating D piecewise linear functions with uniformly spaced knots and computing the product. This can be done time O(D) (D). The storage complexity is O parameters) = -O V(]).
4

---

Published as a conference paper at ICLR 2021
3.1 MONOTONICITY CRITERIA FOR KFL
Let i E (). We say that a function ʃ D - IR, where D C IR,, is increasing (resp. decreasing) in direction in D, if for every x D and real ò 0, such that + Ōe; DD holds that [(x) S f(x + 5e,) (resp. [(x) 2 f(x + de,)). Note that a function that does not depend on x x[i] is thus "trivially" increasing in direction In this section we disregard such edge cases and require function increasing in the ith direction to strictly increase on at least one pair of inputs. To simplify the exposition, we only deal with increasing functions in this section-all the results transfer naturally to the decreasing case, as well.
The next proposition shows a sufficient and necessary condition for a function in KFL(V) to be increasing in subset of its features in Dy. In Section 3.5 we explain how to use this result to train models that are guaranteed to be monotonie.
Proposition 2. Fix V E Nº, let f E KFL(V) and let i,, .1,.... ip E [D] be distinct direction indices for S D. Then f is increasing in directions ii....; ip iss f can be written as:
f(x) = II
wa),
(8)
where a E (+1,-1) and Wa E R [D] are vectors satisfying the following conditions:
1. I 2 2 then wa 2 for all d E [D].
2. If = then wa 2 for all d E [D] (.)
3. For all j E (p). owi, [1] S owi, [2] S ... S ows, Midl
See Appendix for the proof.
3.2 CRITERIA FOR OTHER SHAPE CONSTRAINTS
While the focus of this paper is on learning flexible monotonic functions, other shape constraints, namely convexity and nonnegativity, can easily be imposed on KFL. This section presents the propositions showing sufficient and necessary conditions for these constraints. More shape constraints beyond these are left for future work.
We say that function f D + R is convex (resp. concave) in direction i in Df for every D and real 8 2 such that x, x + de, E D. we have f(tx (1 - (xx+,))) < ff(()) + (1 11--6 f) (x+ de;) (resp. f(xx + (1-t)(x+6l )e,)) 2 tx(x) (1= + de,)) for all [0, 1]. As with monotonicity, we require function convex (resp. concave) in direction i to strictly satisfy the inequality for some x, and (i.e. we disregard functions that are affine in direction in D). The following proposition shows sufficient and necessary criteria for a function to be convex in a subset of directions; an analogous criteria can be derived for concavity.
Proposition 3. Fix V E Nº, let f E KFL(V) and let i ip E [D] be distinct direction indices for S D. Then f convex in directions , 12 iff can be written as:
f(x) = II S ( (x[d] wa),
where E (+1,-1}, and wa E RM [D) are vectors satisfying the following 3 conditions:
1. p 2 then wa 2 0 for all d E [D].
2. 1 = then w. 2 0 for all d E [D] ).
3. For all j E [p]. Vig 2 or V[ig > 2 and o oW., Ik Ik+ + +2] -wi,
|k +1)) 2 o (Wi, [k 1 1]
wi, [k)) for all k E [V[i,] 2].
See Appendix for the proof.
Proposition 4. Fix V ND, let f E KFI((V). Then f is nonnegative (resp. strictly positive) iff can be written as f(x) = II fpwl [x wa). where wa 2 0 (resp. wa > for all d E (D].
See Appendix A for the proof.
5

---

Published as a conference paper at ICLR 2021
3.3 ENSEMBLES OF KFL MODELS
It follows from Propositon 2 that the set of monotonic functions in KFL(V) is fairly restricted: for example, function in (FL that is increasing in two or more directions cannot change sign in Dy. To make the model class larger, we use ensembles of sub-models in KFL(V) and take the average or the sum of their predictions as the composite model's prediction. We are thus motivated to define the class of functions that can be expressed as sums of M KFL models.
KFI(V,, M)
Σ 0: = 96 E KFL(()))
(10)
Since the zero function with domain Dy in KFL(V), we have KFL(V,M) S KFL(V, AM + 1). Let L(V) denote the set of all multilinear inteprolation lattice functions grid of size V. Then, by construction, L is closed under addition. So we have KFL(V)- = KFI,(V, 1) S KFL(V. 2) S .... S C(V). Moreover, the following proposition shows that there exists a positive integer M, such that for all m < M,, there are functions that can be expressed as a sum of m + 1 KFL(V) models which cannot be expressed as sum of m KFL(V) models, and every function in L(V) can be expressed as a sum of M functions in KVL(V).
To state the proposition, require the following definitions tensors, which multidimensional generalizations of matrices. There are multiple ways to define a real tensor. Here we view a real tensor of size V D-dimensional [(1] x .... V[D] array of real numbers. The set of such tensors is denoted by R [ @ ... @ R V We index the entries of tensors of size V by Myy Addition between two tensors of the same size and multiplication of a tensor by a real scalar are defined entrywise. Observe that each element in My can naturally be regarded
tensor of size V and vice versa. The outer product of D vectors W; R E [D] is their Kronecker product, 8 W., regarded as a tensor of size V, and we use the same notation for the outer product as for the Kronecker product. A real tensor is called simple if it is the outer product of some D real vectors. Every tensor T can be expressed as a sum of simple tensors and the rank of T, denoted r r(T"), is the minimum number of simple tensors that sum to T. The rank of a tensor of size V is at most |Myl/ max; maxi(V[i]]. See (Rabanser et al. (217)) for an introduction to tensors.
Proposition For two sets A, B we use A B to denote that A is subset of B but A + B. Let M = max(r(T) : T E P @ & P.. Then KFL(V,1) & KFL(V,2) & .... & KFL(V, M) = C(V).
See Appendix A for the proof.
3.4 DEPENDENCE OF THE CAPACITY OF THE MODEL CLASS ON LATTICE SIZE
In the previous section, we showed that the capacity of (V, M)) increases as M increases up to certain threshold. One may also ask how the capacity of KFL(V, M) depends on V. Unfortunately. the domain Dy of member in KFL(V, .M) is different for different vectors V. which introduces a technical difficulty when trying to compare the capacity across different lattice sizes. In practice, we follow the technique of Gupta et al. 2016) and use a "calibration" transformation c RDD + Dy to map the "raw" input into the lattice domain Dy. Here, c(x) = (cy (x(1)), ... ( (D)),
and each ca : R + [0, Vid - 1] is a Iearned piecewise linear function with a fixed prespecified number of linear segments. See Gupta et al. 2016)) for more details. Let C(V) denote the set of all calibration transformations whose image is in Dy. For a positive integer M, we define the calibrated Kronecker Factored Lattice model class CKFL by: CKFL(V, M) (f(c()) f KFL(V, M), c C(V)).
The following proposition shows that the capacity of CKFL(V, M) increases as V increases. Proposition 6. Let V1, 1/2 ND be two lattice sizes and M be a positive integer. V1 V2, then CKFL(V M) S CKFL(V2, M).
See Appendix A for the proof.
3.5 MODEL TRAINING DETAILS
To ensure that the input to a lattice model lies in its domain, we follow the input calibration techniques explained in Gupta al. (2016). For numeric inputs, learned one-dimensional piecewise

---

Published as a conference paper at ICLR 2021
fKA
X 71
C
:
AVG
+ 3
f(x)
fkfl
X YM
Figure 3: KFL Model Architecture
linear function to transform the feature's s input domain to [0, V(d] - -]. For categorical inputs, we
learn one dimensional embedding for each category value to map real value in [0, V[d] 1].
Calibrators can be efficiently trained to be monotonic.
Our model architecture for KFL is depicted in Figure 3 and defined by the following equation
f(x) = 3 +
M Σ ME[M]
7m Jun (c(x); w (m)
W (m))
where is the input calibration layer, described above (note that has its own learned parameters don't show here to simplify the notation) and 7m, 3 E R are additional scaling and bias parameters, respectively. To guarantee that the final model is monotonic in a given feature, it is sufficient to impose monotonicity on its calibrator and each of the terms in the sum.
We train model by minimizing the empirical risk subject to the monotonicity constraints using projected mini-batch gradient descent. Following Proposition - after every gradient descent step, we project each (m) to be nonnegative where required. Then for each monotonic feature d we project d
((")) so that its components increase a = 1 decrease if o = 1. Computing this projection an instance of the Isotonic Regression problem and can be solved efficiently using the "pool-adjacent- violators" algorithm (Barlow et al. 1972). In our experiments, we instead use a more efficient approximation algorithm that computes vector that satisfies the constraints, but may not be the closest (in Lg-norm) to the original vector. See Appendix B for the exact algorithm we use.
4 EXPERIMENTS
We present experimental results on three datasets, summarized in Table 2 same public Adult Income dataset (Dheeru & Karra Taniskidou 2017) with the same monotonicity constraint setup described in Canini et al. (2016). The other two datasets are provided by a large internet services company with monotonic features specified by product groups, domain knowledge or policy requirements.
The first dataset is the
Table 2: Experiment Dataset Summary
Dataset
Type
Features
# Monotonic
Train
# Test
Adult Income
Classification
14
4
32,561
16,282
Query Result Matching
Regression
14
11
805,660
201,415
User Query Intent
Classification
24
16
522,302
130,576
We compare KFL against two previously proposed baseline lattice models: (1) calibrated multilinear interpolation lattice, and (2) calibrated simplex interpolation lattice. which use the input calibration layer described in Section 3.5 and Gupta et al. (2016). We note that we do not compare KFL to deep lattice networks (DLN) YYou et al. (017) in this paper. In DLN, KFL. would act as a replacement layer for the lattice layers, which only comprise a subset of the model layers. We believe that such a comparison would be dominated by the other layers and not properly show how KFL differs from previously proposed lattice models. All our models were implemented using TensorFlow (Abadi et al. 2015) and TensorFlow Lattice (Google AI Blog 2017). Open- code for KFL has been pushed to the TensorFlow Lattice 2.0 library and can be downloaded at httpuuuccoo/ttssrfllowowooo We used logistic loss for classification and mean squared error (mse) loss for regression. For each
7

---

Published as a conference paper at ICLR 2021
experiment, train for 100 epochs with batch size of 256 using the Adam optimizer and validate the learning rate from {0.001, 0.01, 0.1, 1.0) with five-fold cross-validation. We use a lattice size with the same entry V for each direction and tune V from {2, 4,8) and different settings of M above for our baselines was not feasible on averaged over 10 independent runs. The train and evaluation times were measured on workstation with 6 Intel Xeon W-2135 CPUs. We report the models with best cross-validation results, as well as some other settings for comparison.
from [1, 100) for KFT, (we note that increasing datasets). The results
4.1 UCI ADULT INCOME
For the Adult Income dataset Dheeru & Karra Taniskidou (2017), the goal is to predict whether or not income is greater than equal to $50,000. We followed the same setup described in Canini et al. (2016), specifying capital gain, weekly hours of work, education level, and the gender wage gap as monotonically increasing features. The results are summarized in Table 3 and Figure
Table UCI Adult Income Results
M
V
Train Ace.
Test Acc.
Train Time (8)
Eval Time (js)
# Parameters
Multilinear Simplex
2
85.60 + 0.02
85.51 = 0.05
333
3700
16, 552
2
86.71 + 0.21
85.72 = 0.15
151
2200
16, 552
KFL
86.31 0.06
86.05 0.07
1800
226
KFT.
8
86.51 0.02
86.24 0.05
85
2100
395
4.2
QUERY RESULT MATCHING
This experiment is regression problem of predicting the matching quality score of result to query. The results are summarized in Table and Figure
Table 4: Query Result Matching Results
M
V
Train MSE
Test MSE
Train Time (s)
Eval Time (Ju))
Parameters
Multilinear Simplex
2
0.5694 + 0.0010
0.5702 + 0.0009
4606
2835
16, 512
2
0.5718 + 0.0066
0.5732 + 0.0066
2150
1932
16, 512
KFL
25
8
0.5728 + 0.0054
0.5735 + 0.0055
870
1847
2954
KFL
50
4
0.5700 + 0.0037
0.5707 + 0.0038
868
1839
2979
4.3
USER QUERY INTENT
For this real-world problem, the goal is classify the user intent into one of classes. For the baseline multilinear and simplex models, single lattice with all 24 features is infeasible. When the number features too large for single lattice, we follow the technique described in Canini et al.) (2016), which uses ensemble of lattice sub models-can input features. The result of the model the average of the sub-models' outputs. The calibrators are shared among all lattices. Here random subset of 10 the 24 features. We tune and set L 100. The results are summarized in Table and Figure
taking small subset of the calibrated
random tiny lattice ensemble of L lattices with each seeing
Table 5: User Query Intent Results
M
V
Train Acc.
Test Aec.
Train Time (s)
Eval Time (u8)
# Parameters
Multilinear
2
69.48 0.02
69.20 + 0.01
13, 559
15, 932
102, 619
Simplex
2
69.48
0.03
69.34 + 0.02
4478
6559
102, 619
KFL
100
69.53
0.04
69.35
0.04
1842
2534
9920
KFL
100
69.74
0.08
69.53 + 0.07
3507
2560
19, 520
8

---

Published as a conference paper at ICLR 2021
5 DISCUSSION
For each one of our experiments, we can see very similar results: (1) the accuracy or mse of KFL is comparable or slightly better than the baselines, (2) the training time is significantly reduced, (3) the number of parameters is significantly reduced, (4) KFL can use larger lattice sizes V because the number of parameters scales linearly and not power of D, (5) increasing M increases the capacity of the KFL model class where the value for M that makes KFL expressive enough to perform well is relatively small (and going above such M longer provides any more value), and (6) the evaluation speed of KFL compared to multilinear and simplex interpolation aligns with our theoretical runtime analysis. where KFL is significantly faster than multilinear interpolation (particularly when the number of features is large, e.g. Experiment 4.3) and comparable to simplex interpolation.
04.
Tea 3303
K722
dfl (V--
Emesiine
0.:34
$180
0000
8425
0.40
Seveiee
K7L (--2)
(6-2)
Figure 4: UCI Adult Income
Figure 5: Query Result Matching
Figure 6: User Query Intent
Figure 7: Comparison test results KFL with different M and V values
Furthermore, each experiment highlights different qualities of KFL. Experiment 4.1 shows that increasing V can sometimes be more important than increasing M, where such an increase can potentially lead to further boosts in performance with only linear impact to the model's time and space efficiency. This result follows from Proposition 6 In Figure 4 we see that KFL acts like a form of regularization: KFL's accuracy drops as M gets too high, indicating that we start over fit and lose this regularization effect as the size of the model class increases. Experiment 4.2 shows that KFL can also perform well for regression tasks but will likely need larger M and V for more complex problems. It also shows a trade-off between the values of M and V where computation time, number of parameters, and remain pretty much fixed. Experiment [4. demonstrates KFL's ability to create higher-order feature interactions by keeping all features in a single lattice. Unlike multilinear and simplex interpolated lattice functions, KFL can handle many more features in single lattice. It demonstrates that KFL can achieve even faster evaluations compared to the ensembling method described by Canini et al. (2016). Experiments 4.2 and 4.3 also show that there logarithmic-lin improvement of performance with respect to M, indicating that the M needed to achieve comparable accuracy is potentially impractically large (likely for more complex problems); however, as Proposition 6 shows, there is nice trade-off between M and V where we can instead increase V to compensate and ultimately achieve comparable or better performance with reasonable M.
6 CONCLUSION
We proposed KFL, which reparameterizes monotonic lattice regression using Kronecker factorization achieve significant improvement parameter and computational efficiency. We proved sufficient and necessary conditions to efficiently impose multiple constraints during training on a model in KFL w.r.t subset of its features. We showed that through ensembling the KFL. function class strictly increases as more base KFL. models are added, becoming the class of all multilinear interpolated lattice functions when the number of base models is sufficiently large. Our experimental results demonstrated its practical advantage over the multilinear and simplex interpolated lattice models in terms of speed and storage space while maintaining accuracy. For future work, it would be interesting to (1) explore applications of KFL in more complex architectures such deep lattice networks You eet al. (017) and (2) to understand if we can impose other useful shape constraints (Cotter et al. 2019 Gupta al. 2018

---

Published as a conference paper at ICLR 2021
REFERENCES
M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, Goodfellow, Harp. G. Irving, M. Isard, Y. Jia, R. Jozefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. Murray, C. Olah, M. Schuster, Shlens, B. Steiner, Sutskever, K. Talwar, P. Tucker, V. Vanhoucke, V. Vasudevan, F. Viégas, O. Vinyals, P. Warden, M. Wattenberg, M. Wicke, Y. Yu, and X. Zheng. TensorFlow: Large-scale machine learning on heterogeneous systems, 2015. URL wttp:////wwweeeoflllooooooooo Software available from tensorflow.org.
Y. S. Abu-Mostafa. A method for learning from hints. In Advances in Neural Information Processing Systems, 1993.
R. Barlow, D. Bartholomew, and J. M. Bremner. Statistical inference under order restrictions; the theory and application of isotonic regression. Wiley, 1972.
K. Canini, A. Cotter, M. M. Fard, M. R. Gupta, and J. Pfeifer. Fast and flexible monotonic functions with ensembles of lattices. In Advances in Neural Information Processing Systems, 2016.
A. Cotter, M. R. Gupta, H. Jiang, E. Louidor, J. Muller, T. Narayan, S. Wang, and T. Zhu. Shape constraints for set functions. In Proceedings of the 36th International Conference on Machine Learning, 2019.
H. Daniels and M. Velikova. Monotone and partially monotone neural networks. IEEE Transactions on Neural Networks, 2166))96-9917, 2010.
D. Dheeru and E. Karra Taniskidou.
UCI Machine Learning Repository, 2017. URL http:
larrchive.ics.co ics.iveeeic.... lddm/
C. Dugas, Y. Bengio, F. Bélisle, C. Nadeau, and R. Garcia. Incorporating functional knowledge in neural networks. Journal of Machine Learning Research, 10:1239-1266 1262, June 2009. ISSN 1532-4435.
E. K. Garcia, R. Arora, and M. R. Gupta. Optimized regression for efficient function evaluation. IEEE Transactions Image Processing, (109)4412-44144 2012.
George, C. Laurent, X. Bouthillier, Ballas, and Vincent. Fast approximate natural gradient descent in a kronecker factored eigenbasi.. In Advances in Neural Information Processing Systems, 2018.
Google AI Blog. Tensorflow lattice; Flexibility empowered by prior knowledge, 2017. URL https: 7/ai 1/ai.goom http:///ww....ooooooooooooo/oaaa
html
M. R. Gupta, A. Cotter, J. Pfeifer, K. Voevodski, K. Canini, A. Mangylov, W. Moczydlowski, and A. Van Eshroeck. Monotonic calibrated interpolated look-up tables. Jourmal of Machine Learning Research, 17(109):1-47, 2016. utthttp:/// htth::/tp::mmrt// wttp//pppes////////// 1tt.:/1552333..1. htmll
M. R. Gupta, D. Bahri, A. Cotter, and K. Canini. Diminishing returns shape constraints for inter- pretability and regularization. In Advances in Neural Information Processing Systems, 2018.
C. Jose, M. Cisse, and F. Fleuret. Kronecker recurrent units. In Proceedings of the 35th International Conference on Machine Learning, 2018.
C.F. Van Loan. The ubiquitous Kronecker product. Journal of Computational and Applied Mathe- matics, 123(1)885-100 2000. ISSN 0377-0427, URL htt.::::wwww.scceneed...c. com/ Sci
J. Martens and R. Grosse. Optimizing neural networks with kronecker-factored approximate curvature. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
K. Osawa, Y. Tsuji, Y. Ueno, A. Naruse, R. Yokota, and S. Matsuoka. Large-scale distributed second-order optimization using kronecker factored approximate curvature for deep convolutional neural networks. In IEEE Conference Computer Vision and Pattern Recognition, June 2019.
10

---

Published as a conference paper at ICLR 2021
Y. Qu and B. Hu. Generalized constraint neural network regression model subject to linear priors. IEEE Transactions on Neural Networks, 22(12):2447-2444 2011.
S. Rabanser, O.
Shchur, and S. Günnemann. Introduction to tensor decompositions and their applications in machine learning. ArXiv, abs/1711.1078., 2017.
Sill. Monotonic networks. In Advances Neural Information Processing Systems, 1997.
You, K. Canini, D. Ding, J. Pfeifer, and M. R. Gupta. Deep lattice networks and partial monotonic functions. In Advances in Neural Information Processing Systems, 2017.
X. Zhang, F. X. Yu, R. Guo, S. Kumar, S. Wang, and S.F. Chang. Fast orthogonal projection based on kronecker product. In International Conference on Computer Vision, 2015.

---

Published as a conference paper at ICLR 2021
SUPPLEMENTAL MATERIAL
A PROOFS
Proposition 1. Let V E ND. For all W1 E ERV WD E R
fka(x; Wi,..... WD) = II l pw pww/ (x|d]: for all Dv.
(5)
Proof of Proposition For E N. let [ ppwi (1; 01.=) Jpwl [T; 02,0) conditions in the proposition. By the definition of KFL(V), we have fkal; Wi,..., wD) fmll @ @L_
R R" be given by (x
[2; 0,, Let Wi...., wD be vectors satisfying the
Fix + Iupultilinear It follows from 2 that for all x E Dv we have
(xx) @ 8 2 (x|]). Therefore using we get, for all x E D..
fxn Wi...., WD) fmul (x: @a-wa)) (&2 wa) f vvld((x(d))
D = II (wa v (x(g((((d)))
(6)
Now, for each d E [D] we have
wa V Vid (x(d))
Σ wali) ex,(1) Spwi (en(xx(g) (x[d); Σ [alliee,yaa)
|E(v/d]]
fpwi (x[d] wa)
Substituting 7 into 66. we obtain 5).
. up E [D] be distinct direction indices for S D. Then f is increasing in directions i....., ip iff f can be written as:
Proposition 2. Fix V ED, let f KFL(V) and let i .1....y
f(x) = II p (x wa),
(8)
where E [+1,-1) -1], and wa E R4, d E [D] are vectors satisfying the following 3 conditions:
1. P then wa for all d E [D].
2. p then wa 2 for all d E [D] }
3. For all j E [p). ow,, [1] ow,,
ow,,12] [2] S ... S ow,, Dill
To prove the proposition we shall make use of the following lemma. Lemma 1. Let f(x) IIa (x[[; wa) be function in KFL(V). for some i E [D], f is
increasing in direction Dy then for all [D] (i), either wa 2 0 or wa S 0.
Proof of Lemma 7 Let ff be above, and assume to the contrary that for some j [D] {i), neither
Wy 2 nor w < 0 holds. Then there must exist s, E [V[i]] such that [ < 0 and w [t] >
For [D), let (xx) fa wa). Then (s 1) Wy wy(s [8] < 0 and l,(t 1) wj > By
assumption there exists Dy and 8 > 0, such that f + 5c,) f(x)
Now, for any
r E [0, Vial -
f(x+ (r-
f(x+ (rx+(rx((j))e) fx(x(i) + o),, (r) II ex(x(d) (x(r) II (a(x(d) dE(DiM(t
dE(DIVE)
(r))
4(xli] + 6) II tx Ca(x(d)
(x(r)
de de(D)\{))
dE(P)
(r(r)
= (f (o;)) f(x))
(x(x))))
'Otherwise f(x + (e.)) f(x) for all x,5 implying that f(x) does not depend xhii-which we don't. regard increasing direction

---

Published as a conference paper at ICLR 2021
Since for some re 1, for that r, (rxxi])e < f(x+(r (x))())),,,, which contradicts our assumption that is increasing in direction i.
holds that (x)() it follows from the last equation that
Proof of Proposition 2 We first show the "if" direction. Assume that f can be written as above and let j E [p]. Then the product of two terms: [xpnl way) and Iays fpw (x (x|d; wa). Condition implies the first term is increasing direction ij. The second term doesn't depend on x[8}] and conditions and 2 imply that it is nonnegative over Dy. It follows that f, the product of the two terms, is increasing in direction iz.
We next show the "only if" direction. To simplify the notation, we only prove this for the case p 2 2. A similar argument shows the proposition holds for p = I, as well. Let f E KFL(V) be increasing in directions i1..... Sp in Dy- By Proposition there exists D vectors, w' RVdd d E [D), such that f(x) IIa pwo (ow](((([) [d]; w')) Let wa be w'a if w' < 0 or w's otherwise. By Lemma applied to directions i and 12, follows that for every d [D]. We 2 O. Since for any scalar E IR, (x|d]] (ww')) = afpwi (z][d]] w²)). it follows that f(x) = IIa fowl wa).
where a = (-1)) (dw(s0)), Therefore condition holds.
As for condition 3, let j E [p] and assume to the contrary that ow; [s] > ow,, [s Is+ 1] for some
E [V] Since f not identically zero in Dy (as we don't 't consider the zero function increasing in direction i,), for each d E [D], there must be E [0. V/d] - 1] such that ( wa) * 0. Since wa 2 0. it follows that (xw; wa) > 0. Let x E R be the vector with x[d] = Ia if * ij and x[t,] = 8, otherwise. Then we have f(x) = a spwi(s; Way) Ilattt Spwi (I.d Wa) = ow;,1e [s] Il Haye, Smwt (I.; wa) > ow + 1] Ieys, (1w wa) = f(x + ei,) contradicting our assumption that is increasing in direction iz. Therefore condition 3 holds as well.
Proposition 3. Fix V E NP, let f E KFL(V) and let i,, ....... ip E [D] be distinct direction indices for S D. Then I convex in directions i1,...,7p iff J can be written as:
f(x) = a II [x][(]] wa).
where E {+1, -1,, and wa E 1I [D] are vectors satisfying the following 3 conditions:
1f 2 then Wa 2 0 for all E (D).
2. pf then w. 2 0 for all E [D] }
3. For all j E [p). Vii,l
V(i,) > 2 and a ow,, +2] Wi, [k + 1]) 2 a (W., [k+11
Wi, for all k E [V[i,] - 2).
To prove the proposition shall make use of the following lemma. Lemma's 2. Let f(x) =
IIa fpw (x[d] wa) be a function in KFL(V). Iffor some E [D], f is convex
direction in Dy then for all [D] X (i), either wa 2 wa S
Proof of Lemma
Let f be as above, and assume to the contrary that for some j E [D] {i} neither
W, 2 nor w, O. Then there must exist 8, E [V]s]] such that w wy[s] < 0 and wy > For
d E [D], let (x(]) [x[]( wa). Then (s 1) wy[s] 0 and E,(g
1) w,[g] > 0.
By our assumption there exists x E Dy and > 0 such that tf(x) + (1 - t)f(x + de,)
f(ix + (x + )e;)) > 0 To further simplify notation, we Na (a(x(d)) zati.j and
'Oteewiise (x) + (1- 1- fx) + de,) ftx + (1 (x + 5e:)) 0 for all 6, implying that f(x) affine direction which don't regard as convex in direction
2

---

Published as a conference paper at ICLR 2021
Iazz (x(() 2dzt Now, for any E [0, Vij]l, we have:
tf(x + (r- (1- ( x(5])o; dc;)
- (1- (r-x(j)e; + 0e:))
((((x(]] + (a-x(i]]+11000) -x)]))((+++++(
(r)
(x(1x(1] + ()( + (xxx((])))=z++) =))zz (1)(())))=a) zayi + (1 (x(()) + +5)
ex(((]))
(r(
-(f(x) + (1=x) + de:) f(tx + (1 () + dee))
Eg (x(i))
Since for some r E {s- 1 1 it holds that (x(r)/e,x())) < 0, follows from the last equation
that for that r, [(((x + (r 1-r-(jj x e,, + (r x + 5e,)) > tx (r - x(j])e;) +
(1 - fx (r x(j])e; de;). which contradicts our assumption that f is convex in direction i
(for the point x + (r- x()))e)),)
Proof of Proposition 3 We first show the "if" direction. Assume that I can be written as above and let j E [p). Then f is the product of two terms: a (xw(((((t) Wiy) and IIess fp (x(d); wa). Condition implies the first term is convex in direction áz. The second term does not depend on x[i]] and conditions and 2 imply that it is non-negative over Dy. It follows that f. the product of the two terms, is convex in direction iz.
We next show the "only if" direction. To simplify the notation, we only prove this for the case p 2 2. A similar argument shows the proposition holds for p = 1, as well. Let f E KFL(V) be
convex in directions i1, .... ip in Dy. By Proposition there exists D vectors, W'a E RV/ d [D] such that f(x) = Ia Spwi
( (x[d]: w'). Let wa be Wa a if w'a < 0 or w'r. otherwise. By Lemma 2
applied to directions in and i2, follows that for every d [D], Wa 2 O. Since for any sealar
E I. [pw](z]d]; aww') afpwi(x(d]; w'2), it follows that f(x)
IIa [x|[]] wa). where
= (-1)l(dw()0)) |5)], Therefore condition holds.
As for condition 3, let j E [p] and assume to the contrary that Vliy] > 2 but ow., [k + 2] wi, [k + 1]) < aww,, [K + 1] w,, w.]l for some k [it, - 2]] Since is not identically
zero in Dy (as we don't consider the zero function convex in direction ij). for each d E [D].
there must be xa E V[d] - 1] such that (pwi(cat wa) * O. Since Wa 2
follows that
fpwl (Iz; wa) > 0. Now let
0.5 and consider ordered inputs X1, X2 E R. such that
xi xild = x2 = xx for all d' E [D]. xi = k - 1, and xaliz] = k + 1. We first de- compose s(x) = pxm wi,) Ilayi Snmi(x(d) wa). Next, by construction, we note that Laze, f [d]; wa) = Iaays fpw] (xa [d]; wa) = Ila4ss, (xal(x = 0, and since f
is convex in direction ij. we have:
(t [i,]] + (1 - ()(22(1))); wi, - fmt W., 02 - po σ (0.1 - 1) + 0.5(k + 1); w.,) < 0.5 (o (k- 1; l;,,)) + of + 1; 1;w;,)) 2ow; [k + 1| - ow,, [k|] + tw:; [k: 2]
ow,, [k + +1 - [k]) < ow,, [k + 2] - wi, [k + 1])
which contradicts our assumption.
Proposition 4. Fix V E ND, let f E KFL(V). Then f is nonnegative (resp. strictly positive) iff f can be written as f(x) = IIa [ wa). where Wa 2 0 (resp. Wa > for all d E [D].
(nonnegative case). We first show the "if" direction. Assume that f can be written as above. Then for each d E [D]. since wa 2 0, it follows that fpw] (x[c]; wa) 2 0. Therefore, f. the product of D nonnegative piecewise linear functions, is nonnegative.
Proof of Proposition 4
We next show the "only if" direction. By Proposition there exists D vectors, w E R E [D]. such that f(x) = II f (x[d]: w If for some i E [D]. neither w 2 0 nor
w 0 then there must exist 8, / E [0, V(i 1] such that fpwi(s; w() < and fpwt w/) > 0.
3

---

Published as a conference paper at ICLR 2021
It follows that there exists x E Dy such that either f (s; w() II des J f w/) 0 or fpwa w¹) Lays f w'd) < O, thus making f not nonnegative o
I Hence, for all d E [D]. either w 2 0 or W/ I Now, let wa be -w'a if w f 0 or w'a. otherwise. Since for any scalar IIa Jpwi wa), where
E R. (pw (x awa) = a afpwi (x [d]; wa). it follows that [(x)
o = -l)lldwssHH, Since 1L. fpw (x d]; wa) 2 0, for f to be nonnegative, Idd: w S 0 must
be even. This implies a 1. Then nonnegative function is written as f(x) - IIa pwl (x[d); wa).
where Wa 2 0 for all d E [D].
Proof of Proposition + (strictly positive case). We first show the "if" direction. Assume that f can be written as above. Then for each d E [D], since wa > O, it follows that [xwn(x[d]; wa) > 0. Therefore. f. the product of D strictly positive piecewise linear functions, is strictly positive.
We next show the "only if" direction. By Proposition I there exists D vectors, w'a E R'/,
[d]; w') ). If for some i E [D], neither w > 0 nor w/ < 0 0. Thus, it follows that f is not strictly positive, Hence, for all d E [D], either w' > 0 or w' < 0. Now, let wa be -w'a if w'a < 0 or
E [D], such that f(x) = II J (x|([]
then there must exist x(i] such that [pmi(x[ii; w()
w's, otherwise. Since for any scalar a R, (x[]] o.aa) - p [x|]; wa). it follows that f(x) = o II (x[[] wa). where o = (-1)lfdw
Since II, fowl ( (x[d]: wa) > 0, for f to be
strictly positive, {d: w < O}] must be even. This implies = 1. Then strictly positive function f is written as fxx) = II fpwa (x[d]; wa), where wa > 0 for all d E [D].
Proposition 5. For two sets A, B we use A C B to denote that A is subset of B but A # B. Let M = (a)( : T E P @ @... @ }. Then KFL(V,1) & KFL(V,2) _... S KFL(V,, M) = C(V).
Proof. We first show KFL(V, = C(V). Since L(V) is closed under addition, KFL(V, M) S
C(V). so it suffices to show that C(V) S. KKL(VV,), For A E R-My, denote by f=ul (-: 9) the multilinear interpolation lattice function with parameters O. Let f L(V). Regard @ as
tensor of size V and set r = r()). Thus, there exist DD vectors w (4)
E RLl, i [r].j E [D), such
that Eierr 8P w (1) = 0. Thus, from 1. it follows that fmul ; 0) = fmu(:: E 8 w (())== Eierr] fmul:; 3 w) ) Now, by the definition of KFL(V), for each i E [r]. fmul(: 8
KFI,(V), and by the definition of M in the proposition it holds that S M. Since the zero function is in KFL,V), it follows that f= 0) = EiEr) fmu (1 2. (0) E KF)
It remains to show that for each m E [M 11, KFL(V, m) Ç KFL(V, m+11) Since the zero function in KFL(V), KFL(V, m) C KFL(V, m + 1). Assume to the contrary that KFL(V, m + +1)
KFL(V,m), and let 1 E IRM, be tensor of size V and rank M. Then
0 = Σ
(11)
SE[M
(8) E RPL,, with j E [D] and i E [M]. From the definition of for some MD vectors w m1), it follows that Eiejmtaj Smu(; & ( E KFL(V, m + 1), thus by our as- sumption it is also in KFL(V,m), Therefore there exist mD vectors u ( E RVb,, with [m] and i E [D), such that Exeim+1/ funl(: w(()) Exelmi fmul(: o ) or equivalently that fmu( Esejm+t 8 (6) = fmul:: Eie(m) 8/Pi1 ) Since the mapping - fmu(:: ()) is one-to-one (as for all v E &Mv. f(v) = 0r. where 0y is the entry of 0 with index v), it follows from the last equality that Eiem+ f- w (6)
Exemm) @p
P u (t) Therefore we may replace the sum
of the first m + elements in (11 with the sum of the m simple tensors Exe(m) 8 3 u obtaining a sum of M - simple tensors that yields o, contradicting the assumption that r(0) = M.
Proposition 6. Let V1, 122 No be two lattice sizes and M be a positive integer: If V1 $ V2, then CKFL(),, S CKFL(V2, M).
2If for some [D] \ [1] w/ 0 then f is still nonnegative, but for this edge case, f can be trivially written f(x) I.. fowil (x /dl: wa) where Wa 0.
4

---

Published as a conference paper at ICLR 2021
Proof. Assume V1 V2 and let g E CKFL(M, We need to show that g E CKFL( M), as well. By our assumption = f(c(-)) for some f E KFL(V1, M) and c E C(V)). Thus,
(mm) for For each such m and d, define whtm) E Rvild by w = wa
[M] E [D], such that f E fua(: w (m)
...., w(") (mm)
there exist vectors Wa
(mm) [i] for j E [i[d]] and war [s] O, for j [V][d]] \ [i[d]] Let f KFL,(V2, M) be the function given by f* En f ((m) ..... w D Since V I V2, have Dy, S Dv., and thus E C(V2), as well. Therefore, by the definition of CKFL, we have (c(()) E CKFL(V2, M). Now, for each E [M], it follows from ( and the construction of the vectors whtm) that for all y Dy, mm)
(m) we have (y; w(() ...., w D = fualy; wi ..... w wh)) (mr)). Consequently, for all E Da
fly) = -f Since for all x E RRD, c(x) E Dv,, we get that f(c(-)) [*(c(-)). Therefore g E CKFL(V2, M).
B APPROXIMATION ALGORITHM FOR MONOTONICITY PROJECTION
We Algorithm map vector E RD close (in L2 norm) vector w' that satisfies w[1] .... S w[D]. The vector w' may not be the closest such vector to w, but in our experiments the algorithm worked well enough as the projection step in the pro- jected SGD optimization algorithm and is faster than the pooccetfianntsvoooattrss algorithm. We use an analogous algorithm map to close vector with monotonic decreasing compo- nents. In the description of the algorithm we denote by |v| the L2 norm of real vector
input :A vector w E RD output:A vector w' E R.D s.t. w'[1] .... S w(D) and |w' ww| is "small",
v w;
/// Make v satisfy the constraints by increasing components.
for t 2 D do vli] + max(v]i), v(i 1|]:
end
ww f- V-w.
2
// Make w' satisfy the constraints by decreasing components.
for +- D-1 to do
w = min (w'l] [. w'l [|};
end
A Agorithm I: Approximation Algorithm for solving Simply Ordered Uniformally Weighted Isotonic Regression
5


Reviews:
[{"review_id": "ztKN3kNDc2U", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors study statistical models based on the Kronecker-factored lattice (KFL) and investigated the condition that the monotonicity holds. The KFL provides efficient and flexible modeling for monotonic shape constraints. Furthermore, the ensemble of KFL is proposed, and its approximation ability is theoretically investigated. Some numerical experiments indicate that the KFL trains faster with fewer parameters with comparable prediction accuracy to existing methods. \n\nThis paper was assigned as an emergency review. So I did not have sufficient time to understand the content of this paper deeply. \nThe paper provides a computationally efficient method for the modeling of monotonic functions. However, the authors should investigate more variety of shape constraints such as convexity, positivity, etc.\n\nProposition 2 is an interesting result. However, more detailed studies on the shape would be necessary for the publication. For example, is it possible to derive the condition that the function is increasing in a variable and convex in the other variable?\n\nProposition 3 seems relatively straightforward. Supplementing untrivial statements would be good for readers to understand the significance of the proposition. \n\nIn the numerical experiments, the authors found that the hyperparameter V is important to tune the capacity of the proposed statistical model. Is there some theoretical support for that finding? Showing a clear insight would be excellent.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "p27g10Gz16", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "(Added on 11/29/2020) **Post Rebuttal Comment**\n\nI thank the authors for sincerely replying my review comments. I think the authors answered my questions. \n\nAddtional Comments\n\n- Section 3.4: $(c_1(x[1]),...,c_D(x[D])$ →$(c_1(x[1]),...,c_D(x[D]))$ (Add a right parenthesis)\n\n---------------------------------------------------------\n\n**Review Summary**\n\nTheoretical claims about the condition about single KFL's monotonicity and the expressive power of the ensemble of KFL's are correct. Also, the ensemble of KFL demonstrates empirical performance comparable with existing methods with fewer computational complexities up to 24-dimensional feature vectors. In the experiments, this paper learns the monotonic function using the ensemble of KFL, whose weak learners are monotonic. However, I wonder whether it is theoretically justified (see \"Soundness of the claims\" section).\n\n**Summary of the Paper**\n\nThis paper proposed Kronecker-Factored Lattice (KFL) for learning monotonic functions, which is computationally efficient than the existing method in terms of input dimension. This paper derived a necessary and sufficient condition that KFL is monotonic, which is easy to check. This paper also proposed an ensemble of KFL and showed that its expressive power is sufficiently strong that any lattice-point-interpolating function when the number of base learners is sufficiently large. This paper applied the ensemble of KFL for learning monotonic function using three datasets and confirmed that the proposed methods performed comparably with the existing methods with few computational resources and time.\n\n**Claim**\n\nIf I understand correctly, the main claims of this paper are as follows. I assume them and evaluate the paper based on whether it supports them.\n- Claim 1: The computational and storage cost of the proposed method is efficient. (Contribution 1, 4)\n- Claim 2: We can use KFL to learn monotonic function (Contribution 2)\n- Claim 3: The ensemble of KFL is sufficiently expressive (Contribution 3)\n- Claim 4: The proposed method empirically performs well (Contribution 4)\n\n**Soundness of the claims**\n\nCan theory support the claim?\n- Claim 1 is supported by the discussion in the last paragraph of Section 2. The proposed method is $O(D)$ evaluation time and $O(\\sum_d \\mathcal{V}[d])$  parameters, which is typically linear in $D$.\n- Regarding Claim 2, the author proposed a training method (Section 3.3, Paragraph 3) of KFL that is justified by Proposition 2.\n- Claim 3 is supported by Proposition 3. This paper showed that the expressive power of the ensemble of $T$ KFL is strictly increasing in terms of $T$ up to some $T_0$. This paper also showed that the $T$ ensemble of KFL can represent any lattice-point-interpolating functino for any $T\\geq T_0$.\n- In the experiments, this paper learned monotonic functions using the ensemble of KFL by imposing monotonicity to base learners (i.e., KFL). However, if I understand correctly, the expressive power of the ensemble of monotonic KFL was not studied. It is true that any function in $\\mathcal{L}(\\mathcal{V})$ can represent the sum of KFLs, which are not necessarily monotonic. However, it is not known we can express the monotonic function using monotonic KFL's only.\n\nCan empirical evaluation support the claim?\n- Claim 1 is supported by the fact that the training time in Tables 3, 4, and 5 is reduced. Regarding storage cost, the number of parameters is reduced.\n- Claim 2, 3 do not have corresponding empirical support due to their theoretical nature.\n- Claim 4 is supported by the test accuracy in Tables 3, 4, and 5. At least we can observe clear improvement from multilinear and simplex methods by Gupta et al. (2016) when appropriately configuring  and $M$. However, from Figure 4--6, the ensemble of KFL does not perform well when $V$ and $M$ is small.\n\n**Significance and novelty**\n\nRelation to previous work (What is different from previous work)?\n- Gupta et al. (2016) also proposed a method for learning monotonic function using a function that interpolates lattice points linearly. They discussed the difference between the proposed method and Gupta et al. (2016). Specifically, Gupta et al. (2016) takes $O(2^D)$ time to evaluate a $D$-variate function and has $O(\\prod_d \\mathcal{V}[d])$ parameters, which is typically exponential in $D$. On the other hand, those of the proposed method are typically linear (Claim 1).\n\nNovelty\n- The idea of the proposed method is reasonable to me in that we employ Kronecker Factorization to reduce the computational and storage complexities and compensate for the reduced expressive power by ensembling. The idea of ensembling is also found in Canini et al. (2016); however, this paper's strength is that it backbones this idea by theoretical results (Proposition 2, 3), which are novel.\n\n**Correctness and Clarity**\n\nIs the theorem correct?\n- The proofs of propositions are correct, so far as I check.\n\nIs the experimental evaluation correct?\n- I do not find any inappropriate points in experimental settings.\n\nIs the experiment reproducible?\n- The implementation of the proposed method is made public. This paper used three datasets in experiments. One dataset (Adult Income) is made public, and the other two datasets are proprietary. So, it is hard for us to reproduce the same experiments using private datasets.\n\n**Clarity**\n\nCan I understand the main point of the paper easily?\n- Yes, I can understand the backgrounds of the proposed method explained in Section 2. The mathematical descriptions of this paper are clear.\n\nIs the organization of paper well?\n- Yes. I did not find any problem with the organization of the paper.\n\nAre figures and tables appropriately made?\n- Yes\n\n**Additional feedback**\n\n- Section 4, Paragraph 1: This paper says that for each monotonic feature $d$, $w^{(m)}_d$ is projected to satisfy the monotonicity constraints of Proposition 2 Condition 3. I think this projection operation is not obvious per se. So, I want this paper to clarify it.\n- Proposition 3: Is there a case in which $M$ is strictly smaller than the upepr bound $|\\mathcal{M}_\\mathcal{V}| /  \\max_i \\mathcal{V}_i$ ? It is merely my intuition but since $T$ can take an arbitrary tensor of size $\\mathcal{V}$, there might not be such a case.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ouomYiRD1JN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThe authors propose KFL, an efficient reparametrization of monotonic lattice regression using Kronecker factorization. The goal is to achieve efficiency both in terms of computations and in terms of the number of parameters. The authors show that the proposed KFL has storage and computational costs that scale linearly in the number of input features. \nExperimental results show that KFL has better speed and storage space. The authors also provide necessary and sufficient conditions for a KFL model to be monotonic with respect to some features. \n\n**+ves**\n+ This appears to be a new parametrization of monotonic lattice regression with parametric and computational advanages\n+ Theoretical results show necessary and sufficient conditions for KFL to be monotonic, and this allows the design of training algorithms; there are also theoretical results on the capacity\n+ Experiments on public and proprietary datasets show that KFL maintains error rate while needing less time to train and fewer parameters. \n\n**Concerns**\n- The gains in training and eval time (especially compared to simplex) seem modest. However the number of parameters is significantly reduced. I wonder if a larger dataset/more complex task would demonstrate the benefits more clearly. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "cK5wirYeKPy", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes to use Kronecker factorization on a lattice for a monotonic lattice. Thanks to the factorization, the computational cost is improved to linear compared to exponential. The paper went on to extend to use an ensemble of KFLs due to each factorized lattice is too restricted. Compared with the baseline, monotonic KFL achieves good accuracy with much faster run times on the experiments.\n\nThe approach seems to strike a good balance between computation and representation of power by choosing an ensemble of factorized functions.\n\nI am not familiar with the motivation for monotonic functions and why the datasets/tasks such as query result matching requires the resulting function to satisfy monotonicity. For this reason, I am not sure about the significance of the work.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The focus of the submission is shape-constrained regression, particularly the goal is to learn monotonic, 'reasonably rich' functions. In order to tackle this task, the authors extend the monotonic regression framework (Gupta et al., 2016) which scales less benignly in the input dimension. They propose to use lattice functions with parameters having Kronecker product structure (, and their ensembles). The resulting function class can be (i) stored and evaluated in linear time (Proposition 1), (ii) characterized / checked from monotonicity perspective (Proposition 2). The efficiency of the approach is demonstrated in three real-world examples.

Shape-constrained regression is a central topic in machine learning and statistics. The authors propose a parametric family to learn monotonically constrained functions. The storage and the evaluation of the resulting functions are both fast (linear), and the numerical experiments are encouraging. The submission can be of definite interest to the ICLR community. 
Decision: Accept (Poster)