Introduction
The escalating energy demands of modern machine learning have driven a resurgence of interest in analog computing paradigms and the development of training methods dedicated to such platforms [34 ] . By replacing the digital von Neumann architecture with analog compute-in-memory substrates, these systems promise substantial improvements in energy efficiency for both inference and training. Among these alternative platforms, resistive networks have attracted special interest.
A resistive network is an electrical circuit comprised of (linear or nonlinear) resistors, with nodes typically partitioned into input, hidden and output sets. In such a network where computation is driven by the circuit’s physics, the input node potentials are clamped to specific values, while the output node potentials serve as the network’s prediction. Conductances of variable resistors serve as the trainable parameters, and the objective is to find parameter configurations that implement a desired input-output mapping. It is well-known that the hidden and output potentials of a linear resistive network minimize the total dissipated power; in nonlinear resistive networks—those containing nonlinear one-port resistive elements—the hidden and output potentials extremize a more general notion known as the co-content [32 ] , also referred to as “pseudo-power” [27 ] . This property allows resistive networks to function as energy-based models where the co-content acts as the energy function. For such systems, energy-based learning rules have been developed which adjust conductances based solely on local voltage measurements, allowing decentralized training [3 , 17 , 25 , 27 ] . On the hardware side, small-scale prototypes have successfully demonstrated self-learning capabilities on toy tasks [16 , 17 ] . On the simulation side, SPICE-class simulations of modest-size nonlinear resistive networks have been performed on MNIST [27 , 51 ] , while recent methods exploit the co-content minimization formulation to achieve speedups of several orders of magnitude [37 , 40 ] , paving the way for large-scale simulations.
To rival artificial neural networks, resistive networks must demonstrate representational capacity, and learning capabilities. Learning in resistive networks was initially formalized by [27 ] through Equilibrium Propagation (EP), an energy-based learning framework that enables gradient descent on an arbitrary cost function [42 ] . EP is part of a broader class of energy-based learning methods [43 ] that optimize parameters by comparing the network in two different states: the inference state (called free state ), and a perturbed state where outputs are clamped or nudged towards a target. Other energy-based learning rules differ from EP in the way the perturbed state is defined. In particular, the Contrastive Learning (CL) algorithm of [25 ] (adapted from [35 , 43 ] ) clamps output nodes to exact target values in the perturbed state, effectively performing gradient descent on a nonnegative contrastive function whose minimum of zero is attained precisely when the network outputs match the target output. In [25 ] , it was shown that the contrastive function is convex for linear networks without hidden nodes, establishing the convergence for a range of step sizes. These results were also recently extended to linear resistive-capacitive networks in [23 ] . On the representational capacity front, [44 ] showed that nonlinear resistive networks can approximate arbitrary continuous functions, provided they incorporate two-port elements like voltage-controlled voltage sources (VCVSs).
In this paper, we establish mathematical foundations for learning and representation in nonlinear resistive networks constructed exclusively from one-port elements. This deliberately precludes the VCVSs utilized by [44 ] . We assume all circuit components possess strictly monotonically increasing current-voltage characteristics, which encompasses Ohmic resistors and diodes, and yields a strictly convex network co-content. Within this framework, we answer two fundamental questions: under what conditions does learning reliably converge, and what is the network’s representational capacity?
While [25 ] proved the convergence of the CL algorithm with clamped outputs, their analysis was limited to linear networks without hidden nodes. Our first main contribution extends their framework to nonlinear networks. We prove that the contrastive function is convex for nonlinear networks without hidden nodes, guaranteeing convergence of the parameters to a global minimum. This is in contrast with the EP objective function, which is in general non-convex, even without hidden nodes. For the more expressive and general case that includes hidden nodes, the contrastive function is no longer convex, but in this case, we prove that the learning dynamics converge on a subsequence to a stationary point. Interestingly, any of such stationary points in the interior of the constraint set is shown to be a global minimum of the contrastive function.
Our second main contribution analyzes the representational expressivity of these circuits. We demonstrate that the input-output mappings of such networks are monotonically non-decreasing and shift-equivariant (translation-equivariant). Remarkably, we establish a novel approximation theorem proving that these two physical constraints are the only limitations on expressivity. Any continuous function satisfying monotonicity and shift equivariance can be approximated to arbitrary precision by a nonlinear resistive network featuring strictly convex co-content functions. To prove this, we introduce a novel circuit construction leveraging scalable, smooth approximations of min-max functions.
Finally, we clarify a terminological ambiguity present in the recent literature on physical learning algorithms. The term “contrastive learning” is used in two distinct ways: as the specific learning rule involving clamped targets [23 , 25 , 43 ] , and as a broad umbrella term for the entire class of energy-based learning methods [17 , 19 , 34 , 49 ] . This broader category includes other algorithms such as coupled learning [2 , 17 , 48 ] , which employs a weaker form of clamping that fixes outputs to a convex combination of the free outputs and targets. To avoid confusion, we introduce the term Target-Clamped Contrastive Learning (TCCL) to explicitly refer to the specific learning rule that utilizes clamped targets. For brevity, we occasionally abbreviate this to Contrastive Learning (CL) when the context is unambiguous, in line with the terminology of [23 , 25 , 43 ] .
We note a recent concurrent study by [30 ] on the computational expressivity of thermodynamic networks; however, their framework permits elements whose current depends on terminal voltages independently rather than on their difference, meaning the network non-equilibrium steady state cannot generally be characterized as the minimum of a co-content function, and energy-based learning algorithms such as TCCL or EP cannot be directly employed.
Another recent work [31 ] studied the convergence of energy-based learning algorithms for linear resistive circuits. This work is complementary to the current paper, in the sense that it deals with local convergence results for EP and coupled learning in linear circuits, whereas our study focuses on global convergence analysis for TCCL in nonlinear circuits.
The remainder of this paper is organized as follows. § 2 introduces nonlinear resistive circuits and co-content functions. Section III formalizes the learning problem. § 4 discusses the contrastive learning framework. § 5 analyzes the convexity of the contrastive function, and Section VI establishes convergence guarantees for the learning dynamics. Section VII defines the fundamental physical constraints of the circuits and proves the approximation theorem. Finally, conclusions are provided in Section VIII. The reader is also directed to Appendix A for relevant notation, and to Appendix B for preliminaries on convex, coercive and Lipschitz continuous functions.
Modeling of Nonlinear Resistive Circuits
We start by introducing a few graph-theoretic concepts used throughout the paper. For a general reference on graph theory, we refer the reader to [11 ] . We consider a connected undirected graph
G = ( V , E ) , \mathcal{G} = (\mathcal{V},\mathcal{E}), G = ( V , E ) ,
consisting of a set of nodes V = { 1 , 2 , … , N } \mathcal{V} = \{1,2,\ldots,N\} V = { 1 , 2 , … , N } and a set of branches (or edges) E \mathcal{E} E , containing B B B unordered pairs of nodes. The incidence matrix of G \mathcal{G} G is defined as follows. First, we denote the edges in the graph by e 1 , e 2 , … , e B e_1,e_2,\ldots,e_B e 1 , e 2 , … , e B , and we assign an arbitrary orientation to each edge. Then, the incidence matrix D ∈ R N × B D \in\mathbb{R}^{N \times B} D ∈ R N × B is defined element-wise by
D i j = { − 1 if edge e j leaves node i , 1 if edge e j enters node i , 0 otherwise. D_{ij} =
\begin{cases}
-1 & \text{if edge } e_j \text{ leaves node } i,\\
1 & \text{if edge } e_j \text{ enters node } i,\\
0 & \text{otherwise.}
\end{cases} D ij = ⎩ ⎨ ⎧ − 1 1 0 if edge e j leaves node i , if edge e j enters node i , otherwise.
By definition of the incidence matrix, we have that im 1 ⊆ ker D T \operatorname{im}\mathbf{1} \subseteq\ker D^{\mathsf{T}} im 1 ⊆ ker D T , where 1 \mathbf{1} 1 denotes the vector of ones. Moreover, since G \mathcal{G} G is connected, it follows from [21 Thm. 8.3.1] that
ker D T = im 1. (1) \ker D^{\mathsf{T}} = \operatorname{im}\mathbf{1}. \tag*{(1)} ker D T = im 1 . (1)
Next, we consider the vectors p ∈ R N p \in\mathbb{R}^{N} p ∈ R N of nodal voltage potentials, and j ∈ R N j \in\mathbb{R}^{N} j ∈ R N of external currents injected into each of the nodes. The vectors v ∈ R B v \in\mathbb{R}^{B} v ∈ R B and i ∈ R B i \in\mathbb{R}^{B} i ∈ R B denote the voltages and currents over and through the edges, respectively. Obviously, due to the laws of Kirchhoff, we have
v = D T p and j = D i . (2) v = D^{\mathsf{T}}p \quad\text{and} \quad j = Di. \tag*{(2)} v = D T p and j = D i . (2)
Every branch k ∈ { 1 , 2 , … , B } k \in\{1,2,\ldots,B\} k ∈ { 1 , 2 , … , B } contains a nonlinear resistor modeled as
i k = d G k d v k ( v k ) . (3) i_k = \frac{dG_k}{dv_k}(v_k). \tag*{(3)} i k = d v k d G k ( v k ) . (3)
Here G k : R → R G_k:\mathbb{R}\to\mathbb{R} G k : R → R is the so-called co-content function [32 ] of the k k k -th resistor, which we assume to be differentiable, coercive and strictly convex. Note that the strict convexity of G k G_k G k is equivalent to d G k d v k \frac{dG_k}{dv_k} d v k d G k being strictly monotonically increasing. Thus, (3) defines a strictly monotone relation between the current and voltage at branch k k k .
Next, we define the “total” co-content function G : R B → R G:\mathbb{R}^{B}\to\mathbb{R} G : R B → R as
G ( v ) : = ∑ k = 1 B G k ( v k ) . G(v) := \sum_{k=1}^{B} G_k(v_k). G ( v ) := k = 1 ∑ B G k ( v k ) .
The function G G G inherits properties of the functions G k G_k G k . In particular, G G G is differentiable, coercive and strictly convex. We also observe that
∇ G ( v ) = [ d G 1 d v 1 ( v 1 ) d G 2 d v 2 ( v 2 ) ⋮ d G B d v B ( v B ) ] . \nabla G(v) =
\begin{bmatrix}
\dfrac{dG_1}{dv_1}(v_1)\\
\dfrac{dG_2}{dv_2}(v_2)\\
\vdots\\
\dfrac{dG_B}{dv_B}(v_B)
\end{bmatrix}. ∇ G ( v ) = d v 1 d G 1 ( v 1 ) d v 2 d G 2 ( v 2 ) ⋮ d v B d G B ( v B ) .
This implies that, by Kirchhoff’s laws (2) and the model of the resistors (3) , we can succinctly write the relation between j j j and p p p as
j = D ∇ G ( D T p ) . (4) j = D\nabla G(D^{\mathsf{T}}p). \tag*{(4)} j = D ∇ G ( D T p ) . (4)
In the context of learning in electrical circuits, it will become useful to partition the set of nodes V \mathcal{V} V into two or multiple sets (corresponding to sets of input, hidden, and output nodes). In what follows, we will derive some preliminary results to aid that discussion.
Let V = V 1 ∪ V 2 \mathcal{V} = \mathcal{V}_1 \cup\mathcal{V}_2 V = V 1 ∪ V 2 where V 1 \mathcal{V}_1 V 1 and V 2 \mathcal{V}_2 V 2 are disjoint. After possible relabeling of the nodes, this yields the partitioned vectors and matrix:
p = [ p 1 p 2 ] , j = [ j 1 j 2 ] , D = [ D 1 D 2 ] , p =
\begin{bmatrix}
p_1\\
p_2
\end{bmatrix},
\quad
j =
\begin{bmatrix}
j_1\\
j_2
\end{bmatrix},
\quad
D =
\begin{bmatrix}
D_1\\
D_2
\end{bmatrix}, p = [ p 1 p 2 ] , j = [ j 1 j 2 ] , D = [ D 1 D 2 ] ,
where p 1 , j 1 ∈ R N 1 p_1,j_1 \in\mathbb{R}^{N_1} p 1 , j 1 ∈ R N 1 , p 2 , j 2 ∈ R N 2 p_2,j_2 \in\mathbb{R}^{N_2} p 2 , j 2 ∈ R N 2 , and D 1 ∈ R N 1 × B D_1 \in\mathbb{R}^{N_1 \times B} D 1 ∈ R N 1 × B , D 2 ∈ R N 2 × B D_2 \in\mathbb{R}^{N_2 \times B} D 2 ∈ R N 2 × B . Here N 1 , N 2 ∈ N N_1,N_2 \in\mathbb{N} N 1 , N 2 ∈ N are positive integers such that N 1 + N 2 = N N_1 + N_2 = N N 1 + N 2 = N .
We set the injected currents in the V 2 \mathcal{V}_2 V 2 -nodes to zero, i.e., j 2 = 0 j_2 = 0 j 2 = 0 . By (4) , this results into the equations
\begin{bmatrix} j_1 \\ 0 \end{bmatrix} =
\begin{bmatrix} D_1 \\ D_2 \end{bmatrix}
\nabla G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2). \tag*{(5)}\end{bmatrix}
Note that for given p 1 p_1 p 1 and p 2 p_2 p 2 , the currents j 1 j_1 j 1 are uniquely defined by the first N 1 N_1 N 1 rows of (5) . In addition, the last N 2 N_2 N 2 rows of (5) provide a relation between p 1 p_1 p 1 and p 2 p_2 p 2 . Indeed,
0 = D 2 ∇ G ( D 1 T p 1 + D 2 T p 2 ) . (6) 0 = D_2\nabla G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2). \tag*{(6)} 0 = D 2 ∇ G ( D 1 T p 1 + D 2 T p 2 ) . (6)
We will view (6) as an input-output model with input p 1 p_1 p 1 and corresponding output p 2 p_2 p 2 . The following lemma clarifies the existence and uniqueness of such an output p 2 p_2 p 2 , given p 1 p_1 p 1 .
Lemma 2. Assume that the function G k : R → R G_k : \mathbb{R} \to\mathbb{R} G k : R → R is differentiable, coercive and strictly convex for all k = 1 , 2 , … , B k = 1, 2, \ldots, B k = 1 , 2 , … , B . Then, for every p 1 ∈ R N 1 p_1 \in\mathbb{R}^{N_1} p 1 ∈ R N 1 , the function H : R N 2 → R H : \mathbb{R}^{N_2} \to\mathbb{R} H : R N 2 → R defined as
H ( p 2 ) = G ( D 1 T p 1 + D 2 T p 2 ) H(p_2) = G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2) H ( p 2 ) = G ( D 1 T p 1 + D 2 T p 2 ) is differentiable, coercive and strictly convex. Moreover, for every p 1 ∈ R N 1 p_1 \in\mathbb{R}^{N_1} p 1 ∈ R N 1 , there exists a unique p 2 ∈ R N 2 p_2 \in\mathbb{R}^{N_2} p 2 ∈ R N 2 satisfying (6) . This p 2 p_2 p 2 is the unique minimizer of H H H .
Proof. Let p 1 ∈ R N 1 p_1 \in\mathbb{R}^{N_1} p 1 ∈ R N 1 . We will first establish the properties of H H H . Obviously, H H H is differentiable by differentiability of G G G . Moreover, since G G G is connected, it follows from (1) that D 2 T D_2^{\mathsf{T}} D 2 T has full column rank. Indeed, suppose that D 2 T x = 0 D_2^{\mathsf{T}}x = 0 D 2 T x = 0 for some vector x ∈ R N 2 x \in\mathbb{R}^{N_2} x ∈ R N 2 . Then
[ 0 x ] ∈ ker D T , \begin{bmatrix} 0 \\ x \end{bmatrix} \in\ker D^{\mathsf{T}}, [ 0 x ] ∈ ker D T ,
which means that x = 0 x = 0 x = 0 by (1) . Hence, D 2 T D_2^{\mathsf{T}} D 2 T has full column rank. As such, if ∥ p 2 ∥ → ∞ \lVert p_2\rVert\to\infty ∥ p 2 ∥ → ∞ , then also ∥ D 1 T p 1 + D 2 T p 2 ∥ → ∞ \lVert D_1^{\mathsf{T}}p_1+D_2^{\mathsf{T}}p_2\rVert\to\infty ∥ D 1 T p 1 + D 2 T p 2 ∥ → ∞ . This shows that H H H is coercive since G G G is coercive. Next, note that for α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] and p 2 , p ‾ 2 ∈ R N 2 p_2,\overline{p}_2 \in\mathbb{R}^{N_2} p 2 , p 2 ∈ R N 2 , we have that H ( α p 2 + ( 1 − α ) p ‾ 2 ) H(\alpha p_2 + (1-\alpha)\overline{p}_2) H ( α p 2 + ( 1 − α ) p 2 ) is equal to
G ( α ( D 1 T p 1 + D 2 T p 2 ) + ( 1 − α ) ( D 1 T p 1 + D 2 T p ‾ 2 ) ) ≤ α G ( D 1 T p 1 + D 2 T p 2 ) + ( 1 − α ) G ( D 1 T p 1 + D 2 T p ‾ 2 ) = α H ( p 2 ) + ( 1 − α ) H ( p ‾ 2 ) , (7) \begin{aligned}
&G\bigl(\alpha(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2) + (1-\alpha)(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}\overline{p}_2)\bigr) \\
&\leq\alpha G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2) + (1-\alpha)G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}\overline{p}_2) \\
&= \alpha H(p_2) + (1-\alpha)H(\overline{p}_2), \tag*{(7)}
\end{aligned} G ( α ( D 1 T p 1 + D 2 T p 2 ) + ( 1 − α ) ( D 1 T p 1 + D 2 T p 2 ) ) ≤ α G ( D 1 T p 1 + D 2 T p 2 ) + ( 1 − α ) G ( D 1 T p 1 + D 2 T p 2 ) = α H ( p 2 ) + ( 1 − α ) H ( p 2 ) , (7)
where the inequality follows by convexity of G G G . Thus, also H H H is a convex function. Moreover, if α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) and p 2 ≠ p ‾ 2 p_2 \ne\overline{p}_2 p 2 = p 2 then the inequality in (7) is strict due to strict convexity of G G G and full column rank of D 2 T D_2^{\mathsf{T}} D 2 T . This proves that also H H H is strictly convex. By Proposition 25 (iv) in Appendix B, H H H has precisely one minimizer. As such, there is precisely one point p 2 p_2 p 2 at which ∇ H ( p 2 ) = 0 \nabla H(p_2) = 0 ∇ H ( p 2 ) = 0 . Now, note that
∇ H ( p 2 ) = D 2 ∇ G ( D 1 T p 1 + D 2 T p 2 ) , \nabla H(p_2) = D_2\nabla G(D_1^{\mathsf{T}}p_1 + D_2^{\mathsf{T}}p_2), ∇ H ( p 2 ) = D 2 ∇ G ( D 1 T p 1 + D 2 T p 2 ) ,
which equals the right hand side of (6) . We conclude that for every p 1 ∈ R N 1 p_1 \in\mathbb{R}^{N_1} p 1 ∈ R N 1 , there indeed exists a unique p 2 ∈ R N 2 p_2 \in\mathbb{R}^{N_2} p 2 ∈ R N 2 satisfying (6) .
:::
The Problem of Learning in Resistive Circuits
The use of resistive networks in analog computing applications has a long history, see, e.g., [22 ] . In this paper, we are interested in learning in resistive networks, where we consider the conductances of variable resistors as trainable parameters. We will follow the modeling framework as outlined in the previous section. In particular, we consider a connected undirected graph G = ( V , E ) \mathcal{G} = (\mathcal{V},\mathcal{E}) G = ( V , E ) with N N N nodes and B B B branches. This time, the node set V \mathcal{V} V is partitioned as V = V I ∪ V H ∪ V O \mathcal{V} = \mathcal{V}_{I} \cup\mathcal{V}_{H} \cup\mathcal{V}_{O} V = V I ∪ V H ∪ V O with V I \mathcal{V}_{I} V I , V H \mathcal{V}_{H} V H and V O \mathcal{V}_{O} V O mutually disjoint. We refer to the nodes in V I \mathcal{V}_{I} V I as input nodes, those in V H \mathcal{V}_{H} V H as hidden nodes, and those in V O \mathcal{V}_{O} V O as output nodes.
All branches of the network contain (nonlinear) adjustable resistors. This means that we associate to each of the resistors a parameterized co-content function of the form θ k G k ( ⋅ ) \theta_kG_k(\cdot) θ k G k ( ⋅ ) , where θ k ∈ R \theta_k \in\mathbb{R} θ k ∈ R is an adjustable parameter and G k : R → R G_k : \mathbb{R} \to\mathbb{R} G k : R → R for all k ∈ { 1 , 2 , … , B } k \in\{1,2,\ldots,B\} k ∈ { 1 , 2 , … , B } . We make the following blanket assumption on the functions G k G_k G k .
Assumption 1. The functions G k : R → R G_k : \mathbb{R} \to\mathbb{R} G k : R → R are coercive, twice continuously differentiable, and such that d 2 G k d v k 2 ( v k ) > 0 \frac{\mathrm{d}^2G_k}{\mathrm{d}v_k^2}(v_k) > 0 d v k 2 d 2 G k ( v k ) > 0 for all v k ∈ R v_k \in\mathbb{R} v k ∈ R and k = 1 , 2 , … , B k = 1,2,\ldots,B k = 1 , 2 , … , B .
Next, we collect the parameters in the vector
θ = [ θ 1 θ 2 ⋮ θ B ] ∈ Θ . \theta=
\begin{bmatrix}
\theta_1 \\
\theta_2 \\
\vdots\\
\theta_B
\end{bmatrix}
\in\Theta. θ = θ 1 θ 2 ⋮ θ B ∈ Θ.
Here, Θ \Theta Θ denotes the constraint set, assumed to be a nonempty, compact and convex subset of ( 0 , ∞ ) B (0,\infty)^B ( 0 , ∞ ) B . As such, we assume that all parameters are positive. This naturally generalizes the case of linear resistors, where the parameters correspond to (positive) tunable conductances. The positivity of the parameters also plays an important role in viewing tunable resistive circuits as input-output models. Indeed, note that Assumption 1 implies that the co-content functions θ k G k ( ⋅ ) \theta_k G_k(\cdot) θ k G k ( ⋅ ) are differentiable, coercive, and strictly convex2 for all positive θ k \theta_k θ k . Therefore, Lemma 2 can be readily applied (with G k G_k G k replaced by θ k G k \theta_k G_k θ k G k ).
Remark 3. For notational convenience, we consider all resistors to be parameterized. However, within this framework, we can easily consider the situation in which a subset of resistors is adjustable and the remaining resistors are fixed. This can be done by defining B 1 , B 2 ∈ N B_1,B_2 \in\mathbb{N} B 1 , B 2 ∈ N such that B = B 1 + B 2 B=B_1+B_2 B = B 1 + B 2 , and taking
Θ : = Θ 1 × { 1 } B 2 , \Theta:= \Theta_1 \times\{1\}^{B_2}, Θ := Θ 1 × { 1 } B 2 ,
where Θ 1 ⊆ ( 0 , ∞ ) B 1 \Theta_1 \subseteq(0,\infty)^{B_1} Θ 1 ⊆ ( 0 , ∞ ) B 1 . A relevant setting is the combination of B 1 B_1 B 1 adjustable linear resistors, with parameters correspond to tunable conductances, and B 2 B_2 B 2 fixed nonlinear resistors, see also [27 ] .
With this in mind, we define the “parameterized” total co-content function G : Θ × R B → R G:\Theta\times\mathbb{R}^{B} \to\mathbb{R} G : Θ × R B → R as
G ( θ , v ) = ∑ k = 1 B θ k G k ( v k ) . (8) G(\theta,v)=\sum_{k=1}^{B}\theta_kG_k(v_k). \tag*{(8)} G ( θ , v ) = k = 1 ∑ B θ k G k ( v k ) . (8)
Let N I N_I N I , N H N_H N H and N O N_O N O denote the number of input, hidden and output nodes, respectively. Then we partition the vector of voltage potentials p ∈ R N p \in\mathbb{R}^{N} p ∈ R N , the vector of nodal currents j ∈ R N j \in\mathbb{R}^{N} j ∈ R N and the incidence matrix D ∈ R N × B D \in\mathbb{R}^{N\times B} D ∈ R N × B as
p = [ p I p H p O ] , j = [ j I j H j O ] , D = [ D I D H D O ] , p=\begin{bmatrix}p_I\\p_H\\p_O\end{bmatrix},\quad
j=\begin{bmatrix}j_I\\j_H\\j_O\end{bmatrix},\quad
D=\begin{bmatrix}D_I\\D_H\\D_O\end{bmatrix}, p = p I p H p O , j = j I j H j O , D = D I D H D O ,
where p I , j I ∈ R N I p_I,j_I \in\mathbb{R}^{N_I} p I , j I ∈ R N I , p H , j H ∈ R N H p_H,j_H \in\mathbb{R}^{N_H} p H , j H ∈ R N H , p O , j O ∈ R N O p_O,j_O \in\mathbb{R}^{N_O} p O , j O ∈ R N O and D I ∈ R N I × B D_I \in\mathbb{R}^{N_I\times B} D I ∈ R N I × B , D H ∈ R N H × B D_H \in\mathbb{R}^{N_H\times B} D H ∈ R N H × B and D O ∈ R N O × B D_O \in\mathbb{R}^{N_O\times B} D O ∈ R N O × B . By (4), the network model is now given by
\begin{bmatrix}j_I\\j_H\\j_O\end{bmatrix}
=
\begin{bmatrix}D_I\\D_H\\D_O\end{bmatrix}
\frac{\partial G}{\partial v}\left(\theta,D_I^\top p_I+D_H^\top p_H+D_O^\top p_O\right). \tag*{(9)}\end{bmatrix}
Setting the nodal current at the hidden and output nodes to zero, i.e., j H = 0 j_H=0 j H = 0 and j O = 0 j_O=0 j O = 0 , we have
0 = [ D H D O ] ∂ G ∂ v ( θ , D I ⊤ p I + D H ⊤ p H + D O ⊤ p O ) . (10) 0=
\begin{bmatrix}D_H\\D_O\end{bmatrix}
\frac{\partial G}{\partial v}\left(\theta,D_I^\top p_I+D_H^\top p_H+D_O^\top p_O\right). \tag*{(10)} 0 = [ D H D O ] ∂ v ∂ G ( θ , D I ⊤ p I + D H ⊤ p H + D O ⊤ p O ) . (10)
By Lemma 2, for every parameter vector θ ∈ Θ \theta\in\Theta θ ∈ Θ and every vector of input potentials p I ∈ R N I p_I \in\mathbb{R}^{N_I} p I ∈ R N I , there exists a unique pair of hidden and output potentials ( p H ( θ , p I ) , p O ( θ , p I ) ) ∈ R N H × R N O (p_H(\theta,p_I),p_O(\theta,p_I)) \in\mathbb{R}^{N_H}\times\mathbb{R}^{N_O} ( p H ( θ , p I ) , p O ( θ , p I )) ∈ R N H × R N O satisfying (10). Here, we stress the dependence of both p H p_H p H and p O p_O p O on θ \theta θ and p I p_I p I .
Now, suppose that we have input-output data in the form of a single, given pair of potentials
( p I d , p O d ) ∈ R N I × R N O . (11) (p_I^d,p_O^d)\in\mathbb{R}^{N_I}\times\mathbb{R}^{N_O}. \tag*{(11)} ( p I d , p O d ) ∈ R N I × R N O . (11)
The goal of learning is to fit the parameters to the training data, i.e., we want to compute a parameter vector θ ∗ ∈ Θ \theta^* \in\Theta θ ∗ ∈ Θ such that
p O ( θ ∗ , p I d ) ≈ p O d . (12) p_O(\theta^*,p_I^d)\approx p_O^d. \tag*{(12)} p O ( θ ∗ , p I d ) ≈ p O d . (12)
In other words, the objective is to find a parameter vector θ ∗ \theta^* θ ∗ that explains the data in the sense that the network approximately maps p I d p_I^d p I d to the target output p O d p_O^d p O d . For simplicity, throughout the paper we focus on a single pair of potentials (11). This is a simplification of a traditional machine learning setting, that generally assumes multiple samples 3
( p I d , j , p O d , j ) ∈ R N I × R N O (p_I^{d,j},p_O^{d,j})\in\mathbb{R}^{N_I}\times\mathbb{R}^{N_O} ( p I d , j , p O d , j ) ∈ R N I × R N O
for j = 1 , 2 , … , n j=1,2,\ldots,n j = 1 , 2 , … , n .
In this work, we study the problem of (12) through the lens of Target-Clamped Contrastive Learning (TCCL), but before delving into the learning framework (Section IV), we briefly review some fundamental concepts of machine learning and motivate the use of TCCL over Equilibrium Propagation in our setting.
In machine learning, training is usually formalized by introducing a cost function
C : R N O × R N O → R C:\mathbb{R}^{N_O}\times\mathbb{R}^{N_O}\to\mathbb{R} C : R N O × R N O → R
with the property that, for all y ∈ R N O y\in\mathbb{R}^{N_O} y ∈ R N O , C ( ⋅ , y ) C(\cdot,y) C ( ⋅ , y ) has a unique global minimizer, equal to y y y . The cost function C C C is often chosen to be convex. Examples include the squared error often used for regression tasks, or the categorical cross-entropy used for classification tasks. Given C C C , the objective function J : Θ → R J:\Theta\to\mathbb{R} J : Θ → R to be minimized with respect to θ \theta θ is the average of cost values over the dataset, i.e.,
J ( θ ) = 1 n ∑ j = 1 n C ( p O ( θ , p I d , j ) , p O d , j ) . (13) J(\theta)=\frac{1}{n}\sum_{j=1}^{n}C\left(p_{O}(\theta,p_{I}^{d,j}),p_{O}^{d,j}\right). \tag*{(13)} J ( θ ) = n 1 j = 1 ∑ n C ( p O ( θ , p I d , j ) , p O d , j ) . (13)
To achieve this, the gradient ∇ J ( θ ) \nabla J(\theta) ∇ J ( θ ) is usually computed using backpropagation, when applicable. However, in a resistive network, it is unclear how to physically realize backpropagation. For energy-based models like the resistive circuits studied here, alternative approaches have been developed in [3 , 17 , 25 , 27 ] , sometimes gathered under the umbrella name of energy-based learning [43 ] . The main thrust of these works is to replace digital computation of ∇ J ( θ ) \nabla J(\theta) ∇ J ( θ ) by learning rules based on local physical quantities , thus amenable to efficient implementation in electrical circuits. To achieve this, these algorithms typically compare two network states corresponding to two different boundary conditions. These algorithms either approximate ∇ J ( θ ) \nabla J(\theta) ∇ J ( θ ) [3 , 27 ] , compute the exact gradient of an alternative (contrastive) objective function [25 ] , or are based on other heuristics [17 ] .
In the context of resistive circuits, learning was first formalized using equilibrium propagation (EP) [27 ] , a training framework for energy-based models introduced in [42 ] . EP approximates ∇ J ( θ ) \nabla J(\theta) ∇ J ( θ ) by comparing the inference state (called free state ) and a nudged state in which outputs are nudged towards the data. EP requires choosing the nudging strength, and serves as a surrogate for the minimization of J J J .
Contrastive Learning with clamped outputs, which in this work we call Target-Clamped Contrastive learning (TCCL), is an alternative energy-based learning rule, which was originally formulated in Hopfield networks [35 ] and has recently been adapted to resistive circuits [25 ] . In TCCL, a clamped state , in which outputs are fully clamped to the data (targets), is considered in lieu of the nudged state. This no longer requires a cost function C C C and a nudging strength; instead, TCCL performs gradient descent on a contrastive function Q Q Q . Importantly, it was shown in [25 ] that the contrastive function is convex for linear resistive circuits without hidden nodes, which is not true for J J J (see Proposition 10 of the current paper). The convexity of Q Q Q implies that the TCCL algorithm of [25 ] always converges to a global minimum of the contrastive function.
The convexity of the contrastive function in the linear input-output case motivates the study of TCCL for more general resistive networks. The purpose of this paper is to generalize TCCL to nonlinear networks that also include hidden nodes. We will establish a rigorous mathematical framework that will reveal the cases in which i) the contrastive function is convex, and ii) TCCL converges to a global minimum of the contrastive function. In addition, we will study approximation properties of nonlinear resistive networks, showcasing the class of functions that can be approximated by these circuits.
The target-clamped contrastive learning framework
In this section, we generalize the contrastive learning framework of [25 ] to the setting of nonlinear resistive networks with input, hidden and output nodes. In § 4 .1, we will introduce a suitable energy function, and discuss the two energy levels of contrastive learning. In § 4 .2 we discuss smoothness properties of the voltage potentials arising in these two energy levels. Finally, in § 4 .3 we will introduce the contrastive function that will serve as an objective function.
The energy function
We define the “energy” function
E : Θ × R N I × R N H × R N O → R E:\Theta\times\mathbb{R}^{N_I}\times\mathbb{R}^{N_H}\times\mathbb{R}^{N_O}\to\mathbb{R} E : Θ × R N I × R N H × R N O → R
by
E ( θ , p I , p H , p O ) : = G ( θ , D I T p I + D H T p H + D O T p O ) . (14) E(\theta,p_I,p_H,p_O):=G\left(\theta,D_I^{\mathsf T}p_I+D_H^{\mathsf T}p_H+D_O^{\mathsf T}p_O\right). \tag*{(14)} E ( θ , p I , p H , p O ) := G ( θ , D I T p I + D H T p H + D O T p O ) . (14)
Note that the terminology “energy” is common in the literature on energy-based learning, for example, in the context of Hopfield networks [35 ] and Boltzmann machines [1 ] . Strictly speaking, however, such functions generally do not correspond to physical energy. In our setting, the function E E E is equal4 to the total co-content of all resistors in the circuit. In the case of linear resistors, E E E boils down to half the dissipated power in the resistors.
Now, consider the data ( p I d , p O d ) (p_I^d,p_O^d) ( p I d , p O d ) and a parameter vector θ ∈ Θ \theta\in\Theta θ ∈ Θ . As in other models where target-clamped contrastive learning has been employed [25 , 35 , 43 ] , we will consider two energy levels:
The free energy level E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ) ) E(\theta,p_I^d,p_H^*(\theta),p_O^*(\theta)) E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ )) . Here, ( p H ∗ ( θ ) , p O ∗ ( θ ) ) (p_H^*(\theta),p_O^*(\theta)) ( p H ∗ ( θ ) , p O ∗ ( θ )) is the pair of so-called free hidden and output potentials, defined as the unique minimizer of E E E for fixed p I d p_I^d p I d and given θ \theta θ , i.e.,
( p H ∗ ( θ ) , p O ∗ ( θ ) ) : = arg min ( x , y ) ∈ R N H × R N O E ( θ , p I d , x , y ) . (15) (p_H^*(\theta),p_O^*(\theta)) := \underset{(x,y)\in\mathbb{R}^{N_H}\times\mathbb{R}^{N_O}}{\arg\min}\ E(\theta,p_I^d,x,y). \tag*{(15)} ( p H ∗ ( θ ) , p O ∗ ( θ )) := ( x , y ) ∈ R N H × R N O arg min E ( θ , p I d , x , y ) . (15)
When the dependence on θ \theta θ is clear from the context, we will simply write p H ∗ p_H^* p H ∗ and p O ∗ p_O^* p O ∗ . Note that these free potentials satisfy
0 = [ ∂ E ∂ p H ( θ , p I d , p H ∗ , p O ∗ ) ∂ E ∂ p O ( θ , p I d , p H ∗ , p O ∗ ) ] , 0 =
\begin{bmatrix}
\frac{\partial E}{\partial p_H}(\theta,p_I^d,p_H^*,p_O^*)\\
\frac{\partial E}{\partial p_O}(\theta,p_I^d,p_H^*,p_O^*)
\end{bmatrix}, 0 = [ ∂ p H ∂ E ( θ , p I d , p H ∗ , p O ∗ ) ∂ p O ∂ E ( θ , p I d , p H ∗ , p O ∗ ) ] ,
and thus,
0 = [ D H D O ] ∂ G ∂ v ( θ , D I ⊤ p I d + D H ⊤ p H ∗ + D O ⊤ p O ∗ ) . 0 =
\begin{bmatrix}
D_H\\
D_O
\end{bmatrix}
\frac{\partial G}{\partial v}\left(\theta,D_I^\top p_I^d+D_H^\top p_H^*+D_O^\top p_O^*\right). 0 = [ D H D O ] ∂ v ∂ G ( θ , D I ⊤ p I d + D H ⊤ p H ∗ + D O ⊤ p O ∗ ) .
As such, p H ∗ p_H^* p H ∗ and p O ∗ p_O^* p O ∗ are precisely the hidden and output potentials arising from the network model (9) by setting j H = 0 j_H=0 j H = 0 , j O = 0 j_O=0 j O = 0 and p I = p I d p_I=p_I^d p I = p I d . In other words, in the notation of Section III, we have p H ∗ ( θ ) = p H ( θ , p I d ) p_H^*(\theta)=p_H(\theta,p_I^d) p H ∗ ( θ ) = p H ( θ , p I d ) and p O ∗ ( θ ) = p O ( θ , p I d ) p_O^*(\theta)=p_O(\theta,p_I^d) p O ∗ ( θ ) = p O ( θ , p I d ) . We recall that the existence and uniqueness of ( p H ∗ , p O ∗ ) (p_H^*,p_O^*) ( p H ∗ , p O ∗ ) follows from Lemma 2 by setting
p 1 = p I d and p 2 = [ p H ∗ p O ∗ ] . p_1=p_I^d
\qquad\text{and}\qquad
p_2=
\begin{bmatrix}
p_H^*\\
p_O^*
\end{bmatrix}. p 1 = p I d and p 2 = [ p H ∗ p O ∗ ] .
The clamped energy level E ( θ , p I d , p H c ( θ ) , p O d ) E(\theta,p_I^d,p_H^c(\theta),p_O^d) E ( θ , p I d , p H c ( θ ) , p O d ) , where both input and output potentials are fixed at the data points. Here, p H c ( θ ) ∈ R N H p_H^c(\theta)\in\mathbb{R}^{N_H} p H c ( θ ) ∈ R N H is the unique minimizer of E E E for fixed p I d p_I^d p I d and p O d p_O^d p O d and given θ \theta θ , i.e.,
p H c ( θ ) : = arg min x ∈ R N H E ( θ , p I d , x , p O d ) . (16) p_H^c(\theta):=\underset{x\in\mathbb{R}^{N_H}}{\arg\min}\ E(\theta,p_I^d,x,p_O^d). \tag*{(16)} p H c ( θ ) := x ∈ R N H arg min E ( θ , p I d , x , p O d ) . (16)
We will simply write p H c p_H^c p H c whenever the dependence on θ \theta θ is clear. Note that p H c p_H^c p H c satisfies
0 = ∂ E ∂ p H ( θ , p I d , p H c , p O d ) , 0=\frac{\partial E}{\partial p_H}(\theta,p_I^d,p_H^c,p_O^d), 0 = ∂ p H ∂ E ( θ , p I d , p H c , p O d ) ,
and thus
0 = D H ∂ G ∂ v ( θ , D I ⊤ p I d + D H ⊤ p H c + D O ⊤ p O d ) . 0=D_H\frac{\partial G}{\partial v}\left(\theta,D_I^\top p_I^d+D_H^\top p_H^c+D_O^\top p_O^d\right). 0 = D H ∂ v ∂ G ( θ , D I ⊤ p I d + D H ⊤ p H c + D O ⊤ p O d ) .
As such, p H c p_H^c p H c is precisely the vector of hidden potentials arising from the network model (9) by setting j H = 0 j_H=0 j H = 0 , p I = p I d p_I=p_I^d p I = p I d and p O = p O d p_O=p_O^d p O = p O d . Note that the existence and uniqueness of p H c p_H^c p H c again follows from Lemma 2.
On the smoothness of the clamped and free potentials
Due to the assumptions on the functions G k G_k G k , we can say more about the smoothness of the clamped and free potentials, as functions of θ \theta θ . This will become useful to derive properties of the contrastive function in Section IV.3. Specifically, by Assumption 1 the function ( θ , p H ) ↦ ∂ E ∂ p H ( θ , p I d , p H , p O d ) (\theta,p_H)\mapsto\frac{\partial E}{\partial p_H}(\theta,p_I^d,p_H,p_O^d) ( θ , p H ) ↦ ∂ p H ∂ E ( θ , p I d , p H , p O d ) is continuously differentiable. Furthermore, the matrix of second derivatives,
∂ 2 E ∂ p H ∂ p H ⊤ ( θ , p I d , p H , p O d ) , \frac{\partial^2 E}{\partial p_H\partial p_H^\top}(\theta,p_I^d,p_H,p_O^d), ∂ p H ∂ p H ⊤ ∂ 2 E ( θ , p I d , p H , p O d ) ,
is equal to
D H ∂ 2 G ∂ v ∂ v ⊤ ( θ , D I ⊤ p I d + D H ⊤ p H + D O ⊤ p O d ) D H ⊤ . D_H\frac{\partial^2G}{\partial v\partial v^\top}\left(\theta,D_I^\top p_I^d+D_H^\top p_H+D_O^\top p_O^d\right)D_H^\top. D H ∂ v ∂ v ⊤ ∂ 2 G ( θ , D I ⊤ p I d + D H ⊤ p H + D O ⊤ p O d ) D H ⊤ .
The latter matrix is positive definite for all θ ∈ Θ \theta\in\Theta θ ∈ Θ and p H ∈ R N H p_H\in\mathbb{R}^{N_H} p H ∈ R N H . Indeed, this follows from the facts that D H D_H D H has full row rank by connectedness of G \mathcal{G} G , and ∂ 2 G ∂ v ∂ v ⊤ ( θ , v ) \frac{\partial^2G}{\partial v\partial v^\top}(\theta,v) ∂ v ∂ v ⊤ ∂ 2 G ( θ , v ) is positive definite for all θ ∈ Θ \theta\in\Theta θ ∈ Θ and v ∈ R B v\in\mathbb{R}^{B} v ∈ R B by Assumption 1. Now, by the implicit function theorem [38 Thm. 9.28] , p H c ( θ ) p_H^c(\theta) p H c ( θ ) is continuously differentiable and its Jacobian ∂ p H c ∂ θ ⊤ ( θ ) \frac{\partial p_H^c}{\partial\theta^\top}(\theta) ∂ θ ⊤ ∂ p H c ( θ ) is given by
− ( D H ∂ 2 G ∂ v ∂ v ⊤ ( θ , v c ( θ ) ) D H ⊤ ) − 1 D H ∂ 2 G ∂ v ∂ θ ⊤ ( θ , v c ( θ ) ) , (17) -\left(D_H\frac{\partial^2G}{\partial v\partial v^\top}(\theta,v^c(\theta))D_H^\top\right)^{-1}
D_H\frac{\partial^2G}{\partial v\partial\theta^\top}(\theta,v^c(\theta)), \tag*{(17)} − ( D H ∂ v ∂ v ⊤ ∂ 2 G ( θ , v c ( θ )) D H ⊤ ) − 1 D H ∂ v ∂ θ ⊤ ∂ 2 G ( θ , v c ( θ )) , (17)
where
v c ( θ ) : = D ⊤ [ p I d p H c ( θ ) p O d ] . (18) v^c(\theta):=D^\top
\begin{bmatrix}
p_I^d\\
p_H^c(\theta)\\
p_O^d
\end{bmatrix}. \tag*{(18)} v c ( θ ) := D ⊤ p I d p H c ( θ ) p O d . (18)
Similarly, it can be shown that p H ∗ ( θ ) p_H^*(\theta) p H ∗ ( θ ) and p O ∗ ( θ ) p_O^*(\theta) p O ∗ ( θ ) are also continuously differentiable, and the Jacobian
[ ∂ p H ∗ ∂ θ ⊤ ( θ ) ∂ p O ∗ ∂ θ ⊤ ( θ ) ] \begin{bmatrix}
\frac{\partial p_H^*}{\partial\theta^\top}(\theta)\\
\frac{\partial p_O^*}{\partial\theta^\top}(\theta)
\end{bmatrix} [ ∂ θ ⊤ ∂ p H ∗ ( θ ) ∂ θ ⊤ ∂ p O ∗ ( θ ) ]
is given by
− ( D H O ∂ 2 G ∂ v ∂ v ⊤ ( θ , v ∗ ( θ ) ) D H O ⊤ ) − 1 D H O ∂ 2 G ∂ v ∂ θ ⊤ ( θ , v ∗ ( θ ) ) (19) -\left(D_{HO}\frac{\partial^2G}{\partial v\partial v^\top}(\theta,v^*(\theta))D_{HO}^\top\right)^{-1}
D_{HO}\frac{\partial^2G}{\partial v\partial\theta^\top}(\theta,v^*(\theta)) \tag*{(19)} − ( D H O ∂ v ∂ v ⊤ ∂ 2 G ( θ , v ∗ ( θ )) D H O ⊤ ) − 1 D H O ∂ v ∂ θ ⊤ ∂ 2 G ( θ , v ∗ ( θ )) (19)
where
D H O : = [ D H D O ] , v ∗ ( θ ) : = D ⊤ [ p I d p H ∗ ( θ ) p O ∗ ( θ ) ] . (20) D_{HO}:=
\begin{bmatrix}
D_H\\
D_O
\end{bmatrix},
\qquad
v^*(\theta):=D^\top
\begin{bmatrix}
p_I^d\\
p_H^*(\theta)\\
p_O^*(\theta)
\end{bmatrix}. \tag*{(20)} D H O := [ D H D O ] , v ∗ ( θ ) := D ⊤ p I d p H ∗ ( θ ) p O ∗ ( θ ) . (20)
Contrastive function and its properties
Now, we will define the contrastive function , that compares the free and clamped energy levels. In particular, given the data ( p I d , p O d ) (p_I^d,p_O^d) ( p I d , p O d ) , we define the function Q : Θ → R Q:\Theta\to\mathbb{R} Q : Θ → R as
Q ( θ ) : = E ( θ , p I d , p H c ( θ ) , p O d ) − E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ) ) . (21) Q(\theta):=E(\theta,p_I^d,p_H^c(\theta),p_O^d)-E(\theta,p_I^d,p_H^*(\theta),p_O^*(\theta)). \tag*{(21)} Q ( θ ) := E ( θ , p I d , p H c ( θ ) , p O d ) − E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ )) . (21)
The following theorem highlights some of the important features of the function Q Q Q .
Theorem 4. The function Q Q Q is continuously differentiable. Moreover, Q Q Q and its gradient ∇ Q \nabla Q ∇ Q satisfy:
i) Q ( θ ) ≥ 0 Q(\theta)\ge0 Q ( θ ) ≥ 0 for all θ ∈ Θ \theta\in\Theta θ ∈ Θ .
ii) Q ( θ d ) = 0 Q(\theta^d)=0 Q ( θ d ) = 0 if and only if θ d ∈ Θ \theta^d\in\Theta θ d ∈ Θ satisfies
p O ∗ ( θ d ) = p O d . (22) p_O^*(\theta^d)=p_O^d. \tag*{(22)} p O ∗ ( θ d ) = p O d . (22) iii) min θ ∈ Θ Q ( θ ) = 0 \min_{\theta\in\Theta}Q(\theta)=0 min θ ∈ Θ Q ( θ ) = 0 if and only if there exists θ d ∈ Θ \theta^d\in\Theta θ d ∈ Θ satisfying (22).
iv) for all k ∈ { 1 , 2 , … , B } k\in\{1,2,\ldots,B\} k ∈ { 1 , 2 , … , B } ,
( ∇ Q ( θ ) ) k = G k ( v k c ( θ ) ) − G k ( v k ∗ ( θ ) ) , (\nabla Q(\theta))_k=G_k(v_k^c(\theta))-G_k(v_k^*(\theta)), ( ∇ Q ( θ ) ) k = G k ( v k c ( θ )) − G k ( v k ∗ ( θ )) , where v c ( θ ) v^c(\theta) v c ( θ ) and v ∗ ( θ ) v^*(\theta) v ∗ ( θ ) are defined in (18) and (20), respectively.
v) Q ( θ ) = θ T ∇ Q ( θ ) Q(\theta)=\theta^\mathsf{T}\nabla Q(\theta) Q ( θ ) = θ T ∇ Q ( θ ) for all θ ∈ Θ \theta\in\Theta θ ∈ Θ .
vi) Q ( θ ) = 0 Q(\theta)=0 Q ( θ ) = 0 if and only if ∇ Q ( θ ) = 0 \nabla Q(\theta)=0 ∇ Q ( θ ) = 0 .
vii) Q ( λ θ ) = λ Q ( θ ) Q(\lambda\theta)=\lambda Q(\theta) Q ( λ θ ) = λ Q ( θ ) for all θ ∈ Θ \theta\in\Theta θ ∈ Θ and λ > 0 \lambda>0 λ > 0 such that λ θ ∈ Θ \lambda\theta\in\Theta λ θ ∈ Θ .
Before turning our attention to proofs, we first discuss some of the consequences of Theorem 4. By i), Q Q Q is nonnegative, while iii) demonstrates that the minimum of Q Q Q is zero if and only if there exists a θ d \theta^d θ d that interpolates the data exactly. In the latter case, by ii), the global minimizers of Q Q Q are precisely those parameter vectors that interpolate the data. Moreover, iv) shows that the gradient ∇ Q \nabla Q ∇ Q can be computed locally, because its k k k -th entry depends only on the local voltages v k c ( θ ) v_k^c(\theta) v k c ( θ ) and v k ∗ ( θ ) v_k^*(\theta) v k ∗ ( θ ) over branch k k k . This property, also shared by EP, ensures that contrastive learning can be implemented locally, as explored further in later sections of this paper. Properties v) and vi) show interesting relations between Q Q Q and ∇ Q \nabla Q ∇ Q . In particular, under the assumption that the data can be interpolated exactly, vi) and iii) show that θ ∗ ∈ Θ \theta^*\in\Theta θ ∗ ∈ Θ is a global minimizer of the constrained optimization problem min θ ∈ Θ Q ( θ ) \min_{\theta\in\Theta}Q(\theta) min θ ∈ Θ Q ( θ ) if and only if ∇ Q ( θ ∗ ) = 0 \nabla Q(\theta^*)=0 ∇ Q ( θ ∗ ) = 0 , i.e., the first-order necessary condition for optimality holds for the unconstrained optimization problem. Finally, vii) makes a connection to the concept of positive homogeneity . To elaborate on this, we recall the following definition of positive homogeneity, here adapted from [20 ] to functions defined on a domain C ⊆ R n C\subseteq\mathbb{R}^n C ⊆ R n .
Definition 5
Definition 5. Let k k k be a nonnegative integer and let C ⊆ R n C\subseteq\mathbb{R}^n C ⊆ R n . We call a function f : C → R f:C\to\mathbb{R} f : C → R positively homogeneous of degree k k k if f ( λ x ) = λ k f ( x ) f(\lambda x)=\lambda^k f(x) f ( λ x ) = λ k f ( x ) for all x ∈ C x\in C x ∈ C and λ > 0 \lambda>0 λ > 0 such that λ x ∈ C \lambda x\in C λ x ∈ C .
The interpretation of Theorem 4 vii) is thus that Q : Θ → R Q:\Theta\to\mathbb{R} Q : Θ → R is positively homogeneous5 of degree 1.
Next, we proceed with the proof of Theorem 4. To this end, we first establish a useful property of the voltage potentials p H ∗ p_H^* p H ∗ , p O ∗ p_O^* p O ∗ and p H c p_H^c p H c . In particular, the next lemma shows that these voltage potentials are positively homogeneous of degree 0 . In other words, they are invariant under parameter scaling.
Lemma 6. The voltage potentials p H ∗ : Θ → R N H p_H^*:\Theta\to\mathbb{R}^{N_H} p H ∗ : Θ → R N H , p O ∗ : Θ → R N O p_O^*:\Theta\to\mathbb{R}^{N_O} p O ∗ : Θ → R N O and p H c : Θ → R N H p_H^c:\Theta\to\mathbb{R}^{N_H} p H c : Θ → R N H , as defined in Section IV.1, are positively homogeneous of degree 0.
Proof. We only show the proof for p H ∗ p_H^* p H ∗ and p O ∗ p_O^* p O ∗ , as the proof for p H c p_H^c p H c is analogous. Let θ ∈ Θ \theta\in\Theta θ ∈ Θ and λ θ ∈ Θ \lambda\theta\in\Theta λ θ ∈ Θ for some scalar λ > 0 \lambda>0 λ > 0 . Since E E E in (14) is linear in its first argument, we have
( p H ∗ ( θ ) , p O ∗ ( θ ) ) = arg min ( x , y ) ∈ R N H × R N O λ E ( θ , p I d , x , y ) = arg min ( x , y ) ∈ R N H × R N O E ( λ θ , p I d , x , y ) = ( p H ∗ ( λ θ ) , p O ∗ ( λ θ ) ) . \begin{aligned}
(p_H^*(\theta),p_O^*(\theta))=
\underset{(x,y)\in\mathbb{R}^{N_H}\times\mathbb{R}^{N_O}}{\operatorname{arg\,min}}\ \lambda E(\theta,p_I^d,x,y) \\
&=
\underset{(x,y)\in\mathbb{R}^{N_H}\times\mathbb{R}^{N_O}}{\operatorname{arg\,min}}\ E(\lambda\theta,p_I^d,x,y) \\
&=(p_H^*(\lambda\theta),p_O^*(\lambda\theta)).
\end{aligned} ( p H ∗ ( θ ) , p O ∗ ( θ )) = ( x , y ) ∈ R N H × R N O arg min λ E ( θ , p I d , x , y ) = ( x , y ) ∈ R N H × R N O arg min E ( λ θ , p I d , x , y ) = ( p H ∗ ( λ θ ) , p O ∗ ( λ θ )) .
This proves the lemma. □
Proof of Theorem 4. Continuous differentiability of Q Q Q immediately follows from Assumption 1 and the continuous differentiability of p H c p_H^c p H c , p H ∗ p_H^* p H ∗ and p O ∗ p_O^* p O ∗ , as established in Section IV.2. Property i) follows by noting that the definitions of p H c p_H^c p H c , p H ∗ p_H^* p H ∗ and p O ∗ p_O^* p O ∗ imply that
E ( θ , p I d , p H c ( θ ) , p O d ) ≥ E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ) ) , E(\theta,p_I^d,p_H^c(\theta),p_O^d)\ge E(\theta,p_I^d,p_H^*(\theta),p_O^*(\theta)), E ( θ , p I d , p H c ( θ ) , p O d ) ≥ E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ )) ,
and thus, Q ( θ ) ≥ 0 Q(\theta) \ge0 Q ( θ ) ≥ 0 for all θ ∈ Θ \theta\in\Theta θ ∈ Θ .
We now prove Property ii). For the “if” part, assume that θ d ∈ Θ \theta^{d} \in\Theta θ d ∈ Θ satisfies (22). This implies that
E ( θ d , p I d , p H ∗ ( θ d ) , p O ∗ ( θ d ) ) = E ( θ d , p I d , p H ∗ ( θ d ) , p O d ) , E(\theta^{d},p_{I}^{d},p_{H}^{*}(\theta^{d}),p_{O}^{*}(\theta^{d}))=E(\theta^{d},p_{I}^{d},p_{H}^{*}(\theta^{d}),p_{O}^{d}), E ( θ d , p I d , p H ∗ ( θ d ) , p O ∗ ( θ d )) = E ( θ d , p I d , p H ∗ ( θ d ) , p O d ) ,
and, as such, p H ∗ ( θ d ) p_{H}^{*}(\theta^{d}) p H ∗ ( θ d ) is a minimizer of E ( θ d , p I d , ⋅ , p O d ) E(\theta^{d},p_{I}^{d},\cdot,p_{O}^{d}) E ( θ d , p I d , ⋅ , p O d ) . By Assumption 1 and connectedness of G \mathcal{G} G , E ( θ d , p I d , ⋅ , p O d ) E(\theta^{d},p_{I}^{d},\cdot,p_{O}^{d}) E ( θ d , p I d , ⋅ , p O d ) is continuous, coercive and strictly convex (see Lemma 2). By Proposition 25 (iv), E ( θ d , p I d , ⋅ , p O d ) E(\theta^{d},p_{I}^{d},\cdot,p_{O}^{d}) E ( θ d , p I d , ⋅ , p O d ) thus has precisely one global minimizer, showing that p H ∗ ( θ d ) = p H c ( θ d ) p_{H}^{*}(\theta^{d})=p_{H}^{c}(\theta^{d}) p H ∗ ( θ d ) = p H c ( θ d ) . Therefore, Q ( θ d ) = 0 Q(\theta^{d})=0 Q ( θ d ) = 0 .
To prove the “only if” part of Property ii), assume that Q ( θ d ) = 0 Q(\theta^{d})=0 Q ( θ d ) = 0 for some θ d ∈ Θ \theta^{d} \in\Theta θ d ∈ Θ . Then
E ( θ d , p I d , p H c ( θ d ) , p O d ) = E ( θ d , p I d , p H ∗ ( θ d ) , p O ∗ ( θ d ) ) . (23) E(\theta^{d},p_{I}^{d},p_{H}^{c}(\theta^{d}),p_{O}^{d})=E(\theta^{d},p_{I}^{d},p_{H}^{*}(\theta^{d}),p_{O}^{*}(\theta^{d})). \tag*{(23)} E ( θ d , p I d , p H c ( θ d ) , p O d ) = E ( θ d , p I d , p H ∗ ( θ d ) , p O ∗ ( θ d )) . (23)
By Lemma 2 and Proposition 25 (iv), E ( θ d , p I d , ⋅ , ⋅ ) E(\theta^{d},p_{I}^{d},\cdot,\cdot) E ( θ d , p I d , ⋅ , ⋅ ) has precisely one minimizer. This minimizer is given by ( p H ∗ ( θ d ) , p O ∗ ( θ d ) ) (p_{H}^{*}(\theta^{d}),p_{O}^{*}(\theta^{d})) ( p H ∗ ( θ d ) , p O ∗ ( θ d )) , and therefore, (23) implies that p O ∗ ( θ d ) = p O d p_{O}^{*}(\theta^{d})=p_{O}^{d} p O ∗ ( θ d ) = p O d .
Next, we prove Property iii). First, note that the minimum in iii) is well-defined by the extreme value theorem, as Q Q Q is continuous and Θ \Theta Θ is compact. The “if” statement directly follows from Properties i) and ii). Conversely, for the “only if” part, assume that min θ ∈ Θ Q ( θ ) = 0 \min_{\theta\in\Theta}Q(\theta)=0 min θ ∈ Θ Q ( θ ) = 0 . Then, there exists a θ d ∈ Θ \theta^{d} \in\Theta θ d ∈ Θ such that Q ( θ d ) = 0 Q(\theta^{d})=0 Q ( θ d ) = 0 . It then follows from Property ii) that θ d \theta^{d} θ d satisfies (22).
To prove Property iv), first note that p H c p_{H}^{c} p H c , p H ∗ p_{H}^{*} p H ∗ and p O ∗ p_{O}^{*} p O ∗ are differentiable by the discussion in Section IV.2. Then, by definition of Q Q Q , note that
∇ Q ( θ ) = ∂ E ∂ θ ( θ , p I d , p H c , p O d ) + ( ∂ p H c ∂ θ ( θ ) ) ⊤ ∂ E ∂ p H ( θ , p I d , p H c , p O d ) − ∂ E ∂ θ ( θ , p I d , p H ∗ , p O ∗ ) − ( ∂ p H ∗ ∂ θ ( θ ) ) ⊤ ∂ E ∂ p H ( θ , p I d , p H ∗ , p O ∗ ) − ( ∂ p O ∗ ∂ θ ( θ ) ) ⊤ ∂ E ∂ p O ( θ , p I d , p H ∗ , p O ∗ ) . \begin{aligned}
\nabla Q(\theta)={}&\frac{\partial E}{\partial\theta}(\theta,p_{I}^{d},p_{H}^{c},p_{O}^{d})\\
&+\left(\frac{\partial p_{H}^{c}}{\partial\theta}(\theta)\right)^{\top}\frac{\partial E}{\partial p_{H}}(\theta,p_{I}^{d},p_{H}^{c},p_{O}^{d})\\
&-\frac{\partial E}{\partial\theta}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*})\\
&-\left(\frac{\partial p_{H}^{*}}{\partial\theta}(\theta)\right)^{\top}\frac{\partial E}{\partial p_{H}}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*})\\
&-\left(\frac{\partial p_{O}^{*}}{\partial\theta}(\theta)\right)^{\top}\frac{\partial E}{\partial p_{O}}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*}).
\end{aligned} ∇ Q ( θ ) = ∂ θ ∂ E ( θ , p I d , p H c , p O d ) + ( ∂ θ ∂ p H c ( θ ) ) ⊤ ∂ p H ∂ E ( θ , p I d , p H c , p O d ) − ∂ θ ∂ E ( θ , p I d , p H ∗ , p O ∗ ) − ( ∂ θ ∂ p H ∗ ( θ ) ) ⊤ ∂ p H ∂ E ( θ , p I d , p H ∗ , p O ∗ ) − ( ∂ θ ∂ p O ∗ ( θ ) ) ⊤ ∂ p O ∂ E ( θ , p I d , p H ∗ , p O ∗ ) .
Next, since
∂ E ∂ p H ( θ , p I d , p H c , p O d ) = 0 , \frac{\partial E}{\partial p_{H}}(\theta,p_{I}^{d},p_{H}^{c},p_{O}^{d})=0, ∂ p H ∂ E ( θ , p I d , p H c , p O d ) = 0 ,
∂ E ∂ p H ( θ , p I d , p H ∗ , p O ∗ ) = 0 , \frac{\partial E}{\partial p_{H}}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*})=0, ∂ p H ∂ E ( θ , p I d , p H ∗ , p O ∗ ) = 0 ,
and
∂ E ∂ p O ( θ , p I d , p H ∗ , p O ∗ ) = 0 , \frac{\partial E}{\partial p_{O}}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*})=0, ∂ p O ∂ E ( θ , p I d , p H ∗ , p O ∗ ) = 0 ,
we see that
∇ Q ( θ ) = ∂ E ∂ θ ( θ , p I d , p H c , p O d ) − ∂ E ∂ θ ( θ , p I d , p H ∗ , p O ∗ ) . \nabla Q(\theta)=\frac{\partial E}{\partial\theta}(\theta,p_{I}^{d},p_{H}^{c},p_{O}^{d})-\frac{\partial E}{\partial\theta}(\theta,p_{I}^{d},p_{H}^{*},p_{O}^{*}). ∇ Q ( θ ) = ∂ θ ∂ E ( θ , p I d , p H c , p O d ) − ∂ θ ∂ E ( θ , p I d , p H ∗ , p O ∗ ) .
Now, Property iv) follows from the definitions of the energy function (14) and the total co-content (8).
To prove Property v), let θ ∈ Θ \theta\in\Theta θ ∈ Θ . Note that it follows from iv) that,
θ ⊤ ∇ Q ( θ ) = ∑ k = 1 B θ k G k ( v k c ( θ ) ) − ∑ k = 1 B θ k G k ( v k ∗ ( θ ) ) . \theta^{\top}\nabla Q(\theta)=\sum_{k=1}^{B}\theta_{k}G_{k}(v_{k}^{c}(\theta))-\sum_{k=1}^{B}\theta_{k}G_{k}(v_{k}^{*}(\theta)). θ ⊤ ∇ Q ( θ ) = k = 1 ∑ B θ k G k ( v k c ( θ )) − k = 1 ∑ B θ k G k ( v k ∗ ( θ )) .
Due to the definitions of G G G in (8), E E E in (14), and Q Q Q in (21), this is precisely equal to Q ( θ ) Q(\theta) Q ( θ ) .
To prove Property vi), note that the “if” statement follows directly from v). To show the “only if”, suppose that θ ∈ Θ \theta\in\Theta θ ∈ Θ is such that Q ( θ ) = 0 Q(\theta)=0 Q ( θ ) = 0 . By Property ii), p O ∗ ( θ ) = p O d p_{O}^{*}(\theta)=p_{O}^{d} p O ∗ ( θ ) = p O d . Since p H c ( θ ) p_{H}^{c}(\theta) p H c ( θ ) is the unique minimizer of E ( θ , p I d , ⋅ , p O d ) E(\theta,p_{I}^{d},\cdot,p_{O}^{d}) E ( θ , p I d , ⋅ , p O d ) , this also implies that p H c ( θ ) = p H ∗ ( θ ) p_{H}^{c}(\theta)=p_{H}^{*}(\theta) p H c ( θ ) = p H ∗ ( θ ) . As such, v c ( θ ) = v ∗ ( θ ) v^{c}(\theta)=v^{*}(\theta) v c ( θ ) = v ∗ ( θ ) . We conclude from Property iv) that ∇ Q ( θ ) = 0 \nabla Q(\theta)=0 ∇ Q ( θ ) = 0 .
Finally, to prove vii), let θ ∈ Θ \theta\in\Theta θ ∈ Θ and λ > 0 \lambda>0 λ > 0 be such that λ θ ∈ Θ \lambda\theta\in\Theta λ θ ∈ Θ . By (21), Q ( λ θ ) Q(\lambda\theta) Q ( λ θ ) is equal to
E ( λ θ , p I d , p H c ( λ θ ) , p O d ) − E ( λ θ , p I d , p H ∗ ( λ θ ) , p O ∗ ( λ θ ) ) , E(\lambda\theta,p_{I}^{d},p_{H}^{c}(\lambda\theta),p_{O}^{d})-E(\lambda\theta,p_{I}^{d},p_{H}^{*}(\lambda\theta),p_{O}^{*}(\lambda\theta)), E ( λ θ , p I d , p H c ( λ θ ) , p O d ) − E ( λ θ , p I d , p H ∗ ( λ θ ) , p O ∗ ( λ θ )) ,
which is equal to
E ( λ θ , p I d , p H c ( θ ) , p O d ) − E ( λ θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ) ) E(\lambda\theta,p_{I}^{d},p_{H}^{c}(\theta),p_{O}^{d})-E(\lambda\theta,p_{I}^{d},p_{H}^{*}(\theta),p_{O}^{*}(\theta)) E ( λ θ , p I d , p H c ( θ ) , p O d ) − E ( λ θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ))
due to Lemma 6. Finally, since E E E is linear in the first argument, the latter equals
λ E ( θ , p I d , p H c ( θ ) , p O d ) − λ E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ ) ) , \lambda E(\theta,p_{I}^{d},p_{H}^{c}(\theta),p_{O}^{d})-\lambda E(\theta,p_{I}^{d},p_{H}^{*}(\theta),p_{O}^{*}(\theta)), λ E ( θ , p I d , p H c ( θ ) , p O d ) − λ E ( θ , p I d , p H ∗ ( θ ) , p O ∗ ( θ )) ,
which equals λ Q ( θ ) \lambda Q(\theta) λ Q ( θ ) . This proves the theorem. □ \square □
Theorem 4 motivates, in a rigorous way, the minimization of the contrastive function Q Q Q . Indeed, Q Q Q is nonnegative and zero precisely at those parameter vectors that interpolate the data. The next sections of this paper are devoted to the analysis of a contrastive learning algorithm used to minimize Q Q Q . As announced before, Theorem 4 (iv) will become important to ensure the local nature of these algorithms.
In the next section, we will first study the convexity of the function Q Q Q .
On the Convexity of the Contrastive Function
This section is structured as follows. First, in Section V.1, we will show that Q Q Q is convex in the case that there are no hidden nodes (i.e., V H = ∅ \mathcal{V}_{H}=\varnothing V H = ∅ ).
Thereafter, in § 5 .2 we will demonstrate that the function J J J in (13) , that EP optimizes, is not convex even in the case with only input-output nodes. This shows an important advantage of using the contrastive function Q Q Q in lieu of J J J in the setting with input and output nodes only. Finally, in § 5 .3 we will demonstrate by means of an example that Q Q Q is generally not convex if the resistive circuit contains hidden nodes.
Convexity of Q Q Q without hidden nodes
In the case of no hidden nodes (V H = ∅ V_H = \varnothing V H = ∅ ), p H p_H p H is void and the energy function boils down to
E ( θ , p I , p O ) = G ( θ , D I T p I + D O T p O ) . (24) E(\theta,p_I,p_O)=G(\theta,D_I^{\mathsf{T}}p_I+D_O^{\mathsf{T}}p_O). \tag*{(24)} E ( θ , p I , p O ) = G ( θ , D I T p I + D O T p O ) . (24)
The free energy is now given by E ( θ , p I d , p O ∗ ( θ ) ) E(\theta,p_I^d,p_O^*(\theta)) E ( θ , p I d , p O ∗ ( θ )) , where p O ∗ ( θ ) p_O^*(\theta) p O ∗ ( θ ) is the unique minimizer of E ( θ , p I d , ⋅ ) E(\theta,p_I^d,\cdot) E ( θ , p I d , ⋅ ) . In turn, the clamped energy simply boils down to E ( θ , p I d , p O d ) E(\theta,p_I^d,p_O^d) E ( θ , p I d , p O d ) . Therefore, in this setting the contrastive function Q Q Q is given by
Q ( θ ) = E ( θ , p I d , p O d ) − E ( θ , p I d , p O ∗ ( θ ) ) . (25) Q(\theta)=E(\theta,p_I^d,p_O^d)-E(\theta,p_I^d,p_O^*(\theta)). \tag*{(25)} Q ( θ ) = E ( θ , p I d , p O d ) − E ( θ , p I d , p O ∗ ( θ )) . (25)
This allows us to establish the following convexity result in Theorem 7. Note that this is a generalization of [25 Lem. 5] to the nonlinear setting.
Theorem 7. If V H = ∅ V_H=\varnothing V H = ∅ , then Q Q Q is convex.
To prove Theorem 7, we first state the following lemma. This result is part of Danskin’s theorem [9 p. 173] , stated here without assuming compactness of Y \mathcal{Y} Y . For completeness, we include a short proof.
Lemma 8. Let X ⊆ R n \mathcal{X}\subseteq\mathbb{R}^n X ⊆ R n be convex and let Y ⊆ R m \mathcal{Y}\subseteq\mathbb{R}^m Y ⊆ R m . Consider f : X × Y → R f:\mathcal{X}\times\mathcal{Y}\to\mathbb{R} f : X × Y → R . If f ( ⋅ , y ) f(\cdot,y) f ( ⋅ , y ) is concave for all y ∈ Y y\in\mathcal{Y} y ∈ Y and f ( x , ⋅ ) f(x,\cdot) f ( x , ⋅ ) has a minimizer for all x ∈ X x\in\mathcal{X} x ∈ X , then the function g : X → R g:\mathcal{X}\to\mathbb{R} g : X → R , defined by
g ( x ) : = min y ∈ Y f ( x , y ) , g(x):=\min_{y\in\mathcal{Y}} f(x,y), g ( x ) := y ∈ Y min f ( x , y ) , is concave.
Proof. For every α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] and x 1 , x 2 ∈ X x_1,x_2\in\mathcal{X} x 1 , x 2 ∈ X ,
g ( α x 1 + ( 1 − α ) x 2 ) = min y ∈ Y f ( α x 1 + ( 1 − α ) x 2 , y ) ≥ min y ∈ Y ( α f ( x 1 , y ) + ( 1 − α ) f ( x 2 , y ) ) ≥ α min y ∈ Y f ( x 1 , y ) + ( 1 − α ) min y ∈ Y f ( x 2 , y ) = α g ( x 1 ) + ( 1 − α ) g ( x 2 ) , \begin{aligned}
g(\alpha x_1+(1-\alpha)x_2)&=\min_{y\in\mathcal{Y}}f(\alpha x_1+(1-\alpha)x_2,y)\\
&\geq\min_{y\in\mathcal{Y}}\bigl(\alpha f(x_1,y)+(1-\alpha)f(x_2,y)\bigr)\\
&\geq\alpha\min_{y\in\mathcal{Y}}f(x_1,y)+(1-\alpha)\min_{y\in\mathcal{Y}}f(x_2,y)\\
&=\alpha g(x_1)+(1-\alpha)g(x_2),
\end{aligned} g ( α x 1 + ( 1 − α ) x 2 ) = y ∈ Y min f ( α x 1 + ( 1 − α ) x 2 , y ) ≥ y ∈ Y min ( α f ( x 1 , y ) + ( 1 − α ) f ( x 2 , y ) ) ≥ α y ∈ Y min f ( x 1 , y ) + ( 1 − α ) y ∈ Y min f ( x 2 , y ) = α g ( x 1 ) + ( 1 − α ) g ( x 2 ) ,
where the first inequality follows from concavity of f ( ⋅ , y ) f(\cdot,y) f ( ⋅ , y ) . This proves the lemma.
Proof of Theorem 7. In view of the definitions of E E E in (24) and G G G in (8) , E ( θ , p I d , p O d ) E(\theta,p_I^d,p_O^d) E ( θ , p I d , p O d ) is linear, and thus convex, in θ \theta θ . The function E ( ⋅ , p I d , p O ) E(\cdot,p_I^d,p_O) E ( ⋅ , p I d , p O ) is linear, thus concave, for all p O ∈ R N O p_O\in\mathbb{R}^{N_O} p O ∈ R N O . Moreover, E ( θ , p I d , ⋅ ) E(\theta,p_I^d,\cdot) E ( θ , p I d , ⋅ ) has a (unique) minimizer for all θ ∈ Θ \theta\in\Theta θ ∈ Θ by Assumption 1. As such, by Lemma 8, the function
E ( θ , p I d , p O ∗ ( θ ) ) = min p O ∈ R N O E ( θ , p I d , p O ) E(\theta,p_I^d,p_O^*(\theta))=\min_{p_O\in\mathbb{R}^{N_O}}E(\theta,p_I^d,p_O) E ( θ , p I d , p O ∗ ( θ )) = p O ∈ R N O min E ( θ , p I d , p O )
is concave in θ \theta θ . Thus, − E ( θ , p I d , p O ∗ ( θ ) ) -E(\theta,p_I^d,p_O^*(\theta)) − E ( θ , p I d , p O ∗ ( θ )) is convex. We conclude from (25) that Q Q Q is convex. This proves the theorem.
Remark 9. We note that Assumption 1 is only used in the proof of Theorem 7 to show that E ( θ , p I d , ⋅ ) E(\theta,p_I^d,\cdot) E ( θ , p I d , ⋅ ) has a minimizer for all θ ∈ Θ \theta\in\Theta θ ∈ Θ . As such, Theorem 7 is valid even for (non-monotone) resistors with co-content functions G k G_k G k that do not satisfy the conditions of Assumption 1, provided that E ( θ , p I d , ⋅ ) E(\theta,p_I^d,\cdot) E ( θ , p I d , ⋅ ) still has a minimizer for all θ ∈ Θ \theta\in\Theta θ ∈ Θ . The proof of Theorem 7 carries over to this more general case without any changes.
Nonconvexity of J J J
In this section, we will show that the objective function J J J in (13) is, in general, not convex , even for resistive circuits with only input and output nodes. This is different from the contrastive function Q Q Q , which was shown to always be convex in the setting without hidden nodes (cf. Theorem 7).
We consider a twice continuously differentiable cost function C : R N O × R N O → R C:\mathbb{R}^{N_O}\times\mathbb{R}^{N_O}\to\mathbb{R} C : R N O × R N O → R , leading to the objective function J J J given by
J ( θ ) = C ( p O ∗ ( θ ) , p O d ) . (26) J(\theta)=C(p_O^*(\theta),p_O^d). \tag*{(26)} J ( θ ) = C ( p O ∗ ( θ ) , p O d ) . (26)
Here, we remind the reader that we consider a single data pair ( p I d , p O d ) (p_I^d,p_O^d) ( p I d , p O d ) , i.e., n = 1 n=1 n = 1 in (13) . In the following proposition, we will work under the assumption that Θ \Theta Θ has nonempty interior (implying that all resistors, including the nonlinear ones, are trainable). In this case, we will show that J J J can only be convex if it is constant.
Proposition 10. *Assume that Θ \Theta Θ has nonempty interior. Suppose that p O ∗ : Θ → R N O p_O^*:\Theta\to\mathbb{R}^{N_O} p O ∗ : Θ → R N O is twice continuously differentiable. Consider any twice continuously differentiable cost C : R N O × R N O → R C:\mathbb{R}^{N_O}\times\mathbb{R}^{N_O}\to\mathbb{R} C : R N O × R N O → R . Then, the objective function J : Θ → R J:\Theta\to\mathbb{R} J : Θ → R in (26) is convex if and only if it is constant on Θ \Theta Θ .
The proof of Proposition 10 relies on Lemma 6. In fact, we will use the property that p O ∗ p_O^* p O ∗ (and thus, J J J ) is positively homogeneous of degree 0.
Proof of Proposition 10. Since the “if” statement is obvious, we focus on proving the “only if” part. Assume that J J J is convex. Then, by the assumptions on C C C and p O ∗ p_O^* p O ∗ , the function J J J is twice continuously differentiable, and
∇ 2 J ( θ ) ≥ 0 \nabla^2 J(\theta) \ge0 ∇ 2 J ( θ ) ≥ 0
for all θ ∈ Θ \theta\in\Theta θ ∈ Θ . Now, let θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ be a point in the interior of Θ \Theta Θ . Then, there exists a sufficiently small ϵ > 0 \epsilon> 0 ϵ > 0 such that λ θ ∈ int Θ \lambda\theta\in\operatorname{int}\Theta λ θ ∈ int Θ for all λ ∈ ( 1 − ϵ , 1 + ϵ ) \lambda\in(1-\epsilon,1+\epsilon) λ ∈ ( 1 − ϵ , 1 + ϵ ) . By Lemma 6, p O ∗ ( θ ) = p O ∗ ( λ θ ) p_O^*(\theta)=p_O^*(\lambda\theta) p O ∗ ( θ ) = p O ∗ ( λ θ ) . By definition of J J J , this also implies that
J ( λ θ ) = J ( θ ) (27) J(\lambda\theta)=J(\theta) \tag*{(27)} J ( λ θ ) = J ( θ ) (27)
for all λ ∈ ( 1 − ϵ , 1 + ϵ ) \lambda\in(1-\epsilon,1+\epsilon) λ ∈ ( 1 − ϵ , 1 + ϵ ) . Differentiating (27) on both sides with respect to λ \lambda λ , and substituting λ = 1 \lambda=1 λ = 1 , yields
θ T ∇ J ( θ ) = 0. (28) \theta^{\mathsf{T}}\nabla J(\theta)=0. \tag*{(28)} θ T ∇ J ( θ ) = 0. (28)
Since θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ was arbitrary, the latter holds for all θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ . Now, we differentiate (28) with respect to θ \theta θ to obtain
∇ J ( θ ) + ∇ 2 J ( θ ) θ = 0 (29) \nabla J(\theta)+\nabla^2J(\theta)\theta=0 \tag*{(29)} ∇ J ( θ ) + ∇ 2 J ( θ ) θ = 0 (29)
for all θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ . Multiplying (29) from left by θ T \theta^{\mathsf{T}} θ T , and substituting (28), we get
θ T ∇ 2 J ( θ ) θ = 0 \theta^{\mathsf{T}}\nabla^2J(\theta)\theta=0 θ T ∇ 2 J ( θ ) θ = 0
for all θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ . Since ∇ 2 J ( θ ) \nabla^2J(\theta) ∇ 2 J ( θ ) is positive semidefinite, this yields ∇ 2 J ( θ ) θ = 0 \nabla^2J(\theta)\theta=0 ∇ 2 J ( θ ) θ = 0 , and therefore
∇ J ( θ ) = 0 \nabla J(\theta)=0 ∇ J ( θ ) = 0
for all θ ∈ int Θ \theta\in\operatorname{int}\Theta θ ∈ int Θ , by (29). As such, J J J is constant on int Θ \operatorname{int}\Theta int Θ . By continuity of J J J , the function is also constant on Θ \Theta Θ , proving the proposition. □
Under the assumption that Θ \Theta Θ has nonempty interior, Proposition 10 shows that any reasonable (non-constant) objective function J J J is not convex, even if the cost function C C C is convex. In case int Θ \operatorname{int}\Theta int Θ is empty (which happens for example if some resistors are fixed and untrainable), J J J may be convex or not, depending on the particular constraint set Θ \Theta Θ , the graph structure, co-content functions and the data. As mentioned before, Proposition 10 highlights an advantage of the contrastive function Q Q Q as objective in lieu of the objective J J J that Equilibrium Propagation optimizes.
Nonconvexity of Q Q Q in the general case
It is quite straightforward to demonstrate that Q Q Q is, in general, not convex in the presence of hidden nodes. In the following, we provide a concrete example.
Example 11. Consider the circuit with two input, two hidden, and two output nodes, given in Figure 1 . We assume all resistors are linear (so G k ( v k ) = 1 2 v k 2 G_k(v_k)=\frac{1}{2}v_k^2 G k ( v k ) = 2 1 v k 2 for k = 1 , 2 , … , 6 k=1,2,\ldots,6 k = 1 , 2 , … , 6 ), and consider the data
p I d = [ 1 − 3 ] , p O d = [ − 2.0968 − 2.3548 ] . p_I^d=\begin{bmatrix}1\\-3\end{bmatrix},\qquad p_O^d=\begin{bmatrix}-2.0968\\-2.3548\end{bmatrix}. p I d = [ 1 − 3 ] , p O d = [ − 2.0968 − 2.3548 ] . In this case, ∇ 2 Q ( 1 ) \nabla^2Q(1) ∇ 2 Q ( 1 ) has a negative eigenvalue, showing that Q Q Q is not convex.
Figure 1. Example of circuit with non-convex Q Q Q used in Example 11.
The target-clamped contrastive learning algorithm
In what follows, we will assume that
Θ = { x ∈ R B ∣ δ i ≤ x i ≤ ϵ i for all i = 1 , 2 , … , B } , (30) \Theta=\{x\in\mathbb{R}^{B}\mid\delta_i\le x_i\le\epsilon_i\text{ for all }i=1,2,\ldots,B\}, \tag*{(30)} Θ = { x ∈ R B ∣ δ i ≤ x i ≤ ϵ i for all i = 1 , 2 , … , B } , (30)
where δ i , ϵ i ∈ R \delta_i,\epsilon_i\in\mathbb{R} δ i , ϵ i ∈ R are given constants satisfying the inequalities 0 < δ i ≤ ϵ i 0<\delta_i\le\epsilon_i 0 < δ i ≤ ϵ i for all i = 1 , 2 , … , B i=1,2,\ldots,B i = 1 , 2 , … , B . The projection onto Θ \Theta Θ takes the form
( P Θ ( x ) ) k = { x k if δ k ≤ x k ≤ ϵ k δ k if x k < δ k ϵ k otherwise, (31) (P_{\Theta}(x))_k=
\begin{cases}
x_k & \text{if }\delta_k\le x_k\le\epsilon_k\\
\delta_k & \text{if }x_k<\delta_k\\
\epsilon_k & \text{otherwise,}
\end{cases} \tag*{(31)} ( P Θ ( x ) ) k = ⎩ ⎨ ⎧ x k δ k ϵ k if δ k ≤ x k ≤ ϵ k if x k < δ k otherwise, (31)
for all k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B . We now consider the following projected gradient descent algorithm:
θ 0 ∈ Θ and θ t + 1 = P Θ ( θ t − γ ∇ Q ( θ t ) ) for t ∈ N . (32) \theta^0\in\Theta\quad\text{and}\quad\theta^{t+1}=P_{\Theta}\left(\theta^t-\gamma\nabla Q(\theta^t)\right)\quad\text{for }t\in\mathbb{N}. \tag*{(32)} θ 0 ∈ Θ and θ t + 1 = P Θ ( θ t − γ ∇ Q ( θ t ) ) for t ∈ N . (32)
Here γ > 0 \gamma>0 γ > 0 is the to-be-determined stepsize of the algorithm. This algorithm was already studied in [25 ] for linear resistive circuits without hidden nodes.
Here we treat the nonlinear case, including hidden nodes. A key feature of (32) is that it is a contrastive learning algorithm that can be implemented locally due to Theorem 4 iv) and (31). Specifically, (32) boils down to θ k 0 ∈ [ δ k , ϵ k ] \theta_k^0 \in[\delta_k,\epsilon_k] θ k 0 ∈ [ δ k , ϵ k ] and
θ k t + 1 = P [ δ k , ϵ k ] ( θ k t − γ ( G k ( v k c ( θ t ) ) − G k ( v k ∗ ( θ t ) ) ) ) (33) \theta_k^{t+1}=P_{[\delta_k,\epsilon_k]}\left(\theta_k^t-\gamma\left(G_k\left(v_k^c(\theta^t)\right)-G_k\left(v_k^*(\theta^t)\right)\right)\right) \tag*{(33)} θ k t + 1 = P [ δ k , ϵ k ] ( θ k t − γ ( G k ( v k c ( θ t ) ) − G k ( v k ∗ ( θ t ) ) ) ) (33)
for t ∈ N t \in\mathbb{N} t ∈ N and k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B . Note that the update of the parameter θ k t \theta_k^t θ k t requires two (local) voltages v k c ( θ t ) v_k^c(\theta^t) v k c ( θ t ) and v k ∗ ( θ t ) v_k^*(\theta^t) v k ∗ ( θ t ) at branch k k k . At each step t t t , these voltages can be obtained by two different “experiments”. The first one clamps (i.e., fixes) the input and output potentials at p I d p_I^d p I d and p O d p_O^d p O d and takes j H = 0 j_H=0 j H = 0 , resulting in the clamped voltage v k c ( θ t ) v_k^c(\theta^t) v k c ( θ t ) . The second one only fixes the input potential p I d p_I^d p I d , and takes j H = 0 j_H=0 j H = 0 and j O = 0 j_O=0 j O = 0 , resulting in the free voltage v k ∗ ( θ t ) v_k^*(\theta^t) v k ∗ ( θ t ) at branch k k k . The algorithm is further illustrated in Figure 2 .
Figure 2. Illustration of the proposed target-clamped contrastive learning (TCCL) algorithm and its interaction with the circuit. To perform an update of the parameters at step t t t of the algorithm, we need two different “experiments”, resulting in the voltages v c ( θ t ) v^c(\theta^t) v c ( θ t ) and v ∗ ( θ t ) v^*(\theta^t) v ∗ ( θ t ) . In both experiments, the k k k -th entry of these voltages can be measured locally at branch k k k of the circuit, enabling the local update rule (33).
The expression (33) highlights an important feature of the contrastive learning rule, previously also discussed in the context of equilibrium propagation, see e.g. [41 Sec. II] . Specifically, the update rule for parameter θ k \theta_k θ k depends explicitly on the co-content function G k G_k G k at branch k k k . Its dependence on the other co-content functions in the network is only implicit, through the voltages v k c v_k^c v k c and v k ∗ v_k^* v k ∗ . This is especially relevant for networks with adjustable linear resistors and nonlinear fixed resistors, as also discussed in Remark 3. In this case, the update rule for each of the linear resistors takes the form
θ k t + 1 = P [ δ k , ϵ k ] ( θ k t − γ 2 ( ( v k c ( θ t ) ) 2 − ( v k ∗ ( θ t ) ) 2 ) ) \theta_k^{t+1}=P_{[\delta_k,\epsilon_k]}\left(\theta_k^t-\frac{\gamma}{2}\left(\left(v_k^c(\theta^t)\right)^2-\left(v_k^*(\theta^t)\right)^2\right)\right) θ k t + 1 = P [ δ k , ϵ k ] ( θ k t − 2 γ ( ( v k c ( θ t ) ) 2 − ( v k ∗ ( θ t ) ) 2 ) )
which does not depend on a model of the nonlinear resistors. This highlights a robustness property of contrastive learning: it is possible to implement exact projected gradient descent on the contrastive function, even with incomplete knowledge of the current-voltage characteristics of the nonlinear resistors.
In what follows, we will formally study the convergence of the contrastive learning algorithm (32). To do so, we will first provide conditions under which ∇ Q \nabla Q ∇ Q is Lipschitz continuous in § 6 .1. Thereafter, we will establish the convergence of contrastive learning without hidden nodes in § 6 .2, relying on the convexity result in Theorem 7 . In § 6 .3, we will establish a proof of convergence in the more challenging situation including hidden nodes.
Lipschitz continuity of ∇ Q \nabla Q ∇ Q
In this section, we will prove that ∇ Q \nabla Q ∇ Q is Lipschitz continuous, which will be used to establish convergence guarantees of the contrastive learning algorithm.
Proposition 12. The Hessian of Q Q Q satisfies
∇ 2 Q ( θ ) = [ d G 1 d v 1 ( v 1 c ( θ ) ) ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ d G B d v B ( v B c ( θ ) ) ] ∂ v c ∂ θ T ( θ ) − [ d G 1 d v 1 ( v 1 ∗ ( θ ) ) ⋯ 0 ⋮ ⋱ ⋮ 0 ⋯ d G B d v B ( v B ∗ ( θ ) ) ] ∂ v ∗ ∂ θ T ( θ ) . (34) \nabla^2 Q(\theta)=
\left[
\begin{array}{cccc}
\frac{dG_1}{dv_1}(v_1^c(\theta)) & \cdots& 0 \\
\vdots& \ddots& \vdots\\
0 & \cdots& \frac{dG_B}{dv_B}(v_B^c(\theta))
\end{array}
\right]\frac{\partial v^c}{\partial\theta^{\mathsf{T}}}(\theta)
-
\left[
\begin{array}{cccc}
\frac{dG_1}{dv_1}(v_1^*(\theta)) & \cdots& 0 \\
\vdots& \ddots& \vdots\\
0 & \cdots& \frac{dG_B}{dv_B}(v_B^*(\theta))
\end{array}
\right]\frac{\partial v^*}{\partial\theta^{\mathsf{T}}}(\theta). \tag*{(34)} ∇ 2 Q ( θ ) = d v 1 d G 1 ( v 1 c ( θ )) ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ d v B d G B ( v B c ( θ )) ∂ θ T ∂ v c ( θ ) − d v 1 d G 1 ( v 1 ∗ ( θ )) ⋮ 0 ⋯ ⋱ ⋯ 0 ⋮ d v B d G B ( v B ∗ ( θ )) ∂ θ T ∂ v ∗ ( θ ) . (34) Moreover, the function ∇ Q \nabla Q ∇ Q is Lipschitz continuous with constant
L : = max θ ∈ Θ ∥ ∇ 2 Q ( θ ) ∥ . (35) L:=\max_{\theta\in\Theta}\left\|\nabla^2Q(\theta)\right\|. \tag*{(35)} L := θ ∈ Θ max ∇ 2 Q ( θ ) . (35) Proof. We will first establish the formula for the Hessian of Q Q Q . Thereafter, the Lipschitz continuity of ∇ Q \nabla Q ∇ Q will follow by [29 Lem. 3.1] .
We first note that, due to Theorem 4 iv),
∂ ∂ θ j ( ∇ Q ( θ ) ) k = d G k d v k ( v k c ( θ ) ) ∂ v k c ∂ θ j ( θ ) − d G k d v k ( v k ∗ ( θ ) ) ∂ v k ∗ ∂ θ j ( θ ) , \frac{\partial}{\partial\theta_j}(\nabla Q(\theta))_k=\frac{dG_k}{dv_k}(v_k^c(\theta))\frac{\partial v_k^c}{\partial\theta_j}(\theta)-\frac{dG_k}{dv_k}(v_k^*(\theta))\frac{\partial v_k^*}{\partial\theta_j}(\theta), ∂ θ j ∂ ( ∇ Q ( θ ) ) k = d v k d G k ( v k c ( θ )) ∂ θ j ∂ v k c ( θ ) − d v k d G k ( v k ∗ ( θ )) ∂ θ j ∂ v k ∗ ( θ ) ,
for all k , j = 1 , 2 , … , B k,j=1,2,\ldots,B k , j = 1 , 2 , … , B . This means that the Hessian of Q Q Q takes the form (34). By Assumption 1, d G i d v i \frac{dG_i}{dv_i} d v i d G i is continuous for all i = 1 , 2 , … , B i=1,2,\ldots,B i = 1 , 2 , … , B . Moreover, due to the discussion in Section IV.2, v c v^c v c , v ∗ v^* v ∗ , ∂ v c ∂ θ ⊤ \frac{\partial v^c}{\partial\theta^\top} ∂ θ ⊤ ∂ v c and ∂ v ∗ ∂ θ ⊤ \frac{\partial v^*}{\partial\theta^\top} ∂ θ ⊤ ∂ v ∗ are continuous. As such, ∇ 2 Q \nabla^2Q ∇ 2 Q is also continuous. Obviously, Θ \Theta Θ is compact due to (30). Hence, by the extreme value theorem, the function ∥ ∇ 2 Q ( θ ) ∥ \lVert\nabla^2Q(\theta)\rVert ∥ ∇ 2 Q ( θ )∥ attains its supremum on Θ \Theta Θ . As such, L L L in (35) is well-defined. Finally, because ∥ ∇ 2 Q ( θ ) ∥ ≤ L \lVert\nabla^2Q(\theta)\rVert\le L ∥ ∇ 2 Q ( θ )∥ ≤ L for all θ ∈ Θ \theta\in\Theta θ ∈ Θ , we conclude by [29 Lem. 3.1] that ∇ Q \nabla Q ∇ Q is Lipschitz continuous with constant L L L . □
Remark 13. In the case of linear resistors, i.e., G k ( v k ) = 1 2 v k 2 G_k(v_k)=\frac{1}{2}v_k^2 G k ( v k ) = 2 1 v k 2 for all k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B , the formula for the Hessian of Q Q Q simplifies. Indeed, in this case, d G k d v k ( v k ) = v k \frac{dG_k}{dv_k}(v_k)=v_k d v k d G k ( v k ) = v k for all k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B , while
∂ 2 G ∂ v ∂ v ⊤ ( θ , v ) = diag ( θ ) , and ∂ 2 G ∂ v ∂ θ ⊤ ( θ , v ) = diag ( v ) . \frac{\partial^2G}{\partial v\partial v^\top}(\theta,v)=\operatorname{diag}(\theta),\qquad\text{and}\qquad\frac{\partial^2G}{\partial v\partial\theta^\top}(\theta,v)=\operatorname{diag}(v). ∂ v ∂ v ⊤ ∂ 2 G ( θ , v ) = diag ( θ ) , and ∂ v ∂ θ ⊤ ∂ 2 G ( θ , v ) = diag ( v ) .
Thus, by (17), (18), (19), and (20), the Hessian in (34) simplifies to
∇ 2 Q ( θ ) = diag ( v ∗ ( θ ) ) W H O ( θ ) diag ( v ∗ ( θ ) ) − diag ( v c ( θ ) ) W H diag ( v c ( θ ) ) , \nabla^2Q(\theta)=\operatorname{diag}(v^*(\theta))W_{HO}(\theta)\operatorname{diag}(v^*(\theta))-\operatorname{diag}(v^c(\theta))W_H\operatorname{diag}(v^c(\theta)), ∇ 2 Q ( θ ) = diag ( v ∗ ( θ )) W H O ( θ ) diag ( v ∗ ( θ )) − diag ( v c ( θ )) W H diag ( v c ( θ )) ,
where
W H O ( θ ) : = [ D H D O ] T ( [ D H D O ] diag ( θ ) [ D H D O ] T ) − 1 [ D H D O ] , W_{HO}(\theta):=\begin{bmatrix}D_H\\D_O\end{bmatrix}^{\mathsf T}\left(\begin{bmatrix}D_H\\D_O\end{bmatrix}\operatorname{diag}(\theta)\begin{bmatrix}D_H\\D_O\end{bmatrix}^{\mathsf T}\right)^{-1}\begin{bmatrix}D_H\\D_O\end{bmatrix}, W H O ( θ ) := [ D H D O ] T ( [ D H D O ] diag ( θ ) [ D H D O ] T ) − 1 [ D H D O ] ,
W H ( θ ) : = D H T ( D H diag ( θ ) D H T ) − 1 D H . W_H(\theta):=D_H^{\mathsf T}\left(D_H\operatorname{diag}(\theta)D_H^{\mathsf T}\right)^{-1}D_H. W H ( θ ) := D H T ( D H diag ( θ ) D H T ) − 1 D H .
In the simple case that there are no hidden nodes (V H = ∅ V_H=\varnothing V H = ∅ ), the matrix D H D_H D H is void and ∇ 2 Q ( θ ) \nabla^2Q(\theta) ∇ 2 Q ( θ ) equals
diag ( v ∗ ( θ ) ) D O T ( D O diag ( θ ) D O T ) − 1 D O diag ( v ∗ ( θ ) ) . \operatorname{diag}(v^*(\theta))D_O^{\mathsf T}\left(D_O\operatorname{diag}(\theta)D_O^{\mathsf T}\right)^{-1}D_O\operatorname{diag}(v^*(\theta)). diag ( v ∗ ( θ )) D O T ( D O diag ( θ ) D O T ) − 1 D O diag ( v ∗ ( θ )) .
Note that the latter matrix is positive semidefinite for all θ ∈ Θ \theta\in\Theta θ ∈ Θ . This recovers the argument in [25 ] , showing that Q Q Q is convex in the special case of linear circuits without hidden nodes, see [25 Lem. 5] .
Convergence of contrastive learning without hidden nodes
In this section, we will establish a basic convergence result for contrastive learning in the case that there are no hidden nodes (i.e., V H = ∅ V_H=\varnothing V H = ∅ ). For this, we will rely on the convexity result in Theorem 7 .
We first recall the following result from the literature, on the convergence of projected gradient descent.
Proposition 14. Let C ⊆ R n C\subseteq\mathbb{R}^n C ⊆ R n be a nonempty closed convex set, and let f : R n → R f:\mathbb{R}^n\to\mathbb{R} f : R n → R be differentiable and convex. Suppose that arg min x ∈ C f ( x ) ≠ ∅ \operatorname*{arg\,min}_{x\in C}f(x)\ne\varnothing arg min x ∈ C f ( x ) = ∅ and ∇ f \nabla f ∇ f is Lipschitz continuous with constant L L L . Consider the projected gradient descent algorithm
x 0 ∈ C , x t + 1 = P C ( x t − γ ∇ f ( x t ) ) for t ∈ N . x^0\in C,\qquad x^{t+1}=P_C\left(x^t-\gamma\nabla f(x^t)\right)\quad\text{for }t\in\mathbb{N}. x 0 ∈ C , x t + 1 = P C ( x t − γ ∇ f ( x t ) ) for t ∈ N . If γ ∈ ( 0 , 2 L ) \gamma\in\left(0,\frac{2}{L}\right) γ ∈ ( 0 , L 2 ) then
lim t → ∞ x t = x ∗ , \lim_{t\to\infty}x^t=x^*, t → ∞ lim x t = x ∗ , where x ∗ ∈ arg min x ∈ C f ( x ) x^*\in\operatorname*{arg\,min}_{x\in C}f(x) x ∗ ∈ arg min x ∈ C f ( x ) .
Proposition 14 is a classical result in convex optimization. Typically, this result is stated for the range of stepsizes ( 0 , 1 L ] \left(0,\frac{1}{L}\right] ( 0 , L 1 ] , see e.g. [6 Thm. 10.24] . One way of showing that projected gradient descent converges also for the larger interval of stepsizes ( 0 , 2 L ) \left(0,\frac{2}{L}\right) ( 0 , L 2 ) is to apply methods from monotone operator theory, in particular, the Krasnosel’skiĭ-Mann theorem, see e.g. [39 Thm. 1] and [39 p. 49] . For the sake of completeness, we have included a self-contained proof of Proposition 14 in Appendix C.
Based on Proposition 14 we now prove that the contrastive learning algorithm in (32) always converges to a global minimizer of the contrastive function, assuming there are no hidden nodes. This is the topic of the next theorem.
Theorem 15. Assume that V H = ∅ V_H=\varnothing V H = ∅ . Define L L L as in (35). Consider the contrastive learning algorithm in (32). If γ ∈ ( 0 , 2 L ) \gamma\in\left(0,\frac{2}{L}\right) γ ∈ ( 0 , L 2 ) , then, for every θ 0 ∈ Θ \theta^0\in\Theta θ 0 ∈ Θ ,
lim t → ∞ θ t = θ ∗ , \lim_{t\to\infty}\theta^t=\theta^*, t → ∞ lim θ t = θ ∗ , for some parameter vector θ ∗ ∈ arg min θ ∈ Θ Q ( θ ) \theta^*\in\operatorname*{arg\,min}_{\theta\in\Theta}Q(\theta) θ ∗ ∈ arg min θ ∈ Θ Q ( θ ) . Furthermore, if the data can be interpolated exactly, i.e., if (22) holds for some θ d ∈ Θ \theta^d\in\Theta θ d ∈ Θ , then also p O ∗ ( θ ∗ ) = p O d p_O^*(\theta^*)=p_O^d p O ∗ ( θ ∗ ) = p O d .
Proof. The set Θ \Theta Θ in (30) is nonempty, closed and convex. Moreover, the contrastive function Q Q Q is differentiable, and since V H = ∅ V_H=\varnothing V H = ∅ , convex by Theorem 7 . The function Q Q Q has at least one minimizer by the extreme value theorem, as Q Q Q is continuous and Θ \Theta Θ is compact. Moreover, the gradient ∇ Q \nabla Q ∇ Q is Lipschitz continuous with constant L L L given in (35), by Proposition 12. Therefore, Theorem 15 now follows from Proposition 14, and Theorem 4 iii) and ii). □
Convergence of contrastive learning with hidden nodes
In this section we study the convergence of target-clamped contrastive learning in the more general situation that V H ≠ ∅ \mathcal{V}_H \ne\varnothing V H = ∅ . As we have seen, in this situation the contrastive function is, in general, not convex. For non-convex optimization problems, some care has to be taken with the convergence of the iterates θ t \theta^t θ t , and their convergence does not follow from the convergence of Q ( θ t ) Q(\theta^t) Q ( θ t ) , in general [10 ] . The following theorem asserts that contrastive learning, applied to resistive circuits with hidden nodes, converges on a subsequence to a stationary point θ ∗ \theta^* θ ∗ of the constrained optimization problem min θ ∈ Θ Q ( θ ) \min_{\theta\in\Theta} Q(\theta) min θ ∈ Θ Q ( θ ) . Furthermore, interestingly, any such stationary points in the interior of Θ \Theta Θ are global minimizers of Q Q Q , and are such that p O ∗ ( θ ∗ ) = p O d p_O^*(\theta^*) = p_O^d p O ∗ ( θ ∗ ) = p O d .
Theorem 17. Define L L L as in (35). Consider the contrastive learning algorithm in (32). Let θ 0 ∈ Θ \theta^0 \in\Theta θ 0 ∈ Θ and γ ∈ ( 0 , 2 L ) \gamma\in(0,\frac{2}{L}) γ ∈ ( 0 , L 2 ) . Then lim t → ∞ Q ( θ t ) \lim_{t \to\infty} Q(\theta^t) lim t → ∞ Q ( θ t ) exists. Furthermore, the sequence ( θ t ) t = 0 ∞ (\theta^t)_{t=0}^{\infty} ( θ t ) t = 0 ∞ has a convergent subsequence with limit θ ∗ ∈ Θ \theta^* \in\Theta θ ∗ ∈ Θ satisfying
∇ Q ( θ ∗ ) T ( θ − θ ∗ ) ≥ 0 \nabla Q(\theta^*)^\mathsf{T}(\theta-\theta^*) \ge0 ∇ Q ( θ ∗ ) T ( θ − θ ∗ ) ≥ 0 for all θ ∈ Θ \theta\in\Theta θ ∈ Θ . If θ ∗ ∈ int Θ \theta^* \in\operatorname{int}\Theta θ ∗ ∈ int Θ then Q ( θ ∗ ) = 0 Q(\theta^*)=0 Q ( θ ∗ ) = 0 and we have that p O ∗ ( θ ∗ ) = p O d p_O^*(\theta^*)=p_O^d p O ∗ ( θ ∗ ) = p O d .
Proof. Let t ∈ N t \in\mathbb{N} t ∈ N . We start by applying Lemma 26 i) in Appendix B with C = Θ C=\Theta C = Θ , x = θ t − γ ∇ Q ( θ t ) x=\theta^t-\gamma\nabla Q(\theta^t) x = θ t − γ ∇ Q ( θ t ) and y = θ t y=\theta^t y = θ t , which yields
( θ t − γ ∇ Q ( θ t ) − θ t + 1 ) T ( θ t − θ t + 1 ) ≤ 0. (\theta^t-\gamma\nabla Q(\theta^t)-\theta^{t+1})^\mathsf{T}(\theta^t-\theta^{t+1}) \le0. ( θ t − γ ∇ Q ( θ t ) − θ t + 1 ) T ( θ t − θ t + 1 ) ≤ 0.
In other words,
( θ t + 1 − θ t ) T ∇ Q ( θ t ) ≤ − 1 γ ∥ θ t + 1 − θ t ∥ 2 . (36) (\theta^{t+1}-\theta^t)^\mathsf{T}\nabla Q(\theta^t) \le-\frac{1}{\gamma}\lVert\theta^{t+1}-\theta^t\rVert^2. \tag*{(36)} ( θ t + 1 − θ t ) T ∇ Q ( θ t ) ≤ − γ 1 ∥ θ t + 1 − θ t ∥ 2 . (36)
Now, since ∇ Q \nabla Q ∇ Q is Lipschitz continuous with constant L L L in (35), we obtain, by Lemma 24 in Appendix B,
Q ( θ t + 1 ) − Q ( θ t ) ≤ ( θ t + 1 − θ t ) T ∇ Q ( θ t ) + L 2 ∥ θ t + 1 − θ t ∥ 2 ≤ ( L 2 − 1 γ ) ∥ θ t + 1 − θ t ∥ 2 , (37) Q(\theta^{t+1})-Q(\theta^t) \le(\theta^{t+1}-\theta^t)^\mathsf{T}\nabla Q(\theta^t)+\frac{L}{2}\lVert\theta^{t+1}-\theta^t\rVert^2 \le\left(\frac{L}{2}-\frac{1}{\gamma}\right)\lVert\theta^{t+1}-\theta^t\rVert^2, \tag*{(37)} Q ( θ t + 1 ) − Q ( θ t ) ≤ ( θ t + 1 − θ t ) T ∇ Q ( θ t ) + 2 L ∥ θ t + 1 − θ t ∥ 2 ≤ ( 2 L − γ 1 ) ∥ θ t + 1 − θ t ∥ 2 , (37)
where the second inequality follows by (36). Since γ ∈ ( 0 , 2 L ) \gamma\in(0,\frac{2}{L}) γ ∈ ( 0 , L 2 ) , we have L 2 − 1 γ < 0 \frac{L}{2}-\frac{1}{\gamma}<0 2 L − γ 1 < 0 . As such, the sequence ( Q ( θ t ) ) t = 0 ∞ (Q(\theta^t))_{t=0}^{\infty} ( Q ( θ t ) ) t = 0 ∞ is nonincreasing. By Theorem 4 i), Q Q Q is nonnegative and thus bounded from below. Hence, by the monotone convergence theorem, lim t → ∞ Q ( θ t ) \lim_{t\to\infty}Q(\theta^t) lim t → ∞ Q ( θ t ) exists.
Next, since Θ \Theta Θ is compact by (30), it follows from the Bolzano-Weierstrass theorem that ( θ t ) t = 0 ∞ (\theta^t)_{t=0}^{\infty} ( θ t ) t = 0 ∞ has a convergent subsequence ( θ t j ) j = 0 ∞ (\theta^{t_j})_{j=0}^{\infty} ( θ t j ) j = 0 ∞ , where 0 ≤ t 0 < t 1 < ⋯ 0\le t_0<t_1<\cdots 0 ≤ t 0 < t 1 < ⋯ . Denote the limit of this subsequence by θ ∗ ∈ Θ \theta^*\in\Theta θ ∗ ∈ Θ . By (37), ∥ θ t + 1 − θ t ∥ → 0 \lVert\theta^{t+1}-\theta^t\rVert\to0 ∥ θ t + 1 − θ t ∥ → 0 as t → ∞ t\to\infty t → ∞ . Thus, θ t j + 1 → θ ∗ \theta^{t_j+1}\to\theta^* θ t j + 1 → θ ∗ as j → ∞ j\to\infty j → ∞ . Now, take the limit on both sides of
θ t j + 1 = P Θ ( θ t j − γ ∇ Q ( θ t j ) ) \theta^{t_j+1}=P_\Theta(\theta^{t_j}-\gamma\nabla Q(\theta^{t_j})) θ t j + 1 = P Θ ( θ t j − γ ∇ Q ( θ t j ))
as j → ∞ j\to\infty j → ∞ , and use continuity of both P Θ P_\Theta P Θ and ∇ Q \nabla Q ∇ Q to obtain
θ ∗ = P Θ ( θ ∗ − γ ∇ Q ( θ ∗ ) ) . \theta^*=P_\Theta(\theta^*-\gamma\nabla Q(\theta^*)). θ ∗ = P Θ ( θ ∗ − γ ∇ Q ( θ ∗ )) .
Now, by Lemma 26 i) in Appendix B,
∇ Q ( θ ∗ ) T ( θ − θ ∗ ) ≥ 0 (38) \nabla Q(\theta^*)^\mathsf{T}(\theta-\theta^*)\ge0 \tag*{(38)} ∇ Q ( θ ∗ ) T ( θ − θ ∗ ) ≥ 0 (38)
for all θ ∈ Θ \theta\in\Theta θ ∈ Θ , showing that θ ∗ \theta^* θ ∗ is indeed a stationary point.
Finally, suppose that θ ∗ ∈ int Θ \theta^*\in\operatorname{int}\Theta θ ∗ ∈ int Θ . Then, for sufficiently small ϵ > 0 \epsilon>0 ϵ > 0 ,
θ ∗ − ϵ ∇ Q ( θ ∗ ) ∈ Θ . \theta^*-\epsilon\nabla Q(\theta^*)\in\Theta. θ ∗ − ϵ ∇ Q ( θ ∗ ) ∈ Θ.
Due to (38),
− ϵ ∥ ∇ Q ( θ ∗ ) ∥ 2 ≥ 0 , -\epsilon\lVert\nabla Q(\theta^*)\rVert^2\ge0, − ϵ ∥ ∇ Q ( θ ∗ ) ∥ 2 ≥ 0 ,
meaning that ∇ Q ( θ ∗ ) = 0 \nabla Q(\theta^*)=0 ∇ Q ( θ ∗ ) = 0 . Now, by Theorem 4 vi), Q ( θ ∗ ) = 0 Q(\theta^*)=0 Q ( θ ∗ ) = 0 . Finally, by Theorem 4 ii), p O ∗ ( θ ∗ ) = p O d p_O^*(\theta^*)=p_O^d p O ∗ ( θ ∗ ) = p O d . This proves the theorem. □ \square □
By Theorem 17, any limit point of (32) in the interior of Θ \Theta Θ is a global minimizer of Q Q Q . Furthermore, any such point interpolates the data exactly. This also shows that the contrastive learning algorithm can only converge to interior points of Θ \Theta Θ if the data can be interpolated exactly, i.e. if there exists θ d \theta^d θ d such that (22) holds. If not, the algorithm always converges, subsequentially, to stationary points on the boundary of Θ \Theta Θ .
Computational expressivity of nonlinear resistive networks with monotone elements
Universal function approximation is a classical topic in the study of artificial neural networks, see e.g. [14 ] . So far, however, relatively few results have been obtained on the universal approximation capabilities of analog circuits [44 ] . In the context of this paper, it is therefore relevant to establish the class of functions that the considered nonlinear resistive circuits with monotone elements can approximate. To this end, we first introduce the setting.
We consider a class of resistive circuits with a fixed number of input and output nodes, but with varying number of branches and hidden nodes. Specifically, let N I , N O ∈ N N_I, N_O \in\mathbb{N} N I , N O ∈ N be fixed. We consider the class of resistive circuits defined by
(a) a connected, undirected graph G = ( V , E ) \mathcal{G} = (\mathcal{V}, \mathcal{E}) G = ( V , E ) , where V = V I ∪ V H ∪ V O \mathcal{V} = \mathcal{V}_I \cup\mathcal{V}_H \cup\mathcal{V}_O V = V I ∪ V H ∪ V O with V I , V H , V O \mathcal{V}_I, \mathcal{V}_H, \mathcal{V}_O V I , V H , V O mutually disjoint, and ∣ V I ∣ = N I |\mathcal{V}_I| = N_I ∣ V I ∣ = N I and ∣ V O ∣ = N O |\mathcal{V}_O| = N_O ∣ V O ∣ = N O .
(b) a set of co-content functions G k : R → R G_k : \mathbb{R} \to\mathbb{R} G k : R → R , where, for all k = 1 , 2 , … , ∣ E ∣ k = 1, 2, \ldots, |\mathcal{E}| k = 1 , 2 , … , ∣ E ∣ , G k G_k G k is
d 2 G k d v k 2 ( v k ) > 0 for all v k ∈ R . \frac{\mathrm{d}^2G_k}{\mathrm{d}v_k^2}(v_k) > 0 \text{ for all } v_k \in\mathbb{R}. d v k 2 d 2 G k ( v k ) > 0 for all v k ∈ R .
Consider any such graph G = ( V , E ) \mathcal{G} = (\mathcal{V}, \mathcal{E}) G = ( V , E ) and co-content functions G k G_k G k (k = 1 , 2 , … , ∣ E ∣ k = 1, 2, \ldots, |\mathcal{E}| k = 1 , 2 , … , ∣ E ∣ ). Define
G ( v ) = ∑ k = 1 ∣ E ∣ G k ( v k ) , G(v) = \sum_{k=1}^{|\mathcal{E}|} G_k(v_k), G ( v ) = k = 1 ∑ ∣ E ∣ G k ( v k ) ,
for v ∈ R ∣ E ∣ v \in\mathbb{R}^{|\mathcal{E}|} v ∈ R ∣ E ∣ , and let
D = [ D I D H D O ] D =
\begin{bmatrix}
D_I\\
D_H\\
D_O
\end{bmatrix} D = D I D H D O
be the incidence matrix of G \mathcal{G} G , where D ∈ R ∣ V ∣ × ∣ E ∣ D \in\mathbb{R}^{|\mathcal{V}|\times|\mathcal{E}|} D ∈ R ∣ V ∣ × ∣ E ∣ , D I ∈ R N I × ∣ E ∣ D_I \in\mathbb{R}^{N_I\times|\mathcal{E}|} D I ∈ R N I × ∣ E ∣ , D H ∈ R ∣ V H ∣ × ∣ E ∣ D_H \in\mathbb{R}^{|\mathcal{V}_H|\times|\mathcal{E}|} D H ∈ R ∣ V H ∣ × ∣ E ∣ and D O ∈ R N O × ∣ E ∣ D_O \in\mathbb{R}^{N_O\times|\mathcal{E}|} D O ∈ R N O × ∣ E ∣ .
We denote the input-output function of the circuit, mapping a vector of input potentials to its corresponding vector of output potentials, by F ( ⋅ ) F(\cdot) F ( ⋅ ) . In other words, F F F is the function such that, for all p I ∈ R N I p_I \in\mathbb{R}^{N_I} p I ∈ R N I ,
\begin{bmatrix}
D_H\\
D_O
\end{bmatrix}
\nabla G\left(D_I^{\top}p_I + D_H^{\top}p_H + D_O^{\top}F(p_I)\right) = 0 \tag*{(39)}\end{bmatrix}
for some vector of hidden potentials p H ∈ R ∣ V H ∣ p_H \in\mathbb{R}^{|\mathcal{V}_H|} p H ∈ R ∣ V H ∣ . Note that F F F is well-defined by Lemma 2.
Now, let
F N I , N O ⊆ ( R N O ) R N I \mathcal{F}_{N_I,N_O} \subseteq\left(\mathbb{R}^{N_O}\right)^{\mathbb{R}^{N_I}} F N I , N O ⊆ ( R N O ) R N I
denote the set of all functions from R N I \mathbb{R}^{N_I} R N I to R N O \mathbb{R}^{N_O} R N O that can be obtained this way, i.e., all input-output maps F F F corresponding to a circuit whose graph satisfies (a) and co-content functions satisfy (b).
The following lemma establishes two important properties of the functions F ∈ F N I , N O F \in\mathcal{F}_{N_I,N_O} F ∈ F N I , N O . Here, we will use the notation x ⪯ y x \preceq y x ⪯ y for two vectors x , y ∈ R n x, y \in\mathbb{R}^n x , y ∈ R n , indicating that x i ≤ y i x_i \le y_i x i ≤ y i for all i = 1 , 2 , … , n i = 1, 2, \ldots, n i = 1 , 2 , … , n .
Lemma 18. Let F ∈ F N I , N O F \in\mathcal{F}_{N_I,N_O} F ∈ F N I , N O . Then
i ) i) i ) for all x ∈ R N I x \in\mathbb{R}^{N_I} x ∈ R N I and α ∈ R \alpha\in\mathbb{R} α ∈ R ,
F ( x + α 1 ) = F ( x ) + α 1. F(x + \alpha\mathbf{1}) = F(x) + \alpha\mathbf{1}. F ( x + α 1 ) = F ( x ) + α 1 . i i ) ii) ii ) for all x , y ∈ R N I x, y \in\mathbb{R}^{N_I} x , y ∈ R N I ,
x ⪯ y ⟹ F ( x ) ⪯ F ( y ) . x \preceq y \Longrightarrow F(x) \preceq F(y). x ⪯ y ⟹ F ( x ) ⪯ F ( y ) .
The proof of Lemma 18 is given in Appendix D. Lemma 18 clearly demonstrates that the considered nonlinear resistive circuits are not universal approximators, in the sense that they cannot approximate any continuous function on a compact set up to an arbitrary precision. The physics of the circuit and the assumption of strictly monotone current-voltage characteristics (Assumption 1) impose the two important constraints i) and ii) that any input-output map F F F must exhibit. Property i) is related to the fact that adding the same constant to all potentials does not change the network voltages, while Property ii) expresses a form of monotonicity: if the inputs x x x and y y y are ordered as x ⪯ y x \preceq y x ⪯ y , then also the outputs satisfy F ( x ) ⪯ F ( y ) F(x) \preceq F(y) F ( x ) ⪯ F ( y ) .
Remark 19. The nonlinear resistive networks of [27 ] circumvent the monotonicity constraint imposed by Lemma 18 by employing a dual-rail representation – doubling input nodes and inverting one set of voltages. Alternatively, [44 ] implements this dual-rail representation using voltage-controlled voltage sources (VCVSs), and establish that these nonlinear resistive networks with monotone elements and VCVSs are universal function approximators.
In view of Lemma 18, a relevant question is whether nonlinear resistive circuits can approximate any continuous function that satisfies Properties i) and ii) . It turns out that the answer is affirmative, as made precise in the following theorem.
Theorem 20. For any ϵ > 0 \epsilon> 0 ϵ > 0 , compact set C ⊆ R N I \mathcal{C} \subseteq\mathbb{R}^{N_I} C ⊆ R N I and continuous function f : R N I → R N O f : \mathbb{R}^{N_I} \to\mathbb{R}^{N_O} f : R N I → R N O satisfying
f ( x + α 1 ) = f ( x ) + α 1 ∀ x ∈ R N I and α ∈ R ; f(x + \alpha\mathbf{1}) = f(x) + \alpha\mathbf{1}
\qquad\forall x \in\mathbb{R}^{N_I} \text{ and } \alpha\in\mathbb{R}; f ( x + α 1 ) = f ( x ) + α 1 ∀ x ∈ R N I and α ∈ R ; f ( x ) ⪯ f ( y ) ∀ x , y ∈ R N I s.t. x ⪯ y , f(x) \preceq f(y)
\qquad\forall x,y \in\mathbb{R}^{N_I} \text{ s.t. } x \preceq y, f ( x ) ⪯ f ( y ) ∀ x , y ∈ R N I s.t. x ⪯ y , there exists a function F ∈ F N I , N O F \in\mathcal{F}_{N_I,N_O} F ∈ F N I , N O satisfying
∥ f ( x ) − F ( x ) ∥ ≤ ϵ \lVert f(x) - F(x) \rVert\le\epsilon ∥ f ( x ) − F ( x )∥ ≤ ϵ for all x ∈ C x \in\mathcal{C} x ∈ C .
The remainder of this section is devoted to proving Theorem 20. The proof is technical, and will be split up in several parts. First, in Section VII.1, we will show how the problem can be reduced to the case with a single output, allowing us to focus on the proof of Theorem 20 for N O = 1 N_O=1 N O = 1 in the remainder. Thereafter, in Section VII.2 we will present a min-max approximation of f f f , inspired by results on min-max neural networks [33 , 46 ] approximating monotone functions. Such a min-max approximation, however, cannot be directly implemented by a resistive circuit. Therefore, in Section VII.3, we will show how to construct a circuit that implements a smooth approximation of the min-max function. As we will see, this requires a scaling of some of the circuit’s co-content functions.
Reduction to the single-output case
The purpose of this subsection is to show that it suffices to prove Theorem 20 for the case N O = 1 N_O=1 N O = 1 . We will do this by proving, in Lemma 21, that the output of a circuit composed of two subgraphs with the same set of input nodes is related to the outputs of the subcircuits. This will essentially allow us to consider the function approximation of each entry f i ( x ) f_i(x) f i ( x ) by a subcircuit, for every i = 1 , 2 , … , N O i=1,2,\ldots,N_O i = 1 , 2 , … , N O .
To facilitate the discussion, let G 1 = ( V 1 , E 1 ) \mathcal{G}_1=(\mathcal{V}_1,\mathcal{E}_1) G 1 = ( V 1 , E 1 ) and G 2 = ( V 2 , E 2 ) \mathcal{G}_2=(\mathcal{V}_2,\mathcal{E}_2) G 2 = ( V 2 , E 2 ) be two connected undirected graphs with the same set of input nodes, i.e.,
V i = V I ∪ V H i ∪ V O i , \mathcal{V}_i=\mathcal{V}_I\cup\mathcal{V}_{H_i}\cup\mathcal{V}_{O_i}, V i = V I ∪ V H i ∪ V O i ,
where V I \mathcal{V}_I V I , V H i \mathcal{V}_{H_i} V H i and V O i \mathcal{V}_{O_i} V O i are mutually disjoint for i = 1 , 2 i=1,2 i = 1 , 2 . Label the edges of G 1 \mathcal{G}_1 G 1 by 1 , 2 , … , ∣ E 1 ∣ 1,2,\ldots,|\mathcal{E}_1| 1 , 2 , … , ∣ E 1 ∣ and those of G 2 \mathcal{G}_2 G 2 by ∣ E 1 ∣ + 1 , ∣ E 1 ∣ + 2 , … , B |\mathcal{E}_1|+1,|\mathcal{E}_1|+2,\ldots,B ∣ E 1 ∣ + 1 , ∣ E 1 ∣ + 2 , … , B , where B : = ∣ E 1 ∣ + ∣ E 2 ∣ B:=|\mathcal{E}_1|+|\mathcal{E}_2| B := ∣ E 1 ∣ + ∣ E 2 ∣ . Let G k G_k G k be the co-content function satisfying the assumption in (b) for all k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B . Let F 1 ( ⋅ ) F^1(\cdot) F 1 ( ⋅ ) be the input-output map of the circuit defined by the graph G 1 \mathcal{G}_1 G 1 and the co-content functions G k G_k G k for k = 1 , 2 , … , ∣ E 1 ∣ k=1,2,\ldots,|\mathcal{E}_1| k = 1 , 2 , … , ∣ E 1 ∣ . Let F 2 ( ⋅ ) F^2(\cdot) F 2 ( ⋅ ) be the input-output map of the circuit defined by the graph G 2 \mathcal{G}_2 G 2 and the functions G k G_k G k for k = ∣ E 1 ∣ + 1 , ∣ E 1 ∣ + 2 , … , B k=|\mathcal{E}_1|+1,|\mathcal{E}_1|+2,\ldots,B k = ∣ E 1 ∣ + 1 , ∣ E 1 ∣ + 2 , … , B .
Now, define the new graph G = ( V , E ) \mathcal{G}=(\mathcal{V},\mathcal{E}) G = ( V , E ) by
V : = V I ∪ V H 1 ∪ V H 2 ∪ V O 1 ∪ V O 2 , and E = E 1 ∪ E 2 , \mathcal{V}:=\mathcal{V}_I\cup\mathcal{V}_{H_1}\cup\mathcal{V}_{H_2}\cup\mathcal{V}_{O_1}\cup\mathcal{V}_{O_2}, \quad\text{and} \quad\mathcal{E}=\mathcal{E}_1\cup\mathcal{E}_2, V := V I ∪ V H 1 ∪ V H 2 ∪ V O 1 ∪ V O 2 , and E = E 1 ∪ E 2 ,
and the total co-content
G ( v ) : = ∑ k = 1 B G k ( v k ) . G(v):=\sum_{k=1}^{B}G_k(v_k). G ( v ) := k = 1 ∑ B G k ( v k ) .
Finally, denote by F ( ⋅ ) F(\cdot) F ( ⋅ ) the input-output map of the circuit corresponding to the graph G \mathcal{G} G and functions G k G_k G k for k = 1 , 2 , … , B k=1,2,\ldots,B k = 1 , 2 , … , B . This leads to the following lemma.
Lemma 21. With F F F , F 1 F^1 F 1 and F 2 F^2 F 2 as above, we have that
F ( x ) = [ F 1 ( x ) F 2 ( x ) ] (40) F(x)=\begin{bmatrix}F^1(x)\\F^2(x)\end{bmatrix} \tag*{(40)} F ( x ) = [ F 1 ( x ) F 2 ( x ) ] (40) for all x ∈ R ∣ V I ∣ x\in\mathbb{R}^{|\mathcal{V}_I|} x ∈ R ∣ V I ∣ .
Proof. The incidence matrix D D D of G \mathcal{G} G takes the form
D = [ D I 1 D I 2 D H 1 1 0 0 D H 2 2 D O 1 1 0 0 D O 2 2 ] , (41) D=\begin{bmatrix}
D_I^1 & D_I^2\\
D_{H_1}^1 & 0\\
0 & D_{H_2}^2\\
\hdashline
D_{O_1}^1 & 0\\
0 & D_{O_2}^2
\end{bmatrix}, \tag*{(41)} D = D I 1 D H 1 1 0 D O 1 1 0 D I 2 0 D H 2 2 0 D O 2 2 , (41) where
[ D H 1 i D H 2 i D O i ] \begin{bmatrix}
D_{H_1}^i\\
D_{H_2}^i\\
D_{O_i}
\end{bmatrix} D H 1 i D H 2 i D O i is the incidence matrix of G i \mathcal{G}_i G i for i = 1 , 2 i=1,2 i = 1 , 2 . Let x ∈ R ∣ V I ∣ x\in\mathbb{R}^{|\mathcal{V}_I|} x ∈ R ∣ V I ∣ and partition
F ( x ) = [ F 1 ( x ) F 2 ( x ) ] , F(x)=\begin{bmatrix}F_1(x)\\F_2(x)\end{bmatrix}, F ( x ) = [ F 1 ( x ) F 2 ( x ) ] , where F i ( x ) ∈ R ∣ V O i ∣ F_i(x)\in\mathbb{R}^{|\mathcal{V}_{O_i}|} F i ( x ) ∈ R ∣ V O i ∣ for i = 1 , 2 i=1,2 i = 1 , 2 . Let p H 1 p_{H_1} p H 1 and p H 2 p_{H_2} p H 2 be such that
[ D H 1 1 0 0 D H 2 2 D O 1 1 0 0 D O 2 2 ] ∇ G ( D T [ x p H 1 p H 2 F 1 ( x ) F 2 ( x ) ] ) = 0. \begin{bmatrix}
D_{H_1}^1 & 0\\
0 & D_{H_2}^2\\
D_{O_1}^1 & 0\\
0 & D_{O_2}^2
\end{bmatrix}
\nabla G
\left(
D^\mathsf{T}
\begin{bmatrix}
x\\
p_{H_1}\\
p_{H_2}\\
F_1(x)\\
F_2(x)
\end{bmatrix}
\right)=0. D H 1 1 0 D O 1 1 0 0 D H 2 2 0 D O 2 2 ∇ G D T x p H 1 p H 2 F 1 ( x ) F 2 ( x ) = 0. Due to the fact that
∇ G ( v ) = [ d G 1 ( v 1 ) d v 1 ( v 1 ) d G 2 ( v 2 ) d v 2 ( v 2 ) ⋮ d G B ( v B ) d v B ( v B ) ] , \nabla G(v)=
\begin{bmatrix}
\frac{dG_1(v_1)}{dv_1}(v_1)\\
\frac{dG_2(v_2)}{dv_2}(v_2)\\
\vdots\\
\frac{dG_B(v_B)}{dv_B}(v_B)
\end{bmatrix}, ∇ G ( v ) = d v 1 d G 1 ( v 1 ) ( v 1 ) d v 2 d G 2 ( v 2 ) ( v 2 ) ⋮ d v B d G B ( v B ) ( v B ) , and the structure of the incidence matrix in (41), we obtain, for $i=1,2,
\begin{bmatrix}
D_{H_i}^i\\
D_{O_i}^i
\end{bmatrix}
\nabla G_i\left((D_I^i)^\mathsf{T}x+(D_{H_i}^i)^\mathsf{T}p_{H_i}+(D_{O_i}^i)^\mathsf{T}F_i(x)\right)=0, \tag*{(42)}\end{bmatrix}
where
G 1 ( v 1 ) : = ∑ k = 1 ∣ E 1 ∣ G k ( v k ) , G 2 ( v 2 ) : = ∑ k = ∣ E 1 ∣ + 1 B G k ( v k ) , G^{1}(v^{1}) := \sum_{k=1}^{|E_{1}|} G_{k}(v_{k}), \qquad G^{2}(v^{2}) := \sum_{k=|E_{1}|+1}^{B} G_{k}(v_{k}), G 1 ( v 1 ) := k = 1 ∑ ∣ E 1 ∣ G k ( v k ) , G 2 ( v 2 ) := k = ∣ E 1 ∣ + 1 ∑ B G k ( v k ) ,
while
v 1 : = [ v 1 v 2 ⋮ v ∣ E 1 ∣ ] , and v 2 : = [ v ∣ E 1 ∣ + 1 v ∣ E 1 ∣ + 2 ⋮ v B ] . v^{1} := \begin{bmatrix} v_{1} \\ v_{2} \\ \vdots\\ v_{|E_{1}|} \end{bmatrix}, \qquad\text{and} \qquad v^{2} := \begin{bmatrix} v_{|E_{1}|+1} \\ v_{|E_{1}|+2} \\ \vdots\\ v_{B} \end{bmatrix}. v 1 := v 1 v 2 ⋮ v ∣ E 1 ∣ , and v 2 := v ∣ E 1 ∣ + 1 v ∣ E 1 ∣ + 2 ⋮ v B .
Finally, note that (42) simply corresponds to the equation of the circuit defined on the graph G i G_{i} G i . Due to the uniqueness of the output potentials, we see that F i ( x ) = F i ( x ) F_{i}(x) = F^{i}(x) F i ( x ) = F i ( x ) for i = 1 , 2 i = 1,2 i = 1 , 2 , and thus, (40) holds.
Lemma 21 shows that it suffices to prove Theorem 20 for N O = 1 N_{O}=1 N O = 1 . Indeed, suppose that Theorem 20 holds for N O = 1 N_{O}=1 N O = 1 . Now, let f : R N I → R N O f:\mathbb{R}^{N_{I}}\to\mathbb{R}^{N_{O}} f : R N I → R N O satisfy the assumptions of Theorem 20 for some N O ∈ N N_{O}\in\mathbb{N} N O ∈ N . Then, for all i = 1 , 2 , … , N O i=1,2,\ldots,N_{O} i = 1 , 2 , … , N O , f i f_{i} f i is continuous, f i ( x + α 1 ) = f i ( x ) + α f_{i}(x+\alpha\mathbf{1})=f_{i}(x)+\alpha f i ( x + α 1 ) = f i ( x ) + α , and f i ( x ) ≤ f i ( y ) f_{i}(x)\leq f_{i}(y) f i ( x ) ≤ f i ( y ) for all x ∈ R N I x\in\mathbb{R}^{N_{I}} x ∈ R N I , α ∈ R \alpha\in\mathbb{R} α ∈ R and y ∈ R N I y\in\mathbb{R}^{N_{I}} y ∈ R N I satisfying x ⪯ y x\preceq y x ⪯ y . Let ϵ > 0 \epsilon>0 ϵ > 0 and let C ⊆ R N I C\subseteq\mathbb{R}^{N_{I}} C ⊆ R N I be compact. Then, applying Theorem 20 with N O = 1 N_{O}=1 N O = 1 , there exist resistive circuits with input-output maps F i ∈ F N I , 1 F^{i}\in\mathcal{F}_{N_{I},1} F i ∈ F N I , 1 such that
∣ f i ( x ) − F i ( x ) ∣ ≤ ϵ N O (43) |f_{i}(x)-F^{i}(x)|\leq\frac{\epsilon}{\sqrt{N_{O}}} \tag*{(43)} ∣ f i ( x ) − F i ( x ) ∣ ≤ N O ϵ (43)
for all i = 1 , 2 , … , N O i=1,2,\ldots,N_{O} i = 1 , 2 , … , N O . Repeated application of Lemma 21 shows the existence of a resistive circuit with input-output map F ∈ F N I , N O F\in\mathcal{F}_{N_{I},N_{O}} F ∈ F N I , N O satisfying
F ( x ) = [ F 1 ( x ) F 2 ( x ) ⋮ F N O ( x ) ] F(x)=\begin{bmatrix} F^{1}(x) \\ F^{2}(x) \\ \vdots\\ F^{N_{O}}(x) \end{bmatrix} F ( x ) = F 1 ( x ) F 2 ( x ) ⋮ F N O ( x )
for all x ∈ R N I x\in\mathbb{R}^{N_{I}} x ∈ R N I . By (43) , this shows that
∥ f ( x ) − F ( x ) ∥ ≤ N O ϵ 2 N O = ϵ , \lVert f(x)-F(x)\rVert\leq\sqrt{N_{O}\frac{\epsilon^{2}}{N_{O}}}=\epsilon, ∥ f ( x ) − F ( x )∥ ≤ N O N O ϵ 2 = ϵ ,
proving Theorem 20 for the general case N O ∈ N N_{O}\in\mathbb{N} N O ∈ N . Therefore, it remains to prove Theorem 20 for the case N O = 1 N_{O}=1 N O = 1 .
Min-max representation
The following lemma shows that all continuous functions satisfying the physical constraints can be approximated by certain min-max functions. For a positive integer n n n , we will use the shorthand notation [ n ] : = { 1 , … , n } [n]:=\{1,\ldots,n\} [ n ] := { 1 , … , n } .
Lemma 22. Let ϵ > 0 \epsilon>0 ϵ > 0 and let C ⊆ R N I C\subseteq\mathbb{R}^{N_{I}} C ⊆ R N I be compact. Consider a continuous function f : R N I → R f:\mathbb{R}^{N_{I}}\to\mathbb{R} f : R N I → R satisfying
f ( x + α 1 ) = f ( x ) + α (44) f(x+\alpha\mathbf{1})=f(x)+\alpha \tag*{(44)} f ( x + α 1 ) = f ( x ) + α (44) f ( x ) ≤ f ( y ) , (45) f(x)\leq f(y), \tag*{(45)} f ( x ) ≤ f ( y ) , (45) for all α ∈ R \alpha\in\mathbb{R} α ∈ R and x , y ∈ R N I x,y\in\mathbb{R}^{N_{I}} x , y ∈ R N I such that x ⪯ y x\preceq y x ⪯ y . There exists a finite subset A ⊆ C A\subseteq C A ⊆ C such that the function f A : R N I → R f_{A}:\mathbb{R}^{N_{I}}\to\mathbb{R} f A : R N I → R , defined by
f A ( x ) : = min a ∈ A ( f ( a ) + max i ∈ [ N I ] ( x i − a i ) ) , f_{A}(x):=\min_{a\in A}\left(f(a)+\max_{i\in[N_{I}]}(x_{i}-a_{i})\right), f A ( x ) := a ∈ A min ( f ( a ) + i ∈ [ N I ] max ( x i − a i ) ) , satisfies
∣ f ( x ) − f A ( x ) ∣ ≤ ϵ |f(x)-f_{A}(x)|\leq\epsilon ∣ f ( x ) − f A ( x ) ∣ ≤ ϵ for all $x\in C.
Proof. Since C C C is compact, there exists a finite subset A ⊆ C A\subseteq C A ⊆ C such that, for all x ∈ C x\in C x ∈ C ,
∥ x − a ∥ ∞ ≤ ϵ 2 (46) \lVert x-a\rVert_{\infty}\leq\frac{\epsilon}{2} \tag*{(46)} ∥ x − a ∥ ∞ ≤ 2 ϵ (46)
for some $a\in A.
Now, let x ∈ C x\in C x ∈ C . Then
x ⪯ a + ( max i ∈ [ N I ] ( x i − a i ) ) 1 x\preceq a+\left(\max_{i\in[N_{I}]}(x_{i}-a_{i})\right)\mathbf{1} x ⪯ a + ( i ∈ [ N I ] max ( x i − a i ) ) 1
for all a ∈ A a\in A a ∈ A , and thus,
f ( x ) ≤ f ( a + ( max i ∈ [ N I ] ( x i − a i ) ) 1 ) f(x)\leq f\left(a+\left(\max_{i\in[N_{I}]}(x_{i}-a_{i})\right)\mathbf{1}\right) f ( x ) ≤ f ( a + ( i ∈ [ N I ] max ( x i − a i ) ) 1 )
for all $a\in A, due to (45) . Using (44) , we see that
f ( x ) ≤ f ( a ) + max i ∈ [ N I ] ( x i − a i ) . f(x)\leq f(a)+\max_{i\in[N_{I}]}(x_{i}-a_{i}). f ( x ) ≤ f ( a ) + i ∈ [ N I ] max ( x i − a i ) .
Since this inequality holds for all $a\in A, we conclude that f ( x ) ≤ f A ( x ) f(x)\leq f_{A}(x) f ( x ) ≤ f A ( x ) .
Next, fix an a ∈ A a\in A a ∈ A satisfying (46) . Then,
a − ϵ 2 1 ⪯ x a-\frac{\epsilon}{2}\mathbf{1}\preceq x a − 2 ϵ 1 ⪯ x
and thus,
f ( a ) − ϵ 2 ≤ f ( x ) . (47) f(a)-\frac{\epsilon}{2}\leq f(x). \tag*{(47)} f ( a ) − 2 ϵ ≤ f ( x ) . (47)
Due to the definition of f A f_A f A , we have that
f A ( x ) ≤ f ( a ) + max i ∈ [ N I ] ( x i − a i ) ≤ f ( a ) + ϵ 2 ≤ f ( x ) + ϵ , f_A(x) \le f(a) + \max_{i\in[N_I]}(x_i-a_i)
\le f(a) + \frac{\epsilon}{2}
\le f(x) + \epsilon, f A ( x ) ≤ f ( a ) + i ∈ [ N I ] max ( x i − a i ) ≤ f ( a ) + 2 ϵ ≤ f ( x ) + ϵ ,
where the last inequality follows from (47) . We conclude that 0 ≤ f A ( x ) − f ( x ) ≤ ϵ 0 \le f_A(x)-f(x) \le\epsilon 0 ≤ f A ( x ) − f ( x ) ≤ ϵ , and therefore, ∣ f A ( x ) − f ( x ) ∣ ≤ ϵ |f_A(x)-f(x)| \le\epsilon ∣ f A ( x ) − f ( x ) ∣ ≤ ϵ . This proves the lemma.
Circuit approximation of min-max and proof of Theorem 20
In view of Lemma 22, the idea is now to build a circuit that approximates the function f A ( x ) f_A(x) f A ( x ) . To do so, we will make use of smooth approximations of the max and min functions. For λ > 0 \lambda> 0 λ > 0 and x ∈ R n x \in\mathbb{R}^n x ∈ R n , we define
smax λ ( x ) : = 1 λ ln ( 1 n ∑ i = 1 n e λ x i ) , and \operatorname{smax}_{\lambda}(x) := \frac{1}{\lambda}\ln\left(\frac{1}{n}\sum_{i=1}^{n}e^{\lambda x_i}\right),
\quad\text{and} smax λ ( x ) := λ 1 ln ( n 1 i = 1 ∑ n e λ x i ) , and
smin λ ( x ) : = − 1 λ ln ( 1 n ∑ i = 1 n e − λ x i ) . \operatorname{smin}_{\lambda}(x) := -\frac{1}{\lambda}\ln\left(\frac{1}{n}\sum_{i=1}^{n}e^{-\lambda x_i}\right). smin λ ( x ) := − λ 1 ln ( n 1 i = 1 ∑ n e − λ x i ) .
These functions are scaled versions of the Log-SumExp function, commonly encountered in machine learning applications, see especially the relevant work [26 ] . The following basic lemma clarifies in which sense these functions are approximations of max and min. The lemma also asserts that a property of the max and min functions is carried over to smax λ \operatorname{smax}_{\lambda} smax λ and smin λ \operatorname{smin}_{\lambda} smin λ , respectively. More specifically, the max and min functions can be shown to be nonexpansive with respect to the ∞ \infty ∞ -norm, which also holds true for smax λ \operatorname{smax}_{\lambda} smax λ and smin λ \operatorname{smin}_{\lambda} smin λ .
Lemma 23. For any λ > 0 \lambda> 0 λ > 0 and x ∈ R n x \in\mathbb{R}^n x ∈ R n , we have that
∣ smax λ ( x ) − max i ∈ [ n ] x i ∣ ≤ ln ( n ) λ , and \left|\operatorname{smax}_{\lambda}(x)-\max_{i\in[n]}x_i\right| \le\frac{\ln(n)}{\lambda},
\quad\text{and} smax λ ( x ) − i ∈ [ n ] max x i ≤ λ ln ( n ) , and ∣ smin λ ( x ) − min i ∈ [ n ] x i ∣ ≤ ln ( n ) λ . \left|\operatorname{smin}_{\lambda}(x)-\min_{i\in[n]}x_i\right| \le\frac{\ln(n)}{\lambda}. smin λ ( x ) − i ∈ [ n ] min x i ≤ λ ln ( n ) . Furthermore, both smax λ \operatorname{smax}_{\lambda} smax λ and smin λ \operatorname{smin}_{\lambda} smin λ are nonexpansive with respect to the ∞ \infty ∞ -norm, that is,
∣ smax λ ( x ) − smax λ ( y ) ∣ ≤ ∥ x − y ∥ ∞ (48) \left|\operatorname{smax}_{\lambda}(x)-\operatorname{smax}_{\lambda}(y)\right| \le\lVert x-y\rVert_{\infty} \tag*{(48)} ∣ smax λ ( x ) − smax λ ( y ) ∣ ≤ ∥ x − y ∥ ∞ (48) ∣ smin λ ( x ) − smin λ ( y ) ∣ ≤ ∥ x − y ∥ ∞ , (49) \left|\operatorname{smin}_{\lambda}(x)-\operatorname{smin}_{\lambda}(y)\right| \le\lVert x-y\rVert_{\infty}, \tag*{(49)} ∣ smin λ ( x ) − smin λ ( y ) ∣ ≤ ∥ x − y ∥ ∞ , (49) for all x , y ∈ R n x,y \in\mathbb{R}^n x , y ∈ R n .
The proof of Lemma 23 is given in Appendix E.
We are now in a position to prove Theorem 20. Roughly speaking, the idea is as follows: we will construct a circuit with one layer of input nodes, one layer of hidden nodes and one output node. The purpose of the potentials of the hidden nodes is to approximate the “inner” maximum defining f A f_A f A , while the output potential approximates the “outer” minimum in the definition of f A f_A f A . A technical challenge, addressed in the proof of Theorem 20, is that the hidden potentials cannot compute the smooth approximation smax λ \operatorname{smax}_{\lambda} smax λ of the max-function exactly, due to the presence of branches between hidden nodes and the output node. As we will see, this is overcome by a suitable scaling of some of the co-content functions in the network.
Proof of Theorem 20. As shown in § 7 .1, it suffices to prove the result for N O = 1 N_O=1 N O = 1 . Let ϵ > 0 \epsilon> 0 ϵ > 0 , C ⊆ R N I C \subseteq\mathbb{R}^{N_I} C ⊆ R N I be compact, and let f : R N I → R f:\mathbb{R}^{N_I}\to\mathbb{R} f : R N I → R be a function satisfying the assumptions of Theorem 20. By Lemma 22, there exists a finite subset A ⊆ C A \subseteq C A ⊆ C such that
∣ f ( x ) − f A ( x ) ∣ ≤ ϵ 3 (50) |f(x)-f_A(x)| \le\frac{\epsilon}{3} \tag*{(50)} ∣ f ( x ) − f A ( x ) ∣ ≤ 3 ϵ (50)
for all x ∈ C x\in C x ∈ C . Let q : = ∣ A ∣ q:=|A| q := ∣ A ∣ and denote by a 1 , a 2 , … , a q a^1,a^2,\ldots,a^q a 1 , a 2 , … , a q the elements of A A A . Let λ > 0 \lambda>0 λ > 0 , whose precise value will be determined later, and define z ˉ : R N I → R q \bar{z}:\mathbb{R}^{N_I}\to\mathbb{R}^q z ˉ : R N I → R q elementwise by
z ˉ j ( x ) : = smax λ ( f ( a j ) 1 + x − a j ) , (51) \bar{z}_j(x):=\operatorname{smax}_{\lambda}\left(f(a^j)\mathbb{1}+x-a^j\right), \tag*{(51)} z ˉ j ( x ) := smax λ ( f ( a j ) 1 + x − a j ) , (51)
for x ∈ C x\in C x ∈ C and j ∈ [ q ] j\in[q] j ∈ [ q ] . Also define
y ˉ ( x ) : = smin λ ( z ˉ ( x ) ) \bar{y}(x):=\operatorname{smin}_{\lambda}(\bar{z}(x)) y ˉ ( x ) := smin λ ( z ˉ ( x ))
for x ∈ R N I x\in\mathbb{R}^{N_I} x ∈ R N I . Now, by the triangle inequality,
∣ y ˉ ( x ) − f A ( x ) ∣ ≤ ∣ smin λ ( z ˉ ( x ) ) − min j ∈ [ q ] z ˉ j ( x ) ∣ + ∣ min j ∈ [ q ] z ˉ j ( x ) − min j ∈ [ q ] max i ∈ [ N I ] ( f ( a j ) + x i − a i j ) ∣ . |\bar{y}(x)-f_A(x)| \le\left|\operatorname{smin}_{\lambda}(\bar{z}(x))-\min_{j\in[q]}\bar{z}_j(x)\right|+
\left|\min_{j\in[q]}\bar{z}_j(x)-\min_{j\in[q]}\max_{i\in[N_I]}(f(a^j)+x_i-a_i^j)\right|. ∣ y ˉ ( x ) − f A ( x ) ∣ ≤ smin λ ( z ˉ ( x )) − j ∈ [ q ] min z ˉ j ( x ) + j ∈ [ q ] min z ˉ j ( x ) − j ∈ [ q ] min i ∈ [ N I ] max ( f ( a j ) + x i − a i j ) .
The first term on the right hand side is upper bounded by ln ( q ) λ \frac{\ln(q)}{\lambda} λ l n ( q ) , due to Lemma 23. By nonexpansiveness of min with respect to the ∞ \infty ∞ -norm, the second term is upper bounded by
∥ z ˉ ( x ) − [ max i ∈ [ N I ] ( f ( a 1 ) + x i − a i 1 ) ⋮ max i ∈ [ N I ] ( f ( a q ) + x i − a i q ) ] ∥ ∞ , \left\lVert
\bar{z}(x)-
\begin{bmatrix}
\max_{i\in[N_I]}(f(a^1)+x_i-a_i^1)\\
\vdots\\
\max_{i\in[N_I]}(f(a^q)+x_i-a_i^q)
\end{bmatrix}
\right\rVert_{\infty}, z ˉ ( x ) − max i ∈ [ N I ] ( f ( a 1 ) + x i − a i 1 ) ⋮ max i ∈ [ N I ] ( f ( a q ) + x i − a i q ) ∞ ,
which, by definition of the ∞ \infty ∞ -norm, equals
∣ z ˉ k ( x ) − max i ∈ [ N I ] ( f ( a k ) + x i − a i k ) ∣ \left|\bar{z}_k(x)-\max_{i\in[N_I]}(f(a^k)+x_i-a_i^k)\right| z ˉ k ( x ) − i ∈ [ N I ] max ( f ( a k ) + x i − a i k )
for some index k ∈ [ q ] k \in[q] k ∈ [ q ] . By Lemma 23, the latter term is upper bounded by ln ( N I ) λ \frac{\ln(N_I)}{\lambda} λ l n ( N I ) . We conclude that
∣ y ˉ ( x ) − f A ( x ) ∣ ≤ ln ( q ) λ + ln ( N I ) λ \left|\bar{y}(x)-f_A(x)\right| \le\frac{\ln(q)}{\lambda}+\frac{\ln(N_I)}{\lambda} ∣ y ˉ ( x ) − f A ( x ) ∣ ≤ λ ln ( q ) + λ ln ( N I )
for all x ∈ C x \in C x ∈ C .
Now, choose λ > 0 \lambda>0 λ > 0 sufficiently large such that
∣ y ˉ ( x ) − f A ( x ) ∣ ≤ ϵ 3 (52) \left|\bar{y}(x)-f_A(x)\right| \le\frac{\epsilon}{3} \tag*{(52)} ∣ y ˉ ( x ) − f A ( x ) ∣ ≤ 3 ϵ (52)
for all x ∈ C x \in C x ∈ C .
Next, consider a connected graph G = ( V , E ) \mathcal{G}=(\mathcal{V},\mathcal{E}) G = ( V , E ) , where V = V I ∪ V H ∪ V O \mathcal{V}=\mathcal{V}_I\cup\mathcal{V}_H\cup\mathcal{V}_O V = V I ∪ V H ∪ V O with ∣ V I ∣ = N I |\mathcal{V}_I|=N_I ∣ V I ∣ = N I , ∣ V H ∣ = q |\mathcal{V}_H|=q ∣ V H ∣ = q and ∣ V O ∣ = 1 |\mathcal{V}_O|=1 ∣ V O ∣ = 1 . The set E \mathcal{E} E consists of ( N I + 1 ) q (N_I+1)q ( N I + 1 ) q branches: each input node in V I \mathcal{V}_I V I is connected to all hidden nodes in V H \mathcal{V}_H V H , and all hidden nodes are connected to the output node. There are no branches between input nodes and the output node.
We will now define the co-content functions associated to the branches. For each input node i = 1 , 2 , … , N I i=1,2,\ldots,N_I i = 1 , 2 , … , N I and hidden node j = 1 , 2 , … , q j=1,2,\ldots,q j = 1 , 2 , … , q , we consider, for k = ( i − 1 ) q + j k=(i-1)q+j k = ( i − 1 ) q + j , the function
G k ( v k ) : = c ( v k + 1 λ e − λ ( v k − f ( a j ) + a i j ) ) (53) G_k(v_k):=c\left(v_k+\frac{1}{\lambda}e^{-\lambda(v_k-f(a^j)+a_i^j)}\right) \tag*{(53)} G k ( v k ) := c ( v k + λ 1 e − λ ( v k − f ( a j ) + a i j ) ) (53)
as the co-content of the branch between i i i and j j j . Here c > 0 c>0 c > 0 is a to-be-determined constant. Furthermore, define, for k = N I q + j k=N_Iq+j k = N I q + j with j = 1 , 2 , … , q j=1,2,\ldots,q j = 1 , 2 , … , q , the function
G k ( v k ) : = 1 λ e λ v k − v k (54) G_k(v_k):=\frac{1}{\lambda}e^{\lambda v_k}-v_k \tag*{(54)} G k ( v k ) := λ 1 e λ v k − v k (54)
as the co-content of the branch between the hidden node j j j and the output node. Note that the functions G k G_k G k indeed satisfy the assumptions in (b) for all k = 1 , 2 , … , ( N I + 1 ) q k=1,2,\ldots,(N_I+1)q k = 1 , 2 , … , ( N I + 1 ) q . The total co-content function is now given by
G ( v ) = ∑ k = 1 ( N I + 1 ) q G k ( v k ) . G(v)=\sum_{k=1}^{(N_I+1)q}G_k(v_k). G ( v ) = k = 1 ∑ ( N I + 1 ) q G k ( v k ) .
After assigning an orientation to each branch, the incidence matrix of the network takes the form
D = [ D I D H D O ] = [ − e 1 1 T ⋯ − e N I 1 T 0 I ⋯ I − I 0 ⋯ 0 1 T ] (55) D=\begin{bmatrix}D_I\\D_H\\D_O\end{bmatrix}
=\begin{bmatrix}
-e_1\mathbf{1}^{\mathsf{T}} & \cdots& -e_{N_I}\mathbf{1}^{\mathsf{T}} & 0\\
I & \cdots& I & -I\\
0 & \cdots& 0 & \mathbf{1}^{\mathsf{T}}
\end{bmatrix} \tag*{(55)} D = D I D H D O = − e 1 1 T I 0 ⋯ ⋯ ⋯ − e N I 1 T I 0 0 − I 1 T (55)
where e i e_i e i denotes the i i i -th standard basis vector of R N I \mathbb{R}^{N_I} R N I for i = 1 , 2 , … , N I i=1,2,\ldots,N_I i = 1 , 2 , … , N I . We then have that
G ( D I T x + D H T z + D O T y ) = ∑ j = 1 q ( 1 λ e λ ( y − z j ) − ( y − z j ) ) + c ∑ j = 1 q ∑ i = 1 N I ( z j − x i + 1 λ e − λ ( z j − x i − f ( a j ) + a i j ) ) , G(D_I^{\mathsf{T}}x+D_H^{\mathsf{T}}z+D_O^{\mathsf{T}}y)
=\sum_{j=1}^{q}\left(\frac{1}{\lambda}e^{\lambda(y-z_j)}-(y-z_j)\right)
+c\sum_{j=1}^{q}\sum_{i=1}^{N_I}\left(z_j-x_i+\frac{1}{\lambda}e^{-\lambda(z_j-x_i-f(a^j)+a_i^j)}\right), G ( D I T x + D H T z + D O T y ) = j = 1 ∑ q ( λ 1 e λ ( y − z j ) − ( y − z j ) ) + c j = 1 ∑ q i = 1 ∑ N I ( z j − x i + λ 1 e − λ ( z j − x i − f ( a j ) + a i j ) ) ,
for all x ∈ R N I x\in\mathbb{R}^{N_I} x ∈ R N I , z ∈ R q z\in\mathbb{R}^{q} z ∈ R q and y ∈ R y\in\mathbb{R} y ∈ R . Now, define the functions
H 1 ( x , z ) : = ∑ j = 1 q ∑ i = 1 N I ( z j − x i + 1 λ e − λ ( z j − x i − f ( a j ) + a i j ) ) , H_1(x,z):=\sum_{j=1}^{q}\sum_{i=1}^{N_I}\left(z_j-x_i+\frac{1}{\lambda}e^{-\lambda(z_j-x_i-f(a^j)+a_i^j)}\right), H 1 ( x , z ) := j = 1 ∑ q i = 1 ∑ N I ( z j − x i + λ 1 e − λ ( z j − x i − f ( a j ) + a i j ) ) ,
H 2 ( z , y ) : = ∑ j = 1 q ( 1 λ e λ ( y − z j ) − ( y − z j ) ) , H_2(z,y):=\sum_{j=1}^{q}\left(\frac{1}{\lambda}e^{\lambda(y-z_j)}-(y-z_j)\right), H 2 ( z , y ) := j = 1 ∑ q ( λ 1 e λ ( y − z j ) − ( y − z j ) ) ,
so that
G ( D I T x + D H T z + D O T y ) = c H 1 ( x , z ) + H 2 ( z , y ) . G(D_I^{\mathsf{T}}x+D_H^{\mathsf{T}}z+D_O^{\mathsf{T}}y)=cH_1(x,z)+H_2(z,y). G ( D I T x + D H T z + D O T y ) = c H 1 ( x , z ) + H 2 ( z , y ) .
Given c > 0 c>0 c > 0 and the input potentials x ∈ R N I x\in\mathbb{R}^{N_I} x ∈ R N I , denote by ( z c ( x ) , y c ( x ) ) (z^c(x),y^c(x)) ( z c ( x ) , y c ( x )) the corresponding hidden and output potentials, i.e.,
( z c ( x ) , y c ( x ) ) = arg min ( z , y ) ∈ R q × R G ( D I T x + D H T z + D O T y ) . (z^c(x),y^c(x))=\underset{(z,y)\in\mathbb{R}^{q}\times\mathbb{R}}{\operatorname{arg\,min}}\;G(D_I^{\mathsf{T}}x+D_H^{\mathsf{T}}z+D_O^{\mathsf{T}}y). ( z c ( x ) , y c ( x )) = ( z , y ) ∈ R q × R arg min G ( D I T x + D H T z + D O T y ) .
Existence and uniqueness of these potentials follows from Lemma 2. We emphasize that z c ( x ) z^c(x) z c ( x ) is not equal to z ˉ ( x ) \bar{z}(x) z ˉ ( x ) , i.e., the hidden potentials z c ( x ) z^c(x) z c ( x ) do not compute the smaxλ _\lambda λ functions in (51) exactly. We will, however, show that z c ( ⋅ ) z^c(\cdot) z c ( ⋅ ) converges uniformly to z ˉ ( ⋅ ) \bar{z}(\cdot) z ˉ ( ⋅ ) on C C C as c → ∞ c\to\infty c → ∞ . To do so, we need some preparation.
First, note that
c H 1 ( x , z c ( x ) ) + H 2 ( z c ( x ) , y c ( x ) ) ≤ c H 1 ( x , z ˉ ( x ) ) + H 2 ( z ˉ ( x ) , y ) , cH_1(x,z^c(x))+H_2(z^c(x),y^c(x))
\le cH_1(x,\bar{z}(x))+H_2(\bar{z}(x),y), c H 1 ( x , z c ( x )) + H 2 ( z c ( x ) , y c ( x )) ≤ c H 1 ( x , z ˉ ( x )) + H 2 ( z ˉ ( x ) , y ) ,
for all x ∈ R N I x\in\mathbb{R}^{N_I} x ∈ R N I and y ∈ R y\in\mathbb{R} y ∈ R . It can be readily shown that the minimum of the function H 2 H_2 H 2 is q λ \frac{q}{\lambda} λ q , and thus,
H 2 ( z c ( x ) , y c ( x ) ) ≥ q λ . H_2(z^c(x),y^c(x))\ge\frac{q}{\lambda}. H 2 ( z c ( x ) , y c ( x )) ≥ λ q .
Furthermore, the function x ↦ H 2 ( z ˉ ( x ) , y ) x\mapsto H_2(\bar{z}(x),y) x ↦ H 2 ( z ˉ ( x ) , y ) is continuous for all y y y . Fix y ∈ R y\in\mathbb{R} y ∈ R . Since C C C is compact and H 2 H_2 H 2 and z ˉ \bar{z} z ˉ are continuous, there exists a constant a > 0 a>0 a > 0 such that
H 2 ( z ˉ ( x ) , y ) ≤ a H_2(\bar{z}(x),y)\le a H 2 ( z ˉ ( x ) , y ) ≤ a
for all x ∈ C x\in C x ∈ C . Therefore,
c ( H 1 ( x , z c ( x ) ) − H 1 ( x , z ˉ ( x ) ) ) ≤ H 2 ( z ˉ ( x ) , y ) − H 2 ( z c ( x ) , y c ( x ) ) ≤ a − q λ = : φ c\left(H_1(x,z^c(x))-H_1(x,\bar{z}(x))\right)
\le H_2(\bar{z}(x),y)-H_2(z^c(x),y^c(x))
\le a-\frac{q}{\lambda}=:\varphi c ( H 1 ( x , z c ( x )) − H 1 ( x , z ˉ ( x )) ) ≤ H 2 ( z ˉ ( x ) , y ) − H 2 ( z c ( x ) , y c ( x )) ≤ a − λ q =: φ
for all x ∈ C x\in C x ∈ C . We conclude that
H 1 ( x , z c ( x ) ) − H 1 ( x , z ˉ ( x ) ) ≤ φ c H_1(x,z^c(x))-H_1(x,\bar{z}(x))\le\frac{\varphi}{c} H 1 ( x , z c ( x )) − H 1 ( x , z ˉ ( x )) ≤ c φ
for all x ∈ C x\in C x ∈ C . We claim that, in addition, H 1 ( x , z c ( x ) ) − H 1 ( x , z ˉ ( x ) ) ≥ 0 H_1(x,z^c(x))-H_1(x,\bar{z}(x))\ge0 H 1 ( x , z c ( x )) − H 1 ( x , z ˉ ( x )) ≥ 0 . We will prove this by showing that z ˉ ( x ) \bar{z}(x) z ˉ ( x ) is the minimizer of H 1 ( x , ⋅ ) H_1(x,\cdot) H 1 ( x , ⋅ ) for all x ∈ C x \in C x ∈ C . First, note that H 1 ( x , ⋅ ) H_1(x,\cdot) H 1 ( x , ⋅ ) is continuous, coercive and strictly convex and thus has a unique minimizer for all x ∈ C x \in C x ∈ C by Proposition 25 in Appendix B. To find this minimizer, fix x ∈ C x \in C x ∈ C , and compute
( ∂ H 1 ∂ z ( x , z ) ) j = ∑ i = 1 N I ( 1 − e − λ ( z j − x i − f ( a j ) + a i j ) ) . \left(\frac{\partial H_1}{\partial z}(x,z)\right)_j = \sum_{i=1}^{N_I}\left(1-e^{-\lambda(z_j-x_i-f(a^j)+a_i^j)}\right). ( ∂ z ∂ H 1 ( x , z ) ) j = i = 1 ∑ N I ( 1 − e − λ ( z j − x i − f ( a j ) + a i j ) ) .
Setting this equal to zero yields, for j = 1 , 2 , … , q j=1,2,\ldots,q j = 1 , 2 , … , q ,
e − λ z j ∑ i = 1 N I e λ ( f ( a j ) + x i − a i j ) = N I . e^{-\lambda z_j}\sum_{i=1}^{N_I}e^{\lambda(f(a^j)+x_i-a_i^j)}=N_I. e − λ z j i = 1 ∑ N I e λ ( f ( a j ) + x i − a i j ) = N I .
In other words,
e λ z j = 1 N I ∑ i = 1 N I e λ ( f ( a j ) + x i − a i j ) , e^{\lambda z_j}=\frac{1}{N_I}\sum_{i=1}^{N_I}e^{\lambda(f(a^j)+x_i-a_i^j)}, e λ z j = N I 1 i = 1 ∑ N I e λ ( f ( a j ) + x i − a i j ) ,
hence, by taking natural logarithms,
z j = 1 λ ln ( 1 N I ∑ i = 1 N I e λ ( f ( a j ) + x i − a i j ) ) = smax λ ( f ( a j ) 1 + x − a j ) = z ˉ j ( x ) . \begin{aligned}
z_j=\frac{1}{\lambda}\ln\left(\frac{1}{N_I}\sum_{i=1}^{N_I}e^{\lambda(f(a^j)+x_i-a_i^j)}\right) \\
&=\operatorname{smax}_{\lambda}(f(a^j)\mathbf{1}+x-a^j)=\bar{z}_j(x).
\end{aligned} z j = λ 1 ln ( N I 1 i = 1 ∑ N I e λ ( f ( a j ) + x i − a i j ) ) = smax λ ( f ( a j ) 1 + x − a j ) = z ˉ j ( x ) .
So indeed, z ˉ ( x ) \bar{z}(x) z ˉ ( x ) is the unique minimizer of H 1 ( x , ⋅ ) H_1(x,\cdot) H 1 ( x , ⋅ ) . We conclude that our claim holds, and thus,
0 ≤ H 1 ( x , z c ( x ) ) − H 1 ( x , z ˉ ( x ) ) ≤ φ c (56) 0\leq H_1(x,z^c(x))-H_1(x,\bar{z}(x))\leq\frac{\varphi}{c} \tag*{(56)} 0 ≤ H 1 ( x , z c ( x )) − H 1 ( x , z ˉ ( x )) ≤ c φ (56)
for all x ∈ C x\in C x ∈ C .
We will now show that the function z c ( ⋅ ) z^c(\cdot) z c ( ⋅ ) converges uniformly to z ˉ ( ⋅ ) \bar{z}(\cdot) z ˉ ( ⋅ ) on C C C , as c → ∞ c\to\infty c → ∞ . To this end, fix ρ > 0 \rho>0 ρ > 0 . Define α ( ρ ) \alpha(\rho) α ( ρ ) as
inf x ∈ C , ζ ∈ R q { H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x ) ) ∣ ∥ ζ − z ˉ ( x ) ∥ ≥ ρ } . \inf_{x\in C,\ \zeta\in\mathbb{R}^q}\{H_1(x,\zeta)-H_1(x,\bar{z}(x))\mid\|\zeta-\bar{z}(x)\|\geq\rho\}. x ∈ C , ζ ∈ R q inf { H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x )) ∣ ∥ ζ − z ˉ ( x ) ∥ ≥ ρ } .
Due to the compactness of C C C and the coercivity of H 1 H_1 H 1 , for every x ∈ C x\in C x ∈ C , H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x ) ) → ∞ H_1(x,\zeta)-H_1(x,\bar{z}(x))\to\infty H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x )) → ∞ as ∥ ζ ∥ → ∞ \|\zeta\|\to\infty ∥ ζ ∥ → ∞ . Hence, there exists a sufficiently large constant R > 0 R>0 R > 0 such that α ( ρ ) \alpha(\rho) α ( ρ ) equals
inf x ∈ C , ∥ ζ ∥ ≤ R { H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x ) ) ∣ ∥ ζ − z ˉ ( x ) ∥ ≥ ρ } . \inf_{x\in C,\ \|\zeta\|\leq R}\{H_1(x,\zeta)-H_1(x,\bar{z}(x))\mid\|\zeta-\bar{z}(x)\|\geq\rho\}. x ∈ C , ∥ ζ ∥ ≤ R inf { H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x )) ∣ ∥ ζ − z ˉ ( x ) ∥ ≥ ρ } .
Now, since z ˉ ( x ) \bar{z}(x) z ˉ ( x ) is the unique minimizer of H 1 ( x , ⋅ ) H_1(x,\cdot) H 1 ( x , ⋅ ) for all x ∈ C x\in C x ∈ C , we have that
H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x ) ) > 0 H_1(x,\zeta)-H_1(x,\bar{z}(x))>0 H 1 ( x , ζ ) − H 1 ( x , z ˉ ( x )) > 0
for all ζ ∈ R q \zeta\in\mathbb{R}^q ζ ∈ R q satisfying ∥ ζ − z ˉ ( x ) ∥ ≥ ρ > 0 \|\zeta-\bar{z}(x)\|\geq\rho>0 ∥ ζ − z ˉ ( x ) ∥ ≥ ρ > 0 . Therefore, since
{ ( x , ζ ) ∈ C × R q ∣ ∥ ζ ∥ ≤ R } \{(x,\zeta)\in C\times\mathbb{R}^q\mid\|\zeta\|\leq R\} {( x , ζ ) ∈ C × R q ∣ ∥ ζ ∥ ≤ R }
is compact and H 1 H_1 H 1 and z ˉ \bar{z} z ˉ are continuous, we also have that α ( ρ ) > 0 \alpha(\rho)>0 α ( ρ ) > 0 .
Next, choose c > 0 c>0 c > 0 sufficiently large so that
φ c < α ( ρ ) . \frac{\varphi}{c}<\alpha(\rho). c φ < α ( ρ ) .
It then follows from (56) that
H 1 ( x , z c ( x ) ) − H 1 ( x , z ˉ ( x ) ) < α ( ρ ) H_1(x,z^c(x))-H_1(x,\bar{z}(x))<\alpha(\rho) H 1 ( x , z c ( x )) − H 1 ( x , z ˉ ( x )) < α ( ρ )
for all x ∈ C x\in C x ∈ C . We conclude that ∥ z c ( x ) − z ˉ ( x ) ∥ < ρ \|z^c(x)-\bar{z}(x)\|<\rho ∥ z c ( x ) − z ˉ ( x ) ∥ < ρ for all x ∈ C x\in C x ∈ C . This proves that z c ( ⋅ ) z^c(\cdot) z c ( ⋅ ) converges uniformly to z ˉ ( ⋅ ) \bar{z}(\cdot) z ˉ ( ⋅ ) on C C C as c → ∞ c\to\infty c → ∞ .
The final step of the proof is to show that also y c ( ⋅ ) y^c(\cdot) y c ( ⋅ ) converges uniformly to y ˉ ( ⋅ ) \bar{y}(\cdot) y ˉ ( ⋅ ) on C C C as c → ∞ c\to\infty c → ∞ . To this end, by the network model, we have that
[ D H D O ] ∇ G ( D I ⊤ x + D H ⊤ z c ( x ) + D O ⊤ y c ( x ) ) = 0. \begin{bmatrix}D_H\\D_O\end{bmatrix}\nabla G(D_I^\top x+D_H^\top z^c(x)+D_O^\top y^c(x))=0. [ D H D O ] ∇ G ( D I ⊤ x + D H ⊤ z c ( x ) + D O ⊤ y c ( x )) = 0.
By focusing on the last row, and using the structure of D O D_O D O in (55) and the definitions of G k G_k G k in (54), we see that
∑ j = 1 q ( e λ ( y c ( x ) − z j c ( x ) ) − 1 ) = 0 , \sum_{j=1}^{q}\left(e^{\lambda(y^c(x)-z_j^c(x))}-1\right)=0, j = 1 ∑ q ( e λ ( y c ( x ) − z j c ( x )) − 1 ) = 0 ,
and thus,
e λ y c ( x ) ∑ j = 1 q e − λ z j c ( x ) = q . e^{\lambda y^c(x)}\sum_{j=1}^{q}e^{-\lambda z_j^c(x)}=q. e λ y c ( x ) j = 1 ∑ q e − λ z j c ( x ) = q .
This implies that
e − λ y c ( x ) = 1 q ∑ j = 1 q e − λ z j c ( x ) , e^{-\lambda y^c(x)}=\frac{1}{q}\sum_{j=1}^{q}e^{-\lambda z_j^c(x)}, e − λ y c ( x ) = q 1 j = 1 ∑ q e − λ z j c ( x ) ,
showing that, after taking natural logarithms on both sides,
y c ( x ) = − 1 λ ln ( 1 q ∑ j = 1 q e − λ z j c ( x ) ) = smin λ ( z c ( x ) ) . y^c(x)=-\frac{1}{\lambda}\ln\left(\frac{1}{q}\sum_{j=1}^{q}e^{-\lambda z_j^c(x)}\right)=\operatorname{smin}_{\lambda}(z^c(x)). y c ( x ) = − λ 1 ln ( q 1 j = 1 ∑ q e − λ z j c ( x ) ) = smin λ ( z c ( x )) .
Now, recall that y ˉ ( x ) = smin λ ( z ˉ ( x ) ) \bar{y}(x)=\operatorname{smin}_{\lambda}(\bar{z}(x)) y ˉ ( x ) = smin λ ( z ˉ ( x )) , by definition. By nonexpansiveness of smin λ \operatorname{smin}_{\lambda} smin λ (see Lemma 23),
∣ y c ( x ) − y ˉ ( x ) ∣ = ∣ smin λ ( z c ( x ) ) − smin λ ( z ˉ ( x ) ) ∣ ≤ ∥ z c ( x ) − z ˉ ( x ) ∥ ∞ \begin{aligned}
|y^c(x)-\bar{y}(x)|=|\operatorname{smin}_{\lambda}(z^c(x))-\operatorname{smin}_{\lambda}(\bar{z}(x))| \\
&\leq\|z^c(x)-\bar{z}(x)\|_{\infty}
\end{aligned} ∣ y c ( x ) − y ˉ ( x ) ∣ = ∣ smin λ ( z c ( x )) − smin λ ( z ˉ ( x )) ∣ ≤ ∥ z c ( x ) − z ˉ ( x ) ∥ ∞
for all x ∈ C x\in C x ∈ C . This shows that y c ( ⋅ ) y^c(\cdot) y c ( ⋅ ) converges uniformly to y ˉ ( ⋅ ) \bar{y}(\cdot) y ˉ ( ⋅ ) on C C C as c → ∞ c\to\infty c → ∞ .
Finally, we assemble all ingredients and complete the proof. Choose c > 0 c>0 c > 0 sufficiently large so that
∣ y c ( x ) − y ˉ ( x ) ∣ ≤ ϵ 3 (57) |y^c(x)-\bar{y}(x)|\leq\frac{\epsilon}{3} \tag*{(57)} ∣ y c ( x ) − y ˉ ( x ) ∣ ≤ 3 ϵ (57)
for all x ∈ C x \in C x ∈ C . Then, by combining (57), (52), and (50), for all x ∈ C x \in C x ∈ C ,
∣ y c ( x ) − f ( x ) ∣ ≤ ∣ y c ( x ) − y ˉ ( x ) ∣ + ∣ y ˉ ( x ) − f A ( x ) ∣ + ∣ f A ( x ) − f ( x ) ∣ ≤ ϵ 3 + ϵ 3 + ϵ 3 . \begin{aligned}
\left|y^{c}(x)-f(x)\right| &\le\\
\left|y^{c}(x)-\bar{y}(x)\right|+\left|\bar{y}(x)-f_A(x)\right|+\left|f_A(x)-f(x)\right| &\le\\
\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3}.
\end{aligned} ∣ y c ( x ) − f ( x ) ∣ ∣ y c ( x ) − y ˉ ( x ) ∣ + ∣ y ˉ ( x ) − f A ( x ) ∣ + ∣ f A ( x ) − f ( x ) ∣ 3 ϵ + 3 ϵ + 3 ϵ . ≤ ≤
which is equal to ϵ \epsilon ϵ . Thus, taking F = y c F=y^{c} F = y c proves the theorem. □
Conclusions and Discussion
In this paper, we have established a rigorous mathematical foundation for both the learning dynamics and the representational capacity of nonlinear resistive networks with monotone elements. By framing the solution of these circuits as the global minimizer of a strictly convex co-content function, we proved that Target-Clamped Contrastive Learning (TCCL) reliably converges to parameters that implement desired input-output mappings.
Crucial to our analysis has been a detailed study of the properties of the contrastive function, as reported in Thms. 4 and 7 .
In the case of only input and output nodes, the contrastive function is convex (Thm. 7 ), even for networks with non-monotone resistors (Rem. 9). As a consequence, TCCL converges to a global minimizer of the contrastive function for a range of stepsizes (Thm. 15 ). This property mirrors the convexity of linear regression and logistic regression tasks in traditional machine learning. In contrast, we have shown that the objective function used in Equilibrium Propagation (EP) is in general not convex , even for linear resistive circuits (Prop. 10 ). This demonstrates an important advantage of using TCCL in networks without hidden nodes. A further advantage of TCCL over EP and coupled learning is that it does not involve a nudging parameter, thereby eliminating the need to fine-tune it, and simplifying the learning procedure altogether.
Beyond the setting with only input and output nodes, we have revealed general properties of the contrastive function, also in the presence of hidden nodes (Thm. 4 ). In this setting, the contrastive function is generally not convex, but it exhibits an attractive scaling behavior. Assuming all resistors are trainable, the hidden and output potentials of a resistive network are invariant under scaling of the parameters (Lem. 6 ), and only depend on the relative magnitudes of parameters. As noted in [47 ] , this invariance implies that network parameters can be uniformly rescaled to reduce operating power without altering the input-output mapping.
As we have shown here, this feature implies that the contrastive function is positively homogeneous of degree 1 (Thm. 4 ). Its minimization therefore has a regularization effect: it penalizes parameter configurations with large parameter values, and thereby promotes low (pseudo-)power dissipation during inference. This is achieved without introducing an additional term in the learning rule, as is done in [47 ] . In contrast, the EP objective is positively homogeneous of degree 0 (Lem. 6 ), and consequently exhibits no inherent preference between high- and low-power parameter configurations. In the presence of hidden nodes, we have shown that TCCL converges to a stationary point on a subsesequence (Thm. 17 ). This is in line with similar results on the convergence of (stochastic) gradient descent applied to deep neural networks, see, e.g., [12 Sec. 4.3] . However, different from deep neural networks, due to the positive homogeneity of the contrastive function, all limit points in the interior of the constraint set are global minimizers (Thm. 17 ).
Furthermore, we characterized the computational expressivity of these resistive networks. We demonstrated that their underlying physics inherently restricts them to monotonically non-decreasing and shift-equivariant functions (Lem. 18 ). Crucially, we established a novel approximation theorem proving that these constraints are the only limitations on expressivity, as any continuous function satisfying these two properties can be approximated to arbitrary precision by a sufficiently large network with monotone elements (Thm. 20 ).
Beyond the electrical domain, the framework developed in this work has broader implications for other analog learning systems. Our results generalize naturally to any physical network governed by analogous flow-effort relationships. For instance, mechanical elastic networks characterized by nonlinear force-displacement relationships minimize potential energy in a manner that is similar to co-content minimization in resistive circuits [41 Sec. II.B] . Consequently, the convergence guarantees and approximation results established here can be directly translated to design, train, and analyze such networks. Our learning framework may also be considered for coupled phase oscillators, for which EP has been employed in [50 ] . In case the drive phases are fixed (non-trainable), the energy function of [50 Eq. (1)] is linear in the parameters, and thus, the contrastive function is degree-1 positively homogeneous. However, a challenge compared to the current work is the non-convexity of the energy as a function of the phase angles.
The primary limitation of this study is the restriction to strictly monotone elements, which limits the class of functions the network can approximate. This constraint can be overcome by introducing active two-port elements, such as VCVSs [44 ] , or by incorporating non-monotone components (with regions of negative differential conductance), similar to the approach of [30 ] . However, by introducing non-monotone elements, the network’s energy function (co-content) is no longer convex. For general non-monotone circuit elements, the energy landscape can develop multiple stationary points of different types, each corresponding to a valid physical solution. This multiplicity renders the circuit’s input-output mapping mathematically ill-defined. Developing the mathematical tools to rigorously study expressivity and learning in networks with multiple stationary points remains a key direction for future work. In these networks, EP may prove to be a preferable training strategy, as EP relies only on stationarity rather than global energy minimization; see for instance [24 , 28 ] where EP was successfully employed to (numerically) train other types of energy-based models to classify ImageNet and reconstruct corrupted images.
Another promising direction for future research concerns the representational capacity of networks consisting exclusively of input and output nodes. Thus far, we have investigated the approximation properties of monotone resistive circuits with hidden nodes (Thm. 20 ). However, in view of the strong convergence guarantees established for networks without hidden nodes (Thm. 15 ), it is relevant to characterize the functions that such networks can implement, and to compare these to the class of linear and logistic classifiers in traditional machine learning. A further direction is to extend the framework beyond static resistive circuits by incorporating dynamic circuit elements, such as capacitors, thereby enabling learning of dynamical systems. An initial step in this direction has already been taken in the recent work [23 ] , which extends target-clamped contrastive learning to linear resistive-capacitive networks.
In this work, we have assumed that the data consist of a single pair of input-output potentials. This assumption was made for simplicity and clarity of presentation, and we expect that the framework can be extended straightforwardly to accommodate multiple data points. Indeed, such an extension has already been established in [25 Sec. V] for linear networks without hidden nodes. Here, the idea was to extend the convergence analysis of projected gradient descent for a single data sample to that of stochastic projected gradient descent, thereby allowing for multiple samples. We also note that, while our theoretical analysis is restricted to optimization and expressivity, investigating the generalization performance of nonlinear resistive networks on unseen data is an important avenue for future research.
Finally, we close this paper with a few remarks regarding the origins of our work and the employed terminology. Contrastive Learning (CL) finds its roots in the study of Boltzmann machines [1 ] , where target clamping was shown to minimize the Kullback-Leibler divergence between the data and model distributions. CL with target clamping was later extended to continuous Hopfield networks [35 ] , but in recent years, the physical learning community has favored nudging-based approaches such as EP and coupled learning, while keeping “contrastive learning” as an umbrella term for the broader family of energy-based learning methods [34 , 49 ] . Given the theoretical advantages of fully clamping outputs to their target values, as demonstrated in this work and other studies [23 , 25 ] , we believe this approach deserves further research. We therefore adopt the term Target-Clamped Contrastive Learning (TCCL) to distinguish it from nudging-based approaches. TCCL may also be studied in settings where EP has previously been adapted, including Lagrangian dynamical systems [45 Sec. 6.1] and quantum systems [41 ] , where the principle of co-content minimization is replaced by the principle of least action and the variational principle of quantum mechanics, respectively. Similarly, TCCL may be transposed to bilevel optimization problems [52 ] .
Notation regarding partial derivatives
We first introduce some notation related to partial derivatives. For a differentiable function f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R we use the notation
∂ f ∂ x ( x ) : = [ ∂ f ∂ x 1 ( x ) ∂ f ∂ x 2 ( x ) ⋮ ∂ f ∂ x n ( x ) ] \frac{\partial f}{\partial x}(x) := \begin{bmatrix}
\frac{\partial f}{\partial x_{1}}(x) \\
\frac{\partial f}{\partial x_{2}}(x) \\
\vdots\\
\frac{\partial f}{\partial x_{n}}(x)
\end{bmatrix} ∂ x ∂ f ( x ) := ∂ x 1 ∂ f ( x ) ∂ x 2 ∂ f ( x ) ⋮ ∂ x n ∂ f ( x )
and
∂ f ∂ x T ( x ) : = [ ∂ f ∂ x 1 ( x ) ∂ f ∂ x 2 ( x ) ⋯ ∂ f ∂ x n ( x ) ] . \frac{\partial f}{\partial x^{\mathsf{T}}}(x) := \begin{bmatrix}
\frac{\partial f}{\partial x_{1}}(x) & \frac{\partial f}{\partial x_{2}}(x) & \cdots& \frac{\partial f}{\partial x_{n}}(x)
\end{bmatrix}. ∂ x T ∂ f ( x ) := [ ∂ x 1 ∂ f ( x ) ∂ x 2 ∂ f ( x ) ⋯ ∂ x n ∂ f ( x ) ] .
We will also use the shorthand notation ∇ f : = ∂ f ∂ x \nabla f := \frac{\partial f}{\partial x} ∇ f := ∂ x ∂ f to denote the gradient of f f f . The Jacobian of a differentiable function g : R n → R m g : \mathbb{R}^{n} \to\mathbb{R}^{m} g : R n → R m is defined as
∂ g ∂ x ⊤ ( x ) : = [ ∂ g 1 ∂ x 1 ( x ) ⋯ ∂ g 1 ∂ x n ( x ) ⋮ ⋱ ⋮ ∂ g m ∂ x 1 ( x ) ⋯ ∂ g m ∂ x n ( x ) ] . \frac{\partial g}{\partial x^{\top}}(x) := \begin{bmatrix} \frac{\partial g_{1}}{\partial x_{1}}(x) & \cdots& \frac{\partial g_{1}}{\partial x_{n}}(x) \\ \vdots& \ddots& \vdots\\ \frac{\partial g_{m}}{\partial x_{1}}(x) & \cdots& \frac{\partial g_{m}}{\partial x_{n}}(x) \end{bmatrix}. ∂ x ⊤ ∂ g ( x ) := ∂ x 1 ∂ g 1 ( x ) ⋮ ∂ x 1 ∂ g m ( x ) ⋯ ⋱ ⋯ ∂ x n ∂ g 1 ( x ) ⋮ ∂ x n ∂ g m ( x ) .
The Hessian of a twice differentiable f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R is:
∂ 2 f ∂ x ∂ x ⊤ ( x ) : = ∂ ∂ x ⊤ ( ∂ f ∂ x ) ( x ) = [ ∂ 2 f ∂ x 1 2 ( x ) ∂ 2 f ∂ x 1 ∂ x 2 ( x ) ⋯ ∂ 2 f ∂ x 1 ∂ x n ( x ) ∂ 2 f ∂ x 2 ∂ x 1 ( x ) ∂ 2 f ∂ x 2 2 ( x ) ⋯ ∂ 2 f ∂ x 2 ∂ x n ( x ) ⋮ ⋮ ⋱ ⋮ ∂ 2 f ∂ x n ∂ x 1 ( x ) ∂ 2 f ∂ x n ∂ x 2 ( x ) ⋯ ∂ 2 f ∂ x n 2 ( x ) ] . \begin{aligned}
\frac{\partial^{2} f}{\partial x \partial x^{\top}}(x) := \frac{\partial}{\partial x^{\top}}\left(\frac{\partial f}{\partial x}\right)(x) \\
&= \begin{bmatrix} \frac{\partial^{2} f}{\partial x_{1}^{2}}(x) & \frac{\partial^{2} f}{\partial x_{1}\partial x_{2}}(x) & \cdots& \frac{\partial^{2} f}{\partial x_{1}\partial x_{n}}(x) \\ \frac{\partial^{2} f}{\partial x_{2}\partial x_{1}}(x) & \frac{\partial^{2} f}{\partial x_{2}^{2}}(x) & \cdots& \frac{\partial^{2} f}{\partial x_{2}\partial x_{n}}(x) \\ \vdots& \vdots& \ddots& \vdots\\ \frac{\partial^{2} f}{\partial x_{n}\partial x_{1}}(x) & \frac{\partial^{2} f}{\partial x_{n}\partial x_{2}}(x) & \cdots& \frac{\partial^{2} f}{\partial x_{n}^{2}}(x) \end{bmatrix}.
\end{aligned} ∂ x ∂ x ⊤ ∂ 2 f ( x ) := ∂ x ⊤ ∂ ( ∂ x ∂ f ) ( x ) = ∂ x 1 2 ∂ 2 f ( x ) ∂ x 2 ∂ x 1 ∂ 2 f ( x ) ⋮ ∂ x n ∂ x 1 ∂ 2 f ( x ) ∂ x 1 ∂ x 2 ∂ 2 f ( x ) ∂ x 2 2 ∂ 2 f ( x ) ⋮ ∂ x n ∂ x 2 ∂ 2 f ( x ) ⋯ ⋯ ⋱ ⋯ ∂ x 1 ∂ x n ∂ 2 f ( x ) ∂ x 2 ∂ x n ∂ 2 f ( x ) ⋮ ∂ x n 2 ∂ 2 f ( x ) .
We will use the shorthand notation ∇ 2 f : = ∂ 2 f ∂ x ∂ x ⊤ \nabla^{2} f := \frac{\partial^{2} f}{\partial x \partial x^{\top}} ∇ 2 f := ∂ x ∂ x ⊤ ∂ 2 f . Finally, for a function f : R n 1 × ⋯ × R n m → R f : \mathbb{R}^{n_{1}} \times\cdots\times\mathbb{R}^{n_{m}} \to\mathbb{R} f : R n 1 × ⋯ × R n m → R in the m m m variables x 1 , … , x m x^{1}, \ldots, x^{m} x 1 , … , x m , we use the notation
∂ f ∂ x i ( x 1 , … , x m ) : = [ ∂ f ∂ x 1 i ( x 1 , … , x m ) ⋮ ∂ f ∂ x n i i ( x 1 , … , x m ) ] , \frac{\partial f}{\partial x^{i}}(x^{1}, \ldots, x^{m}) := \begin{bmatrix} \frac{\partial f}{\partial x_{1}^{i}}(x^{1}, \ldots, x^{m}) \\ \vdots\\ \frac{\partial f}{\partial x_{n_{i}}^{i}}(x^{1}, \ldots, x^{m}) \end{bmatrix}, ∂ x i ∂ f ( x 1 , … , x m ) := ∂ x 1 i ∂ f ( x 1 , … , x m ) ⋮ ∂ x n i i ∂ f ( x 1 , … , x m ) ,
∂ f ∂ ( x i ) ⊤ : = ( ∂ f ∂ x i ) ⊤ \frac{\partial f}{\partial(x^{i})^{\top}} := \left(\frac{\partial f}{\partial x^{i}}\right)^{\top} ∂ ( x i ) ⊤ ∂ f := ( ∂ x i ∂ f ) ⊤
and
∂ 2 f ∂ x i ∂ ( x j ) ⊤ : = ∂ ∂ ( x j ) ⊤ ( ∂ f ∂ x i ) \frac{\partial^{2} f}{\partial x^{i}\partial(x^{j})^{\top}} := \frac{\partial}{\partial(x^{j})^{\top}}\left(\frac{\partial f}{\partial x^{i}}\right) ∂ x i ∂ ( x j ) ⊤ ∂ 2 f := ∂ ( x j ) ⊤ ∂ ( ∂ x i ∂ f )
for i , j = 1 , 2 , … , m i,j=1,2,\ldots,m i , j = 1 , 2 , … , m .
Preliminaries on Lipschitz continuity, coercivity and convexity
We call f : D ⊆ R n → R m f : D \subseteq\mathbb{R}^{n} \to\mathbb{R}^{m} f : D ⊆ R n → R m Lipschitz continuous if there exists a constant L ≥ 0 L \ge0 L ≥ 0 such that
∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥ \|f(x)-f(y)\| \le L\|x-y\| ∥ f ( x ) − f ( y ) ∥ ≤ L ∥ x − y ∥
for all x , y ∈ D x,y \in D x , y ∈ D . We call such an L L L a Lipschitz constant of f f f . In case f f f is Lipschitz continuous with L = 1 L=1 L = 1 , we call f f f nonexpansive . The following result for differentiable functions with Lipschitz continuous gradients is well-known (see, e.g., [6 Lem. 5.7] ).
Lemma 24. Let f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R be differentiable and suppose ∇ f \nabla f ∇ f is Lipschitz continuous with constant L L L . Then
f ( x ) ≤ f ( y ) + ( x − y ) ⊤ ∇ f ( y ) + L 2 ∥ x − y ∥ 2 f(x) \le f(y) + (x-y)^{\top}\nabla f(y) + \frac{L}{2}\|x-y\|^{2} f ( x ) ≤ f ( y ) + ( x − y ) ⊤ ∇ f ( y ) + 2 L ∥ x − y ∥ 2 for all x , y ∈ R n x,y \in\mathbb{R}^{n} x , y ∈ R n .
A function f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R is called coercive if f ( x ) → ∞ f(x) \to\infty f ( x ) → ∞ as ∥ x ∥ → ∞ \|x\| \to\infty ∥ x ∥ → ∞ .
A subset C ⊆ R n C \subseteq\mathbb{R}^{n} C ⊆ R n is called convex if for any two points x , y ∈ C x,y \in C x , y ∈ C we have that α x + ( 1 − α ) y ∈ C \alpha x + (1-\alpha)y \in C α x + ( 1 − α ) y ∈ C for all α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . A function f : C → R f : C \to\mathbb{R} f : C → R is convex if
f ( α x + ( 1 − α ) y ) ≤ α f ( x ) + ( 1 − α ) f ( y ) f(\alpha x + (1-\alpha)y) \le\alpha f(x) + (1-\alpha)f(y) f ( α x + ( 1 − α ) y ) ≤ α f ( x ) + ( 1 − α ) f ( y )
for all x , y ∈ C x,y \in C x , y ∈ C and all α ∈ [ 0 , 1 ] \alpha\in[0,1] α ∈ [ 0 , 1 ] . We call f f f concave if − f -f − f is convex. A convex function f : C → R f : C \to\mathbb{R} f : C → R is called strictly convex if
f ( α x + ( 1 − α ) y ) < α f ( x ) + ( 1 − α ) f ( y ) f(\alpha x + (1-\alpha)y) < \alpha f(x) + (1-\alpha)f(y) f ( α x + ( 1 − α ) y ) < α f ( x ) + ( 1 − α ) f ( y )
for all distinct x , y ∈ C x,y \in C x , y ∈ C and all α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . If the function f : C → R f : C \to\mathbb{R} f : C → R is twice continuously differentiable, strict convexity is implied by ∇ 2 f ( x ) > 0 \nabla^{2}f(x) > 0 ∇ 2 f ( x ) > 0 for all x ∈ C x \in C x ∈ C , i.e., the Hessian is positive definite .
We now recall the following basic proposition about (strictly) convex and coercive functions.
Proposition 25. Let f : R n → R f : \mathbb{R}^{n} \to\mathbb{R} f : R n → R . Then the following statements hold:
(i) If f f f is convex, then any local minimum of f f f is also a global minimum.
(ii) If f f f is strictly convex, then it has at most one global minimum.
(iii) If f f f is continuous and coercive, then it has at least one global minimum.
(iv) Thus, if f f f is continuous, coercive and strictly convex, it has precisely one global minimum.
Proposition 25 (i) and (ii) follow from [8 Prop. 3.1.1] , while Proposition 25 (iii) follows from Weierstrass’ theorem, see e.g. [8 Prop. 3.2.1] .
The projection P C : R n → C P_C : \mathbb{R}^{n} \to C P C : R n → C onto a nonempty, closed and convex set C ⊆ R n C \subseteq\mathbb{R}^{n} C ⊆ R n is defined as
P C ( x ) = arg min y ∈ C ∥ x − y ∥ . (58) P_C(x) = \underset{y \in C}{\operatorname{arg\,min}}\ \|x-y\|. \tag*{(58)} P C ( x ) = y ∈ C arg min ∥ x − y ∥. (58)
The following lemma collects properties P C P_C P C .
Lemma 26. Let C ⊆ R n C \subseteq\mathbb{R}^{n} C ⊆ R n be nonempty, closed and convex. Then the following properties hold:
i) We have that z = P C ( x ) z=P_C(x) z = P C ( x ) if and only if
( x − z ) ⊤ ( y − z ) ≤ 0 (x-z)^{\top}(y-z) \le0 ( x − z ) ⊤ ( y − z ) ≤ 0 for all y ∈ C y \in C y ∈ C .
ii) For all x , y ∈ R n x,y \in\mathbb{R}^{n} x , y ∈ R n ,
( x − y ) ⊤ ( P C ( x ) − P C ( y ) ) ≥ ∥ P C ( x ) − P C ( y ) ∥ 2 . (x-y)^{\top}(P_C(x)-P_C(y)) \ge\|P_C(x)-P_C(y)\|^{2}. ( x − y ) ⊤ ( P C ( x ) − P C ( y )) ≥ ∥ P C ( x ) − P C ( y ) ∥ 2 . iii) P C P_C P C is nonexpansive.
Lemma 26 i) follows from [8 Prop. 1.1.9] , while Lemma 26 ii) follows from [5 Prop. 4.8] . This property is called firm nonexpansiveness . Finally, Lemma 26 iii) simply follows from Lemma 26 ii) and the triangle inequality.
Proof of Proposition 14
Let x ∗ ∈ arg min x ∈ C f ( x ) x^* \in\arg\min_{x\in C} f(x) x ∗ ∈ arg min x ∈ C f ( x ) . By [8 Prop. 1.1.9] ,
∇ f ( x ∗ ) ⊤ ( y − x ∗ ) ≥ 0 \nabla f(x^*)^\top(y-x^*) \ge0 ∇ f ( x ∗ ) ⊤ ( y − x ∗ ) ≥ 0
for all y ∈ C y \in C y ∈ C . This implies that
( ( x ∗ − γ ∇ f ( x ∗ ) ) − x ∗ ) ⊤ ( y − x ∗ ) = − γ ∇ f ( x ∗ ) ⊤ ( y − x ∗ ) ≤ 0 \left((x^*-\gamma\nabla f(x^*))-x^*\right)^\top(y-x^*)=-\gamma\nabla f(x^*)^\top(y-x^*)\le0 ( ( x ∗ − γ ∇ f ( x ∗ )) − x ∗ ) ⊤ ( y − x ∗ ) = − γ ∇ f ( x ∗ ) ⊤ ( y − x ∗ ) ≤ 0
for all y ∈ C y \in C y ∈ C , showing that
x ∗ = P C ( x ∗ − γ ∇ f ( x ∗ ) ) , x^*=P_C(x^*-\gamma\nabla f(x^*)), x ∗ = P C ( x ∗ − γ ∇ f ( x ∗ )) ,
by Lemma 26 i). Now, let t ∈ N t\in\mathbb{N} t ∈ N and define
y t : = x t − γ ∇ f ( x t ) , y ∗ : = x ∗ − γ ∇ f ( x ∗ ) . y^t:=x^t-\gamma\nabla f(x^t),\qquad y^*:=x^*-\gamma\nabla f(x^*). y t := x t − γ ∇ f ( x t ) , y ∗ := x ∗ − γ ∇ f ( x ∗ ) .
Then x t + 1 = P C ( y t ) x^{t+1}=P_C(y^t) x t + 1 = P C ( y t ) and x ∗ = P C ( y ∗ ) x^*=P_C(y^*) x ∗ = P C ( y ∗ ) . Hence,
∥ ( y t − y ∗ ) − ( x t + 1 − x ∗ ) ∥ 2 = ∥ y t − y ∗ ∥ 2 − 2 ( y t − y ∗ ) ⊤ ( x t + 1 − x ∗ ) + ∥ x t + 1 − x ∗ ∥ 2 ≤ ∥ y t − y ∗ ∥ 2 − ∥ x t + 1 − x ∗ ∥ 2 , \left\|(y^t-y^*)-(x^{t+1}-x^*)\right\|^2=\|y^t-y^*\|^2-2(y^t-y^*)^\top(x^{t+1}-x^*)+\|x^{t+1}-x^*\|^2\le\|y^t-y^*\|^2-\|x^{t+1}-x^*\|^2, ( y t − y ∗ ) − ( x t + 1 − x ∗ ) 2 = ∥ y t − y ∗ ∥ 2 − 2 ( y t − y ∗ ) ⊤ ( x t + 1 − x ∗ ) + ∥ x t + 1 − x ∗ ∥ 2 ≤ ∥ y t − y ∗ ∥ 2 − ∥ x t + 1 − x ∗ ∥ 2 ,
where the last inequality follows from firm nonexpansiveness of P C P_C P C , see Lemma 26 ii). This shows that
∥ x t + 1 − x ∗ ∥ 2 + ∥ ( y t − y ∗ ) − ( x t + 1 − x ∗ ) ∥ 2 ≤ ∥ y t − y ∗ ∥ 2 . (59) \|x^{t+1}-x^*\|^2+\left\|(y^t-y^*)-(x^{t+1}-x^*)\right\|^2\le\|y^t-y^*\|^2. \tag*{(59)} ∥ x t + 1 − x ∗ ∥ 2 + ( y t − y ∗ ) − ( x t + 1 − x ∗ ) 2 ≤ ∥ y t − y ∗ ∥ 2 . (59)
Now,
y t − y ∗ = ( x t − x ∗ ) − γ ( ∇ f ( x t ) − ∇ f ( x ∗ ) ) . y^t-y^*=(x^t-x^*)-\gamma\left(\nabla f(x^t)-\nabla f(x^*)\right). y t − y ∗ = ( x t − x ∗ ) − γ ( ∇ f ( x t ) − ∇ f ( x ∗ ) ) .
Hence
∥ y t − y ∗ ∥ 2 = ∥ x t − x ∗ ∥ 2 + γ 2 ∥ ∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 − 2 γ ( x t − x ∗ ) ⊤ ( ∇ f ( x t ) − ∇ f ( x ∗ ) ) . \|y^t-y^*\|^2=\|x^t-x^*\|^2+\gamma^2\|\nabla f(x^t)-\nabla f(x^*)\|^2-2\gamma(x^t-x^*)^\top(\nabla f(x^t)-\nabla f(x^*)). ∥ y t − y ∗ ∥ 2 = ∥ x t − x ∗ ∥ 2 + γ 2 ∥∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 − 2 γ ( x t − x ∗ ) ⊤ ( ∇ f ( x t ) − ∇ f ( x ∗ )) .
By the Baillon–Haddad theorem (see, e.g. [4 Thm. 1.1] ),
( x t − x ∗ ) ⊤ ( ∇ f ( x t ) − ∇ f ( x ∗ ) ) ≥ 1 L ∥ ∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 , (x^t-x^*)^\top(\nabla f(x^t)-\nabla f(x^*))\ge\frac{1}{L}\|\nabla f(x^t)-\nabla f(x^*)\|^2, ( x t − x ∗ ) ⊤ ( ∇ f ( x t ) − ∇ f ( x ∗ )) ≥ L 1 ∥∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 ,
and thus,
∥ y t − y ∗ ∥ 2 ≤ ∥ x t − x ∗ ∥ 2 − γ ( 2 L − γ ) ∥ ∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 . \|y^t-y^*\|^2\le\|x^t-x^*\|^2-\gamma\left(\frac{2}{L}-\gamma\right)\|\nabla f(x^t)-\nabla f(x^*)\|^2. ∥ y t − y ∗ ∥ 2 ≤ ∥ x t − x ∗ ∥ 2 − γ ( L 2 − γ ) ∥∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 .
Therefore, it follows from (C1) that
∥ x t + 1 − x ∗ ∥ 2 + ∥ ( y t − y ∗ ) − ( x t + 1 − x ∗ ) ∥ 2 + γ ( 2 L − γ ) ∥ ∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 ≤ ∥ x t − x ∗ ∥ 2 . (60) \|x^{t+1}-x^*\|^2+\left\|(y^t-y^*)-(x^{t+1}-x^*)\right\|^2+\gamma\left(\frac{2}{L}-\gamma\right)\|\nabla f(x^t)-\nabla f(x^*)\|^2\le\|x^t-x^*\|^2. \tag*{(60)} ∥ x t + 1 − x ∗ ∥ 2 + ( y t − y ∗ ) − ( x t + 1 − x ∗ ) 2 + γ ( L 2 − γ ) ∥∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 ≤ ∥ x t − x ∗ ∥ 2 . (60)
Since γ ∈ ( 0 , 2 L ) \gamma\in\left(0,\frac{2}{L}\right) γ ∈ ( 0 , L 2 ) , this implies
∥ x t + 1 − x ∗ ∥ ≤ ∥ x t − x ∗ ∥ . \|x^{t+1}-x^*\|\le\|x^t-x^*\|. ∥ x t + 1 − x ∗ ∥ ≤ ∥ x t − x ∗ ∥.
Thus, ( x t ) t = 0 ∞ (x^t)_{t=0}^{\infty} ( x t ) t = 0 ∞ is bounded, and, moreover, the sequence ( ∥ x t − x ∗ ∥ ) t = 0 ∞ (\|x^t-x^*\|)_{t=0}^{\infty} ( ∥ x t − x ∗ ∥ ) t = 0 ∞ has a limit by the monotone convergence theorem.
Summing (C2) from t = 0 t=0 t = 0 to t = N t=N t = N yields
γ ( 2 L − γ ) ∑ t = 0 N ∥ ∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 ≤ ∥ x 0 − x ∗ ∥ 2 . \gamma\left(\frac{2}{L}-\gamma\right)\sum_{t=0}^{N}\|\nabla f(x^t)-\nabla f(x^*)\|^2\le\|x^0-x^*\|^2. γ ( L 2 − γ ) t = 0 ∑ N ∥∇ f ( x t ) − ∇ f ( x ∗ ) ∥ 2 ≤ ∥ x 0 − x ∗ ∥ 2 .
Hence,
∇ f ( x t ) − ∇ f ( x ∗ ) → 0. \nabla f(x^t)-\nabla f(x^*)\to0. ∇ f ( x t ) − ∇ f ( x ∗ ) → 0.
A similar summing argument also leads to
( y t − y ∗ ) − ( x t + 1 − x ∗ ) → 0. (y^t-y^*)-(x^{t+1}-x^*)\to0. ( y t − y ∗ ) − ( x t + 1 − x ∗ ) → 0.
Since
( y t − y ∗ ) − ( x t + 1 − x ∗ ) = ( x t − x t + 1 ) − γ ( ∇ f ( x t ) − ∇ f ( x ∗ ) ) , (y^t-y^*)-(x^{t+1}-x^*)=(x^t-x^{t+1})-\gamma(\nabla f(x^t)-\nabla f(x^*)), ( y t − y ∗ ) − ( x t + 1 − x ∗ ) = ( x t − x t + 1 ) − γ ( ∇ f ( x t ) − ∇ f ( x ∗ )) ,
we obtain
x t − x t + 1 → 0. x^t-x^{t+1}\to0. x t − x t + 1 → 0.
Because ( x t ) t = 0 ∞ (x^t)_{t=0}^{\infty} ( x t ) t = 0 ∞ is bounded, by Bolzano–Weierstrass it has a convergent subsequence ( x t j ) j = 0 ∞ (x^{t_j})_{j=0}^{\infty} ( x t j ) j = 0 ∞ , where 0 ≤ t 0 < t 1 < ⋯ 0\le t_0<t_1<\cdots 0 ≤ t 0 < t 1 < ⋯ . Denote the limit of this subsequence by x ˉ \bar{x} x ˉ . Since C C C is closed, x ˉ ∈ C \bar{x}\in C x ˉ ∈ C . Also, x t j + 1 → x ˉ x^{t_j+1}\to\bar{x} x t j + 1 → x ˉ , because x t − x t + 1 → 0 x^t-x^{t+1}\to0 x t − x t + 1 → 0 .
Taking the limit on both sides of
x t j + 1 = P C ( x t j − γ ∇ f ( x t j ) ) , x^{t_j+1}=P_C(x^{t_j}-\gamma\nabla f(x^{t_j})), x t j + 1 = P C ( x t j − γ ∇ f ( x t j )) ,
and using continuity of both P C P_C P C and ∇ f \nabla f ∇ f gives
x ˉ = P C ( x ˉ − γ ∇ f ( x ˉ ) ) . \bar{x}=P_C(\bar{x}-\gamma\nabla f(\bar{x})). x ˉ = P C ( x ˉ − γ ∇ f ( x ˉ )) .
Therefore, by Lemma 26 i),
∇ f ( x ˉ ) ⊤ ( y − x ˉ ) ≥ 0 \nabla f(\bar{x})^\top(y-\bar{x})\ge0 ∇ f ( x ˉ ) ⊤ ( y − x ˉ ) ≥ 0
for all y ∈ C y\in C y ∈ C . Since f f f is convex, it follows from [8 Prop. 1.1.8] that
x ˉ ∈ arg min x ∈ C f ( x ) . \bar{x}\in\arg\min_{x\in C}f(x). x ˉ ∈ arg x ∈ C min f ( x ) .
Finally, since we have derived (C2) for an arbitrary x ∗ ∈ arg min x ∈ C f ( x ) x^* \in\arg\min_{x\in C} f(x) x ∗ ∈ arg min x ∈ C f ( x ) , we also obtain
∥ x t + 1 − x ˉ ∥ ≤ ∥ x t − x ˉ ∥ \lVert x^{t+1}-\bar{x}\rVert\le\lVert x^t-\bar{x}\rVert ∥ x t + 1 − x ˉ ∥ ≤ ∥ x t − x ˉ ∥
for all t ∈ N t \in\mathbb{N} t ∈ N . Thus, the sequence ( a t ) t = 0 ∞ (a^t)_{t=0}^{\infty} ( a t ) t = 0 ∞ , defined by a t : = ∥ x t − x ˉ ∥ a^t := \lVert x^t-\bar{x}\rVert a t := ∥ x t − x ˉ ∥ for all t ∈ N t \in\mathbb{N} t ∈ N , is nonincreasing and bounded below. As such, by the monotone convergence theorem, a t → ℓ a^t \to\ell a t → ℓ for some ℓ ≥ 0 \ell\ge0 ℓ ≥ 0 . But along the subsequence, x t j → x ˉ x^{t_j} \to\bar{x} x t j → x ˉ , meaning that
a t j = ∥ x t j − x ˉ ∥ → 0. a^{t_j} = \lVert x^{t_j}-\bar{x}\rVert\to0. a t j = ∥ x t j − x ˉ ∥ → 0.
Hence ℓ = 0 \ell= 0 ℓ = 0 , and therefore
∥ x t − x ˉ ∥ → 0. \lVert x^t-\bar{x}\rVert\to0. ∥ x t − x ˉ ∥ → 0.
Thus x t → x ˉ ∈ arg min x ∈ C f ( x ) x^t \to\bar{x} \in\arg\min_{x\in C} f(x) x t → x ˉ ∈ arg min x ∈ C f ( x ) , proving the proposition.
Proof of Lemma 18
Property i) follows immediately from the fact that D ⊤ 1 = 0 D^\top\mathbf{1}=0 D ⊤ 1 = 0 , meaning that both F ( x + α 1 ) F(x+\alpha\mathbf{1}) F ( x + α 1 ) and F ( x ) + α 1 F(x)+\alpha\mathbf{1} F ( x ) + α 1 are equal to the output of the circuit, given the input x + α 1 x+\alpha\mathbf{1} x + α 1 . Since this output is unique, we have F ( x + α 1 ) = F ( x ) + α 1 F(x+\alpha\mathbf{1})=F(x)+\alpha\mathbf{1} F ( x + α 1 ) = F ( x ) + α 1 .
Next, we prove Property ii). Let x , y ∈ R N I x,y\in\mathbb{R}^{N_I} x , y ∈ R N I be such that x ⪯ y x\preceq y x ⪯ y . Define z ( t ) : = x + t ( y − x ) z(t):=x+t(y-x) z ( t ) := x + t ( y − x ) , where t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . Let p H O ( t ) ∈ R ∣ V H ∣ + N O p_{HO}(t)\in\mathbb{R}^{|V_H|+N_O} p H O ( t ) ∈ R ∣ V H ∣ + N O be the unique vector satisfying
\begin{bmatrix}D_H\\D_O\end{bmatrix}\nabla G\left(D_I^\top z(t)+\begin{bmatrix}D_H^\top&D_O^\top\end{bmatrix}p_{HO}(t)\right)=0, \tag*{(61)}\end{bmatrix}
for all t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . It follows by connectedness of G \mathcal{G} G , the properties of the co-content functions in (b), and the implicit function theorem [38 Thm. 9.28] that p H O p_{HO} p H O is continuously differentiable.
Due to Property (b), ∇ 2 G ( D ⊤ p ( t ) ) \nabla^2G(D^\top p(t)) ∇ 2 G ( D ⊤ p ( t )) is a diagonal positive definite matrix for all t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] . Now, let t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] and define the Laplacian matrix
L ( t ) : = D ∇ 2 G ( D ⊤ p ( t ) ) D ⊤ , where p ( t ) : = [ z ( t ) p H O ( t ) ] . L(t):=D\nabla^2G(D^\top p(t))D^\top,\qquad\text{where }p(t):=\begin{bmatrix}z(t)\\p_{HO}(t)\end{bmatrix}. L ( t ) := D ∇ 2 G ( D ⊤ p ( t )) D ⊤ , where p ( t ) := [ z ( t ) p H O ( t ) ] .
We partition the Laplacian as
L ( t ) = [ L 11 ( t ) L 12 ( t ) L 21 ( t ) L 22 ( t ) ] , L(t)=\begin{bmatrix}L_{11}(t)&L_{12}(t)\\L_{21}(t)&L_{22}(t)\end{bmatrix}, L ( t ) = [ L 11 ( t ) L 21 ( t ) L 12 ( t ) L 22 ( t ) ] ,
where
L 11 ( t ) ∈ R N I × N I L_{11}(t)\in\mathbb{R}^{N_I\times N_I} L 11 ( t ) ∈ R N I × N I ,
L 12 ( t ) = L 21 ( t ) ⊤ ∈ R N I × ( ∣ V H ∣ + N O ) L_{12}(t)=L_{21}(t)^\top\in\mathbb{R}^{N_I\times(|V_H|+N_O)} L 12 ( t ) = L 21 ( t ) ⊤ ∈ R N I × ( ∣ V H ∣ + N O ) , and
L 22 ( t ) ∈ R ( ∣ V H ∣ + N O ) × ( ∣ V H ∣ + N O ) L_{22}(t)\in\mathbb{R}^{(|V_H|+N_O)\times(|V_H|+N_O)} L 22 ( t ) ∈ R ( ∣ V H ∣ + N O ) × ( ∣ V H ∣ + N O ) .
In view of (D1), we obtain
0 = d d t [ D H D O ] ∇ G ( D ⊤ p ( t ) ) = [ D H D O ] ∇ 2 G ( D ⊤ p ( t ) ) D ⊤ p ′ ( t ) = L 21 ( t ) z ′ ( t ) + L 22 ( t ) p H O ′ ( t ) . (62) \begin{aligned}
0&=\frac{d}{dt}\begin{bmatrix}D_H\\D_O\end{bmatrix}\nabla G(D^\top p(t))\\
&=\begin{bmatrix}D_H\\D_O\end{bmatrix}\nabla^2G(D^\top p(t))D^\top p'(t)\\
&=L_{21}(t)z'(t)+L_{22}(t)p'_{HO}(t). \tag*{(62)}
\end{aligned} 0 = d t d [ D H D O ] ∇ G ( D ⊤ p ( t )) = [ D H D O ] ∇ 2 G ( D ⊤ p ( t )) D ⊤ p ′ ( t ) = L 21 ( t ) z ′ ( t ) + L 22 ( t ) p H O ′ ( t ) . (62)
Now, Since G \mathcal{G} G is connected, the matrix [ D H D O ] \begin{bmatrix}D_H\\D_O\end{bmatrix} [ D H D O ] has full row rank, and thus L 22 ( t ) L_{22}(t) L 22 ( t ) is an invertible M M M -matrix. It follows from [7 Ch. 6, Fact N38] that L 22 − 1 ( t ) L_{22}^{-1}(t) L 22 − 1 ( t ) only has nonnegative entries. Furthermore, since L 21 ( t ) L_{21}(t) L 21 ( t ) is an off-diagonal block of the Laplacian matrix, it contains only nonpositive entries. Hence, the matrix − L 22 − 1 ( t ) L 21 ( t ) -L_{22}^{-1}(t)L_{21}(t) − L 22 − 1 ( t ) L 21 ( t ) is entry-wise nonnegative. Now, since z ′ ( t ) = y − x z'(t)=y-x z ′ ( t ) = y − x , we obtain by (D2) that
p H O ′ ( t ) = − L 22 − 1 ( t ) L 21 ( t ) ( y − x ) . p'_{HO}(t)=-L_{22}^{-1}(t)L_{21}(t)(y-x). p H O ′ ( t ) = − L 22 − 1 ( t ) L 21 ( t ) ( y − x ) .
Integrating this expression from t = 0 t=0 t = 0 to t = 1 t=1 t = 1 gives
p H O ( 1 ) − p H O ( 0 ) = − L 22 − 1 ( t ) L 21 ( t ) ( y − x ) . p_{HO}(1)-p_{HO}(0)=-L_{22}^{-1}(t)L_{21}(t)(y-x). p H O ( 1 ) − p H O ( 0 ) = − L 22 − 1 ( t ) L 21 ( t ) ( y − x ) .
Using entry-wise nonnegativity of both − L 22 − 1 ( t ) L 21 ( t ) -L_{22}^{-1}(t)L_{21}(t) − L 22 − 1 ( t ) L 21 ( t ) and y − x y-x y − x yields p H O ( 0 ) ⪯ p H O ( 1 ) p_{HO}(0)\preceq p_{HO}(1) p H O ( 0 ) ⪯ p H O ( 1 ) . In particular, by focusing on the last N O N_O N O entries, and using the facts that z ( 0 ) = x z(0)=x z ( 0 ) = x and z ( 1 ) = y z(1)=y z ( 1 ) = y , we obtain
F ( x ) ⪯ F ( y ) . F(x)\preceq F(y). F ( x ) ⪯ F ( y ) .
This proves the lemma.
Proof of Lemma 23
We will only show the proof for smax λ \operatorname{smax}_{\lambda} smax λ . The proof for smin λ \operatorname{smin}_{\lambda} smin λ follows analogously. To prove the first statement of the lemma, let λ > 0 \lambda>0 λ > 0 and x ∈ R n x\in\mathbb{R}^n x ∈ R n . Define M : = max i ∈ [ n ] x i M:=\max_{i\in[n]}x_i M := max i ∈ [ n ] x i . Then, obviously,
1 n ∑ i = 1 n e λ x i ≤ e λ M . \frac{1}{n}\sum_{i=1}^{n}e^{\lambda x_i}\le e^{\lambda M}. n 1 i = 1 ∑ n e λ x i ≤ e λ M .
By taking natural logarithms, smax λ ( x ) ≤ M \operatorname{smax}_{\lambda}(x)\le M smax λ ( x ) ≤ M . On the other hand, since M = x i M=x_i M = x i for some index i ∈ [ n ] i\in[n] i ∈ [ n ] ,
1 n ∑ i = 1 n e λ x i ≥ 1 n e λ M , \frac{1}{n}\sum_{i=1}^{n}e^{\lambda x_i}\ge\frac{1}{n}e^{\lambda M}, n 1 i = 1 ∑ n e λ x i ≥ n 1 e λ M ,
and thus,
smax λ ( x ) ≥ 1 λ ( λ M − ln ( n ) ) = M − ln ( n ) λ . \operatorname{smax}_{\lambda}(x) \ge\frac{1}{\lambda}(\lambda M-\ln(n))=M-\frac{\ln(n)}{\lambda}. smax λ ( x ) ≥ λ 1 ( λ M − ln ( n )) = M − λ ln ( n ) .
We conclude that
M − ln ( n ) λ ≤ smax λ ( x ) ≤ M , M-\frac{\ln(n)}{\lambda}\le\operatorname{smax}_{\lambda}(x)\le M, M − λ ln ( n ) ≤ smax λ ( x ) ≤ M ,
showing that
∣ smax λ ( x ) − M ∣ ≤ ln ( n ) λ . \left|\operatorname{smax}_{\lambda}(x)-M\right|\le\frac{\ln(n)}{\lambda}. ∣ smax λ ( x ) − M ∣ ≤ λ ln ( n ) .
Now, to prove (48) , let x , y ∈ R n x,y\in\mathbb{R}^{n} x , y ∈ R n and define d : = ∥ x − y ∥ ∞ d:=\lVert x-y\rVert_{\infty} d := ∥ x − y ∥ ∞ . Then, obviously, y − d 1 ⪯ x ⪯ y + d 1 y-d\mathbf{1}\preceq x\preceq y+d\mathbf{1} y − d 1 ⪯ x ⪯ y + d 1 . It follows from the definition of smax λ \operatorname{smax}_{\lambda} smax λ that smax λ ( u ) ≤ smax λ ( v ) \operatorname{smax}_{\lambda}(u)\le\operatorname{smax}_{\lambda}(v) smax λ ( u ) ≤ smax λ ( v ) for all u , v ∈ R n u,v\in\mathbb{R}^{n} u , v ∈ R n such that u ⪯ v u\preceq v u ⪯ v . Therefore,
smax λ ( y − d 1 ) ≤ smax λ ( x ) ≤ smax λ ( y + d 1 ) . \operatorname{smax}_{\lambda}(y-d\mathbf{1})\le\operatorname{smax}_{\lambda}(x)\le\operatorname{smax}_{\lambda}(y+d\mathbf{1}). smax λ ( y − d 1 ) ≤ smax λ ( x ) ≤ smax λ ( y + d 1 ) .
Furthermore, for all α ∈ R \alpha\in\mathbb{R} α ∈ R ,
smax λ ( y + α 1 ) = 1 λ ln ( 1 n ∑ i = 1 n e λ ( y i + α ) ) , \operatorname{smax}_{\lambda}(y+\alpha\mathbf{1})=\frac{1}{\lambda}\ln\left(\frac{1}{n}\sum_{i=1}^{n}e^{\lambda(y_i+\alpha)}\right), smax λ ( y + α 1 ) = λ 1 ln ( n 1 i = 1 ∑ n e λ ( y i + α ) ) ,
which is equal to
1 λ ln ( e λ α 1 n ∑ i = 1 n e λ y i ) = smax λ ( y ) + α . \frac{1}{\lambda}\ln\left(e^{\lambda\alpha}\frac{1}{n}\sum_{i=1}^{n}e^{\lambda y_i}\right)=\operatorname{smax}_{\lambda}(y)+\alpha. λ 1 ln ( e λ α n 1 i = 1 ∑ n e λ y i ) = smax λ ( y ) + α .
Hence,
smax λ ( y ) − d ≤ smax λ ( x ) ≤ smax λ ( y ) + d . \operatorname{smax}_{\lambda}(y)-d\le\operatorname{smax}_{\lambda}(x)\le\operatorname{smax}_{\lambda}(y)+d. smax λ ( y ) − d ≤ smax λ ( x ) ≤ smax λ ( y ) + d .
This shows that
∣ smax λ ( x ) − smax λ ( y ) ∣ ≤ d = ∥ x − y ∥ ∞ , \left|\operatorname{smax}_{\lambda}(x)-\operatorname{smax}_{\lambda}(y)\right|\le d=\lVert x-y\rVert_{\infty}, ∣ smax λ ( x ) − smax λ ( y ) ∣ ≤ d = ∥ x − y ∥ ∞ ,
proving the lemma.