Bahar Tașkesen

Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits

  • Mengmeng Li
  • Daniel Kuhn
  • Bahar Tașkesen
    • Categories Convex Optimization, Data Science Algorithms, Data Science Applications Tags , ,

    Follow-The-Regularized-Leader (FTRL) algorithms often enjoy optimal regret for adversarial as well as stochastic bandit problems and allow for a streamlined analysis. However, FTRL algorithms require the solution of an optimization problem in every iteration and are thus computationally challenging. In contrast, Follow-The-Perturbed-Leader (FTPL) algorithms achieve computational efficiency by perturbing the estimates of the rewards of … Read more

    Distributionally Robust Linear Quadratic Control

  • Bahar Tașkesen
  • Dan Iancu
  • Çağıl Koçyiğit
  • Daniel Kuhn
    • Categories Control Applications, Dynamic Programming, Robust Optimization

    Linear-Quadratic-Gaussian (LQG) control is a fundamental control paradigm that is studied in various fields such as engineering, computer science, economics, and neuroscience. It involves controlling a system with linear dynamics and imperfect observations, subject to additive noise, with the goal of minimizing a quadratic cost function for the state and control variables. In this work, … Read more

    Metrizing Fairness

  • Yves Rychener
  • Bahar Tașkesen
  • Daniel Kuhn
    • Categories Statistics, Stochastic Programming, Unconstrained Optimization Tags , , , , ,

    We study supervised learning problems for predicting properties of individuals who belong to one of two demographic groups, and we seek predictors that are fair according to statistical parity. This means that the distributions of the predictions within the two groups should be close with respect to the Kolmogorov distance, and fairness is achieved by … Read more

    Discrete Optimal Transport with Independent Marginals is #P-Hard

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
  • Karthik Natarajan
    • Categories Dynamic Programming, Linear Programming, Stochastic Programming

    We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector … Read more

    Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts

  • Jose Blanchet
  • Daniel Kuhn
  • Viet Anh Nguyen
  • Bahar Tașkesen
  • Man-Chung Yue
    • Categories Nonlinear Systems and Least-Squares, Robust Optimization, Stochastic Programming

    Least squares estimators, when trained on a few target domain samples, may predict poorly. Supervised domain adaptation aims to improve the predictive accuracy by exploiting additional labeled training samples from a source distribution that is close to the target distribution. Given available data, we investigate novel strategies to synthesize a family of least squares estimator … Read more

    Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
    • Categories Convex and Nonsmooth Optimization, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification. To fill this gap, we prove that … Read more