arXiv research

BCD-prox improves robustness and accuracy in filtering and parameter estimation.

Uniform sampling of training data has been commonly used in traditional stochastic optimization algorithms such as Proximal Stochastic Gradient Descent (prox-SGD) and Proximal Stochastic Dual Coordinate Ascent (prox-SDCA). Although uniform sampling can guarantee that the sampled stochastic quantity is an unbiased estim…

Characterizes minimizing curves in Riemannian manifolds.

Defines weak geodesics on specific subsets of manifolds.

The paper proves properties of curves in Riemannian manifolds.

New algorithm finds mixed Nash equilibria in GANs.

Here we study non-convex composite optimization: first, a finite-sum of smooth but non-convex functions, and second, a general function that admits a simple proximal mapping. Most research on stochastic methods for composite optimization assumes convexity or strong convexity of each function. In this paper, we extend t…

We provide tight upper and lower bounds on the complexity of minimizing the average of $m$ convex functions using gradient and prox oracles of the component functions. We show a significant gap between the complexity of deterministic vs randomized optimization. For smooth functions, we show that accelerated gradient de…

New method predicts and optimizes matrix recovery from noisy measurements.

New algorithm expands FTRL framework with improved worst-case regret bounds.

Optimized method tackles convex optimization with heavy-tailed noise.

Establishes geometric convergence of iterative optimization algorithms.

Method solves nonconvex constrained optimization problems with a new augmented Lagrangian approach.

In this paper, we propose a simple variant of the original stochastic variance reduction gradient (SVRG), where hereafter we refer to as the variance reduced stochastic gradient descent (VR-SGD). Different from the choices of the snapshot point and starting point in SVRG and its proximal variant, Prox-SVRG, the two vec…

Stochastic gradient algorithms estimate the gradient based on only one or a few samples and enjoy low computational cost per iteration. They have been widely used in large-scale optimization problems. However, stochastic gradient algorithms are usually slow to converge and achieve sub-linear convergence rates, due to t…

Improved non-smooth optimization methods achieve faster convergence rates.

We study \emph{TV regularization}, a widely used technique for eliciting structured sparsity. In particular, we propose efficient algorithms for computing prox-operators for $\ell_p$-norm TV. The most important among these is $\ell_1$-norm TV, for whose prox-operator we present a new geometric analysis which unveils a …

A new method solves l1-regularized optimization problems efficiently and sparsely.

Sample efficiency is critical in solving real-world reinforcement learning problems, where agent-environment interactions can be costly. Imitation learning from expert advice has proved to be an effective strategy for reducing the number of interactions required to train a policy. Online imitation learning, which inter…

Universal algorithm for variational inequalities adapts to smoothness and noise.

Lower bound shows no acceleration for specific convex optimization class.

New algorithm reduces regret and constraint violation in online convex optimization with complex constraints.

Two algorithms find optimal points in decentralized optimization.

ProxQuant improves quantized neural networks using proximal operators.

Paper improves rates for solving smooth minimax optimization problems.

Paper develops efficient algorithms for robust optimization across multiple groups.

In this paper, we propose a simple variant of the original SVRG, called variance reduced stochastic gradient descent (VR-SGD). Unlike the choices of snapshot and starting points in SVRG and its proximal variant, Prox-SVRG, the two vectors of VR-SGD are set to the average and last iterate of the previous epoch, respecti…

In this paper we propose a randomized primal-dual proximal block coordinate updating framework for a general multi-block convex optimization model with coupled objective function and linear constraints. Assuming mere convexity, we establish its $O(1/t)$ convergence rate in terms of the objective value and feasibility m…

It has been recently shown that a large class of balanced graph cuts allows for an exact relaxation into a nonlinear eigenproblem. We review briefly some of these results and propose a family of algorithms to compute nonlinear eigenvectors which encompasses previous work as special cases. We provide a detailed analysis…

Paper accelerates SAGA using sampled negative momentum.

A new framework optimizes model transfer across domains with labeled data.

Improved algorithms for convex-concave min-max optimization and monotone variational inequalities.

This monograph presents the main complexity theorems in convex optimization and their corresponding algorithms. Starting from the fundamental theory of black-box optimization, the material progresses towards recent advances in structural optimization and stochastic optimization. Our presentation of black-box optimizati…

New solver SR2 tackles deep neural network training with nonsmooth regularization.

A new method for RLHF using proximal point Nash learning.

Many optimization algorithms converge to stationary points. When the underlying problem is nonconvex, they may get trapped at local minimizers and occasionally stagnate near saddle points. We propose the Run-and-Inspect Method, which adds an "inspect" phase to existing algorithms that helps escape from non-global stati…

New methods integrate nonlinear, sparse, and multi-view aspects for high-dimensional data analysis.

New analysis shows convergence rate of 1/k for gradient and extra-gradient methods.

Paper finds a fast method for a matrix norm proximal operator.

Sparse reconstruction approaches using the re-weighted l1-penalty have been shown, both empirically and theoretically, to provide a significant improvement in recovering sparse signals in comparison to the l1-relaxation. However, numerical optimization of such penalties involves solving problems with l1-norms in the ob…

New algorithm reduces communication in federated learning.

In this paper we propose a primal-dual proximal extragradient algorithm to solve the generalized Dantzig selector (GDS) estimation problem, based on a new convex-concave saddle-point (SP) reformulation. Our new formulation makes it possible to adopt recent developments in saddle-point optimization, to achieve the optim…

Paper tackles robust classification and feature selection with a novel primal-dual method.

We propose weight-sharing regularization for neural networks.

New algorithm learns value and advantage functions for continuous-time Markov processes without structural assumptions.

New algorithm tackles complex optimization problems with inexact and stochastic methods.

Geometric step decay schedules improve stochastic algorithms' convergence on sharp nonconvex problems.

A novel hierarchical Bayesian approach to Federated Learning reduces data exposure and improves convergence rates.