Browsing by Author "Guzman, Cristobal "

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Complementary composite minimization, small gradients in general norms, and applications
    (2024) Diakonikolas, Jelena; Guzman, Cristobal
    Composite minimization is a powerful framework in large-scale convex optimization, based on decoupling of the objective function into terms with structurally different properties and allowing for more flexible algorithmic design. We introduce a new algorithmic framework for complementary composite minimization, where the objective function decouples into a (weakly) smooth and a uniformly convex term. This particular form of decoupling is pervasive in statistics and machine learning, due to its link to regularization. The main contributions of our work are summarized as follows. First, we introduce the problem of complementary composite minimization in general normed spaces; second, we provide a unified accelerated algorithmic framework to address broad classes of complementary composite minimization problems; and third, we prove that the algorithms resulting from our framework are near-optimal in most of the standard optimization settings. Additionally, we show that our algorithmic framework can be used to address the problem of making the gradients small in general normed spaces. As a concrete example, we obtain a nearly-optimal method for the standard l(1) (small gradients in the l(infinity) norm), essentially matching the bound of Nesterov (Optima Math Optim Soc Newsl 88:10-11, 2012) that was previously known only for the Euclidean setup. Finally, we show that our composite methods are broadly applicable to a number of regression and other classes of optimization problems, where regularization plays a key role. Our methods lead to complexity bounds that are either new or match the best existing ones.
  • Thumbnail Image
    Item
    Optimal Affine-Invariant Smooth Minimization Algorithms
    (2018) D'Aspremont, Alexandre ; Guzman, Cristobal ; Jaggi, Martin
  • No Thumbnail Available
    Item
    OPTIMAL ALGORITHMS FOR STOCHASTIC COMPLEMENTARY COMPOSITE MINIMIZATION
    (2024) D'aspremont, Alexandre; Guzman, Cristobal; Lezane, Clement
    Inspired by regularization techniques in statistics and machine learning, we study complementary composite minimization in the stochastic setting. This problem corresponds to the minimization of the sum of a (weakly) smooth function endowed with a stochastic first -order oracle and a structured uniformly convex (possibly nonsmooth and non -Lipschitz) regularization term. Despite intensive work on closely related settings, prior to our work no complexity bounds for this problem were known. We close this gap by providing novel excess risk bounds, both in expectation and with high probability. Our algorithms are nearly optimal, which we prove via novel lower complexity bounds for this class of problems. We conclude by providing numerical results comparing our methods to the state of the art.
  • Thumbnail Image
    Item
    Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization
    (INFORMS, 2021) Feldman, Vitaly; Guzman, Cristobal; Vempala, Santosh
    Stochastic convex optimization, by which the objective is the expectation of a random convex function, is an important and widely used method with numerous applications in machine learning, statistics, operations research, and other areas. We study the complexity of stochastic convex optimization given only statistical query (SQ) access to the objective function. We show that well-known and popular first-order iterative methods can be implemented using only statistical queries. For many cases of interest, we derive nearly matching upper and lower bounds on the estimation (sample) complexity, including linear optimization in the most general setting. We then present several consequences for machine learning, differential privacy, and proving concrete lower bounds on the power of convex optimization-based methods. The key ingredient of our work is SQ algorithms and lower bounds for estimating the mean vector of a distribution over vectors supported on a convex body in R d . This natural problem has not been previously studied, and we show that our solutions can be used to get substantially improved SQ versions of Perception and other online algorithms for learning halfspaces.