Publication
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
Publications associées (62)
Efficient Relaxations for Dense CRFs with Sparse Higher-Order Potentials
Dense conditional random fields (CRFs) have become a popular framework for modeling several problems in computer vision such as stereo correspondence and multiclass semantic segmentation. By modeling long-range interactions, dense CRFs provide a labeling t ...
SIAM PUBLICATIONS2019A General Theory of Equivariant CNNs on Homogeneous Spaces
We present a general theory of Group equivariant Convolutional Neural Networks (G-CNNs) on homogeneous spaces such as Euclidean space and the sphere. Feature maps in these networks represent fields on a homogeneous base space, and layers are equivariant ma ...
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2019Algorithms For Clustering Problems
Clustering is a classic topic in combinatorial optimization and plays a central role in many areas, including data science and machine learning. In this thesis, we first focus on the dynamic facility location problem (i.e., the facility location problem in ...
EPFL2018New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials
Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...
EPFL2018Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...
2018Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization
We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...
NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018Improved stability of optimal traffic paths
Models involving branched structures are employed to describe several supply-demand systems such as the structure of the nerves of a leaf, the system of roots of a tree, and the nervous or cardiovascular systems. Given a flow (traffic path) that transports ...
2018A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming
We propose a conditional gradient framework for a composite convex minimization template with broad applications. Our approach combines the notions of smoothing and homotopy under the CGM framework, and provably achieves the optimal O(1/sqrt(k)) convergenc ...
ICML2018Dynamic Facility Location via Exponential Clocks
Ola Nils Anders Svensson, Ashkan Norouzi Fard, Hyung Chan An
The dynamic facility location problem is a generalization of the classic facility location problem proposed by Eisenstat, Mathieu, and Schabanel to model the dynamics of evolving social/infrastructure networks. The generalization lies in that the distance ...
Association for Computing Machinery2017Strengths and Limitations of Linear Programming Relaxations
Many of the currently best-known approximation algorithms for NP-hard optimization problems are based on Linear Programming (LP) and Semi-definite Programming (SDP) relaxations. Given its power, this class of algorithms seems to contain the most favourable ...
EPFL2017