arXiv research

In machine learning research, the proximal gradient methods are popular for solving various optimization problems with non-smooth regularization. Inexact proximal gradient methods are extremely important when exactly solving the proximal operator is time-consuming, or the proximal operator does not have an analytic sol…

New algorithm solves phase retrieval with adaptive stopping criteria.

Develops a new SPP algorithm with variance reduction for weakly convex optimization.

Improved analysis for fair federated learning reduces dependence on noise floor.

In [19], a general, inexact, efficient proximal quasi-Newton algorithm for composite optimization problems has been proposed and a sublinear global convergence rate has been established. In this paper, we analyze the convergence properties of this method, both in the exact and inexact setting, in the case when the obje…

In this paper we present a convergence rate analysis of inexact variants of several randomized iterative methods. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic subspace ascent. A common feature of these methods is that in their update rule a cert…

Many scientific and engineering applications feature nonsmooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the nonsmooth objective is equipped with a tractable proximity operator and that the convex constraint set affords a self…

New algorithm extends LMC to more complex potentials.

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

Inexact Riemannian optimization converges to stationary points efficiently.

Improved sampling algorithm with state-of-the-art complexity bounds.

We propose an inexact variable-metric proximal point algorithm to accelerate gradient-based optimization algorithms. The proposed scheme, called QNing can be notably applied to incremental first-order methods such as the stochastic variance-reduced gradient descent algorithm (SVRG) and other randomized incremental opti…

Paper proposes iLPA for solving DC composite optimization problems, with applications to matrix completion with outliers.

New method controls gradient error for sparse MRFs.

New method solves complex constrained optimization problems.

Paper analyzes convergence of proximal algorithm in metric spaces without geodesic convexity.

New method tackles nonconvex-nonconcave problems with local KL condition.

New algorithms optimize convex functions with high-order derivatives.

Riemannian Proximal Sampler improves sampling on manifold data.

A new method tackles nonconvex optimization with penalties and proximal terms.

Inexact subgradient methods work well for semialgebraic functions with additive errors.

In kernel methods, the kernels are often required to be positive definite, which restricts the use of many indefinite kernels. To consider those non-positive definite kernels, in this paper, we aim to build an indefinite kernel learning framework for kernel logistic regression. The proposed indefinite kernel logistic r…

In this paper, we introduce various mechanisms to obtain accelerated first-order stochastic optimization algorithms when the objective function is convex or strongly convex. Specifically, we extend the Catalyst approach originally designed for deterministic objectives to the stochastic setting. Given an optimization me…

Wasserstein distance plays increasingly important roles in machine learning, stochastic programming and image processing. Major efforts have been under way to address its high computational complexity, some leading to approximate or regularized variations such as Sinkhorn distance. However, as we will demonstrate, regu…

A new algorithm solves signed Fréchet regression on manifolds with bounded curvature.

Recently, the principal component pursuit has received increasing attention in signal processing research ranging from source separation to video surveillance. So far, all existing formulations are real-valued and lack the concept of phase, which is inherent in inputs such as complex spectrograms or color images. Thus,…

We propose a fast proximal Newton-type algorithm for minimizing regularized finite sums that returns an $ε$-suboptimal point in $\tilde{\mathcal{O}}(d(n + \sqrt{κd})\log(\frac{1}ε))$ FLOPS, where $n$ is number of samples, $d$ is feature dimension, and $κ$ is the condition number. As long as $n > d$, the proposed method…

We propose a Generalized Dantzig Selector (GDS) for linear models, in which any norm encoding the parameter structure can be leveraged for estimation. We investigate both computational and statistical aspects of the GDS. Based on conjugate proximal operator, a flexible inexact ADMM framework is designed for solving GDS…

Recently several methods were proposed for sparse optimization which make careful use of second-order information [10, 28, 16, 3] to improve local convergence rates. These methods construct a composite quadratic approximation using Hessian information, optimize this approximation using a first-order method, such as coo…

Low-rank modeling has many important applications in computer vision and machine learning. While the matrix rank is often approximated by the convex nuclear norm, the use of nonconvex low-rank regularizers has demonstrated better empirical performance. However, the resulting optimization problem is much more challengin…

The paper analyzes the trade-off between smoothness and sparsity in GCN using lp-regularized learning.

ITSPACE improves covariance alignment faster than other methods.

We propose a supervised anomaly detection method for data with inexact anomaly labels, where each label, which is assigned to a set of instances, indicates that at least one instance in the set is anomalous. Although many anomaly detection methods have been proposed, they cannot handle inexact anomaly labels. To measur…

We develop a projected Nesterov's proximal-gradient (PNPG) approach for sparse signal reconstruction that combines adaptive step size with Nesterov's momentum acceleration. The objective function that we wish to minimize is the sum of a convex differentiable data-fidelity (negative log-likelihood (NLL)) term and a conv…

We introduce a generic scheme for accelerating gradient-based optimization methods in the sense of Nesterov. The approach, called Catalyst, builds upon the inexact accelerated proximal point algorithm for minimizing a convex objective function, and consists of approximately solving a sequence of well-chosen auxiliary p…

We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexa…

New methods help escape strict saddle points in nonsmooth optimization.

We consider the class of convex minimization problems, composed of a self-concordant function, such as the $\log\det$ metric, a convex data fidelity term $h(\cdot)$ and, a regularizing -- possibly non-smooth -- function $g(\cdot)$. This type of problems have recently attracted a great deal of interest, mainly due to th…

Paper shows how gradient concentration helps in learning from inexact data.

New characterization limits sampling with inexact scores.

Inexact acquisition solutions in BO lead to sublinear cumulative regret.

This paper analyzes the bias of inexact MCMC methods in high dimensions.

Evolutionary forms, as well as exterior forms, are skew-symmetric differential forms. But in contrast to the exterior forms, the basis of evolutionary forms is deforming manifolds (with unclosed metric forms). Such forms possess a peculiarity, namely, the closed inexact exterior forms are obtained from that. The closur…

In this work, we present a globalized stochastic semismooth Newton method for solving stochastic optimization problems involving smooth nonconvex and nonsmooth convex terms in the objective function. We assume that only noisy gradient and Hessian information of the smooth part of the objective function is available via…

New methods solve complex optimization problems in machine learning.

In this paper, we consider first-order convergence theory and algorithms for solving a class of non-convex non-concave min-max saddle-point problems, whose objective function is weakly convex in the variables of minimization and weakly concave in the variables of maximization. It has many important applications in mach…

Optimizes solving complex min-max problems with stochastic and nonconvex elements.

We propose novel first-order stochastic approximation algorithms for canonical correlation analysis (CCA). Algorithms presented are instances of inexact matrix stochastic gradient (MSG) and inexact matrix exponentiated gradient (MEG), and achieve $ε$-suboptimality in the population objective in $\operatorname{poly}(\fr…