260 citations · 1.8k across the 63 of their papers we have counts for
26 papers · 1 filter
Gradient Descent and the Power Method: Exploiting their connection to find the leftmost eigen-pair and escape saddle points
Rachael Tappenden, Martin Takáč
This work shows that applying Gradient Descent (GD) with a fixed step size to minimize a (possibly nonconvex) quadratic function is equivalent to running the Power Method (PM) on t…
Optimal Power Flow Pursuit in the Alternating Current Model
Jie Liu, Antonio Bellon, Andrea Simonetto +2
Transmission-constrained problems in power systems can be cast as polynomial optimization problems whose coefficients vary over time. We consider the complications therein and sugg…
Algorithm for Constrained Markov Decision Process with Linear Convergence
Egor Gladin, Maksim Lavrik-Karmazin, Karina Zainullina +3
The problem of constrained Markov decision process is considered. An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs…
Stochastic Gradient Methods with Preconditioned Updates
Abdurakhmon Sadiev, Aleksandr Beznosikov, Abdulla Jasem Almansoori +3
This work considers the non-convex finite sum minimization problem. There are several algorithms for such problems, but existing methods often work poorly when the problem is badly…
The Power of First-Order Smooth Optimization for Black-Box Non-Smooth Problems
Alexander Gasnikov, Anton Novitskii, Vasilii Novitskii +6
Gradient-free/zeroth-order methods for black-box convex optimization have been extensively studied in the last decade with the main focus on oracle calls complexity. In this paper,…
Decentralized Personalized Federated Learning: Lower Bounds and Optimal Algorithm for All Personalization Modes
Abdurakhmon Sadiev, Ekaterina Borodich, Aleksandr Beznosikov +5
This paper considers the problem of decentralized, personalized federated learning. For centralized personalized federated learning, a penalty that measures the deviation from the…
New Convergence Aspects of Stochastic Gradient Algorithms
Lam M. Nguyen, Phuong Ha Nguyen, Peter Richtárik +3
The classical convergence analysis of SGD is carried out under the assumption that the norm of the stochastic gradient is uniformly bounded. While this might hold for some loss fun…
Inexact SARAH Algorithm for Stochastic Optimization
Lam M. Nguyen, Katya Scheinberg, Martin Takáč
We develop and analyze a variant of the SARAH algorithm, which does not require computation of the exact gradient. Thus this new method can be applied to general expectation minimi…
Randomized sketch descent methods for non-separable linearly constrained optimization
Ion Necoara, Martin Takac
In this paper we consider large-scale smooth optimization problems with multiple linear coupled constraints. Due to the non-separability of the constraints, arbitrary random sketch…
Entropy Penalized Semidefinite Programming
Mikhail Krechetov, Jakub Marecek, Yury Maximov +1
Low-rank methods for semidefinite programming (SDP) have gained a lot of interest recently, especially in machine learning applications. Their analysis often involves determinant-b…
SGD and Hogwild! Convergence Without the Bounded Gradients Assumption
Lam M. Nguyen, Phuong Ha Nguyen, Marten van Dijk +3
Stochastic gradient descent (SGD) is the optimization algorithm of choice in many machine learning applications such as regularized empirical risk minimization and training deep ne…
Dual Free Adaptive Minibatch SDCA for Empirical Risk Minimization
Xi He, Rachael Tappenden, Martin Takac
In this paper we develop an adaptive dual free Stochastic Dual Coordinate Ascent (adfSDCA) algorithm for regularized empirical risk minimization problems. This is motivated by the…
An Accelerated Communication-Efficient Primal-Dual Optimization Framework for Structured Machine Learning
Chenxin Ma, Martin Jaggi, Frank E. Curtis +2
Distributed optimization algorithms are essential for training machine learning models on very large-scale datasets. However, they often suffer from communication bottlenecks. Conf…
A Coordinate-Descent Algorithm for Tracking Solutions in Time-Varying Optimal Power Flows
Jie Liu, Jakub Marecek, Andrea Simonetto +1
Consider a polynomial optimisation problem, whose instances vary continuously over time. We propose to use a coordinate-descent algorithm for solving such time-varying optimisation…
Fast and Safe: Accelerated gradient methods with optimality certificates and underestimate sequences
Majid Jahani, Naga Venkata C. Gudapati, Chenxin Ma +2
In this work we introduce the concept of an Underestimate Sequence (UES), which is motivated by Nesterov's estimate sequence. Our definition of a UES utilizes three sequences, one…
A Robust Multi-Batch L-BFGS Method for Machine Learning
Albert S. Berahas, Martin Takáč
This paper describes an implementation of the L-BFGS method designed to deal with two adversarial situations. The first occurs in distributed computing environments where some of t…
A Multi-Batch L-BFGS Method for Machine Learning
Albert S. Berahas, Jorge Nocedal, Martin Takáč
The question of how to parallelize the stochastic gradient descent (SGD) method has received much attention in the literature. In this paper, we focus instead on batch methods that…
Partitioning Data on Features or Samples in Communication-Efficient Distributed Optimization?
Chenxin Ma, Martin Takáč
In this paper we study the effect of the way that the data is partitioned in distributed optimization. The original DiSCO algorithm [Communication-Efficient Distributed Optimizatio…
Dual Free Adaptive Mini-batch SDCA for Empirical Risk Minimization
Xi He, Martin Takáč
In this paper we develop dual free mini-batch SDCA with adaptive probabilities for regularized empirical risk minimization. This work is motivated by recent work of Shai Shalev-Shw…
Hybrid Methods in Solving Alternating-Current Optimal Power Flows
Alan C. Liddell, Jie Liu, Jakub Marecek +1
Many steady-state problems in power systems, including rectangular power-voltage formulations of optimal power flows in the alternating-current model (ACOPF), can be cast as polyno…
A Low-Rank Coordinate-Descent Algorithm for Semidefinite Programming Relaxations of Optimal Power Flow
Jakub Marecek, Martin Takac
The alternating-current optimal power flow (ACOPF) is one of the best known non-convex non-linear optimisation problems. We present a novel re-formulation of ACOPF, which is based…
Matrix Completion under Interval Uncertainty
Jakub Marecek, Peter Richtarik, Martin Takac
Matrix completion under interval uncertainty can be cast as matrix completion with element-wise box constraints. We present an efficient alternating-direction parallel coordinate-d…
Distributed Block Coordinate Descent for Minimizing Partially Separable Functions
Jakub Marecek, Peter Richtarik, Martin Takac
In this work we propose a distributed randomized block coordinate descent method for minimizing a convex function with a huge number of variables/coordinates. We analyze its comple…
Fast Distributed Coordinate Descent for Non-Strongly Convex Losses
Olivier Fercoq, Zheng Qu, Peter Richtárik +1
We propose an efficient distributed randomized coordinate descent method for minimizing regularized non-strongly convex loss functions. The method attains the optimal co…