Input Convex Neural Networks

1. Introduction

• Convexity in selected inputs enables global, efficient optimization for inference, but the network may remain nonconvex in other inputs and training remains nonconvex.The paper distinguishes input convexity from convexity of the parameter-learning problem; convexity is exploited at inference time.Source: §1 · p. 1

Structured prediction

• In structured prediction, the network scores input-output pairs, and convexity in the output makes energy minimization globally optimizable when the output space is convex.Prediction selects the output y minimizing the network energy for a given input x.Source: §1 · p. 1

Data imputation

• For data imputation, the network infers missing variables by minimizing its value over them while holding observed variables fixed, including for image inpainting.The formulation can omit additional conditioning inputs or include them, and the missing subset may be arbitrary.Source: §1 · pp. 1–2

Continuous action reinforcement learning

• For continuous-action reinforcement learning, modeling the negative Q function as an ICNN makes action selection a convex optimization over actions for each state.The selected action minimizes −Q(s, a; θ).Source: §1 · p. 2

1. Introduction

• The paper proposes ICNN and partially convex architectures, tailored optimization and inference procedures, and training methods based on max-margin prediction or differentiating the argmin.It evaluates the models on multi-label prediction, image completion, and reinforcement learning, reporting improvements over prior state of the art in many settings.Source: §1 · p. 2

Energy-based learning

• Prior energy-based approaches include structured prediction as a deep network’s last layer and joint input-output models such as GANs and SPENs (Belanger & McCallum, 2016).SPENs perform inference as a nonconvex optimization problem.Source: §2 · p. 2
• Input-convex networks constrain inference through convexity while allowing deep, nonlinear functions over the variables being optimized, without manually specifying those functions.The paper contrasts this approach with methods that make inference easy through particular architectural structures and general models that make no such effort.Source: §2 · p. 2

Structured prediction and MAP inference

• The method is an extreme MAP-inference approach: inference uses convex optimization that need not have probabilistic semantics.The paper also notes a philosophical similarity to sum-product networks (Poon & Domingos, 2011), where inference is made easy by sum-product message passing.Source: §2 · p. 2

Fitting convex functions

• The learning problem can be viewed as fitting convex functions to data; compared with sums of rectified half-planes, its deep architecture supports richer representations while preserving convexity.The authors characterize their training scheme as different from that prior work.Source: §2 · pp. 2–3

3.1. Fully input convex neural networks

• A fully connected FICNN is convex in y when hidden-to-hidden weights are nonnegative and activations are convex and non-decreasing, including ReLU and maxpooling.The network defines a function over y alone.Source: §3.1 · p. 3
• Input passthrough layers preserve direct input connections under nonnegative hidden-weight constraints, and convolutional operators can be included without changing convexity.The paper notes that AlexNet, VGG, and GoogLeNet with ReLUs can be made input convex.Source: §3.1 · p. 3

3.2. Partially input convex architectures

• A k-layer PICNN is convex in y but not x and can represent both k-layer FICNNs and purely feedforward networks.Its x and y hidden units may interact through elementwise products, while only the hidden-to-hidden weights on the y path must be nonnegative.Source: §3.2 · pp. 3–4

4. Inference in ICNNs

• For ReLU- or linear-unit ICNNs, exact inference can be formulated as a linear program, although this approach is impractical.The formulation is described in Section B.Source: §4 · p. 4

4.1. Approximate inference in ICNNs

• Because exact inference is impractical, approximate gradient-based methods exploit the readily computed input gradient, and can achieve reasonable accuracy with complexity at most a constant factor above feedforward networks.The paper describes inference as convex optimization and notes that a small number of forward and backward passes can suffice.Source: §4.1 · p. 4, §4 · p. 4
• Gradient descent is simple but requires step-size choices, lacks an obvious accuracy test for ReLU ICNNs, and can be difficult to differentiate through during learning.The paper reports that alternative approximate approaches typically far outperform it in practice.Source: §4.1 · p. 4

4.2. Approximate inference via the bundle entropy method

• The bundle entropy method replaces the traditional bundle method with an algorithm for bounded Y, typically [0, 1]^n, using negative entropy as a barrier that keeps the solution interior.The approach also extends to settings where elements of Y belong to a higher-dimensional probability simplex.Source: §4.2 · pp. 4–5
• For a trivial PICNN with a linear function of y, entropy-regularized minimization yields the sigmoid of the feedforward network outputs, linking sigmoid units to structured joint energy functions.The equivalence follows from first-order optimality conditions.Source: §4.2 · p. 5
• With typically 5 iterations, bundle entropy substantially outperforms gradient descent; it often reaches exact solutions on lower-dimensional problems and provides an optimality gap.A fixed number of iterations works well in practice.Source: §4.2 · p. 5

5. Learning ICNNs

