In this work, we propose algorithms for solving a class of Bilevel Optimization (BLO) problems, with applications in areas such as signal processing, networking and machine learning. Specifically, we develop a novel barrier-based gradient approximation algorithm that transforms the constrained BLO problem to a problem with only linear equality constraints in the LL task. For the reformulated problem, we compute the implicit gradient and develop a gradient-based scheme, involving only a single gradient descent step and the (approximate) solution of the linearly constrained strongly convex LL task at each iteration. We establish, under certain assumptions, the non-asymptotic convergence guarantees of the proposed method to stationary points. Finally, we perform a number of experiments that show the potential of the proposed algorithm.

This work develops analysis and algorithms for solving a class of bilevel optimization problems where the lower-level (LL) problems have linear constraints. Most of the existing approaches for constrained bilevel problems rely on value function-based approximate reformulations, which suffer from issues such as non-convex and non-differentiable constraints. In contrast, in this work, we develop an implicit gradient-based approach, which is easy to implement, and is suitable for machine learning applications. We first provide an in-depth understanding of the problem, by showing that the implicit objective for such problems is in general non-differentiable. However, if we add some small (linear) perturbation to the LL objective, the resulting implicit objective becomes differentiable almost surely. This key observation opens the door for developing (deterministic and stochastic) gradient-based algorithms similar to the state-of-the-art ones for unconstrained bi-level problems. We show that when the implicit function is assumed to be strongly-convex, convex, and weakly-convex, the resulting algorithms converge with guaranteed rate. Finally, we experimentally corroborate the theoretical findings and evaluate the performance of the proposed framework on numerical and adversarial learning problems.

In this work, we develop an implicit gradient-type (IG-AL) algorithm for bilevel optimization with strongly convex linear inequality constrained lower-level problems. Many learning problems of interest, including problems in distributed optimization, machine learning, economics, and transport research are captured by the above formulation. The key characteristics of the proposed algorithm are: (i) the use of a primal-dual augmented Lagrangian method for solving the lower-level problem, and (ii) construction of an implicit gradient (derived using the KKT conditions of the lower-level problem) for solving the upper-level problem. Importantly, the proposed algorithm avoids the (expensive) projection step to a half-space inherent to gradient descent-based alternatives. The performance of the proposed algorithm is evaluated on a set of numerical experiments.

Decentralized optimization are playing an important role in applications such as training large machine learning models, among others. Despite its superior practical performance, there has been some lack of fundamental understanding about its theoretical properties. In this work, we address the following open research question: To train an overparameterized model over a set of distributed nodes, what is the {\it minimum} communication overhead (in terms of the bits got exchanged) that the system needs to sustain, while still achieving (near) zero training loss? We show that for a class of overparameterized models where the number of parameters $D$ is much larger than the total data samples $N$, the best possible communication complexity is ${\Omega}(N)$, which is independent of the problem dimension $D$. Further, for a few specific overparameterized models (i.e., the linear regression, and certain multi-layer neural network with one wide layer), we develop a set of algorithms which uses certain linear compression followed by adaptive quantization, and show that they achieve dimension independent, and sometimes near optimal, communication complexity. To our knowledge, this is the first time that dimension independent communication complexity has been shown for distributed optimization.

Efficiently finding First-order Nash Equilibria (FNE) in zero-sum games can be challenging, even in a two-player setting. This work proposes an algorithm for finding the FNEs of a two-player zero-sum game, in which the local cost functions can be non-convex, and the players only have access to local stochastic gradients. The proposed approach is based on reformulating the problem of interest as minimizing the Regularized Nikaido-Isoda (RNI) function. We show that the global minima of the RNI correspond to the set of FNEs, and that for certain classes of non-convex games the RNI minimization problem becomes convex. Moreover, we introduce a first-order (stochastic) optimization method, and establish its convergence to a neighborhood of a stationary solution of the RNI objective. The key in the analysis is to properly control the bias between the local stochastic gradient and the true one. Although the RNI function has been used in analyzing convex games, to our knowledge, this is the first time that the properties of the RNI formulation have been exploited to find FNEs for non-convex games in a stochastic setting.

This paper discusses formulations and algorithms which allow a number of agents to collectively solve problems involving both (non-convex) minimization and (concave) maximization operations. These problems have a number of interesting applications in information processing and machine learning, and in particular can be used to model an adversary learning problem called network data poisoning. We develop a number of algorithms to efficiently solve these non-convex min-max optimization problems, by combining techniques such as gradient tracking in the decentralized optimization literature and gradient descent-ascent schemes in the min-max optimization literature. Also, we establish convergence to a first order stationary point under certain conditions. Finally, we perform experiments to demonstrate that the proposed algorithms are effective in the data poisoning attack.

The min-max problem, also known as the saddle point problem, can be used to formulate a wide range of applications in signal processing and wireless communications. However, existing optimization theory and methods, which mostly deal with problems with certain convex-concave structure, are not applicable for the aforementioned applications, which oftentimes involve non-convexity. In this work, we consider a general block-wise one-sided non-convex min-max problem, in which the minimization problem consists of multiple blocks and is non-convex, while the maximization problem is (strongly) concave. We propose two simple algorithms, which alternatingly perform one gradient descent-type step for each minimization block and one gradient ascent-type step for the maximization problem. For the first time, we show that such simple alternating min-max algorithms converge to first-order stationary solutions. We conduct numerical tests on a robust learning problem, and a wireless communication problem in the presence of jammers, to validate the efficiency of the proposed algorithms.

We introduce a tensor completion algorithm that uses a group-sparse regularizer with respect to the PARAFAC factors and is based on an optimization scheme that alternatingly minimizes a quadratic upper bound of the associated cost function. The proposed scheme allows matrixwise updates of the PARAFAC factors and, thus, leads to an efficient and scalable iterative algorithm, suitable for big-data applications. Experiments conducted on both synthetic and real data, corroborate the superior performance, in terms of runtime, of the proposed algorithm as compared with the other state-of-the-art approaches.