My research is concerend with discrete optimization problems in machine learning. Most recently, I have been working on submodular functions and graph cuts.
I have also worked on theoretical aspects of clustering and density estimation, from the perspective of approximation as well as learning theory.
Below is a summary of projects, and links to code. I have also coorganized the NIPS workshop on Discrete Optimization in Machine Learning.
Structured problems with submodular cost
The generic setting here is as follows: take a combinatorial optimization problem, and replace the usual sumofweights cost by a nonlinear, submodular function. This makes the problem much harder but has nice applications. In particular, we worked on this setting with graph cuts, for which there are applications in inference and computer vision.
In addition, we derived online algorithms for structured decision problems (e.g., online spanning tree, or st cut) with submodular cost (in contrast, almost all previous results are for linear costs).
During our work, we came across several functions that are actually not submodular (but maybe some people hoped them to be), and thus I am collecting those functions in a bag of submodular nonexamples.
Clustering & Graph Cuts
Nearest Neighbor Clustering: we developed a generic algorithm to minimize popular clustering objective functions, such as Normalized Cut or kmeans. This method is consistent, thanks to pooling neighboring points. (with Ulrike von Luxburg, Sebastien Bubeck, Michael Kaufmann).
Download Demo Code
Generalized Clustering via Kernel Embeddings: The concept of clustering can be generalized to finding distributions that are maximally separated. The standard case is to measure separation by means of the distribution (kmeans). MMD, the maximum mean discrepancy in a feature space, allows to also take higherorder moments into account. As a result, it is possible to e.g. separate two Gaussians with the same mean but different variance. Interestingly, maximizing MMD is closely related to kernel kmeans and various other clustering criteria. (with Ulrike von Luxburg, Bernhard Schoelkopf, Arthur Gretton, Bharath Sriperumbudur)
Approximation Algorithms for Tensor Clustering: We prove an approximation factor for tensor clustering (i.e., "cutting a big cube into little cubes") for maybe the simplest possible algorithm. Various divergences are possible, such as Euclidean distance, Bregman divergences etc. (with Suvrit Sra, Arindam Banerjee)
Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning. Data is often noisy. If there are several good solutions to an optimization problem (here, graph partitioning), then the noise can be the determining part to make one solution optimal. However, how much do we want to trust this solution, if a small perturbation in the data suddenly makes another solution the best? this work proposes a method to test the stability of an optimal graph cut solution to perturbation of the edge weights (i.e., noise).We also show that several common clustering and graph partitioning objectives fall in our framework. (with Sebastian Nowozin)
ICA
Fast Kernel ICA: We developed a Newtonlike method for kernel ICA that uses HSIC as the independence criterion (with Hao Shen, Arthur Gretton).
Download Code for Fast kernel ICA

S. Jegelka, F. Bach, S. Sra
(2013). Reflection methods for userfriendly submodular optimization In: Advances in Neural Information Processing Systems 26, (Ed) C.J.C. Burges and L. Bottou and M. Welling and Z. Ghahramani and K.Q. Weinberger, 1313–1321, 27th Annual Conference on Neural Information Processing Systems (NIPS 2013), (In Proceedings)

S. Jegelka
(2012). Combinatorial Problems with Submodular Coupling in Machine Learning and Computer Vision ETH Zürich, Switzerland, (Thesis)

S. Jegelka, H. Lin, J. Bilmes
(2011). On Fast Approximate Submodular Minimization In: Advances in Neural Information Processing Systems 24, (Ed) J ShaweTaylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger, 460468, TwentyFifth Annual Conference on Neural Information Processing Systems (NIPS 2011), (In Proceedings)

S. Jegelka, J. Bilmes
(2011). Online submodular minimization for combinatorial structures (Ed) Getoor, L. , T. Scheffer, International Machine Learning Society, Madison, WI, USA, 345352, ISBN: 9781450306195, 28th International Conference on Machine Learning (ICML 2011), (In Proceedings)

S. Jegelka, J. Bilmes
(2011). Approximation Bounds for Inference using Cooperative Cut (Ed) Getoor, L. , T. Scheffer, International Machine Learning Society, Madison, WI, USA, 577584, ISBN: 9781450306195, 28th International Conference on Machine Learning (ICML 2011), (In Proceedings)

S. Jegelka
(2011). Cooperative Cuts: a new use of submodularity in image segmentation Institute of Science and Technology, Second I.S.T. Austria Symposium on Computer Vision and Machine Learning, (In Proceedings)

