Decentralized Feature-Distributed Optimization for Generalized Linear
Models
- URL: http://arxiv.org/abs/2110.15283v1
- Date: Thu, 28 Oct 2021 16:42:47 GMT
- Title: Decentralized Feature-Distributed Optimization for Generalized Linear
Models
- Authors: Brighton Ancelin, Sohail Bahmani, Justin Romberg
- Abstract summary: We consider the "all-for-one" decentralized learning problem for generalized linear models.
The features of each sample are partitioned among several collaborating agents in a connected network, but only one agent observes the response variables.
We apply the Chambolle--Pock primal--dual algorithm to an equivalent saddle-point formulation of the problem.
- Score: 19.800898945436384
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the "all-for-one" decentralized learning problem for generalized
linear models. The features of each sample are partitioned among several
collaborating agents in a connected network, but only one agent observes the
response variables. To solve the regularized empirical risk minimization in
this distributed setting, we apply the Chambolle--Pock primal--dual algorithm
to an equivalent saddle-point formulation of the problem. The primal and dual
iterations are either in closed-form or reduce to coordinate-wise minimization
of scalar convex functions. We establish convergence rates for the empirical
risk minimization under two different assumptions on the loss function
(Lipschitz and square root Lipschitz), and show how they depend on the
characteristics of the design matrix and the Laplacian of the network.
Related papers
- A Convex Relaxation Approach to Generalization Analysis for Parallel Positively Homogeneous Networks [35.85188662524247]
A class of neural networks whose input-output map is the sum of homogeneous maps are studied.
We propose a general framework for linear bounds for such networks.
arXiv Detail & Related papers (2024-11-05T03:24:34Z) - Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems.
We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
arXiv Detail & Related papers (2024-10-22T10:19:27Z) - A Unified Analysis of Multi-task Functional Linear Regression Models
with Manifold Constraint and Composite Quadratic Penalty [0.0]
The power of multi-task learning is brought in by imposing additional structures over the slope functions.
We show the composite penalty induces a specific norm, which helps to quantify the manifold curvature.
A unified convergence upper bound is obtained and specifically applied to the reduced-rank model and the graph Laplacian regularized model.
arXiv Detail & Related papers (2022-11-09T13:32:23Z) - Sparsest Univariate Learning Models Under Lipschitz Constraint [31.28451181040038]
We propose continuous-domain formulations for one-dimensional regression problems.
We control the Lipschitz constant explicitly using a user-defined upper-bound.
We show that both problems admit global minimizers that are continuous and piecewise-linear.
arXiv Detail & Related papers (2021-12-27T07:03:43Z) - Parallel Stochastic Mirror Descent for MDPs [72.75921150912556]
We consider the problem of learning the optimal policy for infinite-horizon Markov decision processes (MDPs)
Some variant of Mirror Descent is proposed for convex programming problems with Lipschitz-continuous functionals.
We analyze this algorithm in a general case and obtain an estimate of the convergence rate that does not accumulate errors during the operation of the method.
arXiv Detail & Related papers (2021-02-27T19:28:39Z) - Understanding Implicit Regularization in Over-Parameterized Single Index
Model [55.41685740015095]
We design regularization-free algorithms for the high-dimensional single index model.
We provide theoretical guarantees for the induced implicit regularization phenomenon.
arXiv Detail & Related papers (2020-07-16T13:27:47Z) - Model Fusion with Kullback--Leibler Divergence [58.20269014662046]
We propose a method to fuse posterior distributions learned from heterogeneous datasets.
Our algorithm relies on a mean field assumption for both the fused model and the individual dataset posteriors.
arXiv Detail & Related papers (2020-07-13T03:27:45Z) - A Multi-Agent Primal-Dual Strategy for Composite Optimization over
Distributed Features [52.856801164425086]
We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
arXiv Detail & Related papers (2020-06-15T19:40:24Z) - Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
We develop a convex analytic approach to analyze finite width two-layer ReLU networks.
We show that an optimal solution to the regularized training problem can be characterized as extreme points of a convex set.
In higher dimensions, we show that the training problem can be cast as a finite dimensional convex problem with infinitely many constraints.
arXiv Detail & Related papers (2020-02-25T23:05:33Z) - Generalisation error in learning with random features and the hidden
manifold model [23.71637173968353]
We study generalised linear regression and classification for a synthetically generated dataset.
We consider the high-dimensional regime and using the replica method from statistical physics.
We show how to obtain the so-called double descent behaviour for logistic regression with a peak at the threshold.
We discuss the role played by correlations in the data generated by the hidden manifold model.
arXiv Detail & Related papers (2020-02-21T14:49:41Z) - Solving high-dimensional eigenvalue problems using deep neural networks:
A diffusion Monte Carlo like approach [14.558626910178127]
The eigenvalue problem is reformulated as a fixed point problem of the semigroup flow induced by the operator.
The method shares a similar spirit with diffusion Monte Carlo but augments a direct approximation to the eigenfunction through neural-network ansatz.
Our approach is able to provide accurate eigenvalue and eigenfunction approximations in several numerical examples.
arXiv Detail & Related papers (2020-02-07T03:08:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.