The DOI matches its Crossref record; 159 of the 159 references it cites were found in a registry or an index.
Learning with Submodular Functions: A Convex Optimization Perspective
Abstract
Submodular functions are relevant to machine learning for at least two reasons: (1) some problems may be expressed directly as the optimization of submodular functions, and (2) the Lovász extension of submodular functions provides a useful set of regularization functions for supervised and unsupervised learning. In Learning with Submodular Functions: A Convex Optimization Perspective, the theory of submodular functions is presented in a self-contained way from a convex analysis perspective, presenting tight links between certain polyhedra, combinatorial optimization and convex optimization problems. In particular, it describes how submodular function minimization is equivalent to solving a wide variety of convex optimization problems. This allows the derivation of new efficient algorithms for approximate and exact submodular function minimization with theoretical guarantees and good practical performance. By listing many examples of submodular functions, it reviews various applications to machine learning, such as clustering, experimental design, sensor placement, graphical model structure learning or subset selection, as well as a family of structured sparsity-inducing norms that can be derived and used from submodular functions. Learning with Submodular Functions: A Convex Optimization Perspective is an ideal reference for researchers, scientists, or engineers with an interest in applying submodular functions to machine learning problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Elements of Information Theory
Cover, T. M., & Thomas, J. A. (2001) · Wiley eBooks · doi:10.1002/0471200611 · Cited by 36,808
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Gelman, A., Carlin, J. B., Stern, H. S., & Rubin, D. B. (2003) · doi:10.1201/9780429258480 · Cited by 27,276
The Elements of Statistical Learning
Hastie, T., Friedman, J., & Tibshirani, R. (2001) · Springer Series in Statistics · doi:10.1007/978-0-387-21606-5 · Cited by 24,162
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Gaussian Processes for Machine Learning
Rasmussen, C. E., & Williams, C. K. I. (2005) · doi:10.7551/mitpress/3206.001.0001 · Cited by 11,705
Network Flows: Theory, Algorithms, and Applications.
Smith, D. K., Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1994) · The Journal of the Operational Research Society · doi:10.2307/2583863 · Cited by 8,034
Maximizing the spread of influence through a social network
Kempe, D., Kleinberg, J., & Tardos, É. (2003) · Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/956750.956769 · Cited by 7,326
Multidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis
Kruskal, J. B. (1964) · Psychometrika · doi:10.1007/bf02289565 · Cited by 7,317
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
Kernel Methods for Pattern Analysis
Shawe-Taylor, J., & Cristianini, N. (2004) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809682 · Cited by 6,587
Stanley, R. P., & Rota, G.-C. (1997) · Cambridge University Press eBooks · doi:10.1017/cbo9780511805967 · Cited by 6,025
Chung, F. (1996) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/092 · Cited by 5,524
Image Denoising Via Sparse and Redundant Representations Over Learned Dictionaries
Elad, M., & Aharon, M. (2006) · IEEE Transactions on Image Processing · doi:10.1109/tip.2006.881969 · Cited by 5,321
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (2001) · SIAM Review · doi:10.1137/s003614450037906x · Cited by 5,085
Introduction to Lattices and Order
Davey, B. A., & Priestley, H. A. (2002) · Cambridge University Press eBooks · doi:10.1017/cbo9780511809088 · Cited by 4,901
Adapting to Unknown Smoothness via Wavelet Shrinkage
Donoho, D. L., & Johnstone, I. M. (1995) · Journal of the American Statistical Association · doi:10.1080/01621459.1995.10476626 · Cited by 4,630
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
Choquet, G. (1954) · Annales de l'Institut Fourier · doi:10.5802/aif.53 · Cited by 4,204
Sparse coding with an overcomplete basis set: A strategy employed by V1?
Olshausen, B. A., & Field, D. J. (1997) · Vision Research · doi:10.1016/s0042-6989(97)00169-7 · Cited by 3,642
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Learning Bayesian Networks: The Combination of Knowledge and Statistical Data
Heckerman, D., Geiger, D., & Chickering, D. M. (1995) · Machine Learning · doi:10.1023/a:1022623210503 · Cited by 3,231
chambolle (2004) · doi:10.1023/b:jmiv.0000011321.19549.88 · Cited by 3,227
What energy functions can be minimized via graph cuts?
Kolmogorov, V., & Zabih, R. (2004) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2004.1262177 · Cited by 3,127
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
Combinatorial optimization. Polyhedra and efficiency.
Schrijver, A. (2003) · UvA-DARE (University of Amsterdam) · Cited by 3,045
An algorithm for quadratic programming
Frank, M., & Wolfe, P. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030109 · Cited by 3,030
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Sparsity and Smoothness Via the Fused Lasso
Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., & Knight, K. (2005) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2005.00490.x · Cited by 2,724
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
Online Learning for Matrix Factorization and Sparse Coding
Mairal, J., Bach, F., Ponce, J., & Sapiro, G. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0908.0050 · Cited by 2,258
Self-citationProximal Splitting Methods in Signal Processing
Combettes, P. L., & Pesquet, J.-C. (2011) · Springer Optimization and Its Applications · doi:10.1007/978-1-4419-9569-8_10 · Cited by 2,183
Supermodularity and Complementarity
Topkis, D. M. (2011) · Princeton University Press eBooks · doi:10.1515/9781400822539 · Cited by 2,138
Elements of Algebraic Topology
Munkres, J. R. (2018) · CRC Press eBooks · doi:10.1201/9780429493911 · Cited by 2,102
Fedorov, V. V., Studden, W. J., & Klimko, E. M. (1972) · Cited by 2,092
Mallows, C. L. (1995) · Technometrics · doi:10.1080/00401706.1995.10484370 · Cited by 2,083
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
A new approach to the maximum-flow problem
Goldberg, A. V., & Tarjan, R. E. (1988) · Journal of the ACM · doi:10.1145/48014.61051 · Cited by 1,882
Sparse Reconstruction by Separable Approximation
Wright, S. J., Nowak, R. D., & Figueiredo, M. A. T. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2016892 · Cited by 1,854
Hunter, D. R., & Lange, K. (2004) · The American Statistician · doi:10.1198/0003130042836 · Cited by 1,783
Clustering with Bregman Divergences
Banerjee, A., Merugu, S., Dhillon, I., & Ghosh, J. (2004) · Proceedings of the 2004 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972740.22 · Cited by 1,472
Problem complexity and method efficiency in optimization
(1984) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(84)90101-0 · Cited by 1,329
Yuille, A. L., & Rangarajan, A. (2003) · Neural Computation · doi:10.1162/08997660360581958 · Cited by 1,151
Submodular Functions and Optimization
(2005) · Annals of discrete mathematics · doi:10.1016/s0167-5060(05)x8001-3 · Cited by 1,145
Selected Topics in Column Generation
Lübbecke, M. E., & Desrosiers, J. (2005) · Operations Research · doi:10.1287/opre.1050.0234 · Cited by 1,102
Mallows, C. L. (1995) · Technometrics · doi:10.2307/1269729 · Cited by 1,080
On Model Selection Consistency of Lasso
ZhaoPeng, & Yubin, Y. (2006) · Journal of Machine Learning Research · doi:10.5555/1248547.1248637 · Cited by 996
Enumerative Combinatorics: Volume 1
Stanley, R. P. (2011) · Cited by 979
Submodular functions and convexity
Lovász, L. (1983) · Mathematical Programming The State of the Art · doi:10.1007/978-3-642-68874-4_10 · Cited by 964
A Class of Submodular Functions for Document Summarization
Lin, H. Z., & Bilmes, J. (2011) · Cited by 960
Supervised Dictionary Learning
Mairal, J., Bach, F., Ponce, J., Sapiro, G., & Zisserman, A. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.3083 · Cited by 938
Self-citationRevisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization
Jaggi, M. (2013) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 911
NESTA: A Fast and Accurate First-Order Method for Sparse Recovery
Becker, S., Bobin, J., & Candès, E. J. (2009) · Cited by 897
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
Statistical Inference under Order Restrictions (The Theory and Application of Isotonic Regression)
Vincze, I., Barlow, R. E., Bartholomew, D. J., Bremner, J. M., & Brunk, H. D. (1973) · International Statistical Review / Revue Internationale de Statistique · doi:10.2307/1402630 · Cited by 842
An analysis of approximations for maximizing submodular set functions - 1Preprint
Fisher, M. L., Nemhauser, G. L., & Wolsey, L. A. (1978) · RePEc: Research Papers in Economics · Cited by 837
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827
Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time
Spielman, D. A., & Teng, S.-H. (2004) · Journal of the ACM · doi:10.1145/990308.990310 · Cited by 825
HOW GOOD IS THE SIMPLEX ALGORITHM
Klee, V. L., & Minty, G. J. (1970) · Cited by 769
Osborne, M. R., Presnell, B., & Turlach, B. A. (2000) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2000.10474883 · Cited by 696
A combinatorial strongly polynomial algorithm for minimizing submodular functions
Iwata, S., Fleischer, L., & Fujishige, S. (2001) · Journal of the ACM · doi:10.1145/502090.502096 · Cited by 683
Horst, R., & Thoai, N. V. (1999) · Journal of Optimization Theory and Applications · doi:10.1023/a:1021765131316 · Cited by 672
Consistency of the group Lasso and multiple kernel learning
Bach, F. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0707.3390 · Cited by 669
Self-citationA Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time
Schrijver, A. (2000) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.2000.1989 · Cited by 651
A note on the group lasso and a sparse group lasso
Friedman, J. H., Hastie, T. J., & Tibshirani, R. J. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1001.0736 · Cited by 619
Numerical optimization: theoretical and practical aspects
(2003) · Choice Reviews Online · doi:10.5860/choice.41-0357 · Cited by 614
Optimization with Sparsity-Inducing Penalties
Bach, F. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985118 · Cited by 608
Self-citationSignal Reconstruction From Noisy Random Projections
Haupt, J., & Nowak, R. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.880031 · Cited by 608
Submodular Functions, Matroids, and Certain Polyhedra
Edmonds, J. (2003) · Lecture Notes in Computer Science · doi:10.1007/3-540-36478-1_2 · Cited by 512
Fonctions convexes duales et points proximaux dans un espace hilbertien
Moreau, J. J. (1962) · HAL (Le Centre pour la Communication Scientifique Directe) · Cited by 501
Exact optimization for markov random fields with convex priors
Ishikawa, H. (2003) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2003.1233908 · Cited by 486
Concavity of certain maps on positive definite matrices and applications to Hadamard products
Ando, T. (1979) · Linear Algebra and its Applications · doi:10.1016/0024-3795(79)90179-4 · Cited by 475
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Golovin, D., & Krause, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.3967 · Cited by 461
Maximizing Non-monotone Submodular Functions
Feige, U., Mirrokni, V. S., & Vondrák, J. (2011) · SIAM Journal on Computing · doi:10.1137/090779346 · Cited by 452
Structured Variable Selection with Sparsity-Inducing Norms
Jenatton, R., Audibert, J.-Y., & Bach, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0904.3523 · Cited by 431
Self-citationCornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1979) · Management Science · doi:10.1287/mnsc.25.8.808 · Cited by 430
A Fast Parametric Maximum Flow Algorithm and Applications
Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989) · SIAM Journal on Computing · doi:10.1137/0218003 · Cited by 427
Accelerated greedy algorithms for maximizing submodular set functions
Minoux, M. (2005) · Springer eBooks · doi:10.1007/bfb0006528 · Cited by 411
Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
Nedić, A., & Ozdaglar, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070708111 · Cited by 399
Convex Analysis and Nonlinear Optimization
Borwein, J. M., & Lewis, A. S. (2000) · Springer eBooks · doi:10.1007/978-1-4757-9859-3 · Cited by 394
Tree-Guided Group Lasso for Multi-Task Regression with Structured Sparsity
Kim, S., & Xing, E. P. (2018) · Figshare · doi:10.1184/r1/6476414 · Cited by 374
On Implementing the Push—Relabel Method for the Maximum Flow Problem
Cherkassky, B. V., & Goldberg, A. V. (1997) · Algorithmica · doi:10.1007/pl00009180 · Cited by 370
On characterization of entropy function via information inequalities
Zhang, Z., & Yeung, R. W. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681320 · Cited by 351
Near-optimal Nonmyopic Value of Information in Graphical Models
Krause, A., & Guestrin, C. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1207.1394 · Cited by 349
Das, A., & Kempe, D. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1102.3975 · Cited by 330
Total Variation Minimization and a Class of Binary MRF Models
Chambolle, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/11585978_10 · Cited by 324
Finding the nearest point in A polytope
Wolfe, P. (1976) · Mathematical Programming · doi:10.1007/bf01580381 · Cited by 321
Structured Sparsity through Convex Optimization
Bach, F., Jenatton, R., Mairal, J., & Obozinski, G. (2012) · Statistical Science · doi:10.1214/12-sts394 · Cited by 315
Self-citationA Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012) · Statistical Science · doi:10.1214/12-sts400 · Cited by 287
Structured Sparse Principal Component Analysis
Jenatton, R., Obozinski, G., & Bach, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0909.1440 · Cited by 277
Self-citationMRF Energy Minimization and Beyond via Dual Decomposition
Komodakis, N., Paragios, N., & Tziritas, G. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2010.108 · Cited by 277
Bayesian Inference and Optimal Design for the Sparse Linear Model
Seeger, M. (2008) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5555/1390681.1390707 · Cited by 277
Learning invariant features through topographic filter maps
Kavukcuoglu, K., Ranzato, M., Fergus, R., & LeCun, Y. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206545 · Cited by 274
Proximal Methods for Hierarchical Sparse Coding
Jenatton, R., Mairal, J., Obozinski, G., & Bach, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.2139 · Cited by 272
Self-citationOn the Non-Negative Garrotte Estimator
Yuan, M., & Lin, Y. (2007) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2007.00581.x · Cited by 264
Active set algorithms for isotonic regression; A unifying framework
Best, M. J., & Chakravarti, N. (1990) · Mathematical Programming · doi:10.1007/bf01580873 · Cited by 262
A faster strongly polynomial time algorithm for submodular function minimization
Orlin, J. B. (2009) · Mathematical Programming · doi:10.1007/s10107-007-0189-2 · Cited by 243
A Unified Continuous Greedy Algorithm for Submodular Maximization
Feldman, M., Naor, J., & Schwartz, R. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.46 · Cited by 242
Statistical inference under order restrictions : the theory and application of isotonic regression
Barlow, R. E. (1972) · Cited by 234
Bundle Methods for Regularized Risk Minimization
Teo, C. H., Vishwanthan, S. V. N., Smola, A. J., & Le, Q. V. (2010) · doi:10.5555/1756006.1756016 · Cited by 223
Optimal flows in networks with multiple sources and sinks
Megiddo, N. (1974) · Mathematical Programming · doi:10.1007/bf01585506 · Cited by 216
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization
Buchbinder, N., Feldman, M., Naor, J., & Schwartz, R. (2012) · 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2012.73 · Cited by 216
A Path Algorithm for the Fused Lasso Signal Approximator
Hoefling, H. (2010) · Journal of Computational and Graphical Statistics · doi:10.1198/jcgs.2010.09208 · Cited by 214
Clusterpath An Algorithm for Clustering using Convex Fusion Penalties
Hocking, T. D., Joulin, A., Bach, F., & Vert, J. (2011) · Cited by 211
Self-citationLearning with Submodular Functions: A Convex Optimization Perspective
Bach, F. (2013) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000039 · Cited by 211
Self-citationAn O(n) algorithm for quadratic knapsack problems
Brucker, P. (1984) · Operations Research Letters · doi:10.1016/0167-6377(84)90010-5 · Cited by 206
Ambuhl, C., Mas, M., & Svensson, O. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.40 · Cited by 206
Algorithms for subset selection in linear regression
Das, A., & Kempe, D. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374384 · Cited by 196
Grouped and Hierarchical Model Selection through Composite Absolute Penalties
Zhao, P., Rocha, G. V., & Yu, B. (2007) · Cited by 195
Some comments on Wolfe's ‘away step’
Guelat, J., & Marcotte, P. (1986) · Mathematical Programming · doi:10.1007/bf01589445 · Cited by 188
An Online Algorithm for Maximizing Submodular Functions
Streeter, M., & Golovin, D. (2007) · doi:10.21236/ada476748 · Cited by 183
Learning with structured sparsity
Huang, J., Zhang, T., & Metaxas, D. (2009) · Proceedings of the 26th Annual International Conference on Machine Learning · doi:10.1145/1553374.1553429 · Cited by 182
Exploring Large Feature Spaces with Hierarchical Multiple Kernel Learning
Bach, F. (2008) · arXiv (Cornell University) · doi:10.48550/arxiv.0809.1493 · Cited by 172
Self-citationSparse Signal Recovery Using Markov Random Fields
Cevher, V., Hegde, C., Duarte, M. F., & Baraniuk, R. G. (2009) · Defense Technical Information Center (DTIC) · doi:10.21236/ada520187 · Cited by 167
On maximizing welfare when utility functions are subadditive
Feige, U. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132523 · Cited by 163
On Total Variation Minimization and Surface Evolution Using Parametric Maximum Flows
Chambolle, A., & Darbon, J. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-009-0238-9 · Cited by 160
An efficient algorithm for image segmentation, Markov random fields and related problems
Hochbaum, D. S. (2001) · Journal of the ACM · doi:10.1145/502090.502093 · Cited by 156
Network Flow Algorithms for Structured SparsityPreprint
Mairal, J., Jenatton, R., Obozinski, G., & Bach, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1008.5209 · Cited by 148
Self-citationSubmodularity and its applications in optimized information gathering
Krause, A., & Guestrin, C. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1989734.1989736 · Cited by 145
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Chekuri, C., Vondrák, J., & Zenklusen, R. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993740 · Cited by 133
The Smooth-Lasso and other ℓ1+ℓ2-penalized methods
Hebiri, M., & van de Geer, S. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs638 · Cited by 130
Conditional gradient algorithms with open loop step size rules
Dunn, J. C., & Harshbarger, S. D. (1978) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(78)90137-3 · Cited by 122
EFFICIENT METHODS IN CONVEX PROGRAMMING
Nemirovski, A. S. (2007) · Cited by 114
Submodular Dictionary Selection for Sparse Representation
Krause, A., & Cevher, V. (2010) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · Cited by 107
Balcan, M.-F., & Harvey, N. J. A. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993741 · Cited by 106
Complexity Analysis of the Lasso Regularization PathPreprint
Mairal, J., & Yu, B. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1205.0079 · Cited by 103
Efficient Minimization of Decomposable Submodular FunctionsPreprint
Stobbe, P., & Krause, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1010.5511 · Cited by 99
Lifted coordinate descent for learning with trace-norm regularization
Dudík, M., Harchaoui, Z., & Malick, J. (2012) · Cited by 96
Consistent probabilistic outputs for protein function prediction
Obozinski, G., Lanckriet, G. R. G., Grant, C. E., Jordan, M. I., & Noble, W. S. (2008) · Genome biology · doi:10.1186/gb-2008-9-s1-s6 · Cited by 94
Pukelsheim, F. (2006) · Society for Industrial and Applied Mathematics eBooks · Cited by 93
Catching Change-points with Lasso
Lévy‐Leduc, C., & Harchaoui, Z. (2007) · neural information processing systems · Cited by 90
Convex and Network Flow Optimization for Structured SparsityPreprint
Mairal, J., Jenatton, R., Obozinski, G., & Bach, F. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1104.1872 · Cited by 87
Self-citationDuality Between Subgradient and Conditional Gradient Methods
Bach, F. (2015) · SIAM Journal on Optimization · doi:10.1137/130941961 · Cited by 84
Self-citationThe Reduced Monotonic Regression Method
Schell, M. J., & Singh, B. (1997) · Journal of the American Statistical Association · doi:10.1080/01621459.1997.10473609 · Cited by 83
Multiscale Mining of fMRI Data with Hierarchical Structured Sparsity
Jenatton, R., Gramfort, A., Michel, V., Obozinski, G., Eger, E., Bach, F., & Thirion, B. (2012) · SIAM Journal on Imaging Sciences · doi:10.1137/110832380 · Cited by 82
Self-citationA conditional gradient method with linear rate of convergence for solving convex linear systems
Beck, A., & Teboulle, M. (2004) · Mathematical Methods of Operations Research · doi:10.1007/s001860300327 · Cited by 79
Projections onto order simplexes
Grotzinger, S. J., & Witzgall, C. (1984) · Applied Mathematics & Optimization · doi:10.1007/bf01449044 · Cited by 77
Fast Newton-type Methods for Total Variation Regularization
Barbero, L., & Sra, S. (2011) · International Conference on Machine Learning · Cited by 76
Reflection methods for user-friendly submodular optimizationPreprint
Jegelka, S., Bach, F., & Sra, S. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1311.4296 · Cited by 72
Self-citationMinimizing a sum of submodular functions
Kolmogorov, V. (2012) · Discrete Applied Mathematics · doi:10.1016/j.dam.2012.05.025 · Cited by 67
Efficient regularized isotonic regression with application to gene–gene interaction search
Luss, R., Rosset, S., & Shahar, M. (2012) · The Annals of Applied Statistics · doi:10.1214/11-aoas504 · Cited by 59
On fast approximate submodular minimization
Jegelka, S., Lin, H. Z., & Bilmes, J. (2011) · MPG.PuRe (Max Planck Society) · Cited by 54
Minimum cuts, modular functions, and matroid polyhedra
Cunningham, W. H. (1985) · Networks · doi:10.1002/net.3230150206 · Cited by 52
The expressive power of binary submodular functions
Živný, S., Cohen, D. A., & Jeavons, P. (2009) · Discrete Applied Mathematics · doi:10.1016/j.dam.2009.07.001 · Cited by 49
Collaborative hierarchical sparse modeling
Sprechmann, P., Ramírez, I., Sapiro, G., & Eldar, Y. C. (2010) · Conference on Information Sciences and Systems · doi:10.1109/ciss.2010.5464845 · Cited by 44
Convex Optimization without Projection StepsPreprint
Jaggi, M. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1108.1170 · Cited by 37
Convex relaxations of structured matrix factorizationsPreprint
Bach, F. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1309.3117 · Cited by 31
Self-citationMulti-scale Mining of fMRI Data with Hierarchical Structured Sparsity
Jenatton, R., Gramfort, A., Michel, V., Obozinski, G., Bach, F., & Thirion, B. (2011) · International Workshop on Pattern Recognition in NeuroImaging · doi:10.1109/prni.2011.15 · Cited by 29
Self-citationLocal search for balanced submodular clusterings
Narasimhan, M., & Bilmes, J. A. (2007) · Cited by 26
Submodularity Cuts and Applications
Kawahara, Y., Nagano, K., Tsuda, K., & Bilmes, J. (2009) · Cited by 24
Decomposing Isotonic Regression for Efficiently Solving Large Problems
Luss, R., Rosset, S., & Shahar, M. (2010) · Cited by 13
Exhaustive family of energies minimizable exactly by a graph cut
Charpiat, G. (2011) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2011.5995567 · Cited by 6
Cited by
Berman, M., Triki, A. R., & Blaschko, M. B. (2018) · 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2018.00464 · Cited by 1,027
Structured Sparsity through Convex Optimization
Bach, F., Jenatton, R., Mairal, J., & Obozinski, G. (2012) · Statistical Science · doi:10.1214/12-sts394 · Cited by 315
Self-citationFast flux discriminant for large-scale sparse nonlinear classification
Chen, W., Chen, Y., & Weinberger, K. Q. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623627 · Cited by 12
Järvenpää, M., Vehtari, A., & Marttinen, P. (2019) · arXiv · doi:10.48550/arxiv.1910.06121 · Cited by 8
Metadata
- Authors
- Bach, F.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2013
- OpenAlex
- W2086058123
- Cited by
- 273
- References
- 159
- FWCI
- 11.52
- Type
- book
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.