Bundle Methods for Regularized Risk Minimization

By Choon Hui Teo, S. V. N. Vishwanathan, Alex Smola, Quoc V. Le. 2010

280 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Statistics and Probability, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Optimization & Training

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “A second key advantage of this algorithm is that the iterations only require optimizing linear functions over the constrained domain, and we show that this is equivalent to the maximization oracle used by subgradient and cutting-plane methods (Joachims et al., 2009; Teo et al., 2010).”
Learning Optimized Risk Scores (2016, background): “Cutting plane algorithms have an impressive track record on large-scale supervised learning problems, as they scale linearly with the number of samples and provide precise control over data-related computation (see e.g., Teo et al., 2009; Franc and Sonnenburg, 2009; Joachims et al., 2009).”
Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, background): “, 2007) and batch (Teo et al., 2010; Boyd et al., 2010) subgradient algorithms summarily rely on the ability to compute gradients in the feature space F explicitly.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “Note that although Kelley’s method is more complex than subgradient descent, the best known convergence rate is still of the order O(1/ √ t) after t iterations [200].”
Trading Computation for Communication: Distributed Stochastic Dual Coordinate Ascent (2013, methodology): “This idea has been implemented in a MapReduce framework [13, 5] and a MPI framework [21, 11].”
Group-Based Alternating Direction Method of Multipliers for Distributed Linear Classification (2017, background): “Basically, these distributed classification algorithms can be categorized in two classes: 1) the primal problemoriented algorithms and 2) the dual problem-oriented algorithms [10]–[12].”
Communication Efficient Distributed Machine Learning with the Parameter Server (2014, methodology): “For the motivating example introduced in (1), we can implement a standard distributed subgradient descent algorithm [34] using the parameter server.”
FASOLE: Fast Algorithm for Structured Output LEarning (2014, unknown): “The CPA algorithm requires less time on the non-structured USPS benchmark because the risk function of multi-class SVM required by CPA can be evaluated by a single matrix multiplication (very effective in Matlab) unlike the SDA solvers (BCFW, SDM, FASOLE) which compute the loss for individual exampl”
Supervised classification and mathematical optimization (2013, unknown): “…Optimization [9] [13] [51] [128] [160] [245], Linear Programming [94] [158] [205] Mixed-Integer Programming [25] [39] [50] [77] [220] [228], Nonsmooth Optimization [7] [13] [44] [51] [222] [223], Multicriteria and Multi-Objective Programming [68] [93] [181] [248] and Robust Optimization [224].”
Breaking the curse of kernelization: budgeted stochastic gradient descent for large-scale SVM training (2012, methodology): “…1995) using large data (Vishwanathan et al., 2003; Zhang, 2004; Bordes et al., 2005; Tsang et al., 2005; Joachims, 2006; Hsieh et al., 2008; Bordes et al., 2009; Zhu et al., 2009; Teo et al., 2010; Chang et al., 2010b; Sonnenburg and Franc, 2010; Yu et al., 2010; Shalev-Shwartz et al., 2011).”
Stochastic (Approximate) Proximal Point Methods: Convergence, Optimality, and Adaptivity (2018, unknown): “s #0, though kx x 0k= O() by standard results [18]. While aside from proximal-point models, it is not clear a priori how to guarantee that Condition(C.iv)holds, one approach is to use bundle methods [25,56], identical to Kelley’s cutting plane method [29]. In this situation, we begin from the linear”
A Quasi-Newton Approach to Nonsmooth Convex Optimization Problems in Machine Learning (2008, methodology): “Inspired by bundle methods (Teo et al., 2009), we achieve this by minimizing convex lower bounds of Mt(p) that are designed to progressively approach Mt(p) over iterations.”
Parallelized Stochastic Gradient Descent (2010, methodology): “Algorithm Latency tolerance MapReduce Network IO Scalability Distributed subgradient [3, 9] moderate yes high linear Distributed convex solver [7] high yes low unclear Multicore stochastic gradient [5] low no n.”
A Comparison of Optimization Methods and Software for Large-scale L1-regularized Linear Classification (2010, methodology): “Teo et al. (2010) proposed a bundle method BMRM to handle non-differentiable loss functions (e.”