Daniel Vainsencher

NeurIPS Conference 2015 Conference Paper

Local Smoothness in Variance Reduced Optimization

• Daniel Vainsencher
• Han Liu
• Tong Zhang

Abstract We propose a family of non-uniform sampling strategies to provably speed up a class of stochastic optimization algorithms with linear convergence including Stochastic Variance Reduced Gradient (SVRG) and Stochastic Dual Coordinate Ascent (SDCA). For a large family of penalized empirical risk minimization problems, our methods exploit data dependent local smoothness of the loss functions near the optimum, while maintaining convergence guarantees. Our bounds are the first to quantify the advantage gained from local smoothness which are significant for some problems significantly better. Empirically, we provide thorough numerical results to back up our theory. Additionally we present algorithms exploiting local smoothness in more aggressive ways, which perform even better in practice.

NeurIPS Conference 2013 Conference Paper

Learning Multiple Models via Regularized Weighting

• Daniel Vainsencher
• Shie Mannor
• Huan Xu

We consider the general problem of Multiple Model Learning (MML) from data, from the statistical and algorithmic perspectives; this problem includes clustering, multiple regression and subspace clustering as special cases. A common approach to solving new MML problems is to generalize Lloyd's algorithm for clustering (or Expectation-Maximization for soft clustering). However this approach is unfortunately sensitive to outliers and large noise: a single exceptional point may take over one of the models. We propose a different general formulation that seeks for each model a distribution over data points; the weights are regularized to be sufficiently spread out. This enhances robustness by making assumptions on class balance. We further provide generalization bounds and explain how the new iterations may be computed efficiently. We demonstrate the robustness benefits of our approach with some experimental results and prove for the important case of clustering that our approach has a non-trivial breakdown point, i. e. , is guaranteed to be robust to a fixed percentage of adversarial unbounded outliers.

ICML Conference 2011 Conference Paper

Bundle Selling by Online Estimation of Valuation Functions

• Daniel Vainsencher
• Ofer Dekel
• Shie Mannor

JMLR Journal 2011 Journal Article

The Sample Complexity of Dictionary Learning

• Daniel Vainsencher
• Shie Mannor
• Alfred M. Bruckstein

A large set of signals can sometimes be described sparsely using a dictionary, that is, every element can be represented as a linear combination of few elements from the dictionary. Algorithms for various signal processing applications, including classification, denoising and signal separation, learn a dictionary from a given set of signals to be represented. Can we expect that the error in representing by such a dictionary a previously unseen signal from the same source will be of similar magnitude as those for the given examples? We assume signals are generated from a fixed distribution, and study these questions from a statistical learning theory perspective. We develop generalization bounds on the quality of the learned dictionary for two types of constraints on the coefficient selection, as measured by the expected L 2 error in representation when the dictionary is used. For the case of l 1 regularized coefficient selection we provide a generalization bound of the order of O(√np ln(mλ)/m), where n is the dimension, p is the number of elements in the dictionary, λ is a bound on the l 1 norm of the coefficient vector and m is the number of samples, which complements existing results. For the case of representing a new signal as a combination of at most k dictionary elements, we provide a bound of the order O(√np ln(mk)/m) under an assumption on the closeness to orthogonality of the dictionary (low Babel function). We further show that this assumption holds for most dictionaries in high dimensions in a strong probabilistic sense. Our results also include bounds that converge as 1/m, not previously known for this problem. We provide similar results in a general setting using kernels with weak smoothness requirements. [abs] [ pdf ][ bib ] &copy JMLR 2011. ( edit, beta )

TCS Journal 2008 Journal Article

On isoperimetrically optimal polyforms

• Daniel Vainsencher
• Alfred M. Bruckstein

In the plane, the way to enclose the most area with a given perimeter and to use the shortest perimeter to enclose a given area, is always to use a circle. If we replace the plane by a regular tiling of it, and construct polyforms i. e. shapes as sets of tiles, things become more complicated. We need to redefine the area and perimeter measures, and study the consequences carefully. A spiral construction often provides, for every integer number of tiles (area), a shape that is most compact in terms of the perimeter or boundary measure; however it may not exhibit all optimal shapes. We characterize in this paper all shapes that have both shortest boundaries and maximal areas for three common planar discrete spaces.