Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm

By Kenneth L. Clarkson. 2008

479 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition, 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 Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets (2020, methodology): “In that setting, Clarkson 2010; Jaggi 2013 deﬁne a modulus of smoothness that leads to aﬃne invariant analysis of the Frank-Wolfe algo-rithm, matching with the aﬃne covariant behavior of the algorithm.”
Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “In terms of convergence, it is known that after O(1/ε) iterations, Algorithm 1 obtains an ε-approximate solution (Frank & Wolfe, 1956; Dunn & Harshbarger, 1978) as well as a guaranteed ε-small duality gap (Clarkson, 2010; Jaggi, 2013), along with a certificate to (5).”
Fully Decentralized Joint Learning of Personalized Models and Collaboration Graphs (2019, background): “Let t ≥ 1 and denote by 1) )] k the partial derivative of f with respect to the k -th block of coordinates corresponding to the model α k where j k is the unit vector with 1 in the j k -th entry (Clarkson, 2010; Jaggi, 2013).”
The geometry of differential privacy: the sparse and approximate cases (2012, methodology): “emma 1 holds to within an additive approximation factor , i.e. k^y0 yk4kwk L+. We call such a point ^y0an additive approximation to the least squares estimator problem. By the analysis of Clarkson [Cla10], Titerations of the Frank-Wolfe algorithm give an additive approximation where 4C(L)=(T+3), for”
Automated Scalable Bayesian Inference via Hilbert Coresets (2017, methodology): “Next, taking inspiration from Clarkson (2010) and Jaggi (2013), we solve the optimization in Eq.”
Differentially Private Matrix Completion, Revisited (2017, background): “Notice that 2 k 2 | Ω | is an upper bound on the curvature constant C f (See Lemma 1 from [39], or Section 2 of [10], for a proof).”
Frank-Wolfe Method is Automatically Adaptive to Error Bound Condition (2018, background): “Many existing works have shown the convergence rate of the standard FW method is O (1 /t ) even for strongly convex objectives (Clarkson, 2008; Hazan, 2008; Jaggi, 2013), and in general the rate could not be improved.”
Stochastic methods for l1 regularized loss minimization (2009, methodology): “We refer the reader to (Frank & Wolfe, 1956; Zhang, 2003; Clarkson, 2008).”
A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization (2013, methodology): “f(xt+1)− f(x∗) (1) = f(xt + αt(pt − xt))− f(x∗) ≤ f(xt)− f(x∗) + αt(pt − xt)∇f(xt) + α(2) tβ‖pt − xt‖(2) β-smoothness of f ≤ f(xt)− f(x∗) + αt(x − xt)∇f(xt) + α(2) tβ‖pt − xt‖(2) optimality of pt ≤ f(xt)− f(x∗) + αt(f(x)− f(xt)) + α(2) tβ‖pt − xt‖(2) convexity of f ≤ (1− αt)(f(xt)− f(x∗)) + α(2) tβD”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, unknown): “The basic iteration is as follows.”
On lower complexity bounds for large-scale smooth convex optimization (2013, result): “Now, as a matter of fact, all known FOM’s are “black-box-oriented” – they “learn” the problem being solved solely via the local information (values and (sub)gradients of the objective and the constraints) accumulated ✩This research was supported by the NSF grant CMMI-1232623.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, methodology): “We propose a distributed Frank-Wolfe (dFW) algorithm, a novel approach to solve such distributed sparse learning problems based on an adaptation of its centralized counterpart (Frank and Wolfe, 1956; Clarkson, 2010; Jaggi, 2013).”
Advanced Structured Prediction (2014, methodology): “2 Such greedy schemes have been studied for example in the context of coreset optimization and the Frank Wolfe method (Clarkson, 2010), but the resulting algorithms are different from coordinate minimization.”
How to Scale Up Kernel Methods to Be As Good As Deep Neural Nets (2014, methodology): “Alternative approaches exploit the equivalence between SVMs and sparse greedy approximation and solve SVMs approximately with a smaller subset of examples called coresets(2) [49, 12].”
Coresets for polytope distance (2009, methodology): “…20PA21-121957) Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro.t or commercial advantage and that copies bear this notice and the full citation on the .rst page.”
GRAD-MATCH: Gradient Matching based Data Subset Selection for Efficient Deep Model Training (2021, methodology): “Recently, there have been several efforts to make machine learning models more efficient via data subset selection (Wei et al., 2014a; Kaushal et al., 2019; Coleman et al., 2020; Har-Peled & Mazumdar, 2004; Clarkson, 2010; Mirzasoleiman et al., 2020a; Killamsetty et al., 2021).”
Nearly Optimal Private LASSO (2015, background): “How fast Frank-Wolfe algorithm converges depends on L’s “curvature”, defined as follows according to [8, 17].”
Projection-Free Optimization on Uniformly Convex Sets (2020, methodology): “These fundamental properties are among the main features that contribute to the recent revival and extensions of the Frank-Wolfe algorithm (Clarkson, 2010; Jaggi, 2011) used for instance in large-scale structured prediction (Bojanowski et al., 2014, 2015; Alayrac et al., 2016; Seguin et al., 2016;…”
Trading Accuracy for Sparsity (2009, methodology): “This condition is often referred to as RIP (restricted isometry property) in the compressed sensing literature [Candes and Tao, 2005].”