Ashwin Pananjady
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Ashwin Pananjady has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Martin J. Wainwright
Laboratory for Information and Decision Systems, Statistics and Data Science Center, Departments of Electrical Engineering and Computer Science and Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
4 shared publications - Thomas A. Courtade
Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, USA
3 shared publications Mengqi Lou
Georgia Institute of Technology, School of Industrial and Systems Engineering, Atlanta GA USA
2 shared publications- Mengqi Lou
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA, USA
2 shared publications - Wenlong Mou
University of Toronto, Toronto, Canada
2 shared publications Adityanand Guntuboyina
Department of Statistics and the Department of Electrical Engineering and Computer Sciences (EECS), University of California at Berkeley, Berkeley, CA, USA
1 shared publication
Latest Publications
- 9 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Imaging Sciences
- Vol. 19 (1) , 446-479
Accurate, Provable, and Fast Polychromatic Tomographic Reconstruction: A Variational Inequality Approach
We consider the problem of signal reconstruction for computed tomography (CT) given a nonlinear forward model that accounts for exponential signal attenuation, a polychromatic X-ray source, general measurement noise (e.g., Poisson shot noise), and observations acquired over multiple wavelength windows. We develop a simple iterative algorithm for single-material reconstruction, which we call EXACT (EXtragradient Algorithm for Computed Tomography), based on formulating our estimate as the fixed point of a monotone variational inequality. We prove guarantees on the statistical and computational performance of EXACT given realistic assumptions on the measurement process. We also consider a recently introduced variant of this model with Gaussian measurements and present sample and iteration complexity bounds for EXACT that improve upon those of existing algorithms. We apply our EXACT algorithm to a CT phantom image recovery task and show that it often requires fewer X-ray views, lower source intensity, and less computation time to achieve similar reconstruction quality to existing methods. Code is available at https://github.com/voilalab/exact .
- 9 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Imaging Sciences
- Vol. 19 (1) , 446-479
Accurate, Provable, and Fast Polychromatic Tomographic Reconstruction: A Variational Inequality Approach
We consider the problem of signal reconstruction for computed tomography (CT) given a nonlinear forward model that accounts for exponential signal attenuation, a polychromatic X-ray source, general measurement noise (e.g., Poisson shot noise), and observations acquired over multiple wavelength windows. We develop a simple iterative algorithm for single-material reconstruction, which we call EXACT (EXtragradient Algorithm for Computed Tomography), based on formulating our estimate as the fixed point of a monotone variational inequality. We prove guarantees on the statistical and computational performance of EXACT given realistic assumptions on the measurement process. We also consider a recently introduced variant of this model with Gaussian measurements and present sample and iteration complexity bounds for EXACT that improve upon those of existing algorithms. We apply our EXACT algorithm to a CT phantom image recovery task and show that it often requires fewer X-ray views, lower source intensity, and less computation time to achieve similar reconstruction quality to existing methods. Code is available at https://github.com/voilalab/exact .
- Open Access
- 17 September 2025
- Published by Springer Nature in Mathematical Programming
- p. 1-61
Hyperparameter tuning via trajectory predictions: stochastic prox-linear methods in matrix sensing
Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large range of step-sizes. In particular, our analysis reveals that this method, though stochastic, converges linearly from a local initialization with a fixed step-size to a statistical error floor. Our analysis also exposes how the batch-size, step-size, and noise level affect the (linear) convergence rate and the eventual statistical estimation error, and we demonstrate how to use our deterministic predictions to perform hyperparameter tuning (e.g. step-size and batch-size selection) without ever running the method. On a technical level, our analysis is enabled in part by showing that the fluctuations of the empirical iterates around our deterministic predictions scale with the error of the previous iterate.
- 17 September 2025
- Published by Springer Nature in Mathematical Programming
- p. 1-61
Open AccessHyperparameter tuning via trajectory predictions: stochastic prox-linear methods in matrix sensing
Motivated by the desire to understand stochastic algorithms for nonconvex optimization that are robust to their hyperparameter choices, we analyze a mini-batched prox-linear iterative algorithm for the canonical problem of recovering an unknown rank-1 matrix from rank-1 Gaussian measurements corrupted by noise. We derive a deterministic recursion that predicts the error of this method and show, using a non-asymptotic framework, that this prediction is accurate for any batch-size and a large range of step-sizes. In particular, our analysis reveals that this method, though stochastic, converges linearly from a local initialization with a fixed step-size to a statistical error floor. Our analysis also exposes how the batch-size, step-size, and noise level affect the (linear) convergence rate and the eventual statistical estimation error, and we demonstrate how to use our deterministic predictions to perform hyperparameter tuning (e.g. step-size and batch-size selection) without ever running the method. On a technical level, our analysis is enabled in part by showing that the fluctuations of the empirical iterates around our deterministic predictions scale with the error of the previous iterate.
- 10 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (9) , 7097-7133
Computationally Efficient Reductions Between Some Statistical Models
We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical experiments. In particular, we provide computationally efficient procedures that approximately reduce uniform, Erlang, and Laplace location models to general target families. We illustrate our methodology by establishing nonasymptotic reductions between some canonical high-dimensional problems, spanning mixtures of experts, phase retrieval, and signal denoising. Notably, the reductions are structure-preserving and can accommodate missing data. We also point to a possible application in transforming one differentially private mechanism to another.
- 10 July 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 71 (9) , 7097-7133
Computationally Efficient Reductions Between Some Statistical Models
We study the problem of approximately transforming a sample from a source statistical model to a sample from a target statistical model without knowing the parameters of the source model, and construct several computationally efficient such reductions between canonical statistical experiments. In particular, we provide computationally efficient procedures that approximately reduce uniform, Erlang, and Laplace location models to general target families. We illustrate our methodology by establishing nonasymptotic reductions between some canonical high-dimensional problems, spanning mixtures of experts, phase retrieval, and signal denoising. Notably, the reductions are structure-preserving and can accommodate missing data. We also point to a possible application in transforming one differentially private mechanism to another.
- 21 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (10) , 6869-6876
A Dual Accelerated Method for Online Stochastic Distributed Averaging: From Consensus to Decentralized Policy Evaluation
Motivated by decentralized sensing and policy evaluation problems, we consider a particular type of distributed stochastic optimization problem over a network, called the online stochastic distributed averaging problem. We design and analyze a dual-based, Polyak–Ruppert averaged method for this problem. We show that the proposed algorithm attains an accelerated deterministic error depending optimally on the condition number of the network, and also that it has optimal stochastic error. This improves on the guarantees of state-of-the-art distributed stochastic optimization algorithms when specialized to this setting, and yields—among other things—corollaries for decentralized policy evaluation. Numerical experiments validate our theoretical results and demonstrate that our approach outperforms existing methods in finite-sample scenarios on several natural network topologies.
- 21 April 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 70 (10) , 6869-6876
A Dual Accelerated Method for Online Stochastic Distributed Averaging: From Consensus to Decentralized Policy Evaluation
Motivated by decentralized sensing and policy evaluation problems, we consider a particular type of distributed stochastic optimization problem over a network, called the online stochastic distributed averaging problem. We design and analyze a dual-based, Polyak–Ruppert averaged method for this problem. We show that the proposed algorithm attains an accelerated deterministic error depending optimally on the condition number of the network, and also that it has optimal stochastic error. This improves on the guarantees of state-of-the-art distributed stochastic optimization algorithms when specialized to this setting, and yields—among other things—corollaries for decentralized policy evaluation. Numerical experiments validate our theoretical results and demonstrate that our approach outperforms existing methods in finite-sample scenarios on several natural network topologies.
- 2 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 72 (1053587X) , 3187-3200
Do Algorithms and Barriers for Sparse Principal Component Analysis Extend to Other Structured Settings?
We study a principal component analysis problem under the spiked Wishart model in which the structure in the signal is captured by a class of union-of-subspace models. This general class includes vanilla sparse PCA as well as its variants with graph sparsity. With the goal of studying these problems under a unified statistical and computational lens, we establish fundamental limits that depend on the geometry of the problem instance, and show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution. We complement these results with end-to-end analyses of two important special cases given by path and tree sparsity in a general basis, showing initialization methods and matching evidence of computational hardness. Overall, our results indicate that several of the phenomena observed for vanilla sparse PCA extend in a natural fashion to its structured counterparts.
- 2 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 72 (1053587X) , 3187-3200
Do Algorithms and Barriers for Sparse Principal Component Analysis Extend to Other Structured Settings?
We study a principal component analysis problem under the spiked Wishart model in which the structure in the signal is captured by a class of union-of-subspace models. This general class includes vanilla sparse PCA as well as its variants with graph sparsity. With the goal of studying these problems under a unified statistical and computational lens, we establish fundamental limits that depend on the geometry of the problem instance, and show that a natural projected power method exhibits local convergence to the statistically near-optimal neighborhood of the solution. We complement these results with end-to-end analyses of two important special cases given by path and tree sparsity in a general basis, showing initialization methods and matching evidence of computational hardness. Overall, our results indicate that several of the phenomena observed for vanilla sparse PCA extend in a natural fashion to its structured counterparts.
- 1 July 2024
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 13 (3)
Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization
We consider the problem of estimating the factors of a rank-$1$ matrix with i.i.d. Gaussian, rank-$1$ measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this non-convex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic one-step recursion that is accurate even in high-dimensional problems. Notably, while the infinite-sample population update is uninformative and suggests exact recovery in a single step, the algorithm—and our deterministic one-step prediction—converges geometrically fast from a random initialization. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behaviour. On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic one-step updates within fluctuations of the order $n^{-1/2}$ when each iteration is run with $n$ observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional $M$-estimation and provides an avenue for sharply analyzing complex iterative algorithms from a random initialization in other high-dimensional optimization problems with random data.- 1 July 2024
- Published by Oxford University Press (OUP) in Information and Inference: A Journal of the IMA
- Vol. 13 (3)
Alternating minimization for generalized rank-1 matrix sensing: sharp predictions from a random initialization
We consider the problem of estimating the factors of a rank-$1$ matrix with i.i.d. Gaussian, rank-$1$ measurements that are nonlinearly transformed and corrupted by noise. Considering two prototypical choices for the nonlinearity, we study the convergence properties of a natural alternating update rule for this non-convex optimization problem starting from a random initialization. We show sharp convergence guarantees for a sample-split version of the algorithm by deriving a deterministic one-step recursion that is accurate even in high-dimensional problems. Notably, while the infinite-sample population update is uninformative and suggests exact recovery in a single step, the algorithm—and our deterministic one-step prediction—converges geometrically fast from a random initialization. Our sharp, non-asymptotic analysis also exposes several other fine-grained properties of this problem, including how the nonlinearity and noise level affect convergence behaviour. On a technical level, our results are enabled by showing that the empirical error recursion can be predicted by our deterministic one-step updates within fluctuations of the order $n^{-1/2}$ when each iteration is run with $n$ observations. Our technique leverages leave-one-out tools originating in the literature on high-dimensional $M$-estimation and provides an avenue for sharply analyzing complex iterative algorithms from a random initialization in other high-dimensional optimization problems with random data.- Top Cited PapersOpen Access
- 8 March 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 7 (1) , 41-153
Optimal and instance-dependent guarantees for Markovian linear stochastic approximation
We study stochastic approximation procedures for approximately solving a d -dimensional linear fixed-point equation based on observing a trajectory of length n from an ergodic Markov chain. We first exhibit a non-asymptotic bound of the order t_{\mathrm{mix}}\frac{d}{n} on the squared error of the last iterate of a standard scheme, where t_{\mathrm{mix}} is a mixing time. We then prove a non-asymptotic instance-dependent bound on a suitably averaged sequence of iterates, with a leading term that matches the local asymptotic minimax limit, including sharp dependence on the parameters (d, t_{\mathrm{mix}}) in the higher-order terms. We complement these upper bounds with a non-asymptotic minimax lower bound that establishes the instance-optimality of the averaged SA estimator. We derive corollaries of these results for policy evaluation with Markov noise—covering the \mathrm{TD}(\lambda) family of algorithms for all \lambda \in [0, 1) —and linear autoregressive models. Our instance-dependent characterizations open the door to the design of fine-grained model selection procedures for hyperparameter tuning (e.g., choosing the value of \lambda when running the \mathrm{TD}(\lambda) algorithm).
- 8 March 2024
- Published by European Mathematical Society - EMS - Publishing House GmbH in Mathematical Statistics and Learning
- Vol. 7 (1) , 41-153
Top Cited PapersOpen AccessOptimal and instance-dependent guarantees for Markovian linear stochastic approximation
We study stochastic approximation procedures for approximately solving a d -dimensional linear fixed-point equation based on observing a trajectory of length n from an ergodic Markov chain. We first exhibit a non-asymptotic bound of the order t_{\mathrm{mix}}\frac{d}{n} on the squared error of the last iterate of a standard scheme, where t_{\mathrm{mix}} is a mixing time. We then prove a non-asymptotic instance-dependent bound on a suitably averaged sequence of iterates, with a leading term that matches the local asymptotic minimax limit, including sharp dependence on the parameters (d, t_{\mathrm{mix}}) in the higher-order terms. We complement these upper bounds with a non-asymptotic minimax lower bound that establishes the instance-optimality of the averaged SA estimator. We derive corollaries of these results for policy evaluation with Markov noise—covering the \mathrm{TD}(\lambda) family of algorithms for all \lambda \in [0, 1) —and linear autoregressive models. Our instance-dependent characterizations open the door to the design of fine-grained model selection procedures for hyperparameter tuning (e.g., choosing the value of \lambda when running the \mathrm{TD}(\lambda) algorithm).
- Open Access
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1153
Modeling and Correcting Bias in Sequential Evaluation
- 7 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1153
Open AccessModeling and Correcting Bias in Sequential Evaluation
- 23 March 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Mathematics of Data Science
- Vol. 5 (1) , 174-200
Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation
We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish baselines on both the deterministic error and stochastic error in this problem. In particular, we prove an oracle complexity lower bound on the deterministic error in an instance-dependent norm associated with the stationary distribution of the transition kernel, and we use the local asymptotic minimax machinery to prove an instance-dependent lower bound on the stochastic error in the independent and identically distributed (i.i.d.) observation model. Existing algorithms fail to match at least one of these lower bounds: To illustrate, we analyze a variance-reduced variant of temporal difference learning, showing in particular that it fails to achieve the oracle complexity lower bound. To remedy this issue, we develop an accelerated, variance-reduced fast temporal difference (VRFTD) algorithm that simultaneously matches both lower bounds and attains a strong notion of instance-optimality. Finally, we extend the VRFTD algorithm to the setting with Markovian observations and provide instance-dependent convergence results. Our theoretical guarantees of optimality are corroborated by numerical experiments.
- 23 March 2023
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Mathematics of Data Science
- Vol. 5 (1) , 174-200
Accelerated and Instance-Optimal Policy Evaluation with Linear Function Approximation
We study the problem of policy evaluation with linear function approximation and present efficient and practical algorithms that come with strong optimality guarantees. We begin by proving lower bounds that establish baselines on both the deterministic error and stochastic error in this problem. In particular, we prove an oracle complexity lower bound on the deterministic error in an instance-dependent norm associated with the stationary distribution of the transition kernel, and we use the local asymptotic minimax machinery to prove an instance-dependent lower bound on the stochastic error in the independent and identically distributed (i.i.d.) observation model. Existing algorithms fail to match at least one of these lower bounds: To illustrate, we analyze a variance-reduced variant of temporal difference learning, showing in particular that it fails to achieve the oracle complexity lower bound. To remedy this issue, we develop an accelerated, variance-reduced fast temporal difference (VRFTD) algorithm that simultaneously matches both lower bounds and attains a strong notion of instance-optimality. Finally, we extend the VRFTD algorithm to the setting with Markovian observations and provide instance-dependent convergence results. Our theoretical guarantees of optimality are corroborated by numerical experiments.
- 28 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (4) , 2308-2336
Optimal Oracle Inequalities for Projected Fixed-Point Equations, with Applications to Policy Evaluation
Linear fixed-point equations in Hilbert spaces arise in a variety of settings, including reinforcement learning, and computational methods for solving differential and integral equations. We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. First, we prove an instance-dependent upper bound on the mean-squared error for a linear stochastic approximation scheme that exploits Polyak–Ruppert averaging. This bound consists of two terms: an approximation error term with an instance-dependent approximation factor and a statistical error term that captures the instance-specific complexity of the noise when projected onto the low-dimensional subspace. Using information-theoretic methods, we also establish lower bounds showing that both of these terms cannot be improved, again in an instance-dependent sense. A concrete consequence of our characterization is that the optimal approximation factor in this problem can be much larger than a universal constant. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation, establishing their optimality. Funding: This work was partially supported by grants from the Office of Naval Research [Grant DOD-ONRN00014-18-1-2640] and the National Science Foundation (NSF) [NSF-IIS Grant 1909365, NSF-DMS Grant 2015454, and NSF-CCF Grant 1955450] to M. J. Wainwright. Part of this work was performed when A. Pananjady was visiting the Simons Institute for the Theory of Computing, where he was supported by a Swiss Re Research Fellowship. Supplemental Material: The online supplementary file is available at https://doi.org/10.1287/moor.2022.1341 .
- 28 December 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 48 (4) , 2308-2336
Optimal Oracle Inequalities for Projected Fixed-Point Equations, with Applications to Policy Evaluation
Linear fixed-point equations in Hilbert spaces arise in a variety of settings, including reinforcement learning, and computational methods for solving differential and integral equations. We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. First, we prove an instance-dependent upper bound on the mean-squared error for a linear stochastic approximation scheme that exploits Polyak–Ruppert averaging. This bound consists of two terms: an approximation error term with an instance-dependent approximation factor and a statistical error term that captures the instance-specific complexity of the noise when projected onto the low-dimensional subspace. Using information-theoretic methods, we also establish lower bounds showing that both of these terms cannot be improved, again in an instance-dependent sense. A concrete consequence of our characterization is that the optimal approximation factor in this problem can be much larger than a universal constant. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation, establishing their optimality. Funding: This work was partially supported by grants from the Office of Naval Research [Grant DOD-ONRN00014-18-1-2640] and the National Science Foundation (NSF) [NSF-IIS Grant 1909365, NSF-DMS Grant 2015454, and NSF-CCF Grant 1955450] to M. J. Wainwright. Part of this work was performed when A. Pananjady was visiting the Simons Institute for the Theory of Computing, where he was supported by a Swiss Re Research Fellowship. Supplemental Material: The online supplementary file is available at https://doi.org/10.1287/moor.2022.1341 .