<p>It sounds like overfitting, which isn't surprising since this model is basically a linear regression model.<br>
There are few options you can try:<br>
1. add hidden layers + activation functions(<a href="https://arxiv.org/abs/1511.07289" rel="nofollow noreferrer">https://arxiv.org/abs/1511.07289</a>: elu paper works on mnist data set with vanilla DNN).<br>
2. Use either CNN or RNN, although CNN is more apt for image problems.<br>
3. Use a better optimizer. If you are new, try ADAM optimizer (<a href="https://www.tensorflow.org/api_docs/python/tf/train/AdamOptimizer" rel="nofollow noreferrer">https://www.tensorflow.org/api_docs/python/tf/train/AdamOptimizer</a>), and then move onto using momentum with nestrov(<a href="https://www.tensorflow.org/api_docs/python/tf/train/MomentumOptimizer" rel="nofollow noreferrer">https://www.tensorflow.org/api_docs/python/tf/train/MomentumOptimizer</a>)</p>

<p>Without feature engineering, it'll be hard to pull off image classification using just linear regression. Also, you do not need to run softmax on your outcomes since softmax is designed to smooth argmax. Lastly, you should input (None,num_features) into shape of placeholders instead to have variational batch size. This will allow you to directly feed your valid and test datasets into feed_dict without having to create additional tensors.</p>
Softmax Regression - validation and test predictions shows no improvement
<p>I'm currently learning how to use Tensorflow and I'm having some issues to implement this Softmax Regression aplication.</p>

<p>There's no error when compiling but, for some reasson text validation and test predictions shows no improvement, only the train prediction is showing improvement.</p>

<p>I'm using Stocastic Gradient Descent(SGD) with minibatches in order to converge faster, but don't know if this could be causing a trouble somehow. </p>

<p>I'll be thankful if you could share some ideas, here's the full code:</p>

<pre><code>import input_data
import numpy as np
import random as ran
import tensorflow as tf
import matplotlib.pyplot as plt

mnist = input_data.read_data_sets('MNIST_Data/', one_hot=True)

#Features &amp; Data
num_features = 784
num_labels = 10
learning_rate = 0.05
batch_size = 128
num_steps = 5001

train_dataset = mnist.train.images
train_labels = mnist.train.labels
test_dataset = mnist.test.images
test_labels = mnist.test.labels
valid_dataset = mnist.validation.images
valid_labels = mnist.validation.labels

graph = tf.Graph()
with graph.as_default():
    tf_train_data = tf.placeholder(tf.float32, shape=(batch_size, num_features))
    tf_train_labels = tf.placeholder(tf.float32, shape=(batch_size, num_labels))
    tf_valid_data = tf.constant(valid_dataset)
    tf_test_data = tf.constant(test_dataset)

    W = tf.Variable(tf.truncated_normal([num_features, num_labels]))
    b = tf.Variable(tf.zeros([num_labels]))

    score_vector = tf.matmul(tf_train_data, W) + b
    cost_func = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits_v2(
                labels=tf_train_labels, logits=score_vector))

    score_valid = tf.matmul(tf_test_data, W) + b
    score_test = tf.matmul(tf_valid_data, W) + b

    optimizer = tf.train.GradientDescentOptimizer(learning_rate).minimize(cost_func)

    train_pred = tf.nn.softmax(score_vector)
    valid_pred = tf.nn.softmax(score_valid)
    test_pred = tf.nn.softmax(score_test)

def accuracy(predictions, labels):
    correct_pred = np.sum(np.argmax(predictions, 1) == np.argmax(labels, 1))
    accu = (100.0 * correct_pred) / predictions.shape[0]
    return accu

with tf.Session(graph=graph) as sess:
    sess.run(tf.global_variables_initializer())
    print("Initialized")

    for step in range(num_steps):
        offset = np.random.randint(0, train_labels.shape[0] - batch_size - 1)

        batch_data = train_dataset[offset:(offset+batch_size), :]
        batch_labels = train_labels[offset:(offset+batch_size), :]

        feed_dict = {tf_train_data : batch_data,
                     tf_train_labels : batch_labels
                     }

        _, l, predictions = sess.run([optimizer, cost_func, train_pred],
                                     feed_dict=feed_dict)

        if (step % 500 == 0):
            print("Minibatch loss at step {0}: {1}".format(step, l))
            print("Minibatch accuracy: {:.1f}%".format(
                accuracy(predictions, batch_labels)))
            print("Validation accuracy: {:.1f}%".format(
                accuracy(valid_pred.eval(), valid_labels)))

    print("\nTest accuracy: {:.1f}%".format(
            accuracy(test_pred.eval(), test_labels)))
</code></pre>