\section{Introduction}
\label{sec:intro}

A $k$-uniform hypergraph $H$ consists of a set of vertices $V(H)$ and a
collection $E(H)$ of $k$-element subsets of $V(H)$, called hyperedges.
For a $k$-uniform hypergraph $H$, a map $c: V(H) \to [k]$ is called a
\emph{$k$-colouring} of $H$, where $[k]:=\{1,\ldots,k\}$. The colouring $c$ is called \emph{rainbow-free} if for every hyperedge
$e=(v_1,\ldots,v_k)\in E(H)$ we have $c(e)=\{c(v_1),\ldots,c(v_k)\}\neq [k]$ and
for every $i\in [k]$ there is $v\in V(H)$ with $c(v)=i$.

The \emph{$k$-rainbow-free} problem is to determine whether a given $k$-uniform
hypergraph is rainbow-free colourable with $k$ colours.\footnote{The
\emph{$k$-rainbow-free} problem is called \emph{$k$-no-rainbow-colouring}
in~\cite{survey}. For $k=2$, a graph is rainbow-free 2-colourable if and only if
it is disconnected (cf. Remark~\ref{rem:smallk}).}

\paragraph{Contributions}

We initiate the study of $k$-rainbow-free colourings on random hypergraphs. We
consider a natural generalisation of \Erdos-R\'enyi random graphs to random
($k$-uniform) hypergraphs: each possible hyperedge is present with a fixed
probability, independently of the other hyperedges.
In Section~\ref{sec:threshold}, we find a threshold function for the event that
a random hypergragraph of the first kind is rainbow-free colourable
(Theorem~\ref{thm:threshold}). The proof uses a second moment argument for the
lowerbound and a first moment argument with an analysis of possible types of
rainbow-free colourings for the upperbound.

\paragraph{Related work}

The $k$-rainbow-free problem is a special case of colouring mixed hypergraphs,
introduced by Voloshin~\cite{mixed_hypergraph_first} and further extended by
Kr\'al', Kratochv\'il, Proskurowski, and Voss~\cite{mixed_hypertrees}. A mixed
hypergraph is a triple $(V,C,D)$ where $V$ is the vertex set and $C$ and $D$ are
collections of subsets of $V$. A colouring of the vertices of a mixed hypergraph
$(V,C,D)$ is called proper if each hyperedge in $C$ contains two vertices of the
same colour and each hyperedge in $D$ contains two vertices of different
colours. The \emph{strict $k$-colouring} problem is to determine whether a given
mixed hypergraph is properly colourable with exactly $k$ colours. The strict
$k$-colouring problem restricted to $k$-uniform mixed hypergraphs with
$D=\emptyset$, so-called co-hypergraphs, is precisely the $k$-rainbow-free
problem. The strict $k$-colouring of co-hypergraphs was later identified, under
the name of \emph{$k$-no-rainbow-colouring}, in the survey by Bodirsky, K\'ara,
and Martin~\cite{survey} as an interesting case of unknown complexity of
\emph{surjective} constraint satisfaction problems on a three-element domain.

Constraint satisfaction problems (CSPs) are generalisations of graph
homomorphisms~\cite{Hell:graphs}. A graph homomorphism from $G$ to $H$ is a map
from the vertex set of $G$ to the vertex set of $H$ that preserves all edges
(but not necessarily non-edges). For a fixed graph $H$, the
\emph{$H$-coulouring} problems is to determine whether a given graph $G$ admits
a homomorphism to $H$. For instance, taking $H=K_3$ to be the complete graph on
$3$ vertices, $H$-colouring is the well known $3$-colouring problem.
Hell and Ne\v{s}et\v{r}il established that, unless $H$
contains a loop or is a bipartite graph, the $H$-colouring problem is
NP-complete~\cite{complexity_H_colouring}.

In an influential paper, Feder and Vardi conjectured that a similar dichotomy
holds for every \emph{digrapgh} $H$, or equivalently, for every finite
relational structure (such as hypergraphs)~\cite{feder_vardi_conjecture}. This
conjecture, known as the CSP dichotomy conjecture, was confirmed by two
independent papers by Bulatov~\cite{Bulatov17:focs} and Zhuk~\cite{Zhuk17:focs},
respectively. While the recent progress on the CSP dichotomy conjecture (and
various CSP variants) relied heavily on the so-called algebraic
approach~\cite{Bulatov05:classifying}, this method does not seem direclty
amenable to \emph{surjective} CSPs, in which we require the homomorphism be
surjective. A dichotomy theorem is known to hold for surjective CSPs on
two-element domains by the work of Creignou and H\'ebrard~\cite{Creignou97}. The
$k$-rainbow-free problem is equivalent to a surjective CSP on a $k$-element domain $[k]$
with a single $k$-ary relation $[k]^k - \{(x_1,\ldots,x_k): x_1,\ldots,x_k
\mbox{ distinct}\}$. Very recently, Zhuk has announced NP-hardness of the
$k$-rainbow-free problem for $k\geq 3$~\cite{Zhuk20:arxiv}.

\section{Preliminaries}
\label{sec:prelim}

If $k$ is clear from the context, we will call a $k$-colouring simply a
colouring. For a colouring $c$ of a $k$-uniform hypergraph, we denote the colour
classes by $C_i:=c^{-1}(i)$, $i\in[k]$.

We state now same basic properties of rainbow-free colourings.

\begin{definition}\label{def:induced}
  Given a $k$-uniform hypergraph $H$ and a subset of vertices $S\subseteq V(H)$,
  we define the \emph{induced subhypergraph} $H_S$ as the $(k-1)$-uniform
  hypergraph with vertices $V(H_S):=V(H)\setminus S$ and hyperedges $E(H_S) :=
  \{e\cap (V(H)\setminus S) \mid e\in E(H)\text{ and } |e\cap S|=1\}$.

	For up to $k$ disjoint sets $S_1,\dots S_\ell\subseteq V(H)$ we write
    $H_{S_1,\dots,S_\ell}:=((H_{S_1})\dots)_{S_\ell}$ for the repeated induced subhypergraph.
\end{definition}

For $k=3$ in Definition~\ref{def:induced}, $H_S$ will be a graph.
Furthermore, note that the order of the subscripts in the definition of the
repeated induced subhypergraph does not matter.

This notion of induced subhypergraphs is useful because of the following proposition.

\begin{proposition}\label{prop:reduction}
	Let $k\geq 2$ be an integer.
  A $k$-uniform hypergraph $H$ is rainbow-free $k$-colourable if and only if there exists a non-empty subset of vertices
	$\emptyset\neq S\subsetneq V(H)$ such that the $(k-1)$-uniform hypergraph $H_S$
  is rainbow-free $(k-1)$-colourable.
	In particular, this implies the existence of a colouring $c$ of $H$ with $C_k = S$.
\end{proposition}

