Improved clustering algorithm for large datasets.
problem Finding alternative partitions in large datasets.
method Iterative Spectral Method (ISM) for alternative clustering.
result Significantly improved scalability and computation time.
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.
169,051 papers · 148 categories
Trend · papers per month
48 results for “iterative alternating”
New algorithm solves minimax games with linear constraints.
problem Nonconvex minimax games with coupled linear constraints.
method Primal-dual alternating proximal gradient (PDAPG) algorithm.
result Achieves ε-stationary solution within O(ε^(-2)) iterations for strongly concave settings.
AGD converges in polynomial iterations to optimal matrix factorization.
problem Matrix factorization optimization with alternating gradient descent.
method Alternating gradient descent with fixed step size, proving convergence in polynomial iterations.
result AGD reaches ε-optimal factorization in T iterations with high probability.
Derivative-free Alternating Projection Algorithms for General Nonconvex-Concave Minimax Problemsmath.OC
New algorithms solve complex minimax problems without needing derivatives.
problem Solving nonconvex-concave minimax problems efficiently.
method Zeroth-order alternating and proximal gradient algorithms.
result Iteration complexity and function value estimation bounds established.
Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCAstat.ML
Study efficient power iteration for tensor models, proving convergence under specific conditions.
problem Simultaneous alternating power iteration for fixed-order asymmetric rank-one spiked tensor models.
method Finite-iteration local theory, geometrically decaying transient, fixed-order multilinear noise event, warm-start mechanism.
result Convergence to the unique informative local fixed point under specific conditions.
A meta-learning approach improves the performance of alternating minimization for non-convex optimization problems.
problem Optimizing non-convex problems with multiple variables using alternating minimization.
method Meta-learning based alternating minimization (MLAM) to replace handcrafted updating rules.
result The proposed MLAM method outperforms traditional AM-based methods in various non-convex optimization problems.
Efficiently compress neural networks with MUSCO method.
problem Compression of deep neural networks.
method Iterative approach alternating low-rank factorization with rank selection and fine-tuning.
result Improves compression rate while maintaining accuracy.
Efficient algorithm for orthogonal canonical correlation analysis (OCCA).
problem Solving the OCCA problem with orthogonality constraints.
method Sub-maximization problem with self-consistent-field (SCF) iteration for trace-fractional structure and orthogonal linear projections.
result Proposed algorithm converges globally to a KKT point and is more efficient.
We show that quasi-alternating links arise naturally when considering surgery on a strongly invertible L-space knot (that is, a knot that yields an L-space for some Dehn surgery). In particular, we show that for many known classes of L-space knots, every sufficiently large surgery may be realized as the two-fold branch…
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…
Alternating Minimization is a widely used and empirically successful heuristic for matrix completion and related low-rank optimization problems. Theoretical guarantees for Alternating Minimization have been hard to come by and are still poorly understood. This is in part because the heuristic is iterative and non-conve…
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…
AM converges super-linearly for solving mixed linear regression problems.
problem Learning linear regressors from unlabeled observations in multiple linear regression models.
method Alternating Minimization (AM) algorithm, which alternates between label estimation and regression solving.
result AM converges super-linearly in certain parameter regimes, requiring only O(log log(1/ε)) iterations to achieve an error of ε.
ScaledGD improves gradient descent for ill-conditioned low-rank matrix estimation.
problem Efficiently solving ill-conditioned low-rank matrix estimation problems.
method Scaled Gradient Descent (ScaledGD) with adaptive pre-conditioners.
result Linear convergence rate independent of condition number, low per-iteration cost.
Paper proposes algorithms for solving nonconvex-nonconcave problems with complexity guarantees.
problem Nonconvex-nonconcave minimax problems with PL condition.
method Zeroth-order AGDA and VRAGDA algorithms.
result Iteration complexities for obtaining ε-stationary points.
Recently, a novel class of Approximate Policy Iteration (API) algorithms have demonstrated impressive practical performance (e.g., ExIt from [2], AlphaGo-Zero from [27]). This new family of algorithms maintains, and alternately optimizes, two policies: a fast, reactive policy (e.g., a deep neural network) deployed at t…
Standard ChIP-seq peak calling pipelines seek to differentiate biochemically reproducible signals of individual genomic elements from background noise. However, reproducibility alone does not imply functional regulation (e.g., enhancer activation, alternative splicing). Here we present a general-purpose, interpretable …
We investigate an existing distributed algorithm for learning sparse signals or data over networks. The algorithm is iterative and exchanges intermediate estimates of a sparse signal over a network. This learning strategy using exchange of intermediate estimates over the network requires a limited communication overhea…
This paper speeds up iterative GP inference with warm starting.
problem Improving scalability of Gaussian process inference.
method Warm starting sequential posteriors using known solutions.
result Significant speed-ups and improved Bayesian optimisation performance.
Many real world learning tasks involve complex or hard-to-specify objectives, and using an easier-to-specify proxy can lead to poor performance or misaligned behavior. One solution is to have humans provide a training signal by demonstrating or judging performance, but this approach fails if the task is too complicated…
New method speeds up Gaussian process training and inference for large datasets.
problem Training and inference in Gaussian processes are computationally expensive for large datasets.
method Iterative alternating projection method that accesses subblocks of the kernel matrix, reducing time and space complexity.
result Empirically, the method accelerates GP training and inference by up to 72x compared to conjugate gradients.
Exponential distribution is ubiquitous in the framework of multi-agent systems. An alternative approach with an economic motivation to derive the exponential distribution in the framework of iterations in the space of distributions is disclosed.
Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from…
Study dynamics of alternating minimization for bilinear regression under large system limits.
problem Understanding the time evolution of alternating minimization for bilinear regression.
method Replica method applied to a multi-temperature glassy system.
result Dynamics of alternating minimization can be described by a two-dimensional discrete stochastic process.
Approximate dynamic programming algorithms, such as approximate value iteration, have been successfully applied to many complex reinforcement learning tasks, and a better approximate dynamic programming algorithm is expected to further extend the applicability of reinforcement learning to various tasks. In this paper w…
New approach uses hinge loss for iterative regularization in classification.
problem Improving classification accuracy through regularization.
method Develops an iterative regularization approach based on hinge loss.
result Proves convergence and rates of convergence for classification.
Paper presents a new training method for overparametrized neural networks that reduces time per iteration.
problem Scalability issue in training overparametrized neural networks.
method Uses a new view of neural networks as binary search trees, modifying a small subset of nodes per iteration.
result Reduces amortized time per iteration to from previous .
Efficiently compress pretrained models using RSI for improved predictive accuracy.
problem Efficiently compressing large pretrained models for practical deployment.
method Randomized subspace iteration (RSI) for low-rank approximation of pretrained models.
result RSI achieves near-optimal approximation quality and outperforms RSVD in predictive accuracy.
We consider factoring low-rank tensors in the presence of outlying slabs. This problem is important in practice, because data collected in many real-world applications, such as speech, fluorescence, and some social network data, fit this paradigm. Prior work tackles this problem by iteratively selecting a fixed number …
l1 reweighting algorithms are very popular in sparse signal recovery and compressed sensing, since in the practice they have been observed to outperform classical l1 methods. Nevertheless, the theoretical analysis of their convergence is a critical point, and generally is limited to the convergence of the functional to…
The paper analyzes convergence properties of NGA and PAMe for -norm PCA.
problem Finite-step convergence of -norm PCA algorithms.
method Conditional subgradient and alternating maximization interpretations of NGA, and PAMe with extrapolation.
result Iterative points of modified NGA and PAMe remain constant after finitely many steps under certain conditions.
LocalKMeans parallelizes Lloyd's algorithm for distributed data.
problem Efficiently clustering data across multiple machines.
method Parallel local iterations with synchronization every L steps.
result Higher required signal-to-noise ratio due to local steps.
We present and analyze several strategies for improving the performance of stochastic variance-reduced gradient (SVRG) methods. We first show that the convergence rate of these methods can be preserved under a decreasing sequence of errors in the control variate, and use this to derive variants of SVRG that use growing…
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…
This paper proposes an alternating back-propagation algorithm for learning the generator network model. The model is a non-linear generalization of factor analysis. In this model, the mapping from the continuous latent factors to the observed signal is parametrized by a convolutional neural network. The alternating bac…
New algorithms improve convergence of minimax optimization.
problem Minimax optimization convergence issues in nonconvex problems.
method Established new convergence results for two single-loop algorithms.
result Improved convergence rates for minimax optimization.
We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is {\em non-convex…
Multi-Rank Sparse and Functional PCA: Manifold Optimization and Iterative Deflation Techniquesstat.ML
Improved estimation of multiple principal components using manifold optimization and iterative deflation techniques.
problem Estimating multiple principal components efficiently and orthogonally.
method Extended SFPCA using manifold optimization and iterative deflation techniques.
result Alternative deflation schemes improve signal extraction and component estimation.
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. …
Improved ADMM for convex distributed learning with differential privacy.
problem Privacy concerns in distributed learning with sensitive data.
method Approximate multi-step ADMM with calibrated noise.
result Higher utility and error bounds asymptotic to state-of-the-art.
Efficient methods for sparse random projections improve classification accuracy in very high-dimensional data.
problem Handling very high-dimensional sparse data efficiently.
method Non-iterative and iterative classification methods using sparse random projections and Jaccard kernel.
result Non-iterative methods yield larger, more accurate models than iterative methods.
New algorithm improves convergence rates for convex optimization problems.
problem Convex optimization problems with noisy stochastic data.
method Stochastic proximal point algorithm with weak linear regularity condition.
result Achieves $\mathcal{O}\left(\frac{1}{k}
ight)$ convergence rate for SPP.
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…
We study the behavior of the degree of the colored Jones polynomial and the boundary slopes of knots under the operation of cabling. We show that, under certain hypothesis on this degree, if a knot satisfies the Slope Conjecture then a -cable of satisfies the conjecture, provided that is not a Jon…
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.
IHT improves sparse distribution learning.
problem Learning sparse discrete distributions.
method Iterative hard thresholding as a solution, with a greedy approximate projection.
result IHT achieves state of the art results for sparse distribution learning.
ILTS iteratively refines linear regression models on subsets of data.
problem Linear regression with corruptions and outliers.
method Iteratively selects and refits the subset of samples with lowest loss.
result ILTS converges linearly to the closest mixture component under certain conditions.
First-order optimization methods, such as stochastic gradient descent (SGD) and its variants, are widely used in machine learning applications due to their simplicity and low per-iteration costs. However, they often require larger numbers of iterations, with associated communication costs in distributed environments. I…