Offline Complexity of the garbling scheme The offline complexity of the garbling scheme means the time complexity of the circuit encoding algorithm, that is, $\textrm{GC.Circ}(1^\lambda, C)$, where $C$ is the circuit to be garbled. It's straightforward to see that the offline complexity is $\textrm{poly}(\lambda, C)$. 

My question is that whether there exists any optimal offline complexity of circuit encoding algorithm? for example, is it possible that the offline complexity is "sublinear" in the circuit size?
From The Foundation of Garbled Circuits


  A garbling scheme is a five-tuple of algorithms $G=(Gb,En,De,Ev,ev)$.
  The first of these is probabilistic; the remaining algorithms are
  deterministic. A string $f$, the original function, describes the
  function ev$(f,\cdot): \{0, 1\}^n\rightarrow \{0, 1\}^m$ that we want
  to garble where $n$ and $m$ are the input and output size resp.  On
  input $f$ and a security parameter $k\in \mathbb{N}$, algorithm $Gb$
  returns a triple of strings $(F, e, d)\rightarrow Gb(1^k, f)$. String
  $e$ describes an encoding function, $En(e,\cdot)$, that maps an
  initial input $x\in\{0, 1\}^n$ to a garbled input $X=En(e, x)$. String
  $F$ describes a garbled function, $Ev(F,\cdot)$, that maps each
  garbled input $X$ to a garbled output $Y = Ev(F, X)$.  String $d$
  describes a decoding function, $De(d,\cdot)$, that maps a garbled
  output $Y$ to a final output $y = De(d, Y )$.


Thus, taking an FHE $(Gen,Enc,Dec)$ scheme (see this)which takes an encoded input $X=Enc(x)$, applies the function $C$ to it to get $Y=C(X)$ and then decode the output by $y=Dec(Y)$ we get that $y=C(x)=Dec(C(Enc(x))$ (since the scheme is fully homomorphic. In this example the garbling algorithm, the one you denote by $CC.Circ$ just do nothing and its complexity is $O(1)$, which is optimal.

This example shows that you must restrict your arguments when you refer to the optimality considerations of a garbling scheme. This topic is currently under an intensive research.