Sahand Negahban

Fast global convergence of gradient methods for high-dimensional statistical recovery

  • Alekh Agarwal
  • Martin J Wainwright
  • Sahand Negahban
    • Categories Convex Optimization, Statistics Tags , ,

    Many statistical $M$-estimators are based on convex optimization problems formed by the combination of a data-dependent loss function with a norm-based regularizer. We analyze the convergence rates of projected gradient and composite gradient methods for solving such problems, working within a high-dimensional framework that allows the data dimension $\pdim$ to grow with (and possibly exceed) … Read more

    Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions

  • Alekh Agarwal
  • Martin J Wainwright
  • Sahand Negahban
    • Categories Convex Optimization, Stochastic Programming Tags , ,

    We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding an $\order(\pdim/T)$ convergence rate for strongly convex objectives in $\pdim$ dimensions, and an $\order(\sqrt{(\spindex \log \pdim)/T})$ convergence rate when … Read more