Sparse Stochastic Zeroth-Order Optimization with an Application to Bandit Structured Prediction
Table 1: Test set evaluation for chunking under F1 score, and for machine translation under BLEU. Results for stochastic learners are shown for SFO, and SZO algorithms with perturbation of all parameters (ALL) or for sparse perturbations of parameters for active features only (SPARSE). All results are averaged over three runs with different random seeds for each algorithm. Best SZO results are shown in bold face; higher results are better.
['Update Rule', 'Test F1 Chunking', 'Test BLEU SMT']
The results were obtained by tuning hyperparameters on development sets for constant learning rate h in the range of 10−2 to 10−3, and exploration parameter μ in the range of 10−1 to 10−2. Best development settings for all algorithms were obtained close to the time horizon of 4M iterations, showing an undertraining behavior in all cases. However, we find the same relations in test set performance as were obtained for convergence speed, with SPARSE two-point updates coming close to the SFO result. Here optimal hyperparameter settings were adjusted on a development set of 1,064 parallel in-domain sentence pairs for constant learning rate h in the range of 100 to 10−5, and exploration parameter μ in the range of 10−2 to 10−6. Final results are obtained by averaging three independent runs using the hyperparameters found on the development set. Best development settings for all algorithms are obtained at 1-4M iterations, except for two-point feedback that reached an optimum already around 100k iterations. The goal of the SMT experiment was to show a possible advantage of using the same non-differentiable MAP criterion at training and test time for SZO algorithms. As we can see, all SZO results outperform the SFO result. In the range of 2.7 BLEU points between out-of-domain and in-domain models, we can achieve an improvement of 1.6 BLEU points by SZO with two-point updates, which is also an improvement of 1.0 BLEU points over the SFO Algorithm.