Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization

We propose a stochastic conditional gradient method (CGM) for minimizing convex finitesum objectives formed as a sum of smooth and non-smooth terms. Existing CGM variants for this template either suffer from slow convergence rates, or require carefully increasing the batch size over the course of the algorithm’s execution, which leads to computing full gradients. In contrast, the proposed method, equipped with a stochastic average gradient (SAG) estimator, requires only one sample periteration. Nevertheless, it guarantees fast convergence rates on par with more sophisticated variance reduction techniques. In applications we put special emphasis on problems with a large number of separable constraints. Such problems are prevalent among semidefinite programming (SDP) formulations arising in machine learning and theoretical computer science. We provide numerical experiments on matrix completion, unsupervised clustering, and sparsest-cut SDPs.

Localized orthogonal decomposition method for the wave equation with a continuum of scales

Assyr Abdulle, Patrick Henning

In this paper we propose and analyze a new multiscale method for the wave equation. The proposed method does not require any assumptions on space regularity or scale-separation and it is formulated in the framework of the Localized Orthogonal Decomposition (LOD). We derive rigorous a priori error estimates for the L2-approximation properties of the method, finding that convergence rates of up to third order can be achieved. The theoretical results are confirrmed by various numerical experiments.

American Mathematical Society2017

Algorithms For Clustering Problems

Ashkan Norouzi Fard

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 evolving metrics). We present a new LP-rounding algorithm for facility location problems, which yields the first constant factor approximation algorithm for the dynamic facility location problem. Our algorithm installs competing exponential clocks on clients and facilities, and connects every client by the path that repeatedly follows the smallest clock in the neighborhood. The use of exponential clocks gives rise to several properties that distinguish our approach from previous LP-roundings for facility location problems. In particular, we use \emph{no clustering} and we enable clients to connect through paths of \emph{arbitrary lengths}. In fact, the clustering-free nature of our algorithm is crucial for applying our LP-rounding approach to the dynamic problem. Furthermore, we present both empirical and theoretical aspects of the

k

-means problem. The best known algorithm for

k

-means with a provable guarantee is a simple local-search heuristic that yields an approximation guarantee of

9+\epsilon

, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that enables us (1) to exploit the geometric structure of

k

-means and (2) to satisfy the hard constraint that at most

k

clusters are selected without deteriorating the approximation guarantee. Our main result is a

6.357

-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of

k

-means where the underlying metric is not required to be Euclidean and for

k

-median in Euclidean metrics. We also improve the running time of our algorithm to almost linear running time and still maintain a provable guarantee. We compare our algorithm with {\sc K-Means++} (a widely studied algorithm) and show that we obtain better accuracy with comparable and even better running time.

EPFL2018

Deep Learning Works in Practice. But Does it Work in Theory?

Rachid Guerraoui, Le Nguyen Hoang

Deep learning relies on a very specific kind of neural networks: those superposing several neural layers. In the last few years, deep learning achieved major breakthroughs in many tasks such as image analysis, speech recognition, natural language processing, and so on. Yet, there is no theoretical explanation of this success. In particular, it is not clear why the deeper the network, the better it actually performs. We argue that the explanation is intimately connected to a key feature of the data collected from our surrounding universe to feed the machine learning algorithms: large non-parallelizable logical depth. Roughly speaking, we conjecture that the shortest computational descriptions of the universe are algorithms with inherently large computation times, even when a large number of computers are available for parallelization. Interestingly, this conjecture, combined with the folklore conjecture in theoretical computer science that

P \neq NC

, explains the success of deep learning.

2018