We propose two new alternating direction methods to solve "fully" nonsmooth constrained convex problems. Our algorithms have the best known worst-case iteration-complexity guarantee under mild assumptions for both the objective residual and feasibility gap. Through theoretical analysis, we show how to update all the al…
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,657 papers · 148 categories
Trend · papers per month
48 results for “alternative direction method”
Chandrasekaran, Parrilo and Willsky (2010) proposed a convex optimization problem to characterize graphical model selection in the presence of unobserved variables. This convex optimization problem aims to estimate an inverse covariance matrix that can be decomposed into a sparse matrix minus a low-rank matrix from sam…
In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounters troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. …
In this paper, we consider the problem of minimizing the sum of two convex functions subject to linear linking constraints. The classical alternating direction type methods usually assume that the two convex functions have relatively easy proximal mappings. However, many problems arising from statistics, image processi…
We propose a new stochastic dual coordinate ascent technique that can be applied to a wide range of regularized learning problems. Our method is based on Alternating Direction Multiplier Method (ADMM) to deal with complex regularization functions such as structured regularizations. Although the original ADMM is a batch…
SAG is a scalable method for adversarial attacks on GNNs.
problem Scalability and robustness of GNNs to adversarial attacks.
method Decomposing large graphs into smaller partitions, using ADMM for optimization.
result SAG reduces computation and memory overhead for large graphs.
Paper proposes an algorithm for PARAFAC2-based CMTF models with various constraints.
problem Jointly analyze matrices and tensors with irregular/ragged data.
method Alternating Optimization (AO) and ADMM for fitting PARAFAC2-based CMTF models with various constraints.
result Accurately recovers underlying patterns using various constraints and linear couplings.
In this paper, we study a simple iterative method for finding the Dantzig selector, which was designed for linear regression problems. The method consists of two main stages. The first stage is to approximate the Dantzig selector through a fixed-point formulation of solutions to the Dantzig selector problem. The second…
Alternative proof of coisotropic embedding theorem for pre-symplectic manifolds.
problem Proving the coisotropic embedding theorem for pre-symplectic manifolds.
method Recast geometric choice of connection as algebraic embedding into cotangent bundle, identify symplectic thickening as submanifold of Hamiltonian momenta conjugate to kernel directions.
result Alternative proof of the coisotropic embedding theorem.
This letter presents a new spectral-clustering-based approach to the subspace clustering problem. Underpinning the proposed method is a convex program for optimal direction search, which for each data point d finds an optimal direction in the span of the data that has minimum projection on the other data points and non…
Online optimization has emerged as powerful tool in large scale optimization. In this paper, we introduce efficient online algorithms based on the alternating directions method (ADM). We introduce a new proof technique for ADM in the batch setting, which yields the O(1/T) convergence rate of ADM and forms the basis of …
A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplingscs.LG
Flexible framework for CMTF with ADMM for various constraints and couplings.
problem Challenges in data fusion from multiple sources with varying characteristics.
method Flexible algorithmic framework using AO and ADMM for various constraints, loss functions, and couplings.
result Accurate and computationally efficient results for various loss functions, including KL divergence.
Auto-conditioned primal-dual hybrid gradient method and alternating direction method of multipliersmath.OC
New methods solve saddle point problems without line search.
problem Solving saddle point problems efficiently and adaptively.
method Auto-conditioned primal-dual hybrid gradient (AC-PDHG) and auto-conditioned ADMM (AC-ADMM) methods.
result Methods achieve optimal complexity and convergence guarantees.
We consider classification tasks in the regime of scarce labeled training data in high dimensional feature space, where specific expert knowledge is also available. We propose a new hybrid optimization algorithm that solves the elastic-net support vector machine (SVM) through an alternating direction method of multipli…
TSSM splits neural networks for parallel training with minimal accuracy loss.
problem Accuracy degradation in parallel training of deep neural networks.
method TSSM reformulates alternating minimization to achieve parallelism with minimal accuracy loss.
result TSSM achieves significant speedup without accuracy loss on multiple datasets.
New algorithm solves maximal monotone inclusion problems.
problem Solving maximal monotone inclusion problems.
method Bregman Douglas-Rachford splitting method and variants.
result Convergence of algorithms under certain assumptions.
We revisit the classical Douglas-Rachford (DR) method for finding a zero of the sum of two maximal monotone operators. Since the practical performance of the DR method crucially depends on the stepsizes, we aim at developing an adaptive stepsize rule. To that end, we take a closer look at a linear case of the problem a…
Proposes a multivariate regression model for better analysis of multiple datasets.
problem Insufficient performance of single-dataset analysis in integrative studies.
method Sparse estimation for variable and group selection, alternating direction method of multipliers algorithm.
result Demonstrated improved performance through simulations and real data analysis.
Self-paced learning (SPL) mimics the cognitive process of humans, who generally learn from easy samples to hard ones. One key issue in SPL is the training process required for each instance weight depends on the other samples and thus cannot easily be run in a distributed manner in a large-scale dataset. In this paper,…
Alternating direction method of multipliers for regularized multiclass support vector machinesstat.ML
The support vector machine (SVM) was originally designed for binary classifications. A lot of effort has been put to generalize the binary SVM to multiclass SVM (MSVM) which are more complex problems. Initially, MSVMs were solved by considering their dual formulations which are quadratic programs and can be solved by s…
The mirror descent algorithm (MDA) generalizes gradient descent by using a Bregman divergence to replace squared Euclidean distance. In this paper, we similarly generalize the alternating direction method of multipliers (ADMM) to Bregman ADMM (BADMM), which allows the choice of different Bregman divergences to exploit …
Dimension reduction of multivariate data supervised by auxiliary information is considered. A series of basis for dimension reduction is obtained as minimizers of a novel criterion. The proposed method is akin to continuum regression, and the resulting basis is called continuum directions. With a presence of binary sup…
The flare Package for High Dimensional Linear Regression and Precision Matrix Estimation in Rstat.ML
A new R package for high-dimensional regression and precision matrix estimation.
problem High-dimensional linear regression and precision matrix estimation challenges.
method flare package implements various regression methods and extensions for sparse precision matrix estimation.
result The flare package is efficient and scalable for large problems.
We empirically test predictability on asset price by using stock selection rules based on maximum drawdown and its consecutive recovery. In various equity markets, monthly momentum- and weekly contrarian-style portfolios constructed from these alternative selection criteria are superior not only in forecasting directio…
New method aggregates nodes in sparse graphical models.
problem Estimating edge-sparse graphical models.
method Tree-aggregated graphical lasso (tag-lasso) method.
result Aggregates nodes in a data-driven fashion using a tree.
In the paper, we study the stochastic alternating direction method of multipliers (ADMM) for the nonconvex optimizations, and propose three classes of the nonconvex stochastic ADMM with variance reduction, based on different reduced variance stochastic gradients. Specifically, the first class called the nonconvex stoch…
Unified framework for clustering and learning causal graphs across subjects.
problem Bias and obscured subpopulation-specific dependencies in multivariate systems.
method Directed Acyclic Graph-based Dependency Clustering via Alternating Direction Method of Multipliers (DAG-DC-ADMM) integrated with Structural Equation Modeling (SEM).
result Unified framework recovers cluster-specific causal dependency structures with high true positive rate and low false discovery rate.
Study shows Direct Feedback Alignment fails to offer more efficient scaling than backpropagation.
problem Understanding and optimizing training methods for neural networks.
method Use of scaling laws to compare Direct Feedback Alignment (DFA) and backpropagation.
result DFA fails to offer more efficient scaling than backpropagation.
In this paper, we design and analyze a new zeroth-order online algorithm, namely, the zeroth-order online alternating direction method of multipliers (ZOO-ADMM), which enjoys dual advantages of being gradient-free operation and employing the ADMM to accommodate complex structured regularizers. Compared to the first-ord…
A new kernel test reduces noise in MMD by focusing on leading eigen-directions.
problem Noise in trailing directional components degrades power of standard kernel two-sample tests.
method Truncate MMD spectral decomposition, retaining only leading eigen-directions.
result Our method achieves superior power and robustness, especially in high-dimensional and unbalanced settings.
We consider multi-task learning, which simultaneously learns related prediction tasks, to improve generalization performance. We factorize a coefficient matrix as the product of two matrices based on a low-rank assumption. These matrices have sparsities to simultaneously perform variable selection and learn and overlap…
Develops a method for identifying structured dynamical systems from data.
problem Identifying structured dynamical systems from undersampled and noisy data.
method Sparse least-squares fitting via optimization with the alternating direction method of multipliers.
result The method is stable and successful under certain conditions, as shown by theoretical guarantees and computational results.
The Alternating Direction Method of Multipliers (ADMM) has been studied for years. The traditional ADMM algorithm needs to compute, at each iteration, an (empirical) expected loss function on all training examples, resulting in a computational complexity proportional to the number of training examples. To reduce the ti…
New approach for fair graph clustering using semidefinite relaxation.
problem Ensuring equitable representation in network analysis.
method Semidefinite relaxation approach for NP-hard optimization problem.
result Optimal accuracy-fairness trade-off achieved.
Variational Optimization forms a differentiable upper bound on an objective. We show that approaches such as Natural Evolution Strategies and Gaussian Perturbation, are special cases of Variational Optimization in which the expectations are approximated by Gaussian sampling. These approaches are of particular interest …
Paper proposes a distributed sampling method for Bayesian inference.
problem Privacy and communication constraints in spatially distributed datasets.
method Alternating Direction Method of Multipliers for distributed sampling.
result Algorithm converges to target distribution in Wasserstein distance.
New method for robust PCA with exponential family distributions.
problem Recovering low-rank structure from data matrices with outliers.
method Alternating Direction Method of Multipliers for .
result Demonstrated effectiveness in steel sheet defect detection and crime activity monitoring.
Alternating direction method of multipliers for penalized zero-variance discriminant analysisstat.ML
We consider the task of classification in the high dimensional setting where the number of features of the given data is significantly greater than the number of observations. To accomplish this task, we propose a heuristic, called sparse zero-variance discriminant analysis (SZVD), for simultaneously performing linear …
We consider the problem of minimizing the sum of a smooth function with a bounded Hessian, and a nonsmooth function. We assume that the latter function is a composition of a proper closed function and a surjective linear map , with the proximal mappings of , , simple to compute. This problem i…
RVFL NNs perform well without direct links and output bias for regression.
problem Effect of direct links and output bias on RVFL performance.
method Classical and two new methods for generating hidden nodes' parameters tested.
result Direct links and output bias do not significantly improve RVFL accuracy for typical nonlinear regression problems.
We study the problem of learning a tensor from a set of linear measurements. A prominent methodology for this problem is based on a generalization of trace norm regularization, which has been used extensively for learning low rank matrices, to the tensor setting. In this paper, we highlight some limitations of this app…
We propose directed time series regression, a new approach to estimating parameters of time-series models for use in certainty equivalent model predictive control. The approach combines merits of least squares regression and empirical optimization. Through a computational study involving a stochastic version of a well …
Regularization is a popular technique in machine learning for model estimation and avoiding overfitting. Prior studies have found that modern ordered regularization can be more effective in handling highly correlated, high-dimensional data than traditional regularization. The reason stems from the fact that the ordered…
In this paper, we study the problem of precision matrix estimation when the dataset contains sensitive information. In the differential privacy framework, we develop a differentially private ridge estimator by perturbing the sample covariance matrix. Then we develop a differentially private graphical lasso estimator by…
Penalized Likelihood Methods for Estimation of Sparse High Dimensional Directed Acyclic Graphsstat.ML
Directed acyclic graphs (DAGs) are commonly used to represent causal relationships among random variables in graphical models. Applications of these models arise in the study of physical, as well as biological systems, where directed edges between nodes represent the influence of components of the system on each other.…
Stochastic Alternating Direction Method of Multipliers for Byzantine-Robust Distributed Learningmath.OC
Paper tackles Byzantine attacks in distributed learning with a new ADMM method.
problem Byzantine workers sending arbitrary messages bias distributed learning.
method Byzantine-robust stochastic ADMM exploiting separable problem structure.
result Proposed method converges to optimal solution at O(1/k) rate.
In this paper a simple, effective adaptation of Alternating Direction Implicit (ADI) time discretization schemes is proposed for the numerical pricing of American-style options under the Heston model via a partial differential complementarity problem. The stability and convergence of the new methods are extensively inv…
Improved neural network training with ADMM for hardware compatibility.
problem Training scalable and parallelizable neural networks.
method Alternating Direction Method of Multipliers (ADMM) combined with iterative least-square methods.
result Achieved significant accuracy improvements over SGD and Adam.