We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods a…
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,742 papers · 148 categories
Trend · papers per month
48 results for “coordinate-wise complexity”
Proposes a new Armijo's condition for coordinate-wise functions.
problem Finding optimal step sizes in coordinate-wise optimization.
method Introduces a new Armijo's condition for functions defined on product spaces.
result Shows the advantage of the new condition over the standard Armijo's condition.
New bound on Rademacher complexity for vector functions.
problem Bounding Rademacher complexity for vector-valued functions.
method Bounding Rademacher complexity by coordinate-wise complexity with a factor of sqrt(K).
result Rademacher complexity is bounded by the maximum coordinate-wise complexity times sqrt(K).
In this work, we consider the resilience of distributed algorithms based on stochastic gradient descent (SGD) in distributed learning with potentially Byzantine attackers, who could send arbitrary information to the parameter server to disrupt the training process. Toward this end, we propose a new Lipschitz-inspired c…
Stochastic methods with coordinate-wise adaptive stepsize (such as RMSprop and Adam) have been widely used in training deep neural networks. Despite their fast convergence, they can generalize worse than stochastic gradient descent. In this paper, by revisiting the design of Adagrad, we propose to split the network par…
Proposes a new Armijo's condition for general functions and provides an algorithm for its application.
problem Finding suitable step sizes for general functions in optimization.
method Introduces a coordinate-wise Armijo's condition and provides an algorithm to find suitable step sizes.
result Proves convergent results for various functions using the proposed algorithm.
In this paper we study the fundamental problems of maximizing a continuous non-monotone submodular function over the hypercube, both with and without coordinate-wise concavity. This family of optimization problems has several applications in machine learning, economics, and communication systems. Our main result is the…
We consider a variant of online convex optimization in which both the instances (input vectors) and the comparator (weight vector) are unconstrained. We exploit a natural scale invariance symmetry in our unconstrained setting: the predictions of the optimal comparator are invariant under any linear transformation of th…
In this short report, we discuss how coordinate-wise descent algorithms can be used to solve minimum variance portfolio (MVP) problems in which the portfolio weights are constrained by norms, where . A portfolio which weights are regularised by such norms is called a sparse portfolio (Brodie et …
Most deep learning-based models for speech enhancement have mainly focused on estimating the magnitude of spectrogram while reusing the phase from noisy speech for reconstruction. This is due to the difficulty of estimating the phase of clean speech. To improve speech enhancement performance, we tackle the phase estima…
New DP-CD method outperforms DP-SGD in solving composite DP-ERM problems.
problem Privacy-preserving machine learning with differential privacy.
method Differentially Private proximal Coordinate Descent (DP-CD) for composite Empirical Risk Minimization (ERM).
result DP-CD outperforms DP-SGD due to larger step sizes and better gradient exploitation.
AdaGrad outperforms SGD in non-convex optimization problems by a factor of d.
problem Finding near-stationary points in stochastic non-convex optimization.
method Refined assumptions on smoothness and gradient noise variance, -norm stationarity measure.
result AdaGrad achieves a convergence rate favorable over SGD in certain non-convex settings.
Nonconvex penalty methods for sparse modeling in linear regression have been a topic of fervent interest in recent years. Herein, we study a family of nonconvex penalty functions that we call the trimmed Lasso and that offers exact control over the desired level of sparsity of estimators. We analyze its structural prop…
Note on subgaussian bounds for sign-quantized linear maps.
problem Understanding subgaussian behavior of sign-quantized linear maps.
method Developed a dimension-independent subgaussian concentration bound for Gaussian vectors under nonlinear mappings.
result Answered a question about sign-quantized linear maps using a new subgaussian bound.
Recently, new defense techniques have been developed to tolerate Byzantine failures for distributed machine learning. The Byzantine model captures workers that behave arbitrarily, including malicious and compromised workers. In this paper, we break two prevailing Byzantine-tolerant techniques. Specifically we show robu…
A new algorithm improves posterior sampling for linear inverse problems.
problem Efficiently sampling from posterior distributions in noisy linear inverse problems.
method Proposes \pddim, a DDIM-type sampler that separately samples along singular directions of the measurement operator.
result The method converges to the Bayesian posterior conditioned on the measurements.
PROBE algorithm efficiently solves sparse high-dimensional linear regression.
problem Sparse high-dimensional linear regression models with complex parameter spaces.
method Partitioned empirical Bayes ECM algorithm for computationally efficient MAP estimation.
result PROBE algorithm provides robust and efficient coordinate-wise optimization.
Paper tackles Byzantine attacks in Federated Learning by clustering and robustifying.
problem Adversarial attacks from Byzantine machines in Federated Learning.
method Iterative Federated Clustering Algorithm (IFCA) with trimmed mean and median aggregation.
result Improved convergence rate for strongly convex loss functions in Byzantine-Robust IFCA.
We design a randomised parallel version of Adaboost based on previous studies on parallel coordinate descent. The algorithm uses the fact that the logarithm of the exponential loss is a function with coordinate-wise Lipschitz continuous gradient, in order to define the step lengths. We provide the proof of convergence …
Sparse high dimensional graphical model selection is a popular topic in contemporary machine learning. To this end, various useful approaches have been proposed in the context of -penalized estimation in the Gaussian framework. Though many of these inverse covariance estimation approaches are demonstrably scala…
This paper analyzes convergence of RMSProp and Adam in non-convex optimization with tight complexity bounds.
problem Analyzing convergence of RMSProp and Adam in non-convex optimization with relaxed assumptions.
method Developed new convergence analyses for RMSProp and Adam, considering adaptive learning rates and affine noise variance.
result RMSProp and Adam converge to ε-stationary points with iteration complexities of O(ε^(-4)) under proper hyperparameters.
Privacy preserving machine learning algorithms are crucial for learning models over user data to protect sensitive information. Motivated by this, differentially private stochastic gradient descent (SGD) algorithms for training machine learning models have been proposed. At each step, these algorithms modify the gradie…
Differentially private random block coordinate descent improves utility in machine learning.
problem Lack of privacy in classical CD methods when handling sensitive information.
method Proposes a differentially private random block coordinate descent method using sketch matrices and importance sampling.
result Demonstrates improved convergence rates and utility guarantees compared to non-private methods.
To a tropical -cycle in , we naturally associate a normal closed and -dimensional current on denoted by . Such a "tropical current" will not be an integration current along any analytic set, si…
In this paper we generalize the framework of the feasible descent method (FDM) to a randomized (R-FDM) and a coordinate-wise random feasible descent method (RC-FDM) framework. We show that the famous SDCA algorithm for optimizing the SVM dual problem, or the stochastic coordinate descent method for the LASSO problem, f…
A simple log-transform fixes heavy-tailed data for generative models.
problem Standard generative models struggle with heavy-tailed data.
method Apply the soft-log transform to data before training and exponentiate samples after generation.
result Log-FM outperforms specialized baselines on multivariate benchmarks.
We present an approach for penalized tensor decomposition (PTD) that estimates smoothly varying latent factors in multi-way data. This generalizes existing work on sparse tensor decomposition and penalized matrix decompositions, in a manner parallel to the generalized lasso for regression and smoothing problems. Our ap…
Fast convergence of the Expectation Maximization algorithm under a logarithmic Sobolev inequalitystat.ML
New framework improves EM algorithm convergence under log-Sobolev inequality.
problem Improving convergence of the EM algorithm.
method Extending gradient flow techniques to EM algorithm, using free energy representation.
result Exponential convergence of EM algorithm under log-Sobolev inequality.
This paper explores the preference-based top- rank aggregation problem. Suppose that a collection of items is repeatedly compared in pairs, and one wishes to recover a consistent ordering that emphasizes the top- ranked items, based on partially revealed preferences. We focus on the Bradley-Terry-Luce (BTL) model…
Proposes MM-DUST for efficient generalized lasso solution paths.
problem Efficiently solve generalized lasso problems in large-scale and non-linear models.
method Majorization-minimization dual stagewise algorithm incorporating quadratic majorizers and stagewise learning.
result Established the uniform convergence of approximated solution paths.
Decentralized learning for GLMs with feature distribution and network connectivity.
problem Optimizing generalized linear models in a decentralized network with feature partitioning.
method Chambolle--Pock primal--dual algorithm applied to an equivalent saddle-point formulation.
result Convergence rates for empirical risk minimization under Lipschitz and square root Lipschitz assumptions.
A method for constructing tight prediction intervals for multiple numerical outputs.
problem Constructing tight prediction intervals for multiple related numerical outputs.
method A novel coordinate-wise standardization procedure that makes residuals comparable across output dimensions, estimating suitable scaling parameters using calibration data.
result The method produces tighter prediction intervals than existing baselines while maintaining valid simultaneous coverage.
Study on Metropolis-within-Gibbs schemes for high-dimensional Bayesian models.
problem Improving the scalability of MCMC methods for complex Bayesian models.
method Relating convergence properties to conditional conductance for non-conjugate hierarchical models.
result Established dimension-free convergence results for Metropolis-within-Gibbs schemes.
A new method for optimizing functions without gradients, improving efficiency and convergence.
problem Optimizing functions without gradient information in machine learning.
method Hybrid Gradient Descent (HGE) using random and coordinate-wise gradient estimates.
result The proposed method achieves optimal convergence rates in convex cases and generalizes to non-convex cases.
New algorithm improves privacy in high-dimensional machine learning models.
problem Privacy issues in learning large machine learning models.
method Differentially private greedy coordinate descent (DP-GCD) algorithm.
result Achieves logarithmic dependence on dimension for quasi-sparse solutions.
FedDuA adapts global learning rate for federated learning.
problem Slow convergence in federated learning due to dataset and parameter space heterogeneity.
method FedDuA uses mirror descent to adaptively select global learning rate based on inter-client and coordinate-wise heterogeneity.
result FedDuA achieves minimax optimal convergence for convex objectives and outperforms baselines in various settings.
Paper explores differential privacy in high-dimensional federated learning, tackling server trustworthiness and estimation.
problem Maintaining privacy in distributed environments with high-dimensional data.
method Investigates scenarios with untrusted and trusted central servers, introduces novel federated estimation algorithms for linear regression models.
result Tight minimax rates depend on high-dimensionality even with sparsity assumptions, and novel algorithms handle slight variations among distributed models.
New federated learning algorithms improve model aggregation robustness.
problem Improving model aggregation in federated learning.
method Complete mathematical convergence analysis and novel aggregation algorithms.
result Derived novel algorithms that modify model architecture based on client contributions.
The paper introduces a new method for feature selection without explicit sparsification.
problem Feature selection with implicit sparsity-inducing mechanisms.
method Optimization over a family of kernels with gradient descent.
result The method achieves exact sparsity without explicit penalization techniques.
Extends PD-NJ-ODE to noisy observations and dependent observation times.
problem Predicting continuous-time stochastic processes with irregular and noisy observations.
method Extends PD-NJ-ODE to handle conditional independence and noisy observations.
result Theoretical guarantees and empirical examples for handling noisy observations and dependent observation times.
This paper introduces a new method to compare collections of distributions on manifolds and graphs.
problem Comparing collections of probability distributions over diverse domains.
method Intrinsic slicing construction for Wasserstein distances, Hilbert embedding, resampling, p-value combination.
result Powerful and well-calibrated p-values for comparing distributions on manifolds and graphs.
Federated learning enables training collaborative machine learning models at scale with many participants whilst preserving the privacy of their datasets. Standard federated learning techniques are vulnerable to Byzantine failures, biased local datasets, and poisoning attacks. In this paper we introduce Adaptive Federa…
Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphsstat.ML
Study on convergence of graph neural networks on random graphs.
problem Convergence of message passing graph neural networks on large random graphs.
method Extended convergence results to a broad class of aggregation functions using McDiarmid inequality.
result Non-asymptotic bounds for convergence quantified with high probability.
High throughput genetic sequencing arrays with thousands of measurements per sample and a great amount of related censored clinical data have increased demanding need for better measurement specific model selection. In this paper we establish strong oracle properties of nonconcave penalized methods for nonpolynomial (N…
Paper tackles distributed linear regression with compositional covariates.
problem Solving distributed statistical methodology and computing for massive compositional data.
method Proposes two distributed optimization techniques based on ADMM and CDMM for solving constrained convex optimization problems.
result Established convergence theories for the proposed algorithms under regularity conditions.
Estimates hybrid dynamical systems with polynomial expansions and Markovian switching.
problem Identifying hybrid dynamical systems with nonlinear autoregressive exogenous (NARX) components and Markovian switching.
method Probabilistic framework using Expectation Maximization for parameter estimation, including submodel coefficients, hidden state values, and transition probabilities. Disentangles mode classification and NARX regression tasks. Uses soft-labels and coordinate descent approach for parameter fitting.
result Demonstrated on a SMNARX problem with three nonlinear sub-models, achieving parsimonious models through l1-norm bridge estimation and hard-thresholding.
Estimates isotonic functions under unknown permutations, achieving optimal statistical and computational efficiency.
problem Estimating isotonic functions with unknown permutations in multiway comparison data.
method Mirsky partition estimator for minimax optimal and adaptive estimation.
result Achieves optimal worst-case statistical performance and computational efficiency.
CompVAE handles multi-ensemble data with compositional generative model.
problem Handling multi-ensemble data with control and generative models.
method Derived from Bayesian variational principles, CompVAE learns a latent representation leveraging observational and symbolic information.
result Supports compositional generative model enabling multi-ensemble operations.