Saeed Ghadimi

Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods

Categories Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization Tags , , , ,

We develop inexact augmented Lagrangian (AL) methods for linearly constrained convex composite optimization problems whose objective is the sum of a smooth convex function and a possibly nonsmooth closed proper convex function with compact domain. Unlike primal accuracy guarantees based on objective-value error, our methods target verifiable approximate KKT solutions. In the convex setting, we … Read more

Optimal diagonal preconditioning beyond worst-case conditioning: theory and practice of omega scaling

Categories Convex and Nonsmooth Optimization, Nonsmooth Optimization, Optimization in Data Science Tags , , , ,

Preconditioning is essential in many areas of mathematics, and in particular is a fundamental tool for accelerating iterative methods for solving linear systems. In this work, we study optimal diagonal preconditioning under two distinct notions of conditioning: the classical worst-case \(\kappa\)-condition number and the averaging-based \(\omega\)-condition number. We observe that \(\omega\)-optimal preconditioning generally outperforms \(\kappa\)-optimal … Read more

Stochastic Multi-level Composition Optimization Algorithms with Level-Independent Convergence Rates

Categories Nonlinear Optimization, Statistics, Stochastic Programming Tags , , ,

In this paper, we study smooth stochastic multi-level composition optimization problems, where the objective function is a nested composition of $T$ functions. We assume access to noisy evaluations of the functions and their gradients, through a stochastic first-order oracle. For solving this class of problems, we propose two algorithms using moving-average stochastic estimates, and analyze … Read more

Non-asymptotic Results for Langevin Monte Carlo: Coordinate-wise and Black-box Sampling

Categories Nonlinear Optimization, Statistics Tags , , ,

Euler-Maruyama and Ozaki discretization of a continuous time diffusion process is a popular technique for sampling, that uses (upto) gradient and Hessian information of the density respectively. The Euler-Maruyama discretization has been used particularly for sampling under the name of Langevin Monte Carlo (LMC) for sampling from strongly log-concave densities. In this work, we make … Read more

Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality, and Saddle-Points

Categories Nonlinear Optimization, Stochastic Programming Tags , , , , ,

In this paper, we propose and analyze zeroth-order stochastic approximation algorithms for nonconvex and convex optimization, with a focus on addressing constrained optimization, high-dimensional setting, and saddle-point avoiding. To handle constrained optimization, we first propose generalizations of the conditional gradient algorithm achieving rates similar to the standard stochastic gradient algorithm using only zeroth-order information. To … Read more

Reinforcement Learning via Parametric Cost Function Approximation for Multistage Stochastic Programming

Categories Applications - OR and Management Sciences, Optimization of Simulated Systems, Stochastic Programming Tags , , , ,

The most common approaches for solving stochastic resource allocation problems in the research literature is to either use value functions (“dynamic programming”) or scenario trees (“stochastic programming”) to approximate the impact of a decision now on the future. By contrast, common industry practice is to use a deterministic approximation of the future which is easier … Read more

A Single Time-Scale Stochastic Approximation Method for Nested Stochastic Optimization

Categories Nonlinear Optimization, Stochastic Programming Tags , ,

We study constrained nested stochastic optimization problems in which the objective function is a composition of two smooth functions whose exact values and derivatives are not available. We propose a single time-scale stochastic approximation algorithm, which we call the Nested Averaged Stochastic Approximation (NASA), to find an approximate stationary point of the problem. The algorithm … Read more

Conditional gradient type methods for composite nonlinear and stochastic optimization

Categories Nonlinear Optimization Tags , , , , ,

In this paper, we present a conditional gradient type (CGT) method for solving a class of composite optimization problems where the objective function consists of a (weakly) smooth term and a (strongly) convex regularization term. While including a strongly convex term in the subproblems of the classical conditional gradient (CG) method improves its rate of … Read more

Generalized Uniformly Optimal Methods for Nonlinear Programming

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , , , ,

In this paper, we present a generic framework to extend existing uniformly optimal convex programming algorithms to solve more general nonlinear, possibly nonconvex, optimization problems. The basic idea is to incorporate a local search step (gradient descent or Quasi-Newton iteration) into these uniformly optimal convex programming methods, and then enforce a monotone decreasing property of … Read more

Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

In this paper, we generalize the well-known Nesterov’s accelerated gradient (AG) method, originally designed for convex smooth optimization, to solve nonconvex and possibly stochastic optimization problems. We demonstrate that by properly specifying the stepsize policy, the AG method exhibits the best known rate of convergence for solving general nonconvex smooth optimization problems by using first-order … Read more