Algebraic methods prove knot primality using Floer homology.
problem Proving the primality of knots.
method Knot Floer homology, metacyclic representations, and twisted homology.
result Primality tests have proven primality for over 99.6% of knots.
On-device research index
arXiv research
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.
168,695 papers · 148 categories
Trend · papers per month
48 results for “primal approach”
This work presents an explicit-implicit procedure to compute a model predictive control (MPC) law with guarantees on recursive feasibility and asymptotic stability. The approach combines an offline-trained fully-connected neural network with an online primal active set solver. The neural network provides a control inpu…
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…
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…
PDCA algorithm learns policies for RL with constraints using a primal-dual approach.
problem Offline constrained reinforcement learning with general function approximation.
method Primal-Dual-Critic Algorithm (PDCA) using a primal-dual approach.
result PDCA finds a near saddle point of the Lagrangian, nearly optimal for constrained RL.
In this paper, we revisit the portfolio optimization problems of the minimization/maximization of investment risk under constraints of budget and investment concentration (primal problem) and the maximization/minimization of investment concentration under constraints of budget and investment risk (dual problem) for the…
CRPO solves challenging SRL problems with convergence guarantee.
problem Safe reinforcement learning with nonconvex constraints.
method Primal approach using alternating policy updates and NPG.
result Achieves convergence rate and error bound.
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…
Proposes a fair meta-learning framework for few-shot classification.
problem Fairness in few-shot learning.
method Primal-Dual subgradient approach for fair initialization.
result Significant improvements over prior work in fairness.
Binarization of digital documents is the task of classifying each pixel in an image of the document as belonging to the background (parchment/paper) or foreground (text/ink). Historical documents are often subjected to degradations, that make the task challenging. In the current work a deep neural network architecture …
New algorithm speeds up large-scale statistical inference.
problem Efficiently solving large-scale mean-field variational inference problems.
method Developed a novel primal-dual algorithm (PD-VI) and a block-preconditioned extension (PD-VI) for mean-field variational inference.
result PD-VI and PD-VI achieve faster convergence and better solution quality compared to existing methods.
Primal-dual regression approach for Markov decision processes with general state and action spacemath.NA
Develops a regression approach for solving MDPs with general state and action spaces.
problem Solving MDPs with large or infinite state and action spaces.
method Regression-based primal-dual martingale approach.
result Tight upper and lower approximations of value functions and optimal policies.
In the present paper, the primal-dual problem consisting of the investment risk minimization problem and the expected return maximization problem in the mean-variance model is discussed using replica analysis. As a natural extension of the investment risk minimization problem under only a budget constraint that we anal…
Dual martingales improve primal optimal stopping problem efficiency.
problem Optimal stopping problem in the primal formulation.
method Investigation of dual martingales to improve primal methods.
result Accurate dual martingale approximations reduce primal problem variance.
Derives a primal-dual MLSVD formulation for multilinear data.
problem Efficiently decompose multilinear data for signal analysis and deep learning.
method Kernelizable primal-dual formulation of MLSVD.
result Derives a new MLSVD formulation with computational advantages.
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…
In this work, we propose a deep neural network architecture motivated by primal-dual splitting methods from convex optimization. We show theoretically that there exists a close relation between the derived architecture and residual networks, and further investigate this connection in numerical experiments. Moreover, we…
Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimizationstat.ML
Drago optimizes DRO problems with faster convergence.
problem Distributionally robust optimization with closed, convex uncertainty sets.
method Primal-dual coupled variance reduction algorithm with cyclic and randomized updates.
result Achieves state-of-the-art linear convergence rate on strongly convex-strongly concave problems.
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…
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 …
A New Randomized Primal-Dual Algorithm for Convex Optimization with Optimal Last Iterate Ratesmath.OC
Unified algorithm solves convex optimization problems with optimal rates.
problem Solving nonsmooth constrained convex optimization problems.
method Unified randomized block-coordinate primal-dual algorithm.
result Achieves optimal convergence rates of and .
In the last few years, due to the growing ubiquity of unlabeled data, much effort has been spent by the machine learning community to develop better understanding and improve the quality of classifiers exploiting unlabeled data. Following the manifold regularization approach, Laplacian Support Vector Machines (LapSVMs)…
A new algorithm tackles bilevel optimization with multiple inner minima.
problem Challenges in bilevel optimization with multiple inner minima.
method Reformulated as constrained optimization, solved via primal-dual bilevel optimization (PDBO) algorithm.
result First non-asymptotic convergence guarantee for bilevel optimization with multiple inner minima.
A new method for distributed optimization reduces communication rounds without minibatches.
problem Efficient training in distributed machine learning with different data distributions.
method A primal-dual method (GA-MSGD) applied to the Lagrangian of distributed optimization.
result Achieves linear convergence in communication rounds for strongly convex objectives.
A Primal Dual Active Set with Continuation Algorithm for the \ell^0-Regularized Optimization Problemmath.OC
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…
Stochastic Primal Dual Coordinate Method with Non-Uniform Sampling Based on Optimality Violationsstat.ML
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…
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…
A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learningcs.LG
Paper proposes a novel metric learning algorithm using Riemannian optimization.
problem Optimizing a smooth, convex function in Riemannian space with constraints.
method Developed a primal-dual algorithm with proximal operator for iterative optimization.
result Demonstrated the efficacy of the proposed metric learning algorithm on fund selection.
New algorithm for federated learning with non-smooth regularizers.
problem Federated Learning with non-smooth composite optimization problems.
method Proposed Federated Dual Averaging (FedDualAvg) algorithm to overcome convergence issues.
result FedDualAvg outperforms other algorithms in federated composite 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 …
New methods price American options in rough volatility models.
problem Pricing American options under rough volatility.
method Integrating deep-signature and signature-kernel learning into optimal stopping problem solutions.
result Performance comparison in rough Heston and rough Bergomi models.
In recent years, there has been a surge of interest in developing deep learning methods for non-Euclidean structured data such as graphs. In this paper, we propose Dual-Primal Graph CNN, a graph convolutional architecture that alternates convolution-like operations on the graph and its dual. Our approach allows to lear…
A new method solves variational inequality problems with multiple constraints without needing optimal Lagrange multipliers.
problem Solving variational inequality problems with multiple functional constraints efficiently.
method Constrained Gradient Method (CGM) for Minty variational inequality problems.
result The Constrained Gradient Method achieves complexity similar to projection-based methods but with cheaper oracles.
Scaff-PD improves fairness and robustness in federated learning with reduced communication.
problem Improving fairness and robustness in federated learning with limited communication.
method Scaff-PD uses a family of distributionally robust objectives and an accelerated primal dual algorithm with bias-corrected steps.
result Scaff-PD achieves significant gains in communication efficiency and convergence speed while maintaining fairness and robustness.
New method accelerates convergence for entropy-regularized reinforcement learning problems.
problem Slow convergence of standard first-order methods for entropy-regularized Markov decision processes.
method Introduce a quadratically convexified primal-dual formulation and a new interpolating metric to accelerate convergence.
result Global convergence and exponential convergence rate for the new method.
Primal-Dual Wasserstein GANstat.ML
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…
This paper contains an overview of results for dynamic multivariate risk measures. We provide the main results of four different approaches. We will prove under which assumptions results within these approaches coincide, and how properties like primal and dual representation and time consistency in the different approa…
Efficient algorithm solves best subset selection problem.
problem Sparse learning problems, especially best subset selection.
method Primal-dual method based on dual forms of -regularized problems.
result Improves solutions of best subset selection with reduced redundant computation.
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…
Paper explores generalization of minimax learners, proposing a new metric.
problem Understanding how minimax learners perform on unseen data.
method Proposes a new metric, the primal gap, to study generalization of minimax learners.
result Derives generalization error bounds for the primal gap in nonconvex-concave settings.
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…
Beating level-set methods for 3D seismic data interpolation: a primal-dual alternating approachmath.OC
Acquisition cost is a crucial bottleneck for seismic workflows, and low-rank formulations for data interpolation allow practitioners to `fill in' data volumes from critically subsampled data acquired in the field. Tremendous size of seismic data volumes required for seismic processing remains a major challenge for thes…
PURE-CD algorithm proves complexity bounds for convex-concave problems.
problem Solving convex-concave min-max problems with bilinear coupling.
method Primal-dual algorithm with random extrapolation and coordinate descent (PURE-CD).
result Complexity bounds match or improve existing results for dense and sparse problems.
Solves the Merton investment-consumption problem using a new approach.
problem Infinite-horizon Merton investment-consumption problem in a constant-parameter Black-Scholes-Merton market.
method Simple and elegant argument involving a stochastic perturbation of the utility function.
result Overcomes complications in existing primal verification proofs.
This paper deals with supervised classification and feature selection in high dimensional space. A classical approach is to project data on a low dimensional space and classify by minimizing an appropriate quadratic cost. A strict control on sparsity is moreover obtained by adding an constraint, here on the ma…
New algorithm achieves sublinear regret in CMDPs without error cancellations.
problem Safety constraints in reinforcement learning with error cancellations.
method Model-based primal-dual algorithm for CMDPs with multiple constraints.
result Achieves sublinear regret without error cancellations.
We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method…
Quantized Stochastic Primal-Dual Methods for Distributed Optimization under Relaxed Global Geometrymath.OC
Quantized Stochastic Primal-Dual Methods for Distributed Optimization
problem Distributed optimization with stochastic gradients and finite-bit communication
method q-PDGD, a quantized stochastic primal-dual method
result Linear contraction to an explicit neighborhood under RSI, O(1/k) convergence under PL inequality