Sparse learning for large-scale and high-dimensional data: a randomized convex-concave optimization approach

DOI10.1007/978-3-319-46379-7_6MaRDI QIDQ2830269zbMATH OpenOpenAlexFDO

Authors Tianbao Yang, Rong Jin, Zhi-Hua Zhou, Lijun Zhang

Publication date 9 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.03766

zbMATH Keywords

convex-concave optimizationdual solutionprimal solutionrandom projectionsparse learning

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20) Nonconvex programming, global optimization (90C26)

Abstract: In this paper, we develop a randomized algorithm and theory for learning a sparse model from large-scale and high-dimensional data, which is usually formulated as an empirical risk minimization problem with a sparsity-inducing regularizer. Under the assumption that there exists a (approximately) sparse solution with high classification accuracy, we argue that the dual solution is also sparse or approximately sparse. The fact that both primal and dual solutions are sparse motivates us to develop a randomized approach for a general convex-concave optimization problem. Specifically, the proposed approach combines the strength of random projection with that of sparse learning: it utilizes random projection to reduce the dimensionality, and introduces $el{l}_1$-norm regularization to alleviate the approximation error caused by random projection. Theoretical analysis shows that under favored conditions, the randomized algorithm can accurately recover the optimal solutions to the convex-concave optimization problem (i.e., recover both the primal and dual solutions).

Recommendations

• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity
• Random convex programs with L₁-regularization: sparsity and generalization
• scientific article; zbMATH DE number 6860836
• Dual averaging methods for regularized stochastic learning and online optimization
• Pathwise coordinate optimization for sparse learning: algorithm and theory

Cites work

• A first-order primal-dual algorithm for convex problems with applications to imaging
• An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems
• An algorithmic theory of learning: Robust concepts and random projection
• An elementary proof of a theorem of Johnson and Lindenstrauss
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• Fast global convergence of gradient methods for high-dimensional statistical recovery
• High-dimensional variable selection with sparse random projections: measurement sparsity and statistical efficiency
• scientific article; zbMATH DE number 1266748 (Why is no real title available?)
• scientific article; zbMATH DE number 2019638 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Kernels as features: on kernels, margins, and low-dimensional mappings
• Large margin methods for structured and interdependent output variables
• One-bit compressed sensing by linear programming
• Optimization with sparsity-inducing penalties
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• Prediction, Learning, and Games
• Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
• Random Projections for Classification: A Recovery Approach
• Randomized Algorithms for Matrices and Data
• Regularization and Variable Selection Via the Elastic Net
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Smooth minimization of non-smooth functions
• SVM Soft Margin Classifiers: Linear Programming versus Quadratic Programming
• The restricted isometry property and its implications for compressed sensing
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• User-friendly tail bounds for sums of random matrices

Cited in

(4)

• Gradient projection Newton algorithm for sparse collaborative learning using synthetic and real datasets of applications
• High-dimension multilabel problems: convex or nonconvex relaxation?
• Optimal computational and statistical rates of convergence for sparse nonconvex learning problems
• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity

This page was built for publication: Sparse learning for large-scale and high-dimensional data: a randomized convex-concave optimization approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830269)