Yes, you're right a lower learning rate should find a better optimum than a higher learning rate. But you should tune the hyper-parameters using grid search to find the best combination of learning rate along with the other hyper-parameters.

The GBM algorithm uses multiple hyper parameters in addition to the learning rate (shrinkage), these are:

1. Number of trees
2. Interaction depth
3. Minimum observation in a node
4. Bag fraction (fraction of randomly selected observations)

The grid search needs to check all of these in order to determine the most optimal set of parameters.

For example, on some data-sets I've tuned with GBM, I've observed that varying behavior as each hyper-parameter is changed. I haven't run GBM on your sample data-set, but I'll refer to a similar tuning exercise for another data-set. Refer to this graph on a classification problem with highly imbalanced classes.

Although the accuracy is highest for lower learning rate, e.g. for max. tree depth of 16, the Kappa metric is 0.425 at learning rate 0.2 which is better than 0.415 at learning rate of 0.35.

But when you look at learning rate at 0.25 vs. 0.26 there is a sharp but small increase in Kappa for max tree depth of 14, 15 and 16; whereas it continues decreasing for tree depth 12 and 13.

Hence, I would suggest you should try the grid search.

Additionally, as you mentioned, this situation could also have been aggravated by a smaller sample size of the data-set.

Yes, you're right a lower learning rate should find a better optimum than a higher learning rate. But you should tune the hyper-parameters using grid search to find the best combination of learning rate along with the other hyper-parameters.

The GBM algorithm uses multiple hyper parameters in addition to the learning rate (shrinkage), these are:

1. Number of trees
2. Interaction depth
3. Minimum observation in a node
4. Bag fraction (fraction of randomly selected observations)

The grid search needs to check all of these in order to determine the most optimal set of parameters.

For example, on some data-sets I've tuned with GBM, I've observed that accuracy varies widely as each hyper-parameter is changed. I haven't run GBM on your sample data-set, but I'll refer to a similar tuning exercise for another data-set. Refer to this graph on a classification problem with highly imbalanced classes.

Although the accuracy is highest for lower learning rate, e.g. for max. tree depth of 16, the Kappa metric is 0.425 at learning rate 0.2 which is better than 0.415 at learning rate of 0.35.

But when you look at learning rate at 0.25 vs. 0.26 there is a sharp but small increase in Kappa for max tree depth of 14, 15 and 16; whereas it continues decreasing for tree depth 12 and 13.

Hence, I would suggest you should try the grid search.

Additionally, as you mentioned, this situation could also have been aggravated by a smaller sample size of the data-set.