\begin{proof}
	First suppose that $H$ has a rainbow-free $k$-colouring $c$.
	Let $S$ be $C_k\neq \emptyset$ and consider $H_S$.
	Write $c'$ for the colouring $c$ restricted to $V(H_S) = V(H) \setminus C_k$.
  We will show that $c'$ is indeed a rainbow-free $(k-1)$-colouring of $H_S$.
	First note that $C'_1\cup \dots\cup C'_{k-1} = V(H_S)$,
	and hence every vertex of $H_S$ has a well-defined colour in $[k-1]$.
	Now consider a hyperedge $e'\in E(H_S)$.
	By definition we have $e' = V(H_S) \cap e$ for some $e\in E(H)$.
	We will use a proof by contradiction to show that $c'(e') \neq [k-1]$,
	so assume that $c'(e') = [k-1]$. This implies $[k-1]=c(e') \subseteq c(e)$.
	Furthermore we know that $e\cap S= e\cap C_k\neq \emptyset$, and hence $k\in c(e)$.
	This implies that $c(e) = [k-1]\cup \{k\} = [k]$, which is a contradiction.
	We conclude that $c'(e) \neq [k-1]$ and hence $C'$ is a rainbow-free colouring of $H_S$, as required.

	For the other direction assume that $\emptyset \neq S\subsetneq V(H)$ is such that $H_S$
  has a rainbow-free $(k-1)$-colouring $c'$.
	Now extend $c'$ to a $k$-colouring $c$ of $H$ by setting $c(v) = k$ for all $v\in S$.
	Thus, we have $C_k = S$.
	Let $e$ be a hyperedge in $H$.
	We wish to show that $c(e) \neq [k]$, so that $c$ is a rainbow-free colouring indeed.
	If $|e\cap S|=0$ we have $k\notin c(S)$.
	In the $|e\cap S|=1$ case we have $e' := e\cap (V(H)\setminus S) \in E(H_S)$.
  Since $c'$ is a rainbow-free $(k-1)$-colouring of $H_S$ we know that $c(e') = c'(e') \neq [k-1]$.
	Adding in the one vertex $v$ of $e$ that is in $S=C_k$,
	we get $c(e) = c(e' \cup \{v\}) \neq [k-1]\cup\{k\} = [k]$, as required.
	If $|e\cap S|\geq 2$ there are at most $k-2$ vertices that have a colour in $[k-1]$.
	Since $k-2 < |[k-1]|$ we know that $c(e')$ can not attain all colours in $[k-1]$.
	Hence, this case also implies $c(e)\neq [k]$.
\end{proof}

By induction, it follows that we can apply multiple steps of
Proposition~\ref{prop:reduction} at once.

\begin{corollary}\label{cor:reduction2}
	Let $2\leq \ell<k$ be integers.
	A $k$-uniform hypergraph $H$ is rainbow-free $k$-colourable if and only if
	there exist disjoint non-empty subsets $S_1, \dots, S_\ell$ of $V(H)$ such
	that $H_{S_1,\dots, S_\ell}$ is rainbow-free $(k-\ell)$-colourable.
\end{corollary}

\begin{remark}\label{rem:smallk}
We remark that Proposition~\ref{prop:reduction} also applies to the corner case of $k=2$.
In particular, a graph $H$ is rainbow-free $2$-colourable if and only if there is a subset $S\subsetneq V(H)$ with no outgoing edges; in other words, $H$ is disconnected.
\end{remark}

If all possible rainbow-free hyperedges are
given, not only do we know that the rainbow-free colouring is unique, but we can
also easily find it.

\begin{proposition}
	\label{prop:all_edges}
  Suppose that $H$ is a $k$-uniform hypergraph with a surjective colouring
  $c:V(H)\to[k]$.
	Furthermore assume that $E=\{e\in V^{(k)}\mid c(e)\neq [k]\}$ consists of
  all rainbow-free hyperedges.
	Write $\overline E:=V^{(k)} \setminus E$ for the set of rainbow hyperedges with $c(e)=[k]$.
	The colour classes of $c$ are determined by
    $C_{c(v)}:=\{v\} \cup \{u \in V \mid\forall e\in \overline E: \{u,v\}\nsubseteq e\}$.
\end{proposition}

\begin{proof}
	If $\{u,v\}\subseteq e$ for some $e\in \overline E$,
	we have that $c(u)\neq c(v)$, since $e$ would be a rainbow-free
  hyperedge otherwise.

	For the other direction assume that $c(u)\neq c(v)$.
	By surjectivity of $c$, all colour classes are non-empty and hence there
  exists a vertex $x_j$ for every colour
	$j$ in $[k]-\{c(u),c(v)\}$.
	Using these vertices $x_j$ together with $u$ and $v$ yields a rainbow hyperedge,
	which is an element of $\overline E$.
	Hence there exists a rainbow hyperedge $e\in \overline E$ containing both $u$ and $v$.
  This implies that the condition from the statement of the proposition is both sufficient and necessary.
\end{proof}

\section{Random hypergraphs}
\label{sec:threshold}

The following definition of random hypergraphs is a direct generalisation of the
\Erdos-R\'enyi random graph model: every possible hyperedge is added with a
given probability.

\begin{definition}
	Let $p : \mathbb N \to [0,1]$ be a given probability function.
	A \emph{random $k$-uniform hypergraph} $H^k_{n,p}$ is a $k$-uniform hypergraph created by the following process:
	\begin{itemize}
    \item Start with a set of vertices $V(H^k_{n,p}):=V$ with $|V|=n$.
    \item For each hyperedge $e\in V^{(k)}$, add $e$ to $E(H^k_{n,p})$ with probability $p=p(n)$.
	\end{itemize}
\end{definition}

Let $A$ be a hypergraph property (in our case being rainbow-free colourable). We
write $\mathop{{}\rm\bf Pr}\nolimits[H^k_{n,p}\models A]$ for the probability that $H^k_{n,p}$ satisfies
$A$. A function $r(n)$ is called a \emph{threshold function} for a hypergraph
property $A$ if (i) when $p(n)\ll r(n)$, $\lim_{n\to\infty}\mathop{{}\rm\bf Pr}\nolimits[H^k_{n,p}\models
A]=0$, (ii) when $p(n)\gg r(n)$, $\lim_{n\to\infty}\mathop{{}\rm\bf Pr}\nolimits[H^k_{n,p}\models A]=1$, or
vice versa.

Our main result is the following theorem.

\begin{theorem}
	\label{thm:threshold}
	The function $p^*=(k-1)(\ln n)/n$ is a threshold function for the event that a random $k$-uniform
	hypergraph $H^k_{n,p}$ is rainbow-free colourable.
\end{theorem}

The two parts of the proof, one for small $p$ and one for large $p$, are covered
by the following two lemmas. The result is well known for
$k=2$~\cite[Theorem~VII.9]{Bollobas} and corresponds to disconnectedness (cf.
Remark~\ref{rem:smallk}). Hence we will assume $k\geq 3$.

\begin{lemma}
	\label{lem:small_p}
	For $k\geq 3$, the random hypergraph $H^k_{n,p}$
	is rainbow-free colourable with high probability if $p\leq D\frac{\ln n}n$ for some $D<k-1$.
\end{lemma}
\begin{lemma}
	\label{lem:large_p}
	If $p\geq D(\ln n)/n$ with $D>k-1$ and $k\geq 3$,
	the random hypergraph $H^k_{n,p}$ is not rainbow-free colourable with high probability.
\end{lemma}

  In order to prove Lemma~\ref{lem:small_p}, we use the second moment method;
  i.e, use the second moment of a random variables to bound the probability that
  the variable is far from its mean.

  Let $X$ be a nonnegative integer-valued random variable such that
  $X=\sum_{i=1}^m X_i$, where $X_i$ is the indicator variable for event $E_i$.
  For indices $i,j$ write $i\sim j$ if $i\neq j$ and the events $E_i$ and $E_j$
  are \emph{not} independent. We set (the sum is over ordered pairs)
  \[
    \Delta = \sum_{i\sim j} \mathop{{}\rm\bf Pr}\nolimits[E_i \wedge E_j].
  \]

  \begin{proposition}[\protect{\cite[Corollary~4.3.4]{the_prob_method}}]
    \label{prop:alon}
    If $\mathop{{}\rm\bf E}\nolimits[X]\to\infty$ and $\Delta=o(\mathop{{}\rm\bf E}\nolimits[X]^2)$ then $\mathop{{}\rm\bf Pr}\nolimits[X>0]\to 1$.
  \end{proposition}

\begin{proof}[Proof of Lemma \ref{lem:small_p}]
  Let $H^k_{n,p}$ be a random hypergraph and let $X$ be the number of
  rainbow-free colourings of $H^k_{n,p}$ with only one colour class of size larger than
  one. Our goal is to show that $X>0$ with high probability, and
  thus $H^k_{n,p}$ is rainbow-free colourable with high probability. We will do so by
  invoking Proposition~\ref{prop:alon}.

	We first show that $\mathop{{}\rm\bf E}\nolimits[X]$ goes to infinity.

	Let $c$ be a colouring of $H^k_{n,p}$ that uses all $k$ colours and has only one colour class
  of size greater than $1$.
	We assume that $|C_i|=1$ for $1\leq i\leq k-1$ and $|C_k|=n-k+1$.
	This colouring $c$ is rainbow-free if and only if there are no hyperedges covering all $k$ colour classes.
	There are $1\cdot \dots \cdot 1 \cdot (n-k+1) = n-k+1$ hyperedges with this property, and hence
	\begin{equation*}
		\mathop{{}\rm\bf Pr}\nolimits[c\text{ is a rainbow-free colouring}] = (1-p)^{n-k+1} = \Theta((1-p)^n).
	\end{equation*}
	Since $\ln (1+x) = x + O(x^2)$ for small $x$, we have $1-p = e^{-p + O(p^2)}$ and thus
	\begin{equation*}
		\mathop{{}\rm\bf Pr}\nolimits[c\text{ is a rainbow-free colouring}]
		=\Theta\parens*{e^{-pn + O(p^2n)}}
		=\Theta\parens*{ e^{-D\ln n + O\parens*{D^2(\ln n)^2/n}}}
		= \Theta(n^{-D}).
	\end{equation*}
	The number of colourings $c$ with one large colour class of size $n-k+1$ is $\binom n{n-k+1} =
	\Theta(n^{k-1})$.
	The expected number of such colourings that are rainbow-free is now given by
	\begin{equation*}
		\mathop{{}\rm\bf E}\nolimits[X] = \binom n{n-k+1} (1-p)^{n-k+1} = \Theta(n^{k-1} n^{-D}) = \Theta(n^{k-1-D}).
	\end{equation*}
	Since $D<k-1$, this implies that $\mathop{{}\rm\bf E}\nolimits[X]\to\infty$ when $n\to\infty$.

  \medskip
  Enumerate all possible colourings $c$ (up to permutations of colours)
	satisfying $|C_k| = n-k+1$ by $c^1$ up to $c^\ell$.
	We write $i\sim j$ if $i\neq j$ and $|C^i_k\cap C^j_k|=n-k$.
  %
	\begin{figure}
		\centering
\begin{tikzpicture}[framed,inner frame xsep=5mm,scale=1.0]
	\tikzset{venn circle/.style={draw,circle,minimum width=5cm}}
	\tikzset{dot/.style={draw,circle,minimum width=1mm,fill=red,color=#1}}

	\node [venn circle] (AM) at (0,0) {};
	\node [venn circle] (BM) at (0,1.5cm) {};
  \node [align=center,above=1.0cm] at (BM) {$A=C^i_k\setminus C^j_k$\\[1mm]$2\leq |A|\leq k$};
  \node [align=center,below=1.0cm] at (AM) {$B=C^j_k\setminus C^i_k$\\[1mm]$2\leq |B|\leq k$};
	\node [align=center] at (0,0.75cm) {$|C^i_k\cap C^j_k| \leq n-k-1$};
  \node [align=right]  at (3.4,-2.3) {$R=V\setminus C^i_k\setminus C^j_k$\\[1mm]$|R|\leq k-3$};
	\node  at (3.6,3.8) {$|V|=n$};
\end{tikzpicture}

\caption{This Venn diagram shows the sets $C^i_k$ (the upper circle) and $C^j_k$ (the lower circle) from the proof of Lemma~\ref{lem:small_p}, along with the definitions of $A$, $B$, and $R$. We have $|C^i_k| = |C^j_k| = n-k+1$ and $|C^i_\ell| = |C^j_\ell|=1$ for all $1\leq \ell<k$.} \label{fig:4_venn}
\end{figure}
	To every colouring $c^i$ we associate the event $E_i$ that $c^i$ is rainbow-free.

 Consider the quantity
  \begin{equation}\label{def:delta}
    \Delta = \sum_{i\sim j} \mathop{{}\rm\bf Pr}\nolimits[E_i \wedge E_j].
	\end{equation}

	We will prove that $\Delta = o(\mathop{{}\rm\bf E}\nolimits[X]^2)$ and
  and thus finish the proof by Proposition~\ref{prop:alon}. In order for
  Proposition~\ref{prop:alon} to be applicable, we need that (for $i\neq j$) $i\sim j$ if the events $E_i$ and $E_j$ are not independent.

  By the definition of $\sim$, we have
	\begin{equation*}
		\Delta = \sum_{i} \sum_{\substack{j\neq i\\ |C^i_k\cap C^j_k|=n-k}} \mathop{{}\rm\bf Pr}\nolimits[E_i \wedge E_j].
	\end{equation*}

  We claim that the event $E_i$ is independent from $E_j$ if $i\neq j$ and $i\nsim j$.
	In this case, the overlap between $C^i_k$ and $C^j_k$ is at most $n-k-1$,
	since an overlap of $n-k$ implies $i\sim j$ and an overlap of $n-k+1$ implies equality.
	Write $A= C^i_k \setminus C^j_k$, $B=C^j_k \setminus C^i_k$, and
  $R=V(H^k_{n,p}) \setminus C^i_k \setminus C^j_k$,
	as is illustrated in Figure~\ref{fig:4_venn}.
  The colouring $c^i$ is rainbow-free if all hyperedges of the form $e_1 = B\cup R\cup
  \{x\}$ for $x\in C^i_k$
	are not present.
  On the other hand, the colouring $c^j$ is rainbow-free if all hyperedges $e_2=A\cup R\cup\{y\}$ for $y\in C^j_k$ are not
	present.
	We have that $|A| = |C^i_k| - |C^i_k \cap C^j_k| \geq (n-k+1) - (n-k-1) = 2$.
	Similarly we have $|B|\geq 2$.
	Since $A$ is disjoint from $B$, we now know that the hyperedges $e_1$ and $e_2$ can not be equal.
	Hence, the colourings $c^i$ and $c^j$ depend on different hyperedges being present,
	and thus these events are independent indeed.

	Let $i$ and $j$ be such that $i\sim j$; i.e., $i\neq j$ and $|C^i_k\cap C^j_k|=n-k$. In this
  case, we have $|A|=|B|=1$.
  The hyperedges that the events $E_i$ and $E_j$ depend on are of the form $A\cup R\cup \{x\}$ for $x\in C^i_k$
  and $B\cup R\cup \{y\}$ for $y\in C^j_k$ respectively.
	We count $2\cdot(n-k+1)$ hyperedges in total, but the hyperedge $A\cup R\cup B$ is counted twice.
	Hence, the probability that $c^i$ and $c^j$ are both rainbow-free colourings is
	\begin{equation*}
		\mathop{{}\rm\bf Pr}\nolimits[E_i \wedge E_j] = (1-p)^{2(n-k+1)-1} \leq e^{-p(2n-2k+1)} = \Theta(e^{-2pn}).
	\end{equation*}
	Given $c^i$ with $|C^i_k|=n-k+1$, the number of colourings $c^j$ such that the large colour classes
	overlap in $n-k$ positions is $(n-k+1)(k-1)$. Putting this back in $\Delta$ gives
	\begin{align*}
		\Delta
		&= \sum_i (n-k+1)(k-1) (1-p)^{2n-2k+1}\nonumber\\
		&\leq \binom n{n-k+1} (n-k+1)(k-1) e^{-p(2n-2k+1)}\nonumber\\
		&\leq n^{k-1} \cdot n \cdot k \cdot e^{-2D\ln n + O((\ln n)/n)}\nonumber\\
		&=O( n^k\cdot  n^{-2D})
		= O(n^{k-2D}).\label{eq:delta}
	\end{align*}
	Since $k\geq 3$ we have $0 < k-2$ and hence $k-2D < 2k-2-2D = 2(k-1-D)$.
	We conclude that
	\begin{equation*}
		\Delta = O(n^{k-2D}) = o(n^{2(k-1-D)})
	\end{equation*}
	and thus $\Delta = o(\mathop{{}\rm\bf E}\nolimits[X]^2)$.
\end{proof}

We will now prove the bound in the other direction, Lemma~\ref{lem:large_p}.
\begin{proof}[Proof of Lemma~\ref{lem:large_p}]
	We use the first moment method to show that the expected number of
  rainbow-free colourings of $H^k_{n,p}$ goes to
	$0$.
	We identify a colouring by the sequence $(s_1,\dots,s_k)$ where $s_i = |C_i|$
  and $s_1\leq \dots \leq s_k$.
	We divide the set of all possible sequences into five types:
	\begin{enumerate}
		\item \label{type1}
			$(s_i)_i = (1,\dots,1,n-k+1)$. There is one such sequence.
		\item \label{type2}
			$(s_i)_i = (1,\dots,1,2,n-k)$. There is one such sequence.
		\item \label{type3}
			$(s_i)_i = (1,\dots,1,x,n-k+2-x)$ with $x\geq 3$. This case contains $O(n)$ sequences.
		\item \label{type4}
			$2\leq s_{k-2}\leq s_{k-1}$ and $s_1+\dots+s_{k-1}\leq 6k$.
			This case contains $O(1)$ sequences, since $k$ is a constant.
		\item \label{type5}
			$2\leq s_{k-2}\leq s_{k-1}$ and $s_1+\dots+s_{k-1}> 6k$.
			This case contains $O(n^{k-1})$ sequences.
	\end{enumerate}
	In each case we will show that the expected number of rainbow-free colourings of the relevant type is $o(1)$, from
	which it follows that the probability that $H^k_{n,p}$ is rainbow-free colourable is $o(1)$.

	Before starting calculations, we introduce some notation.
	We write $\Sigma=  s_1 + \dots + s_{k-1}$ so that $s_k = n - \Sigma \geq n/k$,
	and we write $\Pi = s_1\cdots s_{k-1}$.

	A colouring is rainbow-free if none of the $s_1\cdots s_k$ hyperedges that span all colour classes is present.
	This happens with probability
	\begin{equation*}
		\mathop{{}\rm\bf Pr}\nolimits[c \text{ is rainbow-free}\mid (s_i)_i]
		= (1-p)^{s_1\cdots s_k}
		\leq e^{-ps_1\cdots s_k}
		\leq n^{-D/n \cdot \Pi(n-\Sigma)}.
	\end{equation*}
  Since the number of colourings with a given sequence $(s_i)_i$ is
  upper-bounded by $n^{s_1}\cdots n^{s_{k-1}}=n^{\Sigma}$, the expected number
  of rainbow-free colourings with a given sequence $(s_i)_i$ is bounded by
	\begin{equation}
		\mathop{{}\rm\bf E}\nolimits[\text{number of rainbow-free colourings} \mid (s_i)_i]
		\leq n^{\Sigma - D/n \cdot \Pi(n-\Sigma)}.
		\label{eq:ev}
	\end{equation}
  In each of the cases below we will bound the exponent of $n$ in (\ref{eq:ev}).

	Write $D=k-1+\delta$ for some $\delta>0$.

  \textbf{Case~1}:
	We have $\Sigma = k-1$ and $\Pi = 1$.
  Putting this into~(\ref{eq:ev}) gives an exponent of
  \begin{equation*}
		\Sigma - D/n \cdot \Pi(n-\Sigma) =
		(k-1) - D \cdot (1-(k-1)/n) \to -\delta.
	\end{equation*}
	This is less than $-\delta/2$ if $n$ is large enough.
	Hence, this case is $o(1)$.

  \textbf{Case~2}:
  Here we have $\Sigma = k$ and $\Pi = 2$. The exponent of $n$ in~(\ref{eq:ev}) becomes
	\begin{equation}
		\Sigma - D/n \cdot \Pi(n-\Sigma) =
		k - (k-1+\delta)\cdot 2 \cdot (1-k/n) \to -k + 2 - 2\delta.
		\label{eq:c2}
	\end{equation}
	Since this converges to a negative number, it will be less than $-1/2$ for all large enough $n$.
	Hence, this case is $o(1)$ as well.

  \textbf{Case~3}:
  There are $O(n)$ sequences in this case, so each of them must give an expected value that is $o(n^{-1})$.
	The variables are $\Sigma = k+x-2$ and $\Pi = x$.
  The exponent in~(\ref{eq:ev}) is a quadratic function of $x$:
	\begin{equation}
		\Sigma - (k-1+\delta)/n \cdot \Pi(n-\Sigma) =
		k+x-2-(k-1+\delta) \cdot x \cdot (1-(k+x-2)/n).
		\label{eq:quadratic}
	\end{equation}
	Since the leading coefficient is positive, and we want to prove an upper bound, it suffices to check the
	boundaries $x=3$ and $x=n/2$.
	(The maximal possible value of $x$ is actually even smaller, but overestimating doesn't hurt.)
	For $x=3$ we get
	\begin{equation}
		k + 1 - 3(k-1+\delta) (1-(k+1)/n) \to -2k +4 -3\delta < -1.
		\label{eq:c3}
	\end{equation}
	Since this converges to something less than $-1$, we know that the expected value for $x=3$
	is $o(n^{-1})$ for $n$ large enough.

  Since the value of~(\ref{eq:quadratic}) goes to $-\infty$ if $x=n/2$ and
  $n\to\infty$, the upper bound~(\ref{eq:c3}) on the exponent in~(\ref{eq:ev})
  works for the $x=n/2$ case as well.

  \textbf{Case~4}:
	We are given that $\Sigma \leq 6k$. Furthermore we have $s_{k-2}\geq 2$.
	The minimal value of $\Pi$ is attained if $s_1=\dots=s_{k-3}=1$ and $s_{k-1} =
	\Sigma-(k-3)-2=\Sigma-k+1$.
	Thus, we have $\Pi \geq 2(\Sigma - k + 1)$.
	Since $\Sigma$ is a sum of $k-1$ terms, of which the last two are at least $2$, we also have $\Sigma \geq k+1$.
	\begin{align*}
		\Sigma - (k-1+\delta)/n \cdot \Pi(n-\Sigma)
		&\leq \Sigma - (k-1+\delta) 2 (\Sigma -k+1) (1-\Sigma/n)\\
		&\to \Sigma - (k-1+\delta) 2 (\Sigma -k+1).
	\end{align*}
	The step where we take the limit is allowed because $\Sigma$ is bounded, and hence the term divided
	by $n$ goes to $0$ indeed. We continue
	\begin{align}
		\Sigma - (k-1+\delta) 2 (\Sigma -k+1)
		&= \Sigma(1-2(k-1+\delta)) + 2(k-1)(k-1+\delta)\nonumber\\
		&\leq (k+1)(-2k+1-2\delta) + 2(k-1)(k-1+\delta)\nonumber\\
		&= -2k^2-k+1-2k\delta-2\delta + 2k^2-4k+2+2k\delta-2\delta\nonumber\\
		&= -3k+1-4\delta < 0.
		\label{eq:c4}
	\end{align}
	As before this converges to something negative, and hence it will be $o(1)$.

  \textbf{Case~5}:
	We are now ready for the only remaining case.
	Here we have $\Sigma \geq 6k$ and as before this implies $\Pi \geq 2(\Sigma -k+1)$.
  \begin{equation*}
		\Sigma - (k-1+\delta)/n \cdot \Pi(n-\Sigma)
		\leq
		\Sigma - (k-1+\delta)/n \cdot 2(\Sigma -k+1)(n-\Sigma).
	\end{equation*}
	Using that $s_k = n-\Sigma \geq n/k$ and doing some rewriting gives
	\begin{align*}
		\Sigma - (k-1+\delta)/n \cdot \Pi(n-\Sigma)
		&\leq
		\Sigma - (k-1+\delta)/n \cdot 2(\Sigma -k+1)\frac nk\\
		&=
		\Sigma - \frac{k-1+\delta}k \cdot 2(\Sigma -k+1)\\
		&=
		(1-2(k-1+\delta)/k)\Sigma + 2(k-1)(k-1+\delta)/k\\
		&=
		(-1+2/k-2\delta/k)\Sigma + 2(1-1/k)(k-1+\delta).
	\end{align*}
	We are now at the point where we can use $\Sigma \geq 6k$.
	Because $-1+2/k-2\delta/k < 0$ we get
	\begin{align}
		\Sigma - (k-1+\delta)/n \cdot \Pi(n-\Sigma)
		&\leq (-1+2/k-2\delta/k) \cdot 6k +2(1-1/k)(k-1+\delta)\nonumber\\
		&= -6k + 12-12\delta + 2k-2+2\delta - 2+2/k-2\delta/k\nonumber\\
		&\leq -4k+8-10\delta + 2/k
		\leq -4k+9-10\delta.
		\label{eq:c5}
	\end{align}
	This last value is strictly less than $-k+1$, which is just what we needed.
	We conclude that the total expected number of rainbow-free colourings in this case is $o(1)$ as well,
	and hence the random hypergraph $H^k_{n,p}$ is not rainbow-free colourable with high probability.
\end{proof}

Lemma~\ref{lem:large_p} can be made a bit stronger with respect to the the
colourings of type $(1,\dots,1,n-k+1)$.

\begin{proposition}\label{prop:type1}
	If a random hypergraph $H^k_{n,p}$, with $k\geq 3$, $p = D(\ln n)/n$, and
  $D>k-1$ is rainbow-free colourable then with high probability it has a colouring of type $(1,\dots,1,n-k+1)$.
\end{proposition}
\begin{proof}
	The proof depends heavily on the claims established in the proofs of
  Lemmas~\ref{lem:small_p} and~\ref{lem:large_p}.

  Let $X_i$ be the number of rainbow-free colourings in Case $i$ of the proof of
  Lemma~\ref{lem:large_p}.
	Since $n^{1/n} = e^{(\ln n)/n} \to 1$,
  we know that the convergence of exponents in~(\ref{eq:ev}) in the proof of Lemma~\ref{lem:large_p} implies that
	$n$ raised to the limit of the exponent is off by at most a constant factor. Hence,
	\begin{equation*}
		\mu:=\mathop{{}\rm\bf E}\nolimits[X_1] = \Theta(n^{k-1-D}) = \Theta(n^{-\delta}),
	\end{equation*}
	where $D=k-1+\delta$.
	In Cases~2 to~5 of the proof of Lemma~\ref{lem:large_p},
  Equations~(\ref{eq:c2}), (\ref{eq:c3}), (\ref{eq:c4}), and~(\ref{eq:c5}) imply
  that the expected number of rainbow-free colourings in each case
	is bounded by
	\begin{align*}
		\mathop{{}\rm\bf E}\nolimits[X_2] &= O(n^{-k+2-2\delta}),\\
    \mathop{{}\rm\bf E}\nolimits[X_3] &= O(n)\cdot O(n^{-2k+4-3\delta})= O(n^{-2k+5-3\delta}),\\
		\mathop{{}\rm\bf E}\nolimits[X_4] &= O(n^{-3k+1-4\delta}),\\
    \mathop{{}\rm\bf E}\nolimits[X_5] &= O(n^{k-1})\cdot O(n^{-4k+9-10\delta}) = O(n^{-3k+8-10\delta}).
	\end{align*}
	Since $k\geq 3$, each of these terms is $o(n^{-1-2\delta})$.
	Hence for $2\leq i\leq 5$ we have
	$ \mathop{{}\rm\bf Pr}\nolimits[X_i>0] \leq \mathop{{}\rm\bf E}\nolimits[X_i] = o(n^{-1-2\delta})$.
	To show that almost all random rainbow-free colourable hypergraphs are
  rainbow-free colourable with a colouring of the first
	type indeed, all we have to show is that $\mathop{{}\rm\bf Pr}\nolimits[X_1>0] = \Theta(n^{-\delta})$.

  As in the proof of Lemma~\ref{lem:small_p} enumerate all colourings by $c^1$ to $c^\ell$ and suppose that $c^i$ is a rainbow-free colouring.
	The probability that there is another rainbow-free colouring $c^j$ is bounded by
	\begin{align*}
		\sum_{j\sim i} \mathop{{}\rm\bf Pr}\nolimits[c^j\mid c^i] + \sum_{j\not \sim i,\, j\neq i} \mathop{{}\rm\bf Pr}\nolimits[c^j]
		&\leq n\cdot k \cdot e^{-p(n-k)} + n^{k-1} e^{-p(n-k+1)}\\
		&= O(n^{k-1}n^{-(k-1+\delta)}) = O(n^{-\delta}).
	\end{align*}
	Hence, the probability that the number of rainbow-free colourings is exactly $1$ is at least
	\begin{equation*}
		\sum_{i} \mathop{{}\rm\bf Pr}\nolimits[c^i] (1-O(n^{-\delta})) \sim \sum_i \mathop{{}\rm\bf Pr}\nolimits[c^i] =\Theta(n^{k-1-D}) = \Theta(n^{-\delta}).
	\end{equation*}
  This implies that the probability that $H^k_{n,p}$ is rainbow-free colourable is at
  least $\Theta(n^{-\delta})$.
\end{proof}

Proposition~\ref{prop:type1} implies that checking colourings of the type
$(1,\dots,1,n-k+1)$ is sufficient to find a colouring in $H^k_{n,p}$ with high
probability \emph{if} we know that the hypergraph is rainbow-free colourable.

\section{Conclusions}

We showed that a threshold function of the event that a random $k$-uniform
hypergraph is rainbow-free colourable is $(k-1)(\ln n)/n$. Our results do not
say anything about the case when the hyperedge probability $p$ is close to the
threshold. As far as we know, the behaviour of the rainbow-free colourings of a
random hypergraph in this case is open.


\section{Introduction}
\label{sec:Introduction}

The great success of convolutional neural networks (CNNs) \cite{fukushima_2003} is rooted in receptive fields, a main architectural motif of visual processing in living organisms~\cite{mack2013principles}. Originating in the retina, a receptive field defines the region of visual space within which visual stimuli affect the firing of a single ganglial neuron~\cite{hartline_1940,mack2013principles}. This motif is preserved by neurons of the visual cortex, too~\cite{hubelWiesel1968}.

However, receptive fields are just one of the motifs employed by visual processing in the retina.
Another important motif is the center-surround (CS) motif, which divides the receptive field of a ganglial neuron into a circular excitatory region (the center), and a concentric inhibitory region (the surround)~\cite{doi:10.1152/jn.1953.16.1.37,mack2013principles}.
\begin{figure}[t]
\centering
\includegraphics[width=0.45\textwidth]{Images/fig_1_oocs-1.pdf}
\vspace*{-1.5ex}
\caption{On-off center-surround (OOCS) inductive biases significantly enhance the performance and robustness of a vision network in different lighting conditions.}
\label{fig:oocsArchitecture}
\vspace*{-2ex}
\end{figure}
Finally, a third important motif classifies the center-surround fields into either on-center, when the neurons fire in response to the presence of a light stimulus at the center of their receptive field,  and into off-center (OO), when the neurons fire in response to the absence of a light stimulus at the center of their receptive field~\cite{enroth-cugell_pinto_1972}. The center-surround motif is also reported to occur in the receptive fields of the primary level visual cortex, causing the so called surround-modulation effect~\cite{doi:10.1152/jn.1965.28.2.229,doi:10.1152/jn.1992.67.4.961,doi:10.1146/annurev.ne.08.030185.002203}.
\begin{figure}[t]
\centering
\includegraphics[width=0.4\textwidth]{Images/on_off_receptives.pdf}
\vspace*{-1.5ex}\caption{\cite{mack2013principles}~ The response of a) On-center neurons and b) Off-center neurons and their associated receptive fields, respectively, to five different lighting conditions.}
\label{fig:receptivefields}
\vspace*{-2ex}
\end{figure}

As shown in Figures~\ref{fig:oocsArchitecture}-\ref{fig:images}, the on-off center-surround pathways (OOCS) introduce edge detection inductive biases in a given model. If a light stimulus is turned on at the center of an on-receptive field, but not at its surround, then the on-ganglial neuron fires vigorously. If the light also touches the surround, then the neuron yields a weak response, and ceases to fire in case of a uniform or a surround-only stimulation. This is because of the mutual inhibition of the center and its surround. Complementary, when the light stimulus at the center of an off-receptive field is turned off, but not at its surround, then the off-ganglial neuron fires vigorously. The neuron ceases to fire when the light is turned off at the surround, too~\cite{enroth-cugell_pinto_1972,mack2013principles}.
Various studies of retinal circuity have shown that the on-center and off-center ganglial neurons, respectively, are at the origin of two parallel pathways~\cite{doi:10.1113/jphysiol.2005.088047, Zaghloul2645,SHAPLEY1986229}. They are physiologically and anatomically distinct, and their receptive fields cover the retinal area completely~\cite{Dacey2004-DACOO,mack2013principles}.

Motivated by OOCS in living organisms, we developed a procedure extending any CNN to an OOCS-CNN with same number of parameters, as shown in Figure~\ref{fig:oocsArchitecture}. This first adds the complementary CS convolutional kernels to the input processing. The kernels are fixed and precomputed. Their results are added after one of the original convolutional layers (which intuitively convolve with different kernels, possibly of different sizes). In  Figure~\ref{fig:oocsArchitecture} we add them after the third layer, which worked best on Imagenet. We also split the original layers in two, and concatenate the results thereafter, at the place of addition.
Our experiments show that
OOCS improves both the performance of CNNs in image recognition tasks, and the robustness of CNNs to challenging illumination conditions. In our
experiments with unseen lighting and noisy test sets OOCS-CNNs also outperformed other regularization methods.

\noindent{\bf Summary of Contributions:}
\vspace*{-2mm}
\begin{itemize}
\itemsep-0.2em
\item We introduce OOCS, an inductive edge-detection bias for enhancing the performance and robustness to the variation of lighting conditions of vision networks.
\item We prove that on and off residual pathways capture complementary features that improve the generalization error and robustness to distribution shifts.
\item We show that OOCS can be applied to any CNN architecture without increasing their number of parameters.
\item We conduct an extensive set of experiments showing the superior performance and robustness of OOCS networks compared to standard deep models.
\end{itemize}

\section{Related Work}
\textbf{Receptive field in CNNs.}
In each convolution layer, a small-sized kernel shifts over the input image, convolving each patch beneath it with the kernel matrix. These kernels were inspired by, and function like the receptive fields \cite{luo2016understanding,li2019scale}: they change the activity of the neurons connected to that patch in the next layer~\cite{hubelWiesel1968,li2019selective}. Fukushima's Neocognitron~\cite{fukushima_1980} is arguably the first CNN model to have imported the concept of receptive fields from neural science~\cite{hubelWiesel1968}, and inspired a large body of CNN variants~\cite{fukushima_2003, doi:10.1162/neco.1989.1.4.541, Lecun98gradient-basedlearning,inproceedings,wang2019kervolutional,ding2019acnet,hu2018squeeze}.

\textbf{Bio-inspired Models.}
A large body of works tried to bringing insights from neuroscience to computer vision systems \cite{kim2016convolutional,zoumpourlis2017non,laskar2018correspondence,lechner2020neural,Hasani2021liquid}. Fukushima enhanced the Neocognitron model with several priors \cite{jacobsen2016structured}, such as contrast-extracting preprocessing layer, inspired by the On-Off ganglial neurons, and inhibitory surround connections, such as the surround-modulation in the visual cortex~\cite{fukushima_2003}.
More recent bio-inspired work proposed to replace the feed-forward architecture of CNNs with a recurrent architecture, by adding local-range and long-range feedback connections~\cite{NIPS2018_7775}, or by adding intrinsic horizontal connections~\cite{NIPS2018_7300}.

A center-surround architecture is also proposed in~\cite{NIPS2019_9719},
in the form of a convolutional layer with a fixed kernel (a difference of Gaussians DoG, as shown in Figures~\ref{fig:3dplots}(a) and~\ref{fig:kernels}(a-b)), to the activation map of the first layer of the network. In a fixed kernel, positive weights are introduced for close neighbor neurons, and negative weights for those that are farther apart. This approach improved the performance of CNNs on various image-classification tasks.

Similar to~\cite{NIPS2019_9719}, we also use a DoG kernel with positive weights for the center neurons and negative weights for the surround neurons, as shown in Figures~\ref{fig:3dplots}(a) and~\ref{fig:kernels}(c). However, while~\cite{NIPS2019_9719} uses a DoG kernel similar to~\cite{rodieck_1965}, our work uses the DoG kernel in~\cite{Petkov2005ModificationsOC, kruizinga_petkov_2000}. The disadvantage of~\cite{rodieck_1965} is that the variances of the Gaussians are unknown. For example, in~\cite{NIPS2019_9719} they are fixed to 1.2 for inhibitory synapses and to 1.4 for excitatory ones.  In addition, the DoG in~\cite{rodieck_1965} may result in very small numbers, that have to be normalized as in~\cite{NIPS2019_9719}, for achieving meaningful results. Using the DoG
in~\cite{Petkov2005ModificationsOC, kruizinga_petkov_2000} we do not need to perform a hyperparameter search to find the optimum value for the variances. By just knowing the size of the receptive fields, we can analytically compute the corresponding, large enough, variances.
Finally, in contrast to~\cite{NIPS2019_9719}, we use both on- and off-pathways \cite{kim2016convolutional}, as shown in Figure~\ref{fig:3dplots}, and in Figure~\ref{fig:kernels}(c) and its complement. These pathways capture complementary features which are lost in the use of either on- or off-pathways alone.

\section{Main Results}

\label{sec:Model}
In this section, we discuss our main findings. We first introduce the structure of the OOCS blocks. We then lay the theoretical grounds for their effectiveness in robustifying deep models to the variation of lighting conditions.

\begin{figure}[t]
   \includegraphics[width=0.45\textwidth]{Images/3dplot2.pdf}
   \vspace*{-2ex}
   \caption{Our difference of Guassians function for a) On and b) Off kernels of size 5 and center to surround ratio of $2/3$.}
    \label{fig:3dplots}
   \vspace*{-2ex}
\end{figure}

\textbf{Center Surround Kernels.} Center and surround weights can be computed by a difference of two Gaussian functions (DoG). This difference can be written in Cartesian coordinates (CC), as follows, where the CC origin is taken as the center of the receptive field \cite{rodieck_1965}:
\begin{equation}
\centering
\label{eq:rodiek}
DoG(x,y) = K_1\, e^{-\frac{x^2+y^2}{\sigma_1}} - K_2\,
e^{-\frac{x^2+y^2}{\sigma_2}}
\end{equation}
where $K_1\,{>}\,K_2$ and $\sigma_2\,{>}\,\sigma_1$~\cite{Blackburn1993ASC}.

\textbf{Why the kernel presented by (\ref{eq:rodiek}) is not optimal?}
The main disadvantage of this model is that the variances of the Gaussians have to be determined through a hyper-parameter search. The values of the weights calculated are typically too small, and have to be normalized like in~\cite{NIPS2019_9719}, to obtain meaningful results, as in Figure~\ref{fig:kernels}(b).
\begin{figure}[t]
    \centering
   \includegraphics[width=0.5\textwidth]{Images/kernels.pdf}
   \vspace*{-4ex}
   \caption{From left to right: Kernel taken from~\cite{NIPS2019_9719} used in their experiments; Actual kernel calculated by their proposed method; Our on-center kernel.}
    \label{fig:kernels}
   \vspace*{-2ex}
\end{figure}
Furthermore, with $K_i = 1/2\pi\sigma_i^2$ which is used in \cite{NIPS2019_9719}, the two Gaussian functions take almost equal values for close $\sigma_1$ and $\sigma_2$. This yields their differences taking very small values everywhere. Normalizing the values to the value of the center, results in loosing the center's weight in excitation or inhibition.

\textbf{Improved Center-Surround Kernels.} To overcome the shortcomings discussed above, we set out to design an improved kernel, as shown in Figures~\ref{fig:3dplots}(a-b) and \ref{fig:kernels}(c), based on the DoG model proposed in \cite{Petkov2005ModificationsOC,kruizinga_petkov_2000}, for defining the difference of Gaussians for the center and surround kernels. This model allows us to analytically compute the variances, from the size of the receptive fields \cite{Petkov2005ModificationsOC}:
\begin{equation}
\label{eq:petrov}
DoG_{\sigma,\gamma}(x,y) =  \frac{A_c}{\gamma^2}\, e^{-\frac{x^2+y^2}{2\gamma^2\sigma^2}} - A_s\,e^{-\frac{x^2+y^2}{2\sigma^2}}
\end{equation}
Here, $\gamma$ with $\gamma\,{<}\,1$, defines the ratio between the radius $r$ of the center and that of the surround. We determine the values of the coefficients $A_c$ and $A_s$ by requiring that the sum of all positive values in Equation~\eqref{eq:petrov} are equal to those of the negative values. We normalize this and let their sum be equal to 1 and -1, respectively:
\begin{figure*}[t]
    \centering
   \includegraphics[width=1\textwidth]{Images/samples.pdf}
   \caption{On-center and off-center kernel convolution on samples from Imagenet dataset. The 1st column shows the original image, the 2nd and 3rd columns show on-center and off-center filters respectively. The 4th column shows the filters added together. They extract complementary features within the original image. For example, the  bright spot top-left in the Judo image, is properly detected only by the on-center filter, whereas the dark grains on the bottom of the bird image, only by the off-center filter. Hence both filters are necessary.}
    \label{fig:images}

\end{figure*}
\begin{equation}
\iint [DoG_{\sigma,\gamma}(x,y)]^{+} dx dy = 1,
\end{equation}
\begin{equation}
\iint [DoG_{\sigma,\gamma}(x,y)]^{-} dx dy = -1
\end{equation}
By $[z]^{+}$ and $[z]^{-}$ we denote the positive and the negative half wave rectification functions, respectively:
\begin{equation}
[z]^{+} = max(0,z),
\quad [z]^{-} = min(0,z)
\end{equation}
\vspace*{-4ex}
\begin{proposition}[DoG Coefficients]
\label{theo:infinity} In the infinite continuous case, the coefficients $A_c$ and $A_s$ are equal.
\end{proposition}
The proof is given in the supplementary materials.
By setting the $DoG_{\sigma,\gamma}(x,y) = 0$, and using Proposition~\ref{theo:infinity}, we can immediately calculate $\sigma$ as in Equation~\ref{eq:sigma} below, for arbitrary $r$ and $\gamma$. Note that in the finite discrete case, the values of $A_c$ and $A_s$ are still very similar:
\begin{equation}
\label{eq:sigma}
\sigma \approx \frac{r}{2\gamma}\sqrt{\frac{1-\gamma^2}{-\ln{\gamma}}}
\end{equation}
See Supplementary Materials for the complete calculations.

This model not only allows us to find the variance of the kernels analytically, but also it overcomes the normalization issues of (\ref{eq:rodiek}). The weights calculated by Eq.~\eqref{eq:petrov} do not have to be normalized and can be obtained by the kernel size and the ratio of the center to surround. Moreover, forcing the positive and negative weights to sum up to 1 and -1 results in a balance between the excitations and inhibitions. There is evidence for this balance in neuroscience (see Figure~\ref{fig:receptivefields}).

In the DoG model of Equation~\eqref{eq:rodiek} however, the positive and negative weights do not necessarily sum up to zero, unless in very large kernels.
We calculated the weights of the SM kernel in Figure~\ref{fig:kernels}(b)
using this equation, with the  parameters reported in~\cite{NIPS2019_9719}. However, this kernel is different from the one in Figure~\ref{fig:kernels}(a), which is actually used in their experiments. This kernel is altered in a way that the positive and negative weights sum up to zero.

\textbf{On and Off kernel matrices.}
We use Equation~\eqref{eq:petrov} to compute the weights in the On-center kernel matrix $DoG_{\rm On}$. For the Off-center kernel $DoG_{\rm Off}$, we use the same equation with inverted signs. For a given input  $\chi$, we calculate the On and Off responses by convolving $\chi$ with the computed kernels separately:
\\
\begin{equation}
\chi_{\rm On}[x,y] = (\chi * DoG_{\rm On})[x,y],
\end{equation}
\begin{equation}
\chi_{\rm Off}[x,y] = (\chi * DoG_{\rm Off})[x,y]
\end{equation}
It is important to note that both the on-convolution and the off-convolution covers the entirety of the input image.

\textbf{Designing OOCS Pathways.}
As shown in Figure~\ref{fig:oocsArchitecture}, we add the computed responses to the activation maps of the first layers in the on- and off-pathways, respectively. To implement the on-off residual maps, we split the CNN layers between the on and off parallel pathways, with half of the number of the filters of the original layers, in the layers of each pathway. Thus, the number of the training parameters remains unchanged. At the end of the pathways, we concatenate the activation maps of the last on and off layers, and feed this to the rest of network. The system is structured and trained via Algorithm~\ref{alg:1}. The on-off pathways are residual connections to facilitate the training process while enhancing the network's robustness to illuminations.

\begin{algorithm}[t]
\caption{Building and Training OOCS networks}
\label{alg:1}
\begin{algorithmic}
\STATE \textbf{Inputs:} mini batches $\mathcal{B}$, Network $N$ with layers $L=\{l_1,\dots, l_n\}$ parametrized by $\theta$, $l_{i,1/2} =$ half of layer $l_i$ DoG center radius $r$, Center-Surround ratio $\gamma$.
\STATE \textbf{Output:} OOCS Network
\FOR{$j$ in Number of Training Steps}
\FOR{$b$ \textbf{in} $\mathcal{B}$}
\STATE $x_{\emph{on}} = l_{1,1/2}(b) + b * DoG_{on}(b, r, \gamma)$;
\STATE $x_{\emph{off}} = l_{1,1/2}(b) + b * DoG_{off}(b, r, \gamma)$;
\STATE $x_{\emph{new}}$ = Concatenate($l_{2,1/2}(x_{on})$, $l_{1,1/2}(x_{\emph{off}})$)\;
\STATE Construct the rest of $N$ on $x_{new}$ as input.
\STATE $L_{total} = \sum_{j=1}^{T} L(y_j, \hat{y}_j)$,~~~$\nabla L(\theta) = \frac{\partial L_{tot}}{\partial \theta}$
\STATE $\theta = \theta - \alpha \nabla L(\theta)$
\ENDFOR
\ENDFOR
\STATE \textbf{Return} $N_\theta$
\end{algorithmic}
\end{algorithm}

\begin{figure*}[t]
    \centering
   \includegraphics[width=1\textwidth]{Images/architectures.pdf}
\vspace*{-2ex}
   \caption{The network architecture for the Basenets, SM CNN and our OOCS-CNN.}
    \label{fig:architecture}
\vspace*{-2ex}
\end{figure*}

OOCS blocks can be used to extend any deep model, without the need to search for optimal hyperparameters for the on and the off kernels. Figure~\ref{fig:images} shows the saliency maps of on-convolution, off-convolution, and the combined convolution, for four samples taken from the Imagenet dataset~\cite{DBLP:conf/cvpr/DengDSLL009}.
The OOCS kernels detect unique edge patterns, by extracting positive and negative contrasts. While they both detect edges, they do this in complementary ways. For a dark feature on a light background, the on-convolution detects the outer edges, and the off-convolution detects the inner ones. For a light feature on a dark background, roles are reversed.
More importantly, the strength of the responses is different in the extracted edges, since the on-convolution and the off-convolution have a complementary response to light, as shown in Figure~\ref{fig:receptivefields}~(rows 1,3,5). This means that some of the features extracted by one of the convolutions are not present in the other, or they appear very weak.

\begin{theorem}[On-Off Complementarity]
\label{theo:main}
The on- and off-path\-ways learn unique and complementary features.
\end{theorem}
The proof of Theorem~\ref{theo:main} is given in Supplementary Materials. It uses the definition and the associated properties (eg.,~Proposition~\ref{theo:infinity}) of the on- and off-convolutions. Theorem~\ref{theo:main} demonstrates that it is not enough to use either the on- or the off-convolution, alone. Both are required to maximize information flow, in accurate and robust image recognition.

\section{Experimental Evaluation}
\label{sec:Evaluation}
We perform two sets of experiments. In Section~\ref{subsec:Classification}, we evaluate OOCS on standard image classification benchmarks, and compare its performance to competitive baselines. We also perform a couple of ablation analyses on the baseline networks and OOCS to validate our observations.

In Section~\ref{subsec:Robustness}, we perform a rigorous robustness analysis, by shifting the test distribution from the training set (Out of IID setting). In particular, we evaluate our models under various challenging lighting condition, as well as on the MNIST data set with black-white inverted images.

\begin{table}[t]
  \centering
  \vspace*{-2mm}
    \caption{Top-1 test accuracy and associated variance of the control models and our different OOCS models on Imagenet. n=6}
   \vspace*{4mm}
   \begin{adjustbox}{width=1\columnwidth}
  \begin{tabular}{ll}
    \toprule
       \textbf{Models}  &
       \textbf{Accuracy} \\
    \midrule
      Basenet$_{0}$\hspace*{2.6ex}(standard deep CNN) & 40.8 $\pm$ 0.4 \\
      Basenet$_1$\hspace*{2.6ex}(extra convolution with ReLU) & 39.4 $\pm$ 0.6 \\
      Basenet$_2$\hspace*{2.6ex}(extra convolution)  & 41.0 $\pm$ 0.5\\
      Basenet$_3$\hspace*{2.6ex}(extra skip connection) & 42.1 $\pm$0.5  \\
      Basenet$_4$\hspace*{2.6ex}(5x5 kernel skip connection) & 42.0 $\pm$0.6  \\
      Basenet$_5$\hspace*{2.6ex}(OOCS without on/off kernels) & 41.3 $\pm$0.7  \\
    \midrule
      SM-CNN$_{0}$\hspace*{1ex}(kernel given in Figure~\ref{fig:kernels}a) &  38.1 $\pm$ 0.6    \\
      SM-CNN$_1$\hspace*{1ex}(kernel given in Figure~\ref{fig:kernels}b) &  37.0 $\pm$  0.4 \\
      SM-CNN$_2$\hspace*{1ex}(kernel given in Figure~\ref{fig:kernels}c) &  41.9 $\pm$  0.8 \\
    \midrule
      OOCS$_{0}$\hspace*{1ex}(on-kernel given in Figure~\ref{fig:kernels}c) &  \textbf{44.4 $\pm$ 0.3}   \\
      OOCS$_1$\hspace*{1ex}(kernel size 3x3, CS ratio 1/2) &  43.4 $\pm$ 0.5  \\
      OOCS$_2$\hspace*{1ex}(OOCS weights $1/n_c$ and $1/n_s$) &  43.6 $\pm$ 0.6  \\
      OOCS$_3$\hspace*{1ex}(OOCS computed after first pool) &  44.1 $\pm$ 0.4  \\
      OOCS$_4$\hspace*{1ex}(OOCS with trainable kernels) &  \textbf{44.5 $\pm$ 0.9}  \\
    \bottomrule
  \end{tabular}
  \end{adjustbox}
  \label{Imagenet_results-table}
  \vspace*{-2ex}
\end{table}

We implemented all models in TensorFlow 2.3 \cite{199317}, and used Adam for optimization \cite{DBLP:journals/corr/KingmaB14} with a learning rate of $10^{-4}$. We repeated all of the experiments for six times and report the mean value of the obtained results, together with their standard deviation. The latter was computed with a confidence level of 99.9\%.
\label{headings}

\begin{figure*}[t]
    \centering
    \includegraphics[width=0.7\textwidth]{Images/Imagenet_acc_loss2.pdf}
    \caption{Validation accuracy and loss of the Basenet$_0$, OOCS$_0$, and SM-CNN$_0$  across epochs.}
    \label{fig:valtrain}
\end{figure*}

\subsection{Image Classification}
\label{subsec:Classification}
In this section, we assess the performance (accuracy) of OOCS models in image classification tasks.

\textbf{Dataset.} We used a subset of the Imagenet~\cite{DBLP:conf/cvpr/DengDSLL009}. We randomly chose 600 samples from 100 categories. From these samples, we used 500 of each class for the training set, and 50 for each of the validation and test sets.  After cropping all the rectangular images to squares around the center, we resized all the images to $192\times192$ pixels. We did not perform any preprocessing on the images.

\textbf{Architectural details.}
We use three main architectures for this experiment as shown in Figure~\ref{fig:architecture}: Basenet$_{0}$, SM-CNN$_{0}$, and OOCS$_{0}$. We start from a standard deep CNN architecture for image recognition that we call Basenet$_{0}$. It consists of seven convolutional layers, five max-pooling layers, and two fully connected layers. All convolutional layers have $3\times3$ kernels and strides of 1.  We initialized all kernels with the He initialization~\cite{He_2015}. The max-pooling layers have $2\times2$ kernels and strides of 2. Dropouts~\cite{JMLR:v15:srivastava14a} follow the fully connected layers, and the last layer predicts the category with a softmax function. All of the hidden-weight layers have ReLU activation functions.
We have also three other variations Basenet$_{1}$, Basenet$_{2}$ and Basent$_{3}$ discussed in the "what happens" paragraph below.

We use the Surround-Modulation model of~\cite{NIPS2019_9719} for SM-CNN$_{0}$, with the kernel given in Figure~\ref{fig:3dplots}(b). Although SM and OO retinal receptive fields are two distinct biological phenomena, there are similarities between them and the way they are modeled. To ensure fairness, for the SM-CNN, we added the SM kernel to the activation maps of the first convolution layer in our baseline CNN, precisely aligned with what the authors suggested, and used the kernel weights they have reported. The variants SM-CNN$_{1-2}$ are described below in "what happens"..

For the OOCS-CNN network OOCS$_{0}$, we split the convolutional layers between the first and second pooling layers, into two parallel pathways with half of the filters of the original layers in each. The on-response is calculated by convolution with the on-kernel given in Figure~\ref{fig:3dplots}(c) and the off-response with its complementary kernel. The weights of these kernels are specified as non-trainable parameters.

\textbf{Performance.}
We compared the test accuracy of OOCS$_0$ with the performance of the Basenet$_0$ and of SM-CNN$_0$. Figure~\ref{fig:valtrain} shows the validation accuracy and loss for the three main network variants. As one can see, OOCS$_0$ outperforms the others by a large margin. Moreover, one can observe that SM-CN$_0$ has a better sample efficiency as it is stated in~\cite{NIPS2019_9719}, but has a poor performance on the validation set in comparison to the Basenet$_0$.

\begin{figure*}[t]
\centering
   \includegraphics[width=0.7\textwidth]{Images/noisesPlot2.pdf}

   \caption{Noise-robustness. Test accuracy of the OOCS-CNN, the SM-CNN and the Basenet as a function of increasing input noise variance, with illumination Light0, and with n=6}

    \label{fig:noise_results}
    \vspace*{-4ex}
\end{figure*}

\textbf{What happens if we alter the architectures?} To more thoroughly evaluate OOCS performance, we designed eleven additional network variants: Basenet$_{1-5}$, SM-CNN$_{1-2}$, and OOCS$_{1-4}$. Basenet$_{1-2}$ were designed by adding an extra layer to Basenet$_0$, to see whether the performance of OOCS$_0$ can be obtained by increasing the number of training parameters of Basenet$_0$. This extra layer was added between the first and second pooling layers, with 64 filters. This new layer has a ReLU activation function in Basenet$_1$, and no activation function in Basenet$_2$. Basenet$_{3-4}$, have a skip-connection from the input to the output of the third convolution layer of Basenet$_0$, thus constructing a residual block~\cite{he2016deep}. This investigates if the performance of OOCS$_0$ is in fact related to the skip connection between the input and on-off pathways. The skip connection in Basenet$_4$ is a convolution layer with $5\times{}5$ kernel. Finally, Basenet$_5$ has the exact same architecture of OOCS$_0$, with the parallel pathways but with trainable filters alongside the skip connections. The kernels are initialised with the He initialization~\cite{He_2015}.

SM-CNN$_1$ uses the kernel
given in Figure~\ref{fig:kernels}(b), which is calculated from the DoG proposed by~\cite{NIPS2019_9719}, in Equation~\eqref{eq:rodiek}. We also designed an extra variant, called SM-CNN$_2$, which uses the OOCS kernel for the on-center-surround DoG, and which is given in Figure~\ref{fig:kernels}(c).

OOCS$_1$ uses a smaller kernel to perform the convolutions: $3\times{}3$ as the size for the receptive field, and $\gamma\,{=}\,1/2$ as the center-surround ratio. OOCS$_2$ uses $1/n_c$ and $1/n_s$ as the weights for the elements in the center and surround in the kernel matrix, respectively, where $n_c$ is the number of central elements and $n_s$ is the number of elements in the surround. The aim was to indicate the effectiveness of the proposed DoG model. OOCS$_3$ computes the on- and off-responses from the inputs to the first layers of the pathways and adds them to the activation maps of the first layers in the pathways. Finally, OOCS$_4$ has the same architecture of OOCS$_0$, but with trainable filters on the On and Off skip connections, initialised with the On and Off kernels. Table~\ref{Imagenet_results-table} shows the top-1 test accuracy for the main and control networks. This model was added to see whether the On and Off kernels structure will be reserved throughout the training or we will eventually converge to other settings. All $64$ filters kept the OOCS structure, with differences in on and off weights intensities. OOCS$_0$ and it's variants OOCS$_{1-4}$  outperform all other models.

The results suggest that OOCS$_0$ performance can neither be achieved by increasing the capacity of Basenet$_0$ nor by adding skip-connections to Basenet$_0$. Moreover, the results for Basenet$_4-5$ show that the On-Off Center-Surround structure can not be learned by network without initialising or fixing the kernels with the calculated On and Off kernels. The On Center-Surround kernel of OOCS$_0$ also increases the performance of SM-CNN$_0$ considerably, and outperforms Basenet$_0$. Finally, SM-CNN$_1$ has a lower accuracy than Basenet$_0$.

The accuracy of OOCS$_1$ shows that with a smaller kernel, one still outperforms the Basenets and the SM-CNNs, but it decreases the accuracy compared to Basenet$_0$. OOCS$_2$ achieved a higher accuracy than these networks, too. This shows that forcing the positive and negative parts of the kernel to sum up to 1 and -1 respectively plays an important role in the OOCS-CNN's superior performance. Finally, OOCS$_3$ also outperforms the Basenets and SM-CNNs.

\textbf{OOCS ResNet.}
Here we modify the architecture of a residual network\cite{he2016deep} to include OOCS and evaluate the performance of it with and without the OOCS filters.

\textbf{Dataset.}
In this experiment, we use the same subset of Imagenet. We augmented the training images with randomly rotating them in the range of $15$, randomly shifting horizontally and vertically in the range of 10 percent of total width and height, and randomly flipping the images horizontally.
\begin{table}[t]
  \centering
    \caption{Top-1 test accuracy and associated variance of the Resnet34 and Resnet34-OOCS models on Imagenet. n=6}
  \begin{tabular}{ll}
    \toprule
    \textbf{Models}  & \textbf{Acc} \\
    \midrule
     ResNet34 & 61.73 $\pm$ 0.6 \\
     ResNet34-OOCS &  \textbf{63.39 $\pm$ 0.7} \\
    \bottomrule
  \end{tabular}
  \label{Imagenet_resnet_results-table}
\end{table}

\textbf{Architectural details and Performance.}
We used the ResNet34\cite{he2016deep} as the base network. In order to add OOCS to it, we splitted the first two layers of the first residual block into the On and Off pathways with half of the filters of the original layers in each. The On and Off responses were calculated from the inputs to the first residual block.

As Table~\ref{Imagenet_resnet_results-table} shows the results for both networks, OOCS enhances the performance of larger networks like ResNets and does not lose its effectiveness with data augmentation.

\begin{table*}[t]
  \centering
  \caption{Test Accuracy on all 6 lighting conditions for networks trained on Light0. n=6.}
  \vspace*{1.5ex}
  \begin{tabular}{lcccccc}
    \toprule
    \multicolumn{1}{c}{} & \multicolumn{1}{c}{Familiar Test Set} & \multicolumn{5}{c}{Unfamiliar Test Set}                   \\
   \midrule
    \textbf{Models}     & Light0     & Light1   & Light2    & Light3    & Light4    & Light5 \\
    \midrule
    Basenet & 88.4 $\pm$ 1.9  & 82.2 $\pm$ 2.4  & 46.4 $\pm$ 4.1 & 86.2 $\pm$ 1.5  & 58.8 $\pm$ 2.7  & 79.5 $\pm$ 4.9     \\
    Basenet-L2 & 89.6 $\pm$ 1.9  & 87.0 $\pm$ 2.8  & 48.5 $\pm$ 3.8  & 86.9 $\pm$ 1.5  & 60.8 $\pm$ 3.5 & 80.3 $\pm$ 4.5      \\
    Basenet-Dropout & 89.2 $\pm$ 2.0  & 86.3 $\pm$ 5.7 & 48.5 $\pm$ 4.1  & 86.3 $\pm$ 1.2 &  59.9 $\pm$ 3.8 & 81.3 $\pm$ 5.4      \\
    Basenet-BN     & 89.2 $\pm$ 1.4  & 84.0 $\pm$ 3.7 & 37.4 $\pm$ 7.7 & 87.3 $\pm$ 2.0  & 56.2 $\pm$ 3.7  & 78.9 $\pm$ 4.4   \\
    SM-CNN     & 91.0 $\pm$ 0.9  & 90.6 $\pm$ 0.6  & \textbf{62.5 $\pm$ 1.5}  & 87.3 $\pm$ 1.6  & 61.8 $\pm$ 2.3 & 81.6 $\pm$ 1.7 \\
    OOCS-CNN (Ours)    & \textbf{93.3 $\pm$ 0.7} & \textbf{90.9 $\pm$ 0.7} & 56.7 $\pm$ 1.6 & \textbf{91.2 $\pm$ 1.0} & \textbf{61.9 $\pm$ 1.5} & \textbf{88.2 $\pm$ 1.0}  \\
    \bottomrule
  \end{tabular}
  \label{light0-table}
  \vspace*{-2ex}
\end{table*}
\subsection{Robustness Evaluation}
\label{subsec:Robustness}
Here we evaluate OOCS robustness. To this end we extensively study how deep CNN models perform under the variation of lighting conditions and to distribution shifts.

\textbf{Dataset.} We used the Norb dataset~\cite{DBLP:conf/cvpr/LeCunHB04} to assess the robustness of our proposed OOCS-CNN architecture. This dataset contains images of 3D objects belonging to five generic categories. The images are of size $96\,{\times}\,96$ pixels, and photographed under six different lighting conditions. In a first experiment, we trained our networks on the images from one lighting condition, Light0, and then tested them on all six lighting conditions. In a second experiment we added different kinds of noise to the testing images, in order to evaluate the robustness in the presence of noise.

\textbf{Architectural details.}
Given the image size, we designed CNN Basenets with 6 convolutional layers, 4 max-pooling layers, and 2 fully connected layers. All convolutional layers have $3\times3$ kernels, and strides of 1. The max-pooling layers have $2\times2$ kernels and strides of 2. The number of filters in the first convolution layer is 32 and gets doubled after each pooling layer. For the OOCS-CNN, we split the layers between the first and second max-pooling to On and Off pathways and compute the On and Off convolutions from the input to the first layers of pathways.

\textbf{Robustness Evaluation.}
To assess the robustness of OOCS-CNNs under changes in illumination, we tested the networks on images with a lighting condition that was different from the one in the training set. We compare the performance of our model with Basenet-L2, Basenet-Dropout and Basenet-BN, in addition to the Basenet and SM-CNN.
\begin{table}[t]

  \centering

  \caption{Test Accuracy and variance for images from Light0 with Gaussian noise for networks trained on Light0. n=6.}
  \vspace*{1.5ex}
  \begin{adjustbox}{width=1\columnwidth}
  \begin{tabular}{lcccc}
    \toprule
    \multicolumn{1}{c}{} & \multicolumn{4}{c}{\textbf{Gaussian Noise ($\sigma$)}} \\
    \midrule
    \textbf{Models} &0.05&0.1&0.15&0.2\\
    \midrule
    Basenet&$85.8_{\pm3.6}$&$70.0_{\pm10.8}$&$35.5_{\pm5.9}$&$26.5_{\pm7.1}$\\
    Basenet-L2&$84.8_{\pm2.0}$&$73.3_{\pm3.9}$&$46.0_{\pm10.4}$&$33.0_{\pm8.1}$\\
    Basenet-D&$87.5_{\pm2.9}$&$80.8_{\pm2.4}$&$66.5_{\pm11.7}$&$42.2_{\pm17.7}$\\
    Basenet-BN& $84.4_{\pm2.8}$&$69.8_{\pm10.3}$&$48.8_{\pm13.3}$&$38.4_{\pm8.3}$\\
    SM-CNN&$77.9_{\pm5.2}$&$49.0_{\pm7.7}$&$38.8_{\pm2.6}$ &$35.2_{\pm4.2}$\\
    OOCS-CNN&$\mathbf{91.3_{\pm0.3}}$&$\mathbf{84.2_{\pm2.1}}$&$\mathbf{76.2_{\pm2.6}}$&$\mathbf{70.4_{\pm4.0}}$ \\
    \bottomrule
  \end{tabular}
  \end{adjustbox}
  \label{light0noisegaussian-table}
\end{table}

\begin{table}[t]
  \fontsize{9.0pt}{10.8pt} \selectfont
  \caption{Test Accuracy and variance for images from Light0 with Salt\,\&\,Pepper noise for networks trained on Light0. n=10.}
  \vspace*{1.5ex}
  \centering
  \begin{adjustbox}{width=1\columnwidth}
  \begin{tabular}{lllll}
    \toprule
    \multicolumn{1}{c}{} & \multicolumn{4}{c}{\textbf{Salt and Pepper Noise ($p$)}} \\
    \midrule
    \textbf{Models}     & 0.05     & 0.1   & 0.15    & 0.2 \\
    \midrule
    Basenet & $45.6_{\pm15.3}$ & $30.0_{\pm12.7}$ &$25.8_{\pm8.7}$  & $22.8_{\pm4.5}$     \\
    Basenet-L2 & $49.7_{\pm9.4}$ & $31.6_{\pm7.5}$ & $26.0_{\pm5.4}$ & $23.7_{\pm3.5}$      \\
    Basenet-D & $71.5_{\pm7.5}$ & $48.5_{\pm13.3}$ & $29.1_{\pm12.1}$ & $22.1_{\pm3.5}$      \\
    Basenet-BN     & $54.2_{\pm14.7}$ & $40.6_{\pm13.0}$ & $34.2_{\pm10.8}$ & $29.7_{\pm8.3}$  \\
    SM-CNN  & $46.1_{\pm12.3}$ & $37.9_{\pm4.8}$ & $34.0_{\pm4.1}$ & $29.8_{\pm5.3}$ \\
    OOCS-CNN & $\mathbf{87.7_{\pm2.5}}$ & $\mathbf{82.3_{\pm3.0}}$ & $\mathbf{76.3_{\pm3.2}}$ & $\mathbf{71.8_{\pm2.5}}$  \\
    \bottomrule
  \end{tabular}
  \end{adjustbox}
  \label{light0noisesp-table}
\end{table}

Table~\ref{light0-table} shows the test-accuracy and associated variance for all baselines trained on Light0. Except for Light2, where SM-CNN proved to be superior to the other networks, the OOCS-CNN outperformed the other CNN variants with a considerable margin.

We then added Gaussian and Salt $\&$ Pepper noise to the test set, to evaluate the performance of the networks under perturbations. Table~\ref{light0noisegaussian-table} and Table~\ref{light0noisesp-table} show the test accuracy and variance for networks, trained on Light0 and tested on the same lighting condition, but in the presence of noise.

The results show that the OOCS-CNN is more robust than other regularization methods. Not only has it higher accuracy, the results of the OOCS-CNN have considerably lower variance in comparison to the other networks on modified test sets.
Figure~\ref{fig:noise_results} shows the significant level of robustness to noise achieved by OOCS compared to other methods.

\textbf{Robustness to distribution shifts.}
As discussed before, on- and off-convolutions extract different features for objects on light and dark backgrounds. Both are needed to capture higher details. To assess our claim more thoroughly, we designed the following experiment.

\textbf{Dataset.}
We used the MNIST dataset \cite{lecun-mnisthandwrittendigit-2010} to train our networks. The original dataset contains black handwritten digits on white background. We trained our networks on the original images, but for the test set we altered all the pixel values by subtracting them from $255.$ Figure \ref{fig:mnist} shows the original/altered image for one sample.
\begin{figure}[t]
\centering
   \includegraphics[width=0.27\textwidth]{Images/MNIST.pdf}
   \caption{The on- and off-convolutions are shown in the second and the third columns, respectively, for a sample of the MNIST dataset. In the first row we show the original image, and in the second row the inverted image, with all pixels subtracted from 255.}

    \label{fig:mnist}
\end{figure}

\begin{table}[t]
  \centering
    \caption{Test Accuracy of the networks on the original black-on-white and on the inverted white-on-black test sets. n=6.}
  \vspace*{1.5ex}
  \begin{tabular}{llll}
    \toprule
         & Basenet     & SM-CNN   & OOCS-CNN \\
    \midrule
      Original & $99.1_{\pm0.2}$ & $99.2_{\pm0.1}$ & $99.1_{\pm0.2}$   \\
      Inverted & $29.0_{\pm10.1}$ & $35.7_{\pm4.9}$ & $\mathbf{93.9_{\pm1.2}}$   \\
    \bottomrule
  \end{tabular}
  \label{mnist_table}
\end{table}

\textbf{Robustness evaluation.}
Table \ref{mnist_table} shows the test accuracy of the networks on the original and altered  MNIST test images. On the test set with inverted colors, the accuracy of the Basenet and SM-CNN drops sharply. The OOCS-CNN on the other hand, achieves a much higher accuracy on this challenging test set. Figure~\ref{fig:mnist} shows that on the samples with black foreground, the on-center convolution extracts features similar to the ones extracted by the off-center convolution on the samples with black background and vice versa. Being equipped with both in OOCS-CNN is the reason it still performs better on the altered test set.

\section{Discussion, Scope and Conclusions}
\label{sec:Discussion}
Inspired by the retinal ganglial cells in vertebrates, we first proposed an on-off center-surround (OOCS) enhancement to the receptive fields of vision networks. We then showed that the OOOCS pathways impose an inductive bias on the vision networks, which enhances their robustness to the variation of lighting conditions. We took advantage of the studies in the field of Neuroscience and used an improved CS kernel as a ubiquitous block for obtaining more accurate and more robust vision based networks. The OOCS addition to a CNN is easy to implement, does not increase the number of trainable parameters, and it increases its performance.

\textbf{Performance Out of IID Setting.} OOCS performs extremely well under test-set distribution-shifts. This is a direct result of the complementary on- and off-pathways.

\textbf{Inductive Biases vs. Regularization.} Our experiments (Table 2) show that standard regularization methods such as L2, Dropout and batch-normalization are less effective in improving generalization under distribution shifts, compared to the OOCS. Figure~\ref{fig:reg_vs_ind} gives the absolute distance of the familiar test error (of the same lighting condition as the training set), to the test error of different lighting conditions. We observe that OOCS has a lower distance for distribution shifts compared to regularization methods.
\begin{figure}[t]
    \centering
    \includegraphics[width=0.35\textwidth]{Images/reg_vs_ind.pdf}
    \vspace{-3mm}
    \caption{Relative test error for different lighting conditions compared to the IID test error (shorter bar is better). The values are taken from Table \ref{light0-table}. Each bar represents the deviation of the test error from the test error for Light0.}
    \label{fig:reg_vs_ind}
    \vspace*{-4ex}
\end{figure}

\textbf{Robustness to Digital Distribution Shifts.} What happens if we add OOCS filters to a ResNet architecture? would this improve their robustness properties to distribution shifts such as Gaussian perturbations, brightness, and contrast. We studied this systematically in a set of experiments where we added OOCS filters to a ResNet-34, and compared its performance under variation of these perturbations (See Figures S3 and S4 in the supplementary materials). We observed consistent improvements achieved when OOCS filters are deployed.

\textbf{Usability and Impact of OOCS Blocks.} OOCS pathways can be added to any vision-based model regardless of their exact architecture. They can be interpreted as targeted residual blocks explicitly designed to perform specialized edge detection. In decision critical applications \cite{lechner2019designing,lechner2020neural}, object recognition under different lighting conditions is a game changer. For instance vision-based self-driving cars are sensitive to lighting conditions \cite{lechner2021adversarial,lechner2020gershgorin}. OOCS can robustify driving under direct sun or going from shaded to well lit regions.

\textbf{Bio-inspirations and Future Work.} In this work, our main focus was to bring insights from a simplified model of the retinal cells to designing more robust image classification modules. There are additional top-down connections between layers in the retina, and the sizes of the receptive fields change depending on their location. It is therefore worth exploring the implementation of a complete model of the retina and to further improving the performance of this model, similar to many works that aim to transform biological mechanisms \cite{lechner2017worm,sarma2018openworm,gleeson2018c302,dabney2020distributional} into better machine learning models \cite{hasani2020natural}. The OOCS helps a network to extract the inner and outer edges, hence more work can be done to investigate using it as a preprocessing or data augmentation tool, especially for medical image segmentation tasks.

\section*{Acknowledgements}
Z.B. is supported by the Doctoral College Resilient Embedded Systems, which is run jointly by the TU Wien's Faculty of Informatics and the UAS Technikum Wien. R.G. is partially supported by the Horizon 2020 Era-Permed project Persorad, and ECSEL Project grant no. 783163 (iDev40). R.H and D.R were partially supported by Boeing and MIT. M.L. is supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein
Award).

\nocite{Strisciuglio2019}
\nocite{Azzopardi2014}
\bibliographystyle{icml2021}