S. Jegelka
(2011). Cooperative Cuts COSA Workshop: Combinatorial Optimization, Statistics, and Applications, (In Proceedings)

S. Jegelka, J. Bilmes
(2010). Cooperative Cuts: Graph Cuts with Submodular Edge Weights Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, (TechReport)

S. Jegelka, J. Bilmes
(2010). Cooperative Cuts for Image Segmentation University of Washington, Washington, DC, USA, (TechReport)

S. Jegelka, S. Sra, A. Banerjee
(2009). Approximation Algorithms for Tensor Clustering In: ALT 2009, (Ed) Gavalda, R. , G. Lugosi, T. Zeugmann, S. Zilles, Algorithmic Learning Theory: 20th International Conference (ALT 2009), Springer, Berlin, Germany, 368383, The 20th International Conference on Algorithmic Learning Theory, (In Proceedings)

S. Nowozin, S. Jegelka
(2009). Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning In: ICML 2009, (Ed) Danyluk, A. , L. Bottou, M. Littman, Proceedings of the 26th International Conference on Machine Learning (ICML 2009), ACM Press, New York, NY, USA, 769776, 26th International Conference on Machine Learning, (In Proceedings)

S. Jegelka, A. Gretton, B. Schölkopf, BK. Sriperumbudur, U. Luxburg
(2009). Generalized Clustering via Kernel Embeddings In: KI 2009: AI and Automation, Lecture Notes in Computer Science, Vol. 5803, (Ed) B Mertsching and M Hund and Z Aziz, KI 2009: Advances in Artificial Intelligence, Springer, Berlin, Germany, 144152, 32nd Annual Conference on Artificial Intelligence (KI), (In Proceedings)

H. Shen, S. Jegelka, A. Gretton
(2009). Fast KernelBased Independent Component Analysis IEEE Transactions on Signal Processing, 57, (9), 34983511, (Article)

U. Luxburg, S. Bubeck, S. Jegelka, M. Kaufmann
(2008). Consistent Minimization of Clustering Objective Functions In: Advances in neural information processing systems 20, (Ed) Platt, J. C., D. Koller, Y. Singer, S. Roweis, Advances in Neural Information Processing Systems 20: 21st Annual Conference on Neural Information Processing Systems 2007, Curran, Red Hook, NY, USA, 961968, ISBN: 9781605603520, TwentyFirst Annual Conference on Neural Information Processing Systems (NIPS 2007), (In Proceedings)

S. Sra, S. Jegelka, A. Banerjee
(2008). Approximation Algorithms for Bregman Clustering Coclustering and Tensor Clustering MaxPlanck Institute for Biological Cybernetics, Tübingen, Germany, (TechReport)

H. Shen, S. Jegelka, A. Gretton
(2007). Fast Kernel ICA using an Approximate Newton Method In: JMLR Workshop and Conference Proceedings Volume 2: AISTATS 2007, (Ed) Meila, M. , X. Shen, Proceedings of the 11th International Conference on Artificial Intelligence and Statistics (AISTATS 2007), MIT Press, Cambridge, MA, USA, 476483, 11th International Conference on Artificial Intelligence and Statistics, (In Proceedings)

S. Jegelka, A. Gretton
(2007). Brisk Kernel ICA In: Large Scale Kernel Machines, (Ed) Bottou, L. , O. Chapelle, D. DeCoste, J. Weston, MIT Press, Cambridge, MA, USA, 225250, (InBook)

S. Jegelka
(2007). Statistical Learning Theory Approaches to Clustering EberhardKarlsUniversität Tübingen, Tübingen, Germany, (Thesis)

B. Kulis, S. Sra, S. Jegelka
(2007). Scalable Semidefinite Programming using Convex Perturbations University of Texas, Austin, TX, USA, (TechReport)

S. Jegelka, JA. Bednar, R. Miikkulainen
(2006). Prenatal development of ocular dominance and orientation maps in a selforganizing model of V1 Neurocomputing, 69, (1012), 12911296, (Article)

H. Shen, S. Jegelka, A. Gretton
(2006). Geometric Analysis of Hilbert Schmidt Independence criterion based ICA contrast function National ICT Australia, Canberra, Australia, (TechReport)

S. Jegelka, A. Gretton, D. Achlioptas
(2005). Kernel ICA for Large Scale Problems , NIPS 2005 Workshop on Large Scale Kernel Machines, (In Proceedings)