• Direct functional fitting can reuse existing methods such as Q-learning, provided required ICNN weights are projected onto their feasible sets after updates.The paper identifies Q-learning as an example and specifies clipping or projection for weights constrained to be positive.Source: §5 · pp. 5–6
• Max-margin structured prediction proved difficult to tune for continuous-valued outputs and to extend beyond hinge loss, so most experiments use argmin differentiation instead.The paper discusses max-margin structured prediction in more detail in Section F.Source: §5 · p. 6

5.1. Argmin differentiation

• Argmin differentiation minimizes loss on predictions from a fixed, usually small number of bundle entropy iterations and differentiates through the approximate argmin using KKT conditions.The resulting parameter gradients can be used with stochastic gradient methods such as ADAM.Source: §5.1 · p. 6
• The argmin gradient costs a small constant multiple of k parameter gradients, where k is the number of active bundle-entropy constraints, with the matrix inversion reduced to k × k.The challenging mixed derivative can be computed with autodifferentiation or finite differences.Source: §5.1 · p. 6

6.2. Multi-Label Classification

• On BibTeX, PICNN maps 1,836 binary text features to 159 labels and is evaluated with macro-F1; it and the baseline share 600-unit and 159-unit fully connected layers.The split is 4,880/2,515 from Katakis et al. (2008); PICNN uses ReLU, batch normalization, and 30 gradient-descent iterations at learning rate 0.1 and momentum 0.3.Source: §6.2 · p. 7
• PICNN achieved macro-F1 0.415, versus 0.396 for the baseline feedforward network and 0.422 for SPENs.The authors note that the 0.007 difference between PICNN and SPENs could reflect differences in experimental setups, architectures, or random noise.Source: §6.2 · p. 7

6.3. Image completion on the Olivetti faces

• For face completion, a convolutional PICNN predicts the right half of 64×64 grayscale faces from the left half, using an architecture inspired by DQN to support input transformation invariance.The Olivetti dataset contains 400 images; training and test splits and MSE follow Poon & Domingos (2011) for direct comparison.Source: §6.3 · p. 7
• Image-completion MSE was 833.0 for ICNN bundle entropy, 872.0 for ICNN gradient descent, 850.9 for ICNN nonconvex, and 942 for sum-product (Poon & Domingos, 2011).Bundle entropy leveraged more information than gradient descent from five inner-optimization iterations; the relaxed-convexity network slightly outperformed the convex network but not bundle entropy.Source: Table 2 · p. 8, §6.3 · p. 8
• The image-completion experiment suggests five inner-optimization iterations suffice for good performance, and convexity does not seem to inhibit PICNN representational power.The relaxed-convexity model slightly outperformed the convex model, while bundle entropy performed better than both.Source: §6.3 · p. 8

6.4. Continuous Action Reinforcement Learning

• The reinforcement-learning approach models −Q(s, a; θ) as a PICNN and selects actions by convex optimization, comparing against DDPG (Lillicrap et al., 2015) and NAF (Gu et al., 2016).Unlike NAF’s quadratic action advantage, ICNN permits any convex functional form, but makes action optimization substantially more computationally complex.Source: §6.4 · p. 8
• ICNNs show task-dependent reinforcement-learning results: they have clear advantages on HalfCheetah, Reacher, and HumanoidStandup, perform comparably on many tasks, and perform poorly on Hopper and Walker2D.No method strictly dominates the alternatives; the authors describe the overall results as positive given the strong baselines and ICNNs’ drop-in use as a Q-function approximator.Source: Table 3 · p. 8, §6.4 · p. 8

• Simple constraints on existing network architectures enable input convex neural networks to fit general convex functions and use optimization as inference.Source: §7 · p. 8
• The framework extends models such as CRFs by learning the inference procedure together with the network, without explicitly building typical structured-prediction architectures.Source: §7 · p. 8
• The paper explores only a small subset of possible applications, leaving additional domains as promising directions for future work.Source: §7 · p. 8

A.1. Convolutional architectures

• Convolutions can be incorporated into ICNNs because convolution is a linear operator.The paper introduces convolutions after omitting them from its earlier presentation to keep the notation light.Source: §A.1 · p. 11
• When input and output spaces share a structure, convolutional PICNN layers use same-sized kernels and scale inputs and outputs to match the previous feature map.The presented layer definition omits some Hadamard-product terms for simplicity.Source: §A.1 · p. 11
• For spatial inputs with a differently structured output space, the output-space convolution can be replaced by a matrix-vector operation.The paper gives the simplex as an example of a differently structured output space.Source: §A.1 · p. 11

B. Exact inference in ICNNs

• Inference for the presented networks with ReLU or linear units can be posed as a linear program, with the FICNN formulation reproducing the network equations.The paper presents this as an exact formulation, not a practical solver for the optimization tasks.Source: B. Exact inference in ICNNs · p. 11
• For ReLU networks, nonnegative activations and inequality constraints recover the ReLU equations because minimizing the final layer makes the inequalities tight; the same procedure applies to PICNN inference.At the solution, each activation equals either its affine input or zero.Source: B. Exact inference in ICNNs · p. 11
• LP inference is impractical because it introduces a variable for every network activation and requires expensive matrix inversions that do not exploit neural-network hardware acceleration.The cited solver methods include interior-point methods, ADMM, and Simplex; the paper says their computation can exceed a single forward pass.Source: B. Exact inference in ICNNs · p. 11

