<p>It seems you're attempting to compute 64 features (for each 3x3 patch) in the first convolutional layer and feed this directly into the second convolutional layer, with no intermediate pooling layer. Convolutional neural networks typically have a structure of stacked convolutional layers, followed by contrast normalization and max pooling.</p>

<p>To reduce processing overheads researchers have experimented in moving from fully connected to <a href="http://arxiv.org/pdf/1409.4842v1.pdf" rel="nofollow">sparsely connected architectures</a>, and hence the creation of inception architecture. However, whilst these yield good results for high dimensional inputs, you may be expecting too much from the 32x32 pixels of Cifar10 in TensorFlow.</p>

<p>Therefore, I think the issue is less around patch size of and more to do with overall architecture. This <a href="https://tensorflow.googlesource.com/tensorflow/+/master/tensorflow/models/image/cifar10/cifar10.py" rel="nofollow">code</a> is a known good starting point. Get this working and start reducing parameters until it breaks.</p>
Inception style convolution
<p>I have the necessity to keep the model as small as possible to deploy an image classifier that can run efficiently on an app (the accuracy is not really relevant for me)</p>

<p>I recently approached deep learning and I haven't great experience, hence I'm currently playing with the cifar-10 example.
I tried to replace the first two 5x5 convolutional layers with two 3x3 convolution each, as described in the <a href="http://arxiv.org/abs/1512.00567" rel="nofollow">inception paper</a>.</p>

<p>Unluckily, when I'm going to classify the test set, I got around 0.1 correct classification (random choice)</p>

<p>This is the modified code of the first layer (the second is similar):</p>

<pre><code>with tf.variable_scope('conv1') as scope:
    kernel_l1 = _variable_with_weight_decay('weights_l1', shape=[3, 3, 3, 64],
                                     stddev=1e-4, wd=0.0)
    kernel_l2 = _variable_with_weight_decay('weights_l2', shape=[3, 3, 64, 1],
                                     stddev=1e-4, wd=0.0)
    biases = _variable_on_cpu('biases', [64], tf.constant_initializer(0.0))

    conv_l1 = tf.nn.conv2d(images, kernel_l1, [1, 1, 1, 1], padding='SAME')
    conv_l2 = tf.nn.depthwise_conv2d(conv_l1, kernel_l2, [1, 1, 1, 1], padding='SAME')
    bias = tf.nn.bias_add(conv_l2, biases)
    conv1 = tf.nn.relu(bias, name=scope.name)
    _activation_summary(conv1)
</code></pre>

<p>Is it correct?</p>