Tianbao Yang

A Data Efficient and Feasible Level Set Method for Stochastic Convex Optimization with Expectation Constraints

  • Qihang Lin
  • Selvaprabu Nadarajah
  • Negar Soheili
  • Tianbao Yang
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    Stochastic convex optimization problems with expectation constraints (SOECs) are encountered in statistics and machine learning, business, and engineering. In data-rich environments, the SOEC objective and constraints contain expectations defined with respect to large datasets. Therefore, efficient algorithms for solving such SOECs need to limit the fraction of data points that they use, which we refer … Read more

    Adaptive Accelerated Gradient Converging Methods under Holderian Error Bound Condition

  • Liu Mingrui
  • Tianbao Yang
    • Categories Convex Optimization

    In this paper, we focus our study on the convergence of (proximal) gradient methods and accelerated (proximal) gradient methods for smooth (composite) optimization under a H\”{o}lderian error bound (HEB) condition. We first show that proximal gradient (PG) method is automatically adaptive to HEB while accelerated proximal gradient (APG) method can be adaptive to HEB by … Read more

    Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/epsilon)

  • Qihang Lin
  • Yi Xu
  • Yan Yan
  • Tianbao Yang
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Nonsmooth Optimization

    In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving … Read more

    RSG: Beating Subgradient Method without Smoothness and Strong Convexity

  • Qihang Lin
  • Tianbao Yang
    • Categories Convex and Nonsmooth Optimization Tags , , ,

    In this paper, we study the efficiency of a {\bf R}estarted {\bf S}ub{\bf G}radient (RSG) method that periodically restarts the standard subgradient method (SG). We show that, when applied to a broad class of convex optimization problems, RSG method can find an $\epsilon$-optimal solution with a low complexity than SG method. In particular, we first … Read more

    Distributed Stochastic Variance Reduced Gradient Methods and a Lower Bound for Communication Complexity

  • Jason D. Lee
  • Qihang Lin
  • Tengyu Ma
  • Tianbao Yang
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization

    We study distributed optimization algorithms for minimizing the average of convex functions. The applications include empirical risk minimization problems in statistical machine learning where the datasets are large and have to be stored on different machines. We design a distributed stochastic variance reduced gradient algorithm that, under certain conditions on the condition number, simultaneously achieves … Read more