UMN Machine Learning Seminar: Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution

The UMN Machine Learning Seminar Series brings together faculty, students, and local industrial partners who are interested in the theoretical, computational, and applied aspects of machine learning, to pose problems, exchange ideas, and foster collaborations. The talks are every Thursday from 12 p.m. - 1 p.m. during the Fall 2021 semester.

This week's speaker, Uday V. Shanbhag (Penn State), will be giving a talk titled "Probability Maximization via Minkowski Functionals: Convex Representations and Tractable Resolution."


In this paper, we consider the maximization of a probability P{ζ∣ζ∈K(x)} over a closed and convex set X, a special case of the chance-constrained optimization problem. We define K(x) as K(x)≜{ζ∈K∣c(x,ζ)≥0} where ζ is uniformly distributed on a convex and compact set K and c(x,ζ) is defined as either {c(x,ζ)≜1−|ζTx|m, m≥0} (Setting A) or c(x,ζ)≜Tx−ζ (Setting B). We show that in either setting, P{ζ∣ζ∈K(x)} can be expressed as the expectation of a suitably defined function F(x,ξ) with respect to an appropriately defined Gaussian density (or its variant), i.e. Ep~[F(x,ξ)]. We then develop a convex representation of the original problem requiring the minimization of g(E[F(x,ξ)]) over X where g is an appropriately defined smooth convex function. Traditional stochastic approximation schemes cannot contend with the minimization of g(E[F(⋅,ξ)]) over X, since conditionally unbiased sampled gradients are unavailable. We then develop a regularized variance-reduced stochastic approximation ({\textbf{r-VRSA}}) scheme that obviates the need for such unbiasedness by combining iterative {regularization} with variance-reduction. Notably, ({\textbf{r-VRSA}}) is characterized by both almost-sure convergence guarantees, a convergence rate of O(1/k1/2−a) in expected sub-optimality where a>0, and a sample complexity of O(1/ϵ6+δ) where δ>0.


Uday V. Shanbhag has held the Gary and Sheila Bello Chaired professorship in Ind. & Manuf. Engr. at Penn State University (PSU) since Nov. 2017 and has been at PSU since Fall 2012, prior to which he was at the University of Illinois at Urbana-Champaign (between 2006–2012, both as an assistant and a tenured associate professor). His interests lie in the analysis and solution of optimization problems, variational inequality problems, and noncooperative games complicated by nonsmoothness and uncertainty. He holds undergraduate and Master’s degrees from IIT,Mumbai (1993) and MIT, Cambridge (1998) respectively and a Ph.D. in management science and engineering (Operations Research) from Stanford University (2006).


Start date
Thursday, Oct. 14, 2021, Noon
End date
Thursday, Oct. 14, 2021, 1 p.m.