NANecdet Serhat Aybat

Necdet Serhat Aybat

*This is an algorithmically generated author record based on publicly available information.

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


Necdet Serhat Aybat has a total of 44 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems

    by Xuan Zhang, Qiushui Xu, Necdet Serhat Aybat

    We consider double-regularized nonconvex–strongly concave minimax problems of the form [Formula: see text], where [Formula: see text] are closed convex and [Formula: see text] is [Formula: see text]-smooth in [Formula: see text] and [Formula: see text]-strongly concave in [Formula: see text]. We propose a proximal alternating gradient descent ascent method AGDA+, which can adaptively choose nonmonotone primal-dual step sizes to compute an approximate stationary point for [Formula: see text] without requiring the knowledge of the global Lipschitz constant [Formula: see text] and the concavity modulus [Formula: see text]. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out for its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyperparameters. AGDA+ achieves the optimal iteration complexity of [Formula: see text], and it is the first step-size search method for nonconvex–strongly concave minimax problems that require only [Formula: see text] calls to [Formula: see text] per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency.

  • A Randomized Block-Coordinate Primal-Dual Method for Large-Scale Stochastic Saddle Point Problems

    by Erfan Yazdandoost Hamedani, Afrooz Jalilzadeh, Necdet Serhat Aybat

    We consider (stochastic) convex-concave saddle point (SP) problems with high-dimensional decision variables, arising in various applications including machine learning problems. To contend with the challenges in computing full gradients, we employ a randomized block-coordinate primal-dual scheme in which randomly selected primal and dual blocks of variables are updated. We consider both deterministic and stochastic settings, where deterministic partial gradients and their randomly sampled estimates are used, respectively, at each iteration. We investigate the convergence of the proposed method under different blocking strategies and provide the corresponding complexity results. Although the best-known computational complexity result for computing a saddle point with [Formula: see text] primal-dual gap for deterministic primal-dual methods using full gradients is [Formula: see text], where m and n denote the dimensions of primal and dual variables, respectively, we show that our proposed randomized block-coordinate method achieves an improved complexity of [Formula: see text] assuming a coordinate-friendly structure on the problem. Moreover, for the stochastic setting where a mini-batch sample gradient is utilized, we show a computational complexity of [Formula: see text] through acceleration. Finally, almost sure convergence of the iterate sequence to a saddle point is established. Funding: N. Serhat Aybat was supported by the Office of Naval Research [Grant N00014-24-1-2666]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoo.2024.0056 .


  • Open Access

    Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization

    by Xuan Zhang, Gabriel Mancino-Ball, Necdet Serhat Aybat, Yangyang Xu

    We propose a novel single-loop decentralized algorithm, DGDA-VR, for solving the stochastic nonconvex strongly-concave minimax problems over a connected network of agents, which are equipped with stochastic first-order oracles to estimate their local gradients. DGDA-VR, incorporating variance reduction, achieves O(ε^−3) oracle complexity and O(ε^−2) communication complexity without resorting to multi-communication rounds – both are optimal, i.e., matching the lower bounds for this class of problems. Since DGDA-VR does not require multiple communication rounds, it is applicable to a broader range of decentralized computational environments. To the best of our knowledge, this is the first distributed method using a single communication round in each iteration to jointly optimize the oracle and communication complexities for the problem considered here.


  • Open Access

    Jointly Improving the Sample and Communication Complexities in Decentralized Stochastic Minimax Optimization

    by Xuan Zhang, Gabriel Mancino-Ball, Necdet Serhat Aybat, Yangyang Xu

    We propose a novel single-loop decentralized algorithm called DGDA-VR for solving the stochastic nonconvex strongly-concave minimax problem over a connected network of $M$ agents. By using stochastic first-order oracles to estimate the local gradients, we prove that our algorithm finds an $ε$-accurate solution with $\mathcal{O}(ε^{-3})$ sample complexity and $\mathcal{O}(ε^{-2})$ communication complexity, both of which are optimal and match the lower bounds for this class of problems. Unlike competitors, our algorithm does not require multiple communications for the convergence results to hold, making it applicable to a broader computational environment setting. To the best of our knowledge, this is the first such algorithm to jointly optimize the sample and communication complexities for the problem considered here.

  • Robust Accelerated Primal-Dual Methods for Computing Saddle Points

    by Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

    We consider strongly-convex-strongly-concave saddle point problems assuming we have access to unbiased stochastic estimates of the gradients. We propose a stochastic accelerated primal-du...


  • Open Access

    A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs

    by Diyako Ghaderyan, Necdet Serhat Aybat, A. Pedro Aguiar, Fernando Lobo Pereira

    In this paper, we introduce a fast row-stochastic decentralized algorithm, referred to as FRSD, to solve consensus optimization problems over directed communication graphs. The proposed algorithm only utilizes row-stochastic weights, leading to certain practical advantages in broadcast communication settings over those requiring column-stochastic weights. Under the assumption that each node-specific function is smooth and strongly convex, we show that the FRSD iterate sequence converges with a linear rate to the optimal consensus solution. In contrast to the existing methods for directed networks, FRSD enjoys linear convergence without employing a gradient tracking (GT) technique explicitly, rather it implements GT implicitly with the use of a novel momentum term, which leads to a significant reduction in communication and storage overhead for each node when FRSD is implemented for solving high-dimensional problems over small-to-medium scale networks. In the numerical tests, we compare FRSD with other state-of-the-art methods, which use row-stochastic and/or column-stochastic weights.

  • Open Access

    Robust Accelerated Primal-Dual Methods for Computing Saddle Points

    by Xuan Zhang, Necdet Serhat Aybat, Mert Gürbüzbalaban

    We consider strongly-convex-strongly-concave saddle point problems assuming we have access to unbiased stochastic estimates of the gradients. We propose a stochastic accelerated primal-dual (SAPD) algorithm and show that SAPD sequence, generated using constant primal-dual step sizes, linearly converges to a neighborhood of the unique saddle point. Interpreting the size of the neighborhood as a measure of robustness to gradient noise, we obtain explicit characterizations of robustness in terms of SAPD parameters and problem constants. Based on these characterizations, we develop computationally tractable techniques for optimizing the SAPD parameters, i.e., the primal and dual step sizes, and the momentum parameter, to achieve a desired trade-off between the convergence rate and robustness on the Pareto curve. This allows SAPD to enjoy fast convergence properties while being robust to noise as an accelerated method. SAPD admits convergence guarantees for the distance metric with a variance term optimal up to a logarithmic factor, which can be removed by employing a restarting strategy. We also discuss how convergence and robustness results extend to the convex-concave setting. Finally, we illustrate our framework on distributionally robust logistic regression.

  • A Fast Row-Stochastic Decentralized Method for Distributed Optimization Over Directed Graphs

    by Diyako Ghaderyan, Necdet Serhat Aybat, A. Pedro Aguiar, Fernando Lobo Pereira

    In this paper, we introduce a fast row-stochastic decentralized algorithm, referred to as FRSD, to solve consensus optimization problems over directed communication graphs. The proposed algorithm only utilizes row-stochastic weights, leading to certain practical advantages in broadcast communication settings over those requiring column-stochastic weights. Under the assumption that each node-specific function is smooth and strongly convex, we show that the FRSD iterate sequence converges with a linear rate to the optimal consensus solution. In contrast to the existing methods for directed networks, FRSD enjoys linear convergence without employing a gradient tracking (GT) technique explicitly, rather it implements GT implicitly with the use of a novel momentum term, which leads to a significant reduction in communication and storage overhead for each node when FRSD is implemented for solving high-dimensional problems over small-to-medium scale networks. In the numerical tests, we compare FRSD with other state-of-the-art methods, which use row-stochastic and/or column-stochastic weights.


  • Open Access

    Randomized Primal-Dual Methods with Adaptive Step Sizes

    by E. Yazdandoost Hamedani, A. Jalilzadeh, N. S. Aybat

    In this paper we propose a class of randomized primal-dual methods to contend with large-scale saddle point problems defined by a convex-concave function $\mathcal{L}(\mathbf{x},y)\triangleq\sum_{i=1}^m f_i(x_i)+\Phi(\mathbf{x},y)-h(y)$. We analyze the convergence rate of the proposed method under mere convexity and strong convexity assumptions of $\mathcal{L}$ in $\mathbf{x}$-variable. In particular, assuming $\nabla_y\Phi(\cdot,\cdot)$ is Lipschitz and $\nabla_\mathbf{x}\Phi(\cdot,y)$ is coordinate-wise Lipschitz for any fixed $y$, the ergodic sequence generated by the algorithm achieves the convergence rate of $\mathcal{O}(M/k)$ in the expected primal-dual gap. Furthermore, assuming that $\mathcal{L}(\cdot,y)$ is strongly convex for any $y$, and that $\Phi(\mathbf{x},\cdot)$ is affine for any $\mathbf{x}$, the scheme enjoys a faster rate of $\mathcal{O}(M/k^2)$ in terms of primal solution suboptimality. We implemented the proposed algorithmic framework to solve kernel matrix learning problem, and tested it against other state-of-the-art first-order methods

  • Open Access

    Lp Quasi-norm Minimization: Algorithm and Applications

    by Omar M. Sleem, M. E. Ashour, N. S. Aybat, Constantino M. Lagoa

    Sparsity finds applications in areas as diverse as statistics, machine learning, and signal processing. Computations over sparse structures are less complex compared to their dense counterparts, and their storage consumes less space. This paper proposes a heuristic method for retrieving sparse approximate solutions of optimization problems via minimizing the $\ell_{p}$ quasi-norm, where $0<p<1$. An iterative two-block ADMM algorithm for minimizing the $\ell_{p}$ quasi-norm subject to convex constraints is proposed. For $p=s/q<1$, $s,q \in \mathbb{Z}_{+}$, the proposed algorithm requires solving for the roots of a scalar degree $2q$ polynomial as opposed to applying a soft thresholding operator in the case of $\ell_{1}$. The merit of that algorithm relies on its ability to solve the $\ell_{p}$ quasi-norm minimization subject to any convex set of constraints. However, it suffers from low speed, due to a convex projection step in each iteration, and the lack of mathematical convergence guarantee. We then aim to vanquish these shortcomings by relaxing the assumption on the constraints set to be the set formed due to convex and differentiable, with Lipschitz continuous gradient, functions, i.e. specifically, polytope sets. Using a proximal gradient step, we mitigate the convex projection step and hence enhance the algorithm speed while proving its convergence. We then present various applications where the proposed algorithm excels, namely, matrix rank minimization, sparse signal reconstruction from noisy measurements, sparse binary classification, and system identification. The results demonstrate the significant gains obtained by the proposed algorithm compared to those via $\ell_{1}$ minimization.