Pegasos: primal estimated sub-gradient solver for SVM. We describe and analyze a simple and effective stochastic sub-gradient descent algorithm for solving the optimization problem cast by Support Vector Machines (SVM). We prove that the number of iterations required to obtain a solution of accuracy ϵ is O (1/ϵ) , where each iteration operates on a single training example. In contrast, previous analyses of stochastic gradient descent methods for SVMs require Ω(1/ϵ2) iterations. As in previously devised SVM solvers, the number of iterations also scales linearly with 1/λ, where λ is the regularization parameter of SVM. For a linear kernel, the total run-time of our method is O (d/(λϵ)) , where d is a bound on the number of non-zero features in each example. Since the run-time does not depend directly on the size of the training set, the resulting algorithm is especially suited for learning from large datasets. Our approach also extends to non-linear kernels while working solely on the primal objective function, though in this case the runtime does depend linearly on the training set size. Our algorithm is particularly well suited for large text classification problems, where we demonstrate an order-of-magnitude speedup over previous SVM learning methods

References in zbMATH (referenced in 103 articles , 1 standard article )

Showing results 1 to 20 of 103.
Sorted by year (citations)

1 2 3 4 5 6 next

  1. Liang, Xijun; Zhang, Zhipeng; Song, Yunquan; Jian, Ling: Kernel-based online regression with canal loss (2022)
  2. Bertsimas, Dimitris; Pauphilet, Jean; Van Parys, Bart: Sparse classification: a scalable discrete optimization perspective (2021)
  3. Iiduka, Hideaki: Inexact stochastic subgradient projection method for stochastic equilibrium problems with nonmonotone bifunctions: application to expected risk minimization in machine learning (2021)
  4. Jain, Prateek; Nagaraj, Dheeraj M.; Netrapalli, Praneeth: Making the last iterate of SGD information theoretically optimal (2021)
  5. Pătraşcu, Andrei: New nonasymptotic convergence rates of stochastic proximal point algorithm for stochastic convex optimization (2021)
  6. Patrascu, Andrei; Irofti, Paul: Stochastic proximal splitting algorithm for composite minimization (2021)
  7. Wu, Weichen; Xu, Yitian; Pang, Xinying: A hybrid acceleration strategy for nonparallel support vector machine (2021)
  8. Dieuleveut, Aymeric; Durmus, Alain; Bach, Francis: Bridging the gap between constant step size stochastic gradient descent and Markov chains (2020)
  9. Gao, Kaifeng; Mei, Gang; Piccialli, Francesco; Cuomo, Salvatore; Tu, Jingzhi; Huo, Zenan: Julia language in machine learning: algorithms, applications, and open issues (2020)
  10. Hazan, Tamir; Sabach, Shoham; Voldman, Sergey: Stochastic proximal linear method for structured non-convex problems (2020)
  11. Iiduka, Hideaki: Decentralized hierarchical constrained convex optimization (2020)
  12. Jiang, Wei; Siddiqui, Sauleh: Hyper-parameter optimization for support vector machines using stochastic gradient descent and dual coordinate descent (2020)
  13. Lan, Guanghui; Zhou, Zhiqiang: Algorithms for stochastic optimization with function or expectation constraints (2020)
  14. Rosasco, Lorenzo; Villa, Silvia; Vũ, Bằng Công: Convergence of stochastic proximal gradient algorithm (2020)
  15. Yan, Yinqiao; Li, Qingna: An efficient augmented Lagrangian method for support vector machine (2020)
  16. Ahookhosh, Masoud; Neumaier, Arnold: An optimal subgradient algorithm with subspace search for costly convex optimization problems (2019)
  17. Asi, Hilal; Duchi, John C.: Stochastic (approximate) proximal point methods: convergence, optimality, and adaptivity (2019)
  18. Grimmer, Benjamin: Convergence rates for deterministic and stochastic subgradient methods without Lipschitz continuity (2019)
  19. Guo, Zheng-Chu; Shi, Lei: Fast and strong convergence of online learning algorithms (2019)
  20. Li, Ningning; Xue, Dan; Sun, Wenyu; Wang, Jing: A stochastic trust region method for unconstrained optimization problems (2019)

1 2 3 4 5 6 next