Ethan Fang – Optimization Online

Blessing of Massive Scale: Spatial Graphical Model Estimation with a Total Cardinality Constraint

Published: 2015/11/18

Combinatorial Optimization, Statistics complexity, graphical models, high-dimensional data, l0-constraint method, nonconvex optimization

We consider the problem of estimating high dimensional spatial graphical models with a total cardinality constraint (i.e., the l0-constraint). Though this problem is highly nonconvex, we show that its primal-dual gap diminishes linearly with the dimensionality and provide a convex geometry justification of this ‘blessing of massive scale’ phenomenon. Motivated by this result, we propose … Read more

Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions

Published: 2014/11/13, Updated: 2015/09/01

Ethan Fang

Mengdi Wang

Han Liu

Convex Optimization, Statistics, Stochastic Programming composition, sample complexity, statistical learning, stochastic gradient, stochastic optimization

Classical stochastic gradient methods are well suited for minimizing expected-value objective functions. However, they do not apply to the minimization of a nonlinear function involving expected values or a composition of two expected-value functions, i.e., problems of the form $\min_x \E_v\[f_v\big(\E_w [g_w(x)]\big) \]$. In order to solve this stochastic composition problem, we propose a class … Read more