The paper presents an effective training algorithm for linearly-scored dependency parsers, combining online large-margin multi-class training with efficient parsing techniques for dependency trees. The method achieves competitive dependency accuracy for both English and Czech without language-specific enhancements. The approach is based on the online large-margin learning algorithms of Crammer and Singer, which maximize the accuracy of the overall tree. The system is efficient, accurate, and general, with no need for pruning heuristics. Experiments on the Penn Treebank and Prague Dependency Treebank show that the model performs as well or better than previous comparable systems, including those using support vector machines (SVM) and averaged perceptron algorithms. The paper also discusses the k-best MIRA approximation and its impact on training time and performance. Future work includes adding labels to dependencies and extending the model to handle non-projective dependencies.The paper presents an effective training algorithm for linearly-scored dependency parsers, combining online large-margin multi-class training with efficient parsing techniques for dependency trees. The method achieves competitive dependency accuracy for both English and Czech without language-specific enhancements. The approach is based on the online large-margin learning algorithms of Crammer and Singer, which maximize the accuracy of the overall tree. The system is efficient, accurate, and general, with no need for pruning heuristics. Experiments on the Penn Treebank and Prague Dependency Treebank show that the model performs as well or better than previous comparable systems, including those using support vector machines (SVM) and averaged perceptron algorithms. The paper also discusses the k-best MIRA approximation and its impact on training time and performance. Future work includes adding labels to dependencies and extending the model to handle non-projective dependencies.