35 accepted papers
Reinforcement learning usually assumes a given or sometimes even fixed environment in which an agent seeks an optimal policy to maximize its long-term discounted reward. In contrast, we consider agents that are not limited to passive adaptations: they instead have model-changing actions that activel…
This paper investigates distributionally robust filtering for state-space models subject to exogenous disturbances in state evolution and observation processes. The joint probability distribution of the disturbance process over an arbitrary horizon is unknown but is assumed to reside within a Wasser…
Stochastic Mirror Descent (SMD) has emerged as a method for solving various convex optimization problems and, under appropriate conditions, has been shown to exponentially converge to the global optimum when the underlying loss is strongly convex. However, strong convexity of the loss fails to hold…
We study the infinite-horizon distributionally robust (DR) control of linear systems with quadratic costs, where disturbances have unknown, possibly time-correlated distribution within a Wasserstein-2 ambiguity set. We aim to minimize the worst-case expected regret—the excess cost of a causal policy…
We study the problem of transfer learning and fine-tuning in linear models for both regression and binary classification. In particular, we consider the use of stochastic gradient descent (SGD) on a linear model initialized with pretrained weights and using a small training data set from the target…
The stochastic mirror descent (SMD) algorithm is a general class of training algorithms that utilizes a mirror potential to influence the implicit bias of the training algorithm and includes stochastic gradient descent (SGD) as a special case. In this paper, we explore the performance of the SMD on…
In this work, we study model-based reinforcement learning (RL) in unknown stabilizable linear dynamical systems. When learning a dynamical system, one needs to stabilize the unknown dynamics in order to avoid system blow-ups. We propose an algorithm that certifies fast stabilization of the underlyin…
We consider the problem of filtering in linear state-space models (e.g., the Kalman filter setting) through the lens of regret optimization. Specifically, we study the problem of causally estimating a desired signal, generated by a linear state-space model driven by process noise, based on noisy obs…
We study the convergence, the implicit regularization and the generalization of stochastic mirror descent (SMD) algorithms in overparameterized nonlinear models, where the number of model parameters exceeds the number of training data points. Due to overpa-rameterization, the training loss has infin…
We study the problem of system identification and adaptive control in partially observable linear dynamical systems. Adaptive and closed-loop system identification is a challenging problem due to correlations introduced in data collection. In this paper, we present the first model estimation method…
Logistic models are commonly used for binary classification tasks. The success of such models has often been attributed to their connection to maximum-likelihood estimators. It has been shown that gradient descent algorithm, when applied on the logistic loss, converges to the max-margin classifier (…
Stochastic mirror descent (SMD) algorithms have recently garnered a great deal of attention in optimization, signal processing, and machine learning. They are similar to stochastic gradient descent (SGD), in that they perform updates along the negative gradient of an instantaneous (or stochastically…
We study the performance of a convex data detection method in large multiple-input multiple-output (MIMO) systems. The goal is to recover an n-dimensional complex signal whose entries are from an arbitrary constellation D C C, using m noisy linear measurements. Since the Maximum Likelihood (ML) esti…
Stochastic descent methods (of the gradient and mirror varieties) have become increasingly popular in optimization. In fact, it is now widely recognized that the success of deep learning is not only due to the special deep architecture of the models, but also due to the behavior of the stochastic de…
Logistic regression is commonly used for modeling dichotomous outcomes. In the classical setting, where the number of observations is much larger than the number of parameters, properties of the maximum likelihood estimator in logistic regression are well understood. Recently, Sur and Candes~\cite{s…
We study the problem of recovering a structured signal from independently and identically drawn linear measurements. A convex penalty function $f(\cdot)$ is considered which penalizes deviations from the desired structure, and signal recovery is performed by minimizing $f(\cdot)$ subject to the line…
Given a data matrix with partially observed entries, the low-rank matrix completion problem is one of finding a matrix with the lowest rank that perfectly fits the given observations. While there exist convex relaxations for the low-rank completion problem, the underlying problem is inherently nonco…
Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a distribute…
The problem of estimating an unknown signal, $\mathbf x_0\in \mathbb R^n$, from a vector $\mathbf y\in \mathbb R^m$ consisting of $m$ magnitude-only measurements of the form $y_i=|\mathbf a_i\mathbf x_0|$, where $\mathbf a_i$'s are the rows of a known measurement matrix $\mathbf A$ is a classical p…
This paper develops a Riemannian optimization framework for solving optimization problems on the set of symmetric positive semidefinite stochastic matrices. The paper first reformulates the problem by factorizing the optimization variable as $\mathbf{X}=\mathbf{Y}\mathbf{Y}^T$ and deriving condition…
A problem that has been of recent interest in statistical inference, machine learning and signal processing is that of understanding the asymptotic behavior of regularized least squares solutions under random measurement matrices (or dictionaries). The Least Absolute Shrinkage and Selection Operator…
This paper investigates the problem of recovering an n-dimensional BPSK signal x <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</inf> ∈ {−1, 1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> fro…
Phaseless super-resolution is the problem of recovering an unknown signal from measurements of the “magnitudes” of the “low frequency” Fourier transform of the signal. This problem arises in applications where measuring the phase, and making high-frequency measurements, are either too costly or alto…
Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g. circulant matrices. While binary…
Phaseless super-resolution refers to the problem of super-resolving a signal from only its low-frequency Fourier magnitude measurements. In this paper, we consider the phaseless super-resolution problem of recovering a sum of sparse Dirac delta functions which can be located anywhere in the continuo…
We consider the problem of crowdsourced clustering of a set of items based on queries of the similarity of triple of objects. Such an approach, called triangle queries, was proposed in [1], where it was shown that, for a fixed query budget, it outperforms clustering based on edge queries (i.e, compa…
We study the problem of recovering an n-dimensional BPSK signal from m linear noise-corrupted measurements using the box relaxation method which relaxes the discrete set {±1}n to the convex set [-1,1]n to obtain a convex optimization algorithm followed by hard thresholding. When the noise and measur…
We consider the task of clustering items using answers from non-expert crowd workers. In such cases, the workers are often not able to label the items directly, however, it is reasonable to assume that they can compare items and judge whether they are similar or not. An important question is what qu…
Digital crowdsourcing (CS) is a modern approach to perform certain large projects using small contributions of a large crowd. In CS, a taskmaster typically breaks down the project into small batches of tasks and assigns them to so-called workers with imperfect skill levels. The crowdsourcer then col…
Phaseless super-resolution is the problem of reconstructing a signal from its low-frequency Fourier magnitude measurements. It is the combination of two classic signal processing problems: phase retrieval and super-resolution. Due to the absence of phase and high-frequency measurements, additional i…
Atomic norm denoising has been recently introduced as a generalization of the Least Absolute Shrinkage and Selection Operator (LASSO) to overcome the problem of off-grid parameters. The method has been found to possess many interesting theoretical properties. However, its implementation has been onl…
Consider estimating an unknown, but structured (e.g. sparse, low-rank, etc.), signal $x_0\in R^n$ from a vector $y\in R^m$ of measurements of the form $y_i=g_i(a_i^Tx_0)$, where the $a_i$'s are the rows of a known measurement matrix $A$, and, $g$ is a (potentially unknown) nonlinear and random link-…
A classical problem that arises in numerous signal processing applications asks for the reconstruction of an unknown, k-sparse signal x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0</sub> ∈ ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns…
The problem of recovering signals from the Short-Time Fourier Transform (STFT) magnitude is of paramount importance in many areas of engineering and physics. This problem has received a lot of attention over the last few decades, but not much is known about conditions under which the STFT magnitude…
We consider ill-posed linear inverse problems involving the estimation of structured sparse signals. When the sensing matrix has i.i.d. standard normal entries, there is a full-fledged theory on the sample complexity and robustness properties. In this work, we propose a way of making use of this the…