More Like this

1. Variance Amplification of Accelerated First-Order Algorithms for Strongly Convex Quadratic Optimization Problems

   https://doi.org/10.1109/CDC.2018.8619183  

   Mohammadi, Hesameddin; Razaviyayn, Meisam; Jovanovic, Mihailo R. (December 2018, 2018 IEEE Conference on Decision and Control (CDC))

   We study performance of accelerated first-order optimization algorithms in the presence of additive white stochastic disturbances. For strongly convex quadratic problems, we explicitly evaluate the steady-state variance of the optimization variable in terms of the eigenvalues of the Hessian of the objective function. We demonstrate that, as the condition number increases, variance amplification of both Nesterov's accelerated method and the heavy-ball method by Polyak is significantly larger than that of the standard gradient descent. In the context of distributed computation over networks, we examine the role of network topology and spatial dimension on the performance of these first-order algorithms. For d-dimensional tori, we establish explicit asymptotic dependence for the variance amplification on the network size and the corresponding condition number. Our results demonstrate detrimental influence of acceleration on amplification of stochastic disturbances and suggest that metrics other than convergence rate have to be considered when evaluating performance of optimization algorithms. 

   more » « less
2. Optimal control of fractional semilinear PDEs

   https://doi.org/10.1051/cocv/2019003  

   Antil, Harbir; Warma, Mahamadi (January 2020, ESAIM: Control, Optimisation and Calculus of Variations)

   In this paper, we consider the optimal control of semilinear fractional PDEs with both spectral and integral fractional diffusion operators of order 2 s with s ∈ (0, 1). We first prove the boundedness of solutions to both semilinear fractional PDEs under minimal regularity assumptions on domain and data. We next introduce an optimal growth condition on the nonlinearity to show the Lipschitz continuity of the solution map for the semilinear elliptic equations with respect to the data. We further apply our ideas to show existence of solutions to optimal control problems with semilinear fractional equations as constraints. Under the standard assumptions on the nonlinearity (twice continuously differentiable) we derive the first and second order optimality conditions. 

   more » « less
3. Developing Future Wearable Interfaces for Human-Drone Teams through a Virtual Drone Search Game

   https://doi.org/10.1016/j.ijhcs.2020.102573  

   Fraune, Marlena R.; Khalaf, Ahmed S.; Zemedie, Mahlet; Pianpak, Poom; NaminiMianji, Zahra; Alharthi, Sultan A.; Dolgov, Igor; Hamilton, Bill; Tran, Son; Toups_Dugas, Phoebe O (March 2021, International Journal of Human-Computer Studies)

   Autonomous robotic vehicles (i.e., drones) are potentially transformative for search and rescue (SAR). This paper works toward wearable interfaces, through which humans team with multiple drones. We introduce the Virtual Drone Search Game as a first step in creating a mixed reality simulation for humans to practice drone teaming and SAR techniques. Our goals are to (1) evaluate input modalities for the drones, derived from an iterative narrowing of the design space, (2) improve our mixed reality system for designing input modalities and training operators, and (3) collect data on how participants socially experience the virtual drones with which they work. In our study, 17 participants played the game with two input modalities (Gesture condition, Tap condition) in counterbalanced order. Results indicated that participants performed best with the Gesture condition. Participants found the multiple controls challenging, and future studies might include more training of the devices and game. Participants felt like a team with the drones and found them moderately agentic. In our future work, we will extend this testing to a more externally valid mixed reality game. 

   more » « less
4. A General Analysis of Example-Selection for Stochastic Gradient Descent

   Lu, Yucheng; Meng, Si Yi; De Sa, Christopher (January 2022, International Conference on Learning Representations (ICLR))

   Training example order in SGD has long been known to affect convergence rate. Recent results show that accelerated rates are possible in a variety of cases for permutation-based sample orders, in which each example from the training set is used once before any example is reused. In this paper, we develop a broad condition on the sequence of examples used by SGD that is sufficient to prove tight convergence rates in both strongly convex and non-convex settings. We show that our approach suffices to recover, and in some cases improve upon, previous state-of-the-art analyses for four known example-selection schemes: (1) shuffle once, (2) random reshuffling, (3) random reshuffling with data echoing, and (4) Markov Chain Gradient Descent. Motivated by our theory, we propose two new example-selection approaches. First, using quasi-Monte-Carlo methods, we achieve unprecedented accelerated convergence rates for learning with data augmentation. Second, we greedily choose a fixed scan-order to minimize the metric used in our condition and show that we can obtain more accurate solutions from the same number of epochs of SGD. We conclude by empirically demonstrating the utility of our approach for both convex linear-model and deep learning tasks. Our code is available at: https://github.com/EugeneLYC/qmc-ordering. 

   more » « less
5. Convergence of Augmented Lagrangian Methods for Composite Optimization Problems

   https://doi.org/10.1287/moor.2023.0324  

   Van_Hang, Nguyen Thi; Sarabi, Ebrahim (March 2025, Mathematics of Operations Research)

   Local convergence analysis of the augmented Lagrangian method (ALM) is established for a large class of composite optimization problems with nonunique Lagrange multipliers under a second-order sufficient condition. We present a new second-order variational property called the semistability of second subderivatives and demonstrate that it is widely satisfied for numerous classes of functions, which is important for applications in constrained and composite optimization problems. Using the latter condition and a certain second-order sufficient condition, we are able to establish Q-linear convergence of the primal-dual sequence for an inexact version of the ALM for composite programs. Funding: Research of the first author is partially supported by Singapore National Academy of Science via SASEAF Programme under the grant RIE2025 NRF International Partnership Funding Initiative. Research of the second author is partially supported by the National Science Foundation under the grant DMS 2108546. 

   more » « less