More Like this

1. SUCAG: Stochastic Unbiased Curvature-aided Gradient Method for Distributed Optimization

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

   Wai, Hoi-To; Freris, Nikolaos M.; Nedic, Angelia; Scaglione, Anna (December 2018, 2018 IEEE Conference on Decision and Control (CDC))

   We propose and analyze a new stochastic gradient method, which we call Stochastic Unbiased Curvature-aided Gradient (SUCAG), for finite sum optimization problems. SUCAG constitutes an unbiased total gradient tracking technique that uses Hessian information to accelerate convergence. We analyze our method under the general asynchronous model of computation, in which each function is selected infinitely often with possibly unbounded (but sublinear) delay. For strongly convex problems, we establish linear convergence for the SUCAG method. When the initialization point is sufficiently close to the optimal solution, the established convergence rate is only dependent on the condition number of the problem, making it strictly faster than the known rate for the SAGA method. Furthermore, we describe a Markov-driven approach of implementing the SUCAG method in a distributed asynchronous multi-agent setting, via gossiping along a random walk on an undirected communication graph. We show that our analysis applies as long as the graph is connected and, notably, establishes an asymptotic linear convergence rate that is robust to the graph topology. Numerical results demonstrate the merits of our algorithm over existing methods. 

   more » « less
2. A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem

   Jiang, Ruichen; Abolfazli, Nazanin; Mokhtari, Aryan; Yazdandoost Hamedani, Erfan (April 2023, Proceedings of Machine Learning Research)

   Ruiz, Francisco; Dy, Jennifer; van de Meent, Jan-Willem (Ed.)

   In this paper, we study a class of bilevel optimization problems, also known as simple bilevel optimization, where we minimize a smooth objective function over the optimal solution set of another convex constrained optimization problem. Several iterative methods have been developed for tackling this class of problems. Alas, their convergence guarantees are either asymptotic for the upper-level objective, or the convergence rates are slow and sub-optimal. To address this issue, in this paper, we introduce a novel bilevel optimization method that locally approximates the solution set of the lower-level problem via a cutting plane and then runs a conditional gradient update to decrease the upper-level objective. When the upper-level objective is convex, we show that our method requires $${O}(\max\{1/\epsilon_f,1/\epsilon_g\})$$ iterations to find a solution that is $$\epsilon_f$$-optimal for the upper-level objective and $$\epsilon_g$$-optimal for the lower-level objective. Moreover, when the upper-level objective is non-convex, our method requires $${O}(\max\{1/\epsilon_f^2,1/(\epsilon_f\epsilon_g)\})$$ iterations to find an $$(\epsilon_f,\epsilon_g)$$-optimal solution. We also prove stronger convergence guarantees under the Holderian error bound assumption on the lower-level problem. To the best of our knowledge, our method achieves the best-known iteration complexity for the considered class of bilevel problems. 

   more » « less
3. A randomized incremental primal-dual method for decentralized consensus optimization

   https://doi.org/10.1142/S0219530519410082  

   Chen, Chenxi; Chen, Yunmei; Ye, Xiaojing (November 2019, Analysis and Applications)

   We consider a class of convex decentralized consensus optimization problems over connected multi-agent networks. Each agent in the network holds its local objective function privately, and can only communicate with its directly connected agents during the computation to find the minimizer of the sum of all objective functions. We propose a randomized incremental primal-dual method to solve this problem, where the dual variable over the network in each iteration is only updated at a randomly selected node, whereas the dual variables elsewhere remain the same as in the previous iteration. Thus, the communication only occurs in the neighborhood of the selected node in each iteration and hence can greatly reduce the chance of communication delay and failure in the standard fully synchronized consensus algorithms. We provide comprehensive convergence analysis including convergence rates of the primal residual and consensus error of the proposed algorithm, and conduct numerical experiments to show its performance using both uniform sampling and important sampling as node selection strategy. 

   more » « less
4. On the Initialization for Convex-Concave Min-max Problems

   Liu, Mingrui; Orabona, Francesco (January 2022, International Conference on Algorithmic Learning Theory)

   Dasgupta, Sanjoy; Haghtalab, Nika (Ed.)

   Convex-concave min-max problems are ubiquitous in machine learning, and people usually utilize first-order methods (e.g., gradient descent ascent) to find the optimal solution. One feature which separates convex-concave min-max problems from convex minimization problems is that the best known convergence rates for min-max problems have an explicit dependence on the size of the domain, rather than on the distance between initial point and the optimal solution. This means that the convergence speed does not have any improvement even if the algorithm starts from the optimal solution, and hence, is oblivious to the initialization. Here, we show that strict-convexity-strict-concavity is sufficient to get the convergence rate to depend on the initialization. We also show how different algorithms can asymptotically achieve initialization-dependent convergence rates on this class of functions. Furthermore, we show that the so-called “parameter-free” algorithms allow to achieve improved initialization-dependent asymptotic rates without any learning rate to tune. In addition, we utilize this particular parameter-free algorithm as a subroutine to design a new algorithm, which achieves a novel non-asymptotic fast rate for strictly-convex-strictly-concave min-max problems with a growth condition and Hölder continuous solution mapping. Experiments are conducted to verify our theoretical findings and demonstrate the effectiveness of the proposed algorithms. 

   more » « less
5. A blob method for mean field control with terminal constraints

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

   Craig, Katy; Elamvazhuthi, Karthik; Lee, Harlin (January 2025, ESAIM: Control, Optimisation and Calculus of Variations)

   In the present work, we develop a novel particle method for a general class of mean field control problems, with source and terminal constraints. Specific examples of the problems we consider include the dynamic formulation of thep-Wasserstein metric, optimal transport around an obstacle, and measure transport subject to acceleration controls. Unlike existing numerical approaches, our particle method is meshfree and does not require global knowledge of an underlying cost function or of the terminal constraint. A key feature of our approach is a novel way of enforcing the terminal constraint via a soft, nonlocal approximation, inspired by recent work on blob methods for diffusion equations.We prove convergence of our particle approximation to solutions of the continuum mean-field control problem in the sense of Γ-convergence. A byproduct of our result is an extension of existing discrete-to-continuum convergence results for mean field control problems to more general state and measure costs, as arise when modeling transport around obstacles, and more general constraint sets, including controllable linear time invariant systems. Finally, we conclude by implementing our method numerically and using it to compute solutions the example problems discussed above. We conduct a detailed numerical investigation of the convergence properties of our method, as well as its behavior in sampling applications and for approximation of optimal transport maps. 

   more » « less