C. The bundle method for approximate inference in ICNNs

• The bundle method maintains a piecewise-linear global lower bound on a convex objective using first-order cutting planes, then repeatedly optimizes that bound.At each iteration it adds a first-order approximation at the current iterate; the resulting optimization can be written with linear inequality constraints.Source: C. The bundle method for approximate… · p. 12

D. Bundle Entropy Algorithm

• Bundle entropy optimization minimizes f(x, y) over y in [0, 1]^n for K iterations, using fixed x and an initial point y1.The algorithm appends gradient-based linear constraints and tracks the number of active constraints.Source: D. Bundle Entropy Algorithm · p. 12

E. Deep Q-learning with ICNNs

• Deep Q-learning with ICNNs uses a convex minimization algorithm such as gradient descent or bundle entropy to optimize the action objective.The objective is Q(s, a|θ) with gradient descent and Q(s, a|θ) + H(a) with the bundle entropy method.Source: E. Deep Q-learning with ICNNs · p. 13

F. Max-margin structured prediction

• Max-margin structured prediction requires the target output’s joint energy to be below alternatives, with a loss-scaled margin to prevent a constant energy function from satisfying the constraints.The framework adds slack variables for possible constraint violations.Source: F. Max-margin structured prediction · p. 13
• For multiclass classification, the method can use a multivariate entropy term and Δ(y, y⋆) = y⋆T (1 − y); loss-augmented inference is convex for suitable margin scaling.Here y⋆ is a one-hot encoding of the example.Source: F. Max-margin structured prediction · p. 13
• Although optimization problem (29) remains nonconvex in θ, structured-prediction subgradient learning selects a training example, solves the optimization problem, and updates network parameters when the margin is violated.Updates project onto the non-negative orthant; the method also supports mini-batches, AdaGrad, ADAM (Kingma & Ba, 2014), and approximate solutions for y⋆.Source: F. Max-margin structured prediction · p. 13

G. Proof of Proposition 3

• The proof uses the chain rule and implicit differentiation of the bundle-entropy KKT conditions to recover Proposition 3’s formula.The KKT conditions considered are those for the active constraints.Source: G. Proof of Proposition 3 · pp. 13–14
• For derivatives with respect to h, differentiating the KKT equations gives a system whose Jacobian product is used directly in the objective.Although the Jacobian can be obtained by solving with dh = I, the proof instead left-multiplies the relevant terms by ∂ℓ.Source: G. Proof of Proposition 3 · p. 14
• Differentiating with respect to G yields analogous matrix equations and Jacobian products, which combine with the stated definitions to recover the proposition’s formula.The definitions specify the quantities used in that final substitution.Source: G. Proof of Proposition 3 · p. 14

H. State and action space sizes in the OpenAI gym MuJoCo benchmarks.

• Table 4 presents state and action space sizes for the OpenAI Gym MuJoCo benchmarks.The supplied passage identifies the table’s scope but provides no cell values.Source: Table 4 · p. 14

I. Synthetic classification examples

• The synthetic study evaluates two-hidden-layer FICNNs and PICNNs on two-dimensional binary classification tasks from scikit-learn (Pedregosa et al., 2011).Figure 4 shows the classification performance on the dataset.Source: §I · p. 14
• The FICNN energy function is jointly fully convex in X × Y and can capture complex, but sometimes restrictive, decision boundaries.Source: §I · p. 14
• The PICNN is nonconvex over X but convex over Y, overcoming the FICNN’s boundary restrictions and capturing more complex decision boundaries.Source: §I · p. 14

K. Image Completion

• Figure 4 depicts FICNN (top) and PICNN (bottom) classification of synthetic non-convex decision boundaries.Source: Figure 4 · p. 15

J. Multi-Label Classification Training Plots

• Test macro-F1 was 0.396 for the feedforward network and 0.415 for PICNN on BibTeX, with higher scores better.Source: Figure 5 · p. 15
• Figure 5 plots training (blue) and test (red) macro-F1 for both models on BibTeX.Source: Figure 5 · p. 15

K. Image Completion

• The bundle entropy method reached a minimum test MSE of 833.0 on Olivetti faces.Source: K. Image Completion · p. 14, Figure 6 · p. 15
• Back optimization reached a minimum test MSE of 872.0 on Olivetti faces.Source: K. Image Completion · p. 14, Figure 6 · p. 15
• Back optimization with the convexity constraint relaxed reached a minimum test MSE of 850.9 on Olivetti faces.Source: K. Image Completion · p. 14, Figure 6 · p. 15