More Like this

1. Random coordinate descent: A simple alternative for optimizing parameterized quantum circuits

   https://doi.org/10.1103/PhysRevResearch.6.033029  

   Ding, Zhiyan; Ko, Taehee; Yao, Jiahao; Lin, Lin; Li, Xiantao (July 2024, Physical Review Research)

   Variational quantum algorithms rely on the optimization of parameterized quantum circuits in noisy settings. The commonly used back-propagation procedure in classical machine learning is not directly applicable in this setting due to the collapse of quantum states after measurements. Thus, gradient estimations constitute a significant overhead in a gradient-based optimization of such quantum circuits. This paper introduces a random coordinate descent algorithm as a practical and easy-to-implement alternative to the full gradient descent algorithm. This algorithm only requires one partial derivative at each iteration. Motivated by the behavior of measurement noise in the practical optimization of parameterized quantum circuits, this paper presents an optimization problem setting that is amenable to analysis. Under this setting, the random coordinate descent algorithm exhibits the same level of stochastic stability as the full gradient approach, making it as resilient to noise. The complexity of the random coordinate descent method is generally no worse than that of the gradient descent and can be much better for various quantum optimization problems with anisotropic Lipschitz constants. Theoretical analysis and extensive numerical experiments validate our findings. Published by the American Physical Society2024 

   more » « less
2. Projected Stochastic Gradient Langevin Algorithms for Constrained Sampling and Non-Convex Learning

   Lamperski, A. (August 2021, Proceedings of Thirty Fourth Conference on Learning Theory)

   Belkin, M.; Kpotufe, S. (Ed.)

   Langevin algorithms are gradient descent methods with additive noise. They have been used for decades in Markov Chain Monte Carlo (MCMC) sampling, optimization, and learning. Their convergence properties for unconstrained non-convex optimization and learning problems have been studied widely in the last few years. Other work has examined projected Langevin algorithms for sampling from log-concave distributions restricted to convex compact sets. For learning and optimization, log-concave distributions correspond to convex losses. In this paper, we analyze the case of non-convex losses with compact convex constraint sets and IID external data variables. We term the resulting method the projected stochastic gradient Langevin algorithm (PSGLA). We show the algorithm achieves a deviation of 𝑂(𝑇−1/4(𝑙𝑜𝑔𝑇)1/2) from its target distribution in 1-Wasserstein distance. For optimization and learning, we show that the algorithm achieves 𝜖-suboptimal solutions, on average, provided that it is run for a time that is polynomial in 𝜖 and slightly super-exponential in the problem dimension. 

   more » « less
3. First-Order Dynamic Optimization for Streaming Convex Costs

   https://doi.org/10.23919/ACC60939.2024.10645050  

   Rostami, Mohammadreza; Moradian, Hossein; Kia, Solmaz S (July 2024, IEEE)

   This paper proposes a set of novel optimization algorithms for solving a class of convex optimization problems with time-varying streaming cost functions. We develop an approach to track the optimal solution with a bounded error. Unlike prior work, our algorithm is executed only by using the first-order derivatives of the cost function, which makes it computationally efficient for optimization with time-varying cost function. We compare our algorithms to the gradient descent algorithm and show why gradient descent is not an effective solution for optimization problems with time-varying cost. Several examples, including solving a model predictive control problem cast as a convex optimization problem with a streaming time-varying cost function, demonstrate our results. 

   more » « less
4. Safe Online Convex Optimization with Unknown Linear Safety Constraints

   Chaudhary Sapana; Kalathil, Dileep (February 2022, AAAI Conference on Artificial Intelligence (AAAI))

   We study the problem of safe online convex optimization, where the action at each time step must satisfy a set of linear safety constraints. The goal is to select a sequence of ac- tions to minimize the regret without violating the safety constraints at any time step (with high probability). The parameters that specify the linear safety constraints are unknown to the algorithm. The algorithm has access to only the noisy observations of constraints for the chosen actions. We pro- pose an algorithm, called the Safe Online Projected Gradient Descent(SO-PGD) algorithm to address this problem. We show that, under the assumption of the availability of a safe baseline action, the SO-PGD algorithm achieves a regret O(T^2/3). While there are many algorithms for online convex optimization (OCO) problems with safety constraints avail- able in the literature, they allow constraint violations during learning/optimization, and the focus has been on characterizing the cumulative constraint violations. To the best of our knowledge, ours is the first work that provides an algorithm with provable guarantees on the regret, without violating the linear safety constraints (with high probability) at any time step. 

   more » « less
5. Heavy-tailed Streaming Statistical Estimation

   Tsai, Che-Ping; Prasad, Adarsh; Balakrishnan, Sivaraman; Ravikumar, Pradeep (March 2022, International Conference on Artificial Intelligence and Statistics (AISTATS))

   We consider the task of heavy-tailed statistical estimation given streaming p-dimensional samples. This could also be viewed as stochastic optimization under heavy-tailed distributions, with an additional O(p) space complexity constraint. We design a clipped stochastic gradient descent algorithm and provide an improved analysis, under a more nuanced condition on the noise of the stochastic gradients, which we show is critical when analyzing stochastic optimization problems arising from general statistical estimation problems. Our results guarantee convergence not just in expectation but with exponential concentration, and moreover does so using O(1) batch size. We provide consequences of our results for mean estimation and linear regression. Finally, we provide empirical corroboration of our results and algorithms via synthetic experiments for mean estimation and linear regression. 

   more » « less