arXiv research

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…

Let $z=(x,y)$ be coordinates for the product space $\mathbb{R}^{m_1}\times \mathbb{R}^{m_2}$. Let $f:\mathbb{R}^{m_1}\times \mathbb{R}^{m_2}\rightarrow \mathbb{R}$ be a $C^1$ function, and $\nabla f=(\partial _xf,\partial _yf)$ its gradient. Fix $0<α<1$. For a point $(x,y) \in \mathbb{R}^{m_1}\times \mathbb{R}^{m_2}$, …

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.

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 $l_{q}$ norms, where $1\leq q \leq 2$. A portfolio which weights are regularised by such norms is called a sparse portfolio (Brodie et …

New DP-CD method outperforms DP-SGD in solving composite DP-ERM problems.

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…

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.

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.

PROBE algorithm efficiently solves sparse high-dimensional linear regression.

Paper tackles Byzantine attacks in Federated Learning by clustering and robustifying.

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 $\ell_1$-penalized estimation in the Gaussian framework. Though many of these inverse covariance estimation approaches are demonstrably scala…

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…

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…

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…

New framework improves EM algorithm convergence under log-Sobolev inequality.

AdaGrad outperforms SGD in non-convex optimization problems by a factor of d.

Decentralized learning for GLMs with feature distribution and network connectivity.

A method for constructing tight prediction intervals for multiple numerical outputs.

Study on Metropolis-within-Gibbs schemes for high-dimensional Bayesian models.

New algorithm improves privacy in high-dimensional machine learning models.

FedDuA adapts global learning rate for federated learning.

Conditional Generative Models are now acknowledged an essential tool in Machine Learning. This paper focuses on their control. While many approaches aim at disentangling the data through the coordinate-wise control of their latent representations, another direction is explored in this paper. The proposed CompVAE handle…

Paper explores differential privacy in high-dimensional federated learning, tackling server trustworthiness and estimation.

New federated learning algorithms improve model aggregation robustness.

The paper introduces a new method for feature selection without explicit sparsification.

Extends PD-NJ-ODE to noisy observations and dependent observation times.

This paper introduces a new method to compare collections of 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…

Study on convergence of graph neural networks on random graphs.

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.

Differentially private random block coordinate descent improves utility in machine learning.

Estimates hybrid dynamical systems with polynomial expansions and Markovian switching.

Generative AutoEncoders require a chosen probability distribution in latent space, usually multivariate Gaussian. The original Variational AutoEncoder (VAE) uses randomness in encoder - causing problematic distortion, and overlaps in latent space for distinct inputs. It turned out unnecessary: we can instead use determ…

To a tropical $p$-cycle $V_{\mathbb{T}}$ in $\mathbb{R}^n$, we naturally associate a normal closed and $(p,p)$-dimensional current on $(\mathbb{C}^*)^n$ denoted by $\mathscr{T}_n^p(V_{\mathbb{T}})$. Such a "tropical current" $\mathscr{T}_n^p(V_{\mathbb{T}})$ will not be an integration current along any analytic set, si…

We solve continuous-time latent SDE identifiability using diffusion shifts.

A simple log-transform fixes heavy-tailed data for generative models.

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…

The paper analyzes high-dimensional linear regression using parametric empirical Bayes methods.

New algorithm optimizes Bayesian network learning from Gaussian data.

A new method for streaming PCA provides confidence intervals for eigenvector entries.

Study community detection in multi-view data with various types of information.