A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
Improved MPC with neural networks and active sets for large-scale problems.
We develop a primal dual active set with continuation algorithm for solving the \ell^0-regularized least-squares problem that frequently arises in compressed sensing. The algorithm couples the the primal dual active set method with a continuation strategy on the regularization parameter. At each inner iteration, it fir…
In this paper, we consider the problem of recovering a sparse signal based on penalized least squares formulations. We develop a novel algorithm of primal-dual active set type for a class of nonconvex sparsity-promoting penalties, including , bridge, smoothly clipped absolute deviation, capped and mini…
New K-SVD framework speeds up image denoising with active set algorithm.
Optimizes identifying top-k items from comparisons with minimal comparisons.
Drago optimizes DRO problems with faster convergence.
This paper provides a set of sensitivity analysis and activity identification results for a class of convex functions with a strong geometric structure, that we coined "mirror-stratifiable". These functions are such that there is a bijection between a primal and a dual stratification of the space into partitioning sets…
Unified algorithm solves convex optimization problems with optimal rates.
Paper explores generalization of minimax learners, proposing a new metric.
New algorithm for federated learning with non-smooth regularizers.
New method accelerates convergence for entropy-regularized reinforcement learning problems.
Neural networks generalize on simple data generated by a programming language.
In approachability with full monitoring there are two types of conditions that are known to be equivalent for convex sets: a primal and a dual condition. The primal one is of the form: a set C is approachable if and only all containing half-spaces are approachable in the one-shot game; while the dual one is of the form…
Paper studies statistical manifolds with logarithmic divergences.
Quantized Stochastic Primal-Dual Methods for Distributed Optimization
New algorithm speeds up large-scale statistical inference.
Improved RL algorithm with linear MDPs for offline learning with partial data coverage.
CRPO solves challenging SRL problems with convergence guarantee.
Dual martingales improve primal optimal stopping problem efficiency.
Sketching techniques have become popular for scaling up machine learning algorithms by reducing the sample size or dimensionality of massive data sets, while still maintaining the statistical power of big data. In this paper, we study sketching from an optimization point of view: we first show that the iterative Hessia…
A new method for distributed optimization reduces communication rounds without minibatches.
Two algorithms solve nonconvex minimax problems with linear constraints, achieving complexity guarantees.
Algebraic methods prove knot primality using Floer homology.
Derives a primal-dual MLSVD formulation for multilinear data.
Random extrapolation speeds up coordinate descent for sparse and dense data.
We present a primal-dual algorithmic framework to obtain approximate solutions to a prototypical constrained convex optimization problem, and rigorously characterize how common structural assumptions affect the numerical efficiency. Our main analysis technique provides a fresh perspective on Nesterov's excessive gap te…
A new method solves variational inequality problems with multiple constraints without needing optimal Lagrange multipliers.
PDCA algorithm learns policies for RL with constraints using a primal-dual approach.
In this paper, we study a constrained utility maximization problem following the convex duality approach. After formulating the primal and dual problems, we construct the necessary and sufficient conditions for both the primal and dual problems in terms of FBSDEs plus additional conditions. Such formulation then allows…
LEAD algorithm speeds up decentralized optimization with compression.
New methods solve saddle point problems without line search.
We consider empirical risk minimization of linear predictors with convex loss functions. Such problems can be reformulated as convex-concave saddle point problems, and thus are well suitable for primal-dual first-order algorithms. However, primal-dual algorithms often require explicit strongly convex regularization in …
Proposes a fair meta-learning framework for few-shot classification.
We study primal-dual type stochastic optimization algorithms with non-uniform sampling. Our main theoretical contribution in this paper is to present a convergence analysis of Stochastic Primal Dual Coordinate (SPDC) Method with arbitrary sampling. Based on this theoretical framework, we propose Optimality Violation-ba…
Constrained Markov Decision Process (CMDP) is a natural framework for reinforcement learning tasks with safety constraints, where agents learn a policy that maximizes the long-term reward while satisfying the constraints on the long-term cost. A canonical approach for solving CMDPs is the primal-dual method which updat…
We study a stochastic and distributed algorithm for nonconvex problems whose objective consists of a sum of nonconvex -smooth functions, plus a nonsmooth regularizer. The proposed NonconvEx primal-dual SpliTTing (NESTT) algorithm splits the problem into subproblems, and utilizes an augmented Lagrangian b…
Study on Gaussian-width complexity on statistical manifolds and its applications in learning and recovery.
In the era of big data, an important weapon in a machine learning researcher's arsenal is a scalable Support Vector Machine (SVM) algorithm. SVMs are extensively used for solving classification problems. Traditional algorithms for learning SVMs often scale super linearly with training set size which becomes infeasible …
Paper proposes a novel metric learning algorithm using Riemannian optimization.
We provide theoretical complexity analysis for new algorithms to compute the optimal transport (OT) distance between two discrete probability distributions, and demonstrate their favorable practical performance over state-of-art primal-dual algorithms and their capability in solving other problems in large-scale, such …
Novel analysis of EFP for finite-sum problems in neural networks.
We introduce Primal-Dual Wasserstein GAN, a new learning algorithm for building latent variable models of the data distribution based on the primal and the dual formulations of the optimal transport (OT) problem. We utilize the primal formulation to learn a flexible inference mechanism and to create an optimal approxim…
NeAda solves nonconvex minimax optimization by balancing primal and dual variables adaptively.
Efficient algorithm solves best subset selection problem.
In this paper we study several classes of stochastic optimization algorithms enriched with heavy ball momentum. Among the methods studied are: stochastic gradient descent, stochastic Newton, stochastic proximal point and stochastic dual subspace ascent. This is the first time momentum variants of several of these metho…
Previous studies on stochastic primal-dual algorithms for solving min-max problems with faster convergence heavily rely on the bilinear structure of the problem, which restricts their applicability to a narrowed range of problems. The main contribution of this paper is the design and analysis of new stochastic primal-d…
We consider a generic convex optimization problem associated with regularized empirical risk minimization of linear predictors. The problem structure allows us to reformulate it as a convex-concave saddle point problem. We propose a stochastic primal-dual coordinate (SPDC) method, which alternates between maximizing ov…
PURE-CD algorithm proves complexity bounds for convex-concave problems.