The Experts below are selected from a list of 113157 Experts worldwide ranked by ideXlab platform

Angelia Nedic - One of the best experts on this subject based on the ideXlab platform.

  • on projected stochastic gradient descent algorithm with weighted averaging for least squares regression
    IEEE Transactions on Automatic Control, 2017
    Co-Authors: Kobi Cohen, Angelia Nedic, R Srikant
    Abstract:

    The problem of least squares regression of a $d$ -dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded Constraint Set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit $O(1/k)$ upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the Constraint Set. We show that the variance term dominates the error and decreases with rate $1/k$ , while the term that is related to the size of the Constraint Set decreases with rate $\log k/k^2$ . We then compare the asymptotic ratio $\rho$ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that $\rho \leq 4$ for all $d\geq 1$ when the random entries of the sensing vector are uncorrelated and identically distributed. We further improve the upper bound by showing that $\rho \leq 4/3$ for the case of $d=1$ and unbounded parameter Set when the random sensing entries are equal across time. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with $\rho \leq 4/3$ even for large $d$ in practice.

  • on projected stochastic gradient descent algorithm with weighted averaging for least squares regression
    arXiv: Information Theory, 2016
    Co-Authors: Kobi Cohen, Angelia Nedic, R Srikant
    Abstract:

    The problem of least squares regression of a $d$-dimensional unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded Constraint Set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit $O(1/k)$ upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the Constraint Set. We show that the variance term dominates the error and decreases with rate $1/k$, while the term which is related to the size of the Constraint Set decreases with rate $\log k/k^2$. We then compare the asymptotic ratio $\rho$ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that $\rho\leq 4$ under some mild conditions for all $d\geq 1$. We further improve the upper bound by showing that $\rho\leq 4/3$ for the case of $d=1$ and unbounded parameter Set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with $\rho\leq 4/3$ even for large $d$ in practice.

  • on projected stochastic gradient descent algorithm with weighted averaging for least squares regression
    International Conference on Acoustics Speech and Signal Processing, 2016
    Co-Authors: Kobi Cohen, Angelia Nedic, R Srikant
    Abstract:

    The problem of least squares regression of a ridimensionai unknown parameter is considered. A stochastic gradient descent based algorithm with weighted iterate-averaging that uses a single pass over the data is studied and its convergence rate is analyzed. We first consider a bounded Constraint Set of the unknown parameter. Under some standard regularity assumptions, we provide an explicit O(1/k) upper bound on the convergence rate, depending on the variance (due to the additive noise in the measurements) and the size of the Constraint Set. We show that the variance term dominates the error and decreases with rate 1 /k, while the Constraint Set term decreases with rate log k/k2. We then compare the asymptotic ratio ρ between the convergence rate of the proposed scheme and the empirical risk minimizer (ERM) as the number of iterations approaches infinity. We show that ρ 1. We further improve the upper bound by showing that ρ < 4/3 for the case of d =1 and unbounded parameter Set. Simulation results demonstrate strong performance of the algorithm as compared to existing methods, and coincide with ρ < 4/3 even for large d in practice.

  • distributed random projection algorithm for convex optimization
    IEEE Journal of Selected Topics in Signal Processing, 2013
    Co-Authors: Soomin Lee, Angelia Nedic
    Abstract:

    Random projection algorithm is of interest for constrained optimization when the Constraint Set is not known in advance or the projection operation on the whole Constraint Set is computationally prohibitive. This paper presents a distributed random projection algorithm for constrained convex optimization problems that can be used by multiple agents connected over a time-varying network, where each agent has its own objective function and its own constrained Set. We prove that the iterates of all agents converge to the same point in the optimal Set almost surely. Experiments on distributed support vector machines demonstrate good performance of the algorithm.

  • a new class of distributed optimization algorithms application to regression of distributed data
    Optimization Methods & Software, 2012
    Co-Authors: Sundhar S Ram, Angelia Nedic, Venugopal V Veeravalli
    Abstract:

    In a distributed optimization problem, the complete problem information is not available at a single location but is rather distributed among different agents in a multi-agent system. In the problems studied in the literature, each agent has an objective function and the network goal is to minimize the sum of the agents’ objective functions over a Constraint Set that is globally known. In this paper, we study a generalization of the above distributed optimization problem. In particular, the network objective is to minimize a function of the sum of the individual objective functions over the Constraint Set. The ‘outer’ function and the Constraint Set are known to all the agents. We discuss an algorithm and prove its convergence, and then discuss extensions to more general and complex distributed optimization problems. We provide a motivation for our algorithms through the example of distributed regression of distributed data.

B De Moor - One of the best experts on this subject based on the ideXlab platform.

Mayuresh V. Kothare - One of the best experts on this subject based on the ideXlab platform.

  • comments on efficient robust constrained model predictive control with a time varying terminal Constraint Set by wan and kothare
    Systems & Control Letters, 2006
    Co-Authors: Z Wan, Mayuresh V. Kothare, Bert Pluymers, B De Moor
    Abstract:

    Abstract We present an algorithm that modifies the original formulation proposed in Wan and Kothare [Efficient robust constrained model predictive control with a time-varying terminal Constraint Set, Systems Control Lett. 48 (2003) 375–383]. The modified algorithm can be proved to be robustly stabilizing and preserves all the advantages of the original algorithm, thereby overcoming the limitation pointed out recently by Pluymers et al. [Min–max feedback MPC using a time-varying terminal Constraint Set and comments on “Efficient robust constrained model predictive control with a time-varying terminal Constraint Set”, Systems Control Lett. 54 (2005) 1143–1148].

  • efficient robust constrained model predictive control with a time varying terminal Constraint Set
    Systems & Control Letters, 2003
    Co-Authors: Mayuresh V. Kothare
    Abstract:

    Abstract An efficient robust constrained model predictive control algorithm with a time varying terminal Constraint Set is developed for systems with model uncertainty and input Constraints. The approach is novel in that it off-line constructs a continuum of terminal Constraint Sets and on-line achieves robust stability by using a relatively short control horizon (even N =0) with a time varying terminal Constraint Set. This algorithm not only dramatically reduces the on-line computation but also significantly enlarges the size of the allowable Set of initial conditions. Moreover, this control scheme retains the unconstrained optimal performance in the neighborhood of the equilibrium. The controller design is illustrated through a benchmark problem.

Bert Pluymers - One of the best experts on this subject based on the ideXlab platform.

Venugopal V Veeravalli - One of the best experts on this subject based on the ideXlab platform.

  • a new class of distributed optimization algorithms application to regression of distributed data
    Optimization Methods & Software, 2012
    Co-Authors: Sundhar S Ram, Angelia Nedic, Venugopal V Veeravalli
    Abstract:

    In a distributed optimization problem, the complete problem information is not available at a single location but is rather distributed among different agents in a multi-agent system. In the problems studied in the literature, each agent has an objective function and the network goal is to minimize the sum of the agents’ objective functions over a Constraint Set that is globally known. In this paper, we study a generalization of the above distributed optimization problem. In particular, the network objective is to minimize a function of the sum of the individual objective functions over the Constraint Set. The ‘outer’ function and the Constraint Set are known to all the agents. We discuss an algorithm and prove its convergence, and then discuss extensions to more general and complex distributed optimization problems. We provide a motivation for our algorithms through the example of distributed regression of distributed data.

  • distributed stochastic subgradient projection algorithms for convex optimization
    Journal of Optimization Theory and Applications, 2010
    Co-Authors: Sundhar S Ram, Angelia Nedic, Venugopal V Veeravalli
    Abstract:

    We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex Constraint Set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the Constraint Set.

  • distributed subgradient projection algorithm for convex optimization
    International Conference on Acoustics Speech and Signal Processing, 2009
    Co-Authors: Sundhar S Ram, Angelia Nedic, Venugopal V Veeravalli
    Abstract:

    We consider constrained minimization of a sum of convex functions over a convex and compact Set, when each component function is known only to a specific agent in a time-varying peer to peer network. We study an iterative optimization algorithm in which each agent obtains a weighted average of its own iterate with the iterates of its neighbors, updates the average using the subgradient of its local function and then projects onto the Constraint Set to generate the new iterate. We obtain error bounds on the limit of the function value when a constant stepsize is used.

  • distributed stochastic subgradient projection algorithms for convex optimization
    arXiv: Optimization and Control, 2008
    Co-Authors: Sundhar S Ram, Angelia Nedich, Venugopal V Veeravalli
    Abstract:

    We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex Constraint Set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the Constraint Set. The goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.