2018

Yong Sheng Soh is selected as the winner of the 2018 INFORMS Optimization Society Student Prize


Citation

Yong Sheng Soh (California Institute of Technology). Paper title: Learning Semidefinite Regularizers.  (Other authors: Venkat Chandrasekaran)

Regularization techniques are widely employed in the solution of many optimization problems arising in statistics, operations research, signal processing, and many other disciplines. The common approach is to add penalty functions to the objectives with the goal of inducing a particular desirable structure in the solution. However, picking the "right" penalty often requires prior domain-specific expertise, and can become particularly challenging when dealing with high-dimensional and unstructured data-sets. In contrast, the current paper proposes a framework for identifying suitable regularizers directly from data rather than through human-provided expertise. The paper makes four fundamental contributions. It first makes a very interesting connection between a well-established method in machine learning named "dictionary learning" and the problem of learning a regularization function by solving linear programs. Using this insight, the paper develops an algorithmic framework to learn semidefinite programming regularizers from data, relying on very sophisticated tools developed in entirely different contexts (in particular, the Operator Sinkhorn procedure). Third, the paper proves that under suitable conditions on the input data, the algorithm provides a locally linearly convergent method for identifying the correct regularizer so as to promote the type of structure contained in the data. The analysis is a real tour-de-force that blends ideas from algebraic geometry, measure concentration, operator theory, and nonlinear optimization. Finally, the paper demonstrates the superiority of such semidefinite programming regularizers in several image de-noising tasks using real data.


Second Prize

- Felix Happach (Technische Universitat Munich). Paper title: Good Clusterings Have Large Volume (Other authors: Steffen Borgwardt)
- Joey Huchette (Massachusetts Institute of Technology). Paper title: A combinatorial approach for small and strong formulations of disjunctive constraints. (Other authors: Juan-Pablo Vielma)

Honorable Mention

- Yanli Liu (UCLA). Paper title: A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs. (Other authors: Ernest K Ryu, Wotao Yin)
- Naman Agarwal and Brian Bullins (Princeton). Paper title: Second-Order Stochastic Optimization for Machine Learning in Linear Time. (Other authors: Elad Hazan)
- Nam Ho-Nguyen (Carnegie Mellon University). Paper title: Online First-Order Framework for Robust Convex Optimization. (Other authors: Fatma Kilinc-Karzan)

Selection Committee

Dan Iancu (chair), Amir Ali Ahmadi, Frank Curtis, Illya Hicks