Invited Session Thu.1.MA 141

Thursday, 10:30 - 12:00 h, Room: MA 141

Cluster 22: Stochastic optimization [...]

High dimensional statistics: Techniques from stochastic and robust optimization


Chair: Constantine Caramanis



Thursday, 10:30 - 10:55 h, Room: MA 141, Talk 1

Philippe Rigollet
Deviation optimal model selection using greedy algorithms


A statistical problem of model selection for regression can be simply described as a stochastic optimization problem where the objective is quadratic and the domain finite or countable.
To solve this problem it is now known that, contrary to the principle of empirical risk minimization, one should seek a solution in the convex hull of the domain. This idea is implemented by exponential weights that are known to solve the problem in expectation, but they are, surprisingly, sub-optimal in deviation. We propose a new formulation called Q-aggregation that consists in minimizing a penalized version of the original criterion but for which the penalty vanishes at the points of interest. This approach leads to efficient greedy algorithms in the spirit of Frank-Wolfe but for which stronger bounds can be derived.



Thursday, 11:00 - 11:25 h, Room: MA 141, Talk 2

Shie Mannor
Robust sparse regression and orthogonal matching pursuit

Coauthors: Constantine Caramanis, Yudong Chen


In this talk we consider simple, greedy methods for high dimensional regression with noise and erasures. We consider the setting of such corruptions not only in the output variable, but also in the covariates. We show our algorithms are more simple and hence much faster, with excellent empirical performance. We prove bounds on their performance that substantiate our computational results, and in particular show that the guaranteed performance is at least as good as all existing algorithms, including those of greater complexity.



Thursday, 11:30 - 11:55 h, Room: MA 141, Talk 3

Sujay Sanghavi
Learning the graph of network cascades

Coauthor: Praneeth Netrapalli


Cascades, or epidemic processes, are widely used models for phenomena in social networks (for vial marketing, spread of ideas), genetic networks (spread of activation of genes) and epidemiological networks (communicable diseases in populations). We consider the natural inverse problem in this setting: learning the graph of a network, given only node states as the cascade spreads. In this talk we
a) Show that for most popular cascade models, this can be posed as a sparse recovery problem in high dimensions, but from non-linear measurements.
b) Show that simple maximum likelihood, without regularization but with thresholding, achieves consistent graph recovery with sample complexity close to the corresponding lower bound
c) Establish a connection between the network graph, and the Markov graph of the cascade process.
We finish with two open problems: the performance of simple greedy algorithms, and the role of correlation decay.


  online loans . One of the main advantages of Sovaldi is that it can be used by patients belonging to all 4 genotypes. Buy Sovaldi is a very strong drug, and as all of them, it has a number of side effects that can be caused.