In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Input: Consider Input: Metric learning seeks a transformation of the feature space that enhances prediction quality for the given task at hand. In this work we provide PAC-style sample complexity rates for supervised metric learning. We give matching lowerand upper-bounds showing that the sample complexity scales with the representation dimension when no assumptions are made about the underlying data distribution. However, by leveraging the structure of the data distribution, we show that one can achieve rates that are fine-tuned to a specific notion of intrinsic complexity for a given dataset. Our analysis reveals that augmenting the metric learning optimization criterion with a simple norm-based regularization can help adapt to a dataset’s intrinsic complexity, yielding better generalization. Experiments on benchmark datasets validate our analysis and show that regularizing the metric can help discern the signal even when the data contains high amounts of noise.

Output: Sample Complexity of Learning Mahalanobis Distance Metrics


Input: Consider Input: The alternating direction method of multipliers (ADMM) has been recognized as a versatile approach for solving modern large-scale machine learning and signal processing problems efficiently. When the data size and/or the problem dimension is large, a distributed version of ADMM can be used, which is capable of distributing the computation load and the data set to a network of computing nodes. Unfortunately, a direct synchronous implementation of such algorithm does not scale well with the problem size, as the algorithm speed is limited by the slowest computing nodes. To address this issue, in a companion paper, we have proposed an asynchronous distributed ADMM (AD-ADMM) and studied its worst-case convergence conditions. In this paper, we further the study by characterizing the conditions under which the AD-ADMM achieves linear convergence. Our conditions as well as the resulting linear rates reveal the impact that various algorithm parameters, network delay and network size have on the algorithm performance. To demonstrate the superior time efficiency of the proposed AD-ADMM, we test the ADADMM on a high-performance computer cluster by solving a large-scale logistic regression problem. Keywords− Distributed optimization, ADMM, Asynchronous, Consensus optimization ⋆Tsung-Hui Chang is the corresponding author. Address: School of Science and Engineering, The Chinese University of Hong Kong, Shenzhen, China 518172, E-mail: tsunghui.chang@ieee.org. Wei-Cheng Liao is with Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA, E-mail: mhong@umn.edu Mingyi Hong is with Department of Industrial and Manufacturing Systems Engineering, Iowa State University, Ames, 50011, USA, E-mail: mingyi@iastate.edu Xiangfeng Wang is with Shanghai Key Lab for Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai, 200062, China, E-mail: xfwang@sei.ecnu.edu.cn September 10, 2015 DRAFT

Output: Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance


Input: Consider Input: <lb>We analyze online [6] and mini-batch [20] k-means variants. Both<lb>scale up the widely used Lloyd’s algorithm via stochastic approximation,<lb>and have become popular for large-scale clustering and unsupervised<lb>feature learning. We show, for the first time, that they have global<lb>convergence towards “local optima” at rate<lb>O(1t ) under general condi-<lb>tions. In addition, we show if the dataset is clusterable, with suitable<lb>initialization, mini-batch k-means converges to an optimal k-means<lb>solution at rate<lb>O(1t ) with high probability. The k-means objective is<lb>non-convex and non-differentiable: we exploit ideas from non-convex<lb>gradient-based optimization by providing a novel characterization of the<lb>trajectory of k-means algorithm on its solution space, and circumvent<lb>its non-differentiability via geometric insights about k-means update.


Output: Convergence rate of stochastic k-means