Can Kizilkale PhD Proposal

Thursday, June 6, 2019 - 11:30am to 1:30pm
HFH 1132
Topics in Computer Science
Can Kizikale
Shivkumar Chandrasekaran (Chair), Omer Egecioglu, John Gilbert


The first topic will be on Restarted Moment based First Order Methods. First order methods are very popular due to their low complexity and using momentum to speed them up is a well-known technique. These methods are known to have non-monotonic but periodic behavior in the high momentum regime. If important parameters like condition number are known the momentum can be adjusted to get linear convergence. Unfortunately, these parameters are usually not accessible. One of the most intuitive and well-known heuristics is to look at the inner product of the momentum and gradient vector, and restart when this inner product is positive. In this part of the talk, we will analyze this restarting scheme, propose a novel restarting criteria and discuss how to extend these methods to non-smooth objective functions. 

For the second topic, we investigate the computation of the sparsest solution to an underdetermined system of linear equations using the Huber loss function as a proxy for the 1-norm and a quadratic error term a la Lasso. The approach is termed “penalized Huber ` loss”. We will show results that allow calculating a sparse solution using a simple extrapolation formula under a sign constancy condition that can be removed if one works with extreme points. Conditions leading to sign constancy, as well as necessary and sufficient conditions for computation of the sparsest solution by penalized Huber loss, and ties among different solutions will be discussed.

The last topic will be on mechanism design on trade networks. For preferences satisfying gross substitutes property, it has been shown that a competitive equilibrium exists in trading networks. So far the majority of the work for this problem are focused on mechanisms achieving an efficient outcome for the submodular flow problem. We will discuss the shortcomings of the recent approaches and how to tackle settings with additional constraints.

Everyone welcome!