Trading Accuracy for Sparsity in Optimization Problems with Sparsity Constraints

By Shai Shalev-Shwartz, Nati Srebro, Tong Zhang. 2010

176 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mechanics, 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 Optimization & Training

Citations in the corpus

Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (2012, methodology): “The SMO algorithm was generalized to structural SVMs (Taskar, 2004, Chapter 6), but its convergence rate scales badly with the size of the output space: it was estimated as O (n|Y|/λε) in Zhang et al. (2011). Further, this method requires an expectation oracle to work with its factored dual paramete”
Accelerated proximal stochastic dual coordinate ascent for regularized loss minimization (2013, background): “ = ˚(0) + sup c>0 (kk D L)c= 1: This observation allows us to smooth L-Lipschitz functions by adding regularization to their conjugate. In particular, the following lemma generalizes Lemma 2.5 in [26]. 10 Lemma 2. Let ˚be a proper, convex, L-Lipschitz function w.r.t. a norm kk P, let kk Dbe the d”
The Statistics of Streaming Sparse Regression (2014, background): “[52] Shai Shalev-Shwartz, Nathan Srebro, and Tong Zhang.”
vqSGD: Vector Quantized Stochastic Gradient Descent (2022, background): “[29] suggest randomized sparsiﬁcation schemes that are unbiased, but are not known to provide any theoretical convergence guarantees in very low sparsity regimes.”
Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages (2013, background): “The non-convex l0 constraint results in a hard optimization problem which is typically solved by state-of-the-art optimizers using greedy methods [35].”
Nearly Optimal Private LASSO (2015, background): “Due to these reasons Frank-Wolfe algorithm has found many applications in machine learning [23, 16, 8].”
Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, background): “Greedy algorithms (Shalev-Shwartz et al., 2010) for cardinality constrained problems have similar convergence guarantees and smaller per iteration cost but tend to underperform when compared to threshold based algorithms (Khanna & Kyrillidis, 2018).”
A Provable Algorithm for Learning Interpretable Scoring Systems (2018, methodology): “Several approaches are considered in [23] in order to find an approximation of equation (3.”
A Distributed Frank-Wolfe Algorithm for Communication-Efficient Sparse Learning (2014, background): “1) with O(1/ ) nonzero entries, which is sometimes called an -coreset of size O(1/ ) [23, 24].”
Functional Frank-Wolfe Boosting for General Loss Functions (2015, background): “There are extensive studies on minimizing the Lasso loss function ( l 1 penalized loss) [17, 18, 19].”
Stochastic methods for l1 regularized loss minimization (2009, methodology): “Following the Gauss-Siedel approach of Zhang and Oles (2001), Genkin et al.”
Sparse Feature Attacks in Adversarial Learning (2014, background): “Existing literatures [29], [30] indicate that in a classical classification environment, there will always be a trade-off between the enforced sparsity and the accuracy obtained when ‘1 regularizer is applied.”
Learning Nonlinear Functions Using Regularized Greedy Forest (2011, background): “This observation was theoretically justified in [27] where the following rate of convergence was obtained under suitable conditions: there exists a constant”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, methodology): “For optimizing over the simplex , this trade-off was also described by (Gärtner & Jaggi, 2009; Clarkson, 2010), and by (Shalev-Shwartz et al., 2010) for the 1 -ball (considering primal error).”