Samet Oymak

Email: firstlast at gmail dot com (first=samet, last=oymak)


I am a researcher at The Voleon Group. Previously, I worked at Google as a software engineer and spent time at Berkeley as a postdoctoral scholar at the Simons Institute. I received my PhD degree in Electrical Engineering from Caltech.

I am broadly interested in optimization, statistics and learning theory. This include various convex/nonconvex optimization problems, dimensionality reduction techniques and large scale distributed algorithms. Often, I am interested in developing efficient algorithms that have good tradeoffs between speed, accuracy, and the amount of required data. Recently, I am studying several deep learning problems from a theoretical point of view to build principled algorithms.

Here is my CV. Some recent publications are listed below.

Recent papers

Learning Feature Nonlinearities with Binned Regression: What to do when the dependence betweens feature and response is nonlinear? We propose a principled algorithm to learn additive models based on feature binning. Borrowing techniques from high-dimensional statistics, we show that such models can be learned with linear convergence and using near optimal amount of data. Our findings naturally highlight the role of model complexity. Sharp Time-Data Tradeoffs for Linear Inverse Problems: We present a unified convergence analysis of the gradient projection algorithm applied to inverse problems. We *very* accurately characterize the convergence rate associated with a wide variety of random measurement ensembles in terms of the data amount and structural complexity of the model. Universality Laws for Randomized Dimension Reduction: Gaussianity assumption plays a central role in various data science problems. In this work, we show that a large class of random matrices behaves in a identical fashion to Gaussians for various optimization and learning problems. Fast and Reliable Estimation from Nonlinear Observations: We show that it is possible to quickly learn nonlinear models even if the relation between input and output (i.e. link function) is not known. The key idea is linear approximation of the nonlinearity. Sample Optimal Bounds for Fast Binary Embedding: A common strategy for fast document and image retrieval is to create a binary signature of the data by embedding it into Hamming cube. Ideally, we want a fast and space efficient embedding. We show that subsampled Fourier transform indeed provides an almost-optimal embedding strategy even after {+1, -1} quantization. Sketching any set with RIP matrices: We show that for the purposes of dimensionality reduction certain class of structured random matrices behave similarly to random Gaussian matrices. This class includes several matrices for which matrix-vector multiply can be computed in log-linear time, providing efficient dimensionality reduction of general sets. Simultaneously structured models: In several applications, the model of interest has several structures at the same time. Examples include, quadratic compressed sensing, sparse PCA, low-rank tensor completion and estimating sparse and smooth signals (fused lasso). We show a weakness result for multi-objective convex penalizations that aims to recover and/or estimate such signals. The recently updated paper has simpler failure conditions that apply to a wide-range of measurement ensembles under much less assumptions. Precise graph clustering: Graph clustering problem arises in community detection and social networking setups. Given basic statistics of the graph, can we deduce whether we can identify (planted) clusters? We develop simple but precise performance formulae for convex optimization based clustering techniques. These bounds reveal intriguing phase transitions.

My thesis can be found here. Finally, you can click here for some personal facts.