Mehmet A. Donmez

Nargiz Kalantarova, Mehmet A. Donmez, Suleyman S. Kozat

In this correspondence, we introduce a minimax regret criteria to the least squares problems with bounded data uncertainties and solve it using semi-definite programming. We investigate a robust minimax least squares approach that minimizes a worst case difference regret. The regret is defined as the difference between a squared data error and the smallest attainable squared data error of a least squares estimator. We then propose a robust regularized least squares approach to the regularized least squares problem under data uncertainties by using a similar framework. We show that both unstructured and structured robust least squares problems and robust regularized least squares problem can be put in certain semi-definite programming forms. Through several simulations, we demonstrate the merits of the proposed algorithms with respect to the the well-known alternatives in the literature.

Sait Tunc, Mehmet A. Donmez, Suleyman S. Kozat

We investigate how and when to diversify capital over assets, i.e., the portfolio selection problem, from a signal processing perspective. To this end, we first construct portfolios that achieve the optimal expected growth in i.i.d. discrete-time two-asset markets under proportional transaction costs. We then extend our analysis to cover markets having more than two stocks. The market is modeled by a sequence of price relative vectors with arbitrary discrete distributions, which can also be used to approximate a wide class of continuous distributions. To achieve the optimal growth, we use threshold portfolios, where we introduce a recursive update to calculate the expected wealth. We then demonstrate that under the threshold rebalancing framework, the achievable set of portfolios elegantly form an irreducible Markov chain under mild technical conditions. We evaluate the corresponding stationary distribution of this Markov chain, which provides a natural and efficient method to calculate the cumulative expected wealth. Subsequently, the corresponding parameters are optimized yielding the growth optimal portfolio under proportional transaction costs in i.i.d. discrete-time two-asset markets. As a widely known financial problem, we next solve optimal portfolio selection in discrete-time markets constructed by sampling continuous-time Brownian markets. For the case that the underlying discrete distributions of the price relative vectors are unknown, we provide a maximum likelihood estimator that is also incorporated in the optimization framework in our simulations.

Mehmet A. Donmez, Sait Tunc, Suleyman S. Kozat

We introduce a new analysis of an adaptive mixture method that combines outputs of two constituent filters running in parallel to model an unknown desired signal. This adaptive mixture is shown to achieve the mean square error (MSE) performance of the best constituent filter, and in some cases outperforms both, in the steady-state. However, the MSE analysis of this mixture in the steady-state and during the transient regions uses approximations and relies on statistical models on the underlying signals and systems. Hence, such an analysis may not be useful or valid for signals generated by various real life systems that show high degrees of nonstationarity, limit cycles and, in many cases, that are even chaotic. To this end, we perform the transient and the steady-state analysis of this adaptive mixture in a "strong" deterministic sense without any approximations in the derivations or statistical assumptions on the underlying signals such that our results are guaranteed to hold. In particular, we relate the time-accumulated squared estimation error of this adaptive mixture at any time to the time-accumulated squared estimation error of the optimal convex mixture of the constituent filters directly tuned to the underlying signal in an individual sequence manner.

Mehmet A. Donmez, Maxim Raginsky, Andrew C. Singer

We present a generic framework for trading off fidelity and cost in computing stochastic gradients when the costs of acquiring stochastic gradients of different quality are not known a priori. We consider a mini-batch oracle that distributes a limited query budget over a number of stochastic gradients and aggregates them to estimate the true gradient. Since the optimal mini-batch size depends on the unknown cost-fidelity function, we propose an algorithm, {\it EE-Grad}, that sequentially explores the performance of mini-batch oracles and exploits the accumulated knowledge to estimate the one achieving the best performance in terms of cost-efficiency. We provide performance guarantees for EE-Grad with respect to the optimal mini-batch oracle, and illustrate these results in the case of strongly convex objectives. We also provide a simple numerical example that corroborates our theoretical findings.

Mehmet A. Donmez, Sait Tunc, Suleyman S. Kozat

We analyze an online learning algorithm that adaptively combines outputs of two constituent algorithms (or the experts) running in parallel to model an unknown desired signal. This online learning algorithm is shown to achieve (and in some cases outperform) the mean-square error (MSE) performance of the best constituent algorithm in the mixture in the steady-state. However, the MSE analysis of this algorithm in the literature uses approximations and relies on statistical models on the underlying signals and systems. Hence, such an analysis may not be useful or valid for signals generated by various real life systems that show high degrees of nonstationarity, limit cycles and, in many cases, that are even chaotic. In this paper, we produce results in an individual sequence manner. In particular, we relate the time-accumulated squared estimation error of this online algorithm at any time over any interval to the time accumulated squared estimation error of the optimal convex mixture of the constituent algorithms directly tuned to the underlying signal in a deterministic sense without any statistical assumptions. In this sense, our analysis provides the transient, steady-state and tracking behavior of this algorithm in a strong sense without any approximations in the derivations or statistical assumptions on the underlying signals such that our results are guaranteed to hold. We illustrate the introduced results through examples.

Mehmet A. Donmez, Huseyin A. Inan, Suleyman S. Kozat

We investigate adaptive mixture methods that linearly combine outputs of $m$ constituent filters running in parallel to model a desired signal. We use "Bregman divergences" and obtain certain multiplicative updates to train the linear combination weights under an affine constraint or without any constraints. We use unnormalized relative entropy and relative entropy to define two different Bregman divergences that produce an unnormalized exponentiated gradient update and a normalized exponentiated gradient update on the mixture weights, respectively. We then carry out the mean and the mean-square transient analysis of these adaptive algorithms when they are used to combine outputs of $m$ constituent filters. We illustrate the accuracy of our results and demonstrate the effectiveness of these updates for sparse mixture systems.