arXiv research

New algorithm minimizes worst-case regret in uncertain, time-varying dynamics.

In this paper we consider $l_0$ regularized convex cone programming problems. In particular, we first propose an iterative hard thresholding (IHT) method and its variant for solving $l_0$ regularized box constrained convex programming. We show that the sequence generated by these methods converges to a local minimizer.…

Improved ADMM for convex distributed learning with differential privacy.

Optimizes CM for stochastic convex optimization with progressive precision.

Improved CFR achieves faster convergence to Nash equilibrium.

In this paper we study general $l_p$ regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of first- and second-order stationary points, and hence also of local minimizers of the $l_p$ minimization problems. We extend some existing iterative reweighted $l_1$ (IRL1) a…

We study the performance of a family of randomized parallel coordinate descent methods for minimizing the sum of a nonsmooth and separable convex functions. The problem class includes as a special case L1-regularized L1 regression and the minimization of the exponential loss ("AdaBoost problem"). We assume the input da…

Support vector machines (SVMs) are an important tool in modern data analysis. Traditionally, support vector machines have been fitted via quadratic programming, either using purpose-built or off-the-shelf algorithms. We present an alternative approach to SVM fitting via the majorization--minimization (MM) paradigm. Alg…

This study analyzes adversarial training on linearly separable data and finds that gradient updates can achieve large margins in polynomial iterations.

Classifies links with minimal Khovanov homology rank.

Solving inverse problems with iterative algorithms is popular, especially for large data. Due to time constraints, the number of possible iterations is usually limited, potentially affecting the achievable accuracy. Given an error one is willing to tolerate, an important question is whether it is possible to modify the…

Paper improves worst-case regret bounds for RLSVI in reinforcement learning.

Paper proposes iterative trimmed loss minimization for learning from corrupted data.

In this paper we consider the composite self-concordant (CSC) minimization problem, which minimizes the sum of a self-concordant function $f$ and a (possibly nonsmooth) proper closed convex function $g$. The CSC minimization is the cornerstone of the path-following interior point methods for solving a broad class of co…

New iterative method solves Yamabe problem on small domains.

New method uses robust estimators for Newton's method in empirical risk minimization.

QMME balances cost and speed in convex optimization.

Paper characterizes gradient descent in high-dimensional learning problems.

Study improves curvature estimate for stable marginally outer trapped hypersurfaces with a free boundary.

Proves existence of at least two minimal spheres in any 3D space.

Paper achieves $ε^{-2}$ sample complexity for actor-critic methods with minimal assumptions.

The cyclic block coordinate descent-type (CBCD-type) methods, which performs iterative updates for a few coordinates (a block) simultaneously throughout the procedure, have shown remarkable computational performance for solving strongly convex minimization problems. Typical applications include many popular statistical…

Study symplectification of rank 2 distributions and their connections.

WaveFit uses fixed-point iteration to create high-quality neural vocoders.

Alternative proof and extension of curvature estimates for minimal immersions.

A meta-learning approach improves the performance of alternating minimization for non-convex optimization problems.

SGD's performance improves with critical batch size, minimizing SFO complexity.

A new algorithm finds minimizers in dueling optimization with a monotone adversary.

ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.

Algorithm estimates sparse signals from linear measurements, improving recovery guarantees.

Paper proposes a novel method to reduce mutual information for missing data imputation.

Cost-aware BO minimizes function evaluations with varying costs.

Non-convex optimization is ubiquitous in machine learning. Majorization-Minimization (MM) is a powerful iterative procedure for optimizing non-convex functions that works by optimizing a sequence of bounds on the function. In MM, the bound at each iteration is required to \emph{touch} the objective function at the opti…

We study randomized sketching methods for approximately solving least-squares problem with a general convex constraint. The quality of a least-squares approximation can be assessed in different ways: either in terms of the value of the quadratic objective function (cost approximation), or in terms of some distance meas…

This work presents a general framework for solving the low rank and/or sparse matrix minimization problems, which may involve multiple non-smooth terms. The Iteratively Reweighted Least Squares (IRLS) method is a fast solver, which smooths the objective function and minimizes it by alternately updating the variables an…

New methods for estimating panel regression models with interactive fixed effects.

We study knots in $\mathbb{S}^3$ obtained by the intersection of a minimal surface in $\mathbb{R}^4$ with a small 3-sphere centered at a branch point. We construct examples of new minimal knots. In particular we show the existence of non-fibered minimal knots. We show that simple minimal knots are either reversible or …

We present novel minibatch stochastic optimization methods for empirical risk minimization problems, the methods efficiently leverage variance reduced first-order and sub-sampled higher-order information to accelerate the convergence speed. For quadratic objectives, we prove improved iteration complexity over state-of-…

New bounds on SGD's final iterate convergence rate in constant dimension.

New algorithm for nonconvex optimization on constrained Riemannian manifolds converges quickly.

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $ε$-accurate solution with probability at least $1-ρ$ in at most $O(\tfrac{n}ε \log \tfrac{1}ρ)$ iterations, where $n$ is the numbe…

Paper proposes efficient algorithm for non-convex rank minimization.

New algorithm selects best preconditioner for iterative methods.

We propose a mixed integer programming (MIP) model and iterative algorithms based on topological orders to solve optimization problems with acyclic constraints on a directed graph. The proposed MIP model has a significantly lower number of constraints compared to popular MIP models based on cycle elimination constraint…

In this paper we study general Schatten-$p$ quasi-norm (SPQN) regularized matrix minimization problems. In particular, we first introduce a class of first-order stationary points for them, and show that the first-order stationary points introduced in [11] for an SPQN regularized $vector$ minimization problem are equiva…

LocalKMeans parallelizes Lloyd's algorithm for distributed data.

Sharp Liouville theorem for minimal graphs on manifolds with nonnegative Ricci curvature.

Majorization-minimization algorithms consist of iteratively minimizing a majorizing surrogate of an objective function. Because of its simplicity and its wide applicability, this principle has been very popular in statistics and in signal processing. In this paper, we intend to make this principle scalable. We introduc…