• ### Joint Active Learning with Feature Selection via CUR Matrix Decomposition(1503.01239)

Sept. 9, 2018 cs.LG
This paper presents an unsupervised learning approach for simultaneous sample and feature selection, which is in contrast to existing works which mainly tackle these two problems separately. In fact the two tasks are often interleaved with each other: noisy and high-dimensional features will bring adverse effect on sample selection, while informative or representative samples will be beneficial to feature selection. Specifically, we propose a framework to jointly conduct active learning and feature selection based on the CUR matrix decomposition. From the data reconstruction perspective, both the selected samples and features can best approximate the original dataset respectively, such that the selected samples characterized by the features are highly representative. In particular, our method runs in one-shot without the procedure of iterative sample selection for progressive labeling. Thus, our model is especially suitable when there are few labeled samples or even in the absence of supervision, which is a particular challenge for existing methods. As the joint learning problem is NP-hard, the proposed formulation involves a convex but non-smooth optimization problem. We solve it efficiently by an iterative algorithm, and prove its global convergence. Experimental results on publicly available datasets corroborate the efficacy of our method compared with the state-of-the-art.
• ### Deep Extreme Multi-label Learning(1704.03718)

June 8, 2018 cs.LG
Extreme multi-label learning (XML) or classification has been a practical and important problem since the boom of big data. The main challenge lies in the exponential label space which involves $2^L$ possible label sets especially when the label dimension $L$ is huge, e.g., in millions for Wikipedia labels. This paper is motivated to better explore the label space by originally establishing an explicit label graph. In the meanwhile, deep learning has been widely studied and used in various classification problems including multi-label classification, however it has not been properly introduced to XML, where the label space can be as large as in millions. In this paper, we propose a practical deep embedding method for extreme multi-label classification, which harvests the ideas of non-linear embedding and graph priors-based label space modeling simultaneously. Extensive experiments on public datasets for XML show that our method performs competitive against state-of-the-art result.
• ### A Fast Proximal Point Method for Wasserstein Distance(1802.04307)

Feb. 12, 2018 cs.LG, stat.ML
Wasserstein distance plays increasingly important roles in machine learning, stochastic programming and image processing. Major efforts have been under way to address its high computational complexity, some leading to approximate or regularized variations such as Sinkhorn distance. However, as we will demonstrate, several important machine learning applications call for the computation of exact Wasserstein distance, and regularized variations with small regularization parameter will fail due to numerical stability issues or degradate the performance. We address this challenge by developing an Inexact Proximal point method for Optimal Transport (IPOT) with the proximal operator approximately evaluated at each iteration using projections to the probability simplex. We also simplify the architecture for learning generative models based on optimal transport solution, and generalize the idea of IPOT to a new method for computing Wasserstein barycenter. We provide convergence analysis of IPOT and experiments showing our new methods outperform the state-of-the-art methods in terms of both effectiveness and efficiency.
• ### Observation of the superconducting proximity effect in the surface state of SmB6 thin films(1604.07455)

The proximity effect at the interface between a topological insulator (TI) and a superconductor is predicted to give rise to chiral topological superconductivity and Majorana fermion excitations. In most TIs studied to date, however, the conducting bulk states have overwhelmed the transport properties and precluded the investigation of the interplay of the topological surface state and Cooper pairs. Here, we demonstrate the superconducting proximity effect in the surface state of SmB6 thin films which display bulk insulation at low temperatures. The Fermi velocity in the surface state deduced from the proximity effect is found to be as large as 10^5 m/s, in good agreement with the value obtained from a separate transport measurement. We show that high transparency between the TI and a superconductor is crucial for the proximity effect. The finding here opens the door to investigation of exotic quantum phenomena using all-thin-film multilayers with high-transparency interfaces.
• ### Asynchronous Distributed ADMM for Large-Scale Optimization- Part I: Algorithm and Convergence Analysis(1509.02597)

Feb. 19, 2016 cs.DC, cs.LG, cs.SY
• ### A Scalable Frank-Wolfe based Augmented Lagrangian Method for Linearly Constrained Composite Convex Programming(1507.07624)

Oct. 12, 2015 math.OC
In this paper, we consider large-scale linearly constrained composite convex optimization problem, whose objective is a sum of a smooth function and a possibly nonsmooth function. We propose a scalable \textbf{F}rank-\textbf{W}olfe based \textbf{A}ugmented \textbf{L}agrangian (FW-AL) method for solving this problem. At each iteration, the proposed FW-AL method employs the FW method (or its variants) to approximately solve the AL subproblem {(with fixed Lagrange multiplier)} within a preselected tolerance and then updates the Lagrange multiplier. The proposed FW-AL method is well suitable for solving large-scale problems, because its computational cost per step scales (essentially) linearly with the size of the input. We analyze the non-ergodic convergence rate of the proposed FW-AL method.
• ### One-dimensional edge state transport in a topological Kondo insulator(1312.6132)

Topological insulators, with metallic boundary states protected against time-reversal-invariant perturbations, are a promising avenue for realizing exotic quantum states of matter including various excitations of collective modes predicted in particle physics, such as Majorana fermions and axions. According to theoretical predictions, a topological insulating state can emerge from not only a weakly interacting system with strong spin-orbit coupling, but also in insulators driven by strong electron correlations. The Kondo insulator compound SmB6 is an ideal candidate for realizing this exotic state of matter, with hybridization between itinerant conduction electrons and localized $f$-electrons driving an insulating gap and metallic surface states at low temperatures. Here we exploit the existence of surface ferromagnetism in SmB6 to investigate the topological nature of metallic surface states by studying magnetotransport properties at very low temperatures. We find evidence of one-dimensional surface transport with a quantized conductance value of $e^2/h$ originating from the chiral edge channels of ferromagnetic domain walls, providing strong evidence that topologically non-trivial surface states exist in SmB6.
• ### Asynchronous Distributed ADMM for Large-Scale Optimization- Part II: Linear Convergence Analysis and Numerical Performance(1509.02604)

Sept. 9, 2015 cs.DC, cs.LG, cs.SY
• ### Dynamic Structure Embedded Online Multiple-Output Regression for Stream Data(1412.5732)

Sept. 8, 2015 cs.LG
Online multiple-output regression is an important machine learning technique for modeling, predicting, and compressing multi-dimensional correlated data streams. In this paper, we propose a novel online multiple-output regression method, called MORES, for stream data. MORES can \emph{dynamically} learn the structure of the coefficients change in each update step to facilitate the model's continuous refinement. We observe that limited expressive ability of the regression model, especially in the preliminary stage of online update, often leads to the variables in the residual errors being dependent. In light of this point, MORES intends to \emph{dynamically} learn and leverage the structure of the residual errors to improve the prediction accuracy. Moreover, we define three statistical variables to \emph{exactly} represent all the seen samples for \emph{incrementally} calculating prediction loss in each online update round, which can avoid loading all the training data into memory for updating model, and also effectively prevent drastic fluctuation of the model in the presence of noise. Furthermore, we introduce a forgetting factor to set different weights on samples so as to track the data streams' evolving characteristics quickly from the latest samples. Experiments on one synthetic dataset and three real-world datasets validate the effectiveness of the proposed method. In addition, the update speed of MORES is at least 2000 samples processed per second on the three real-world datasets, more than 15 times faster than the state-of-the-art online learning algorithm.
• ### Joint Power Splitting and Secure Beamforming Design in the Multiple Non-regenerative Wireless-powered Relay Networks(1507.01774)

July 7, 2015 cs.IT, math.IT
The physical-layer security issue in the multiple non-regenerative wireless-powered relay (WPR) networks is investigated in this letter, where the idle relay is treated as a potential eavesdropper. To guarantee secure communication, the destination-based artificial noise is sent to degrade the receptions of eavesdroppers, and it also becomes a new source of energy powering relays to forward the information with power splitting (PS) technique. We propose an efficient algorithm ground on block-wise penalty function method to jointly optimize PS ratio and beamforming to maximize the secrecy rate. Despite the nonconvexity of the considered problem, the proposed algorithm is numerically efficient and is proved to converge to the local optimal solution. Simulation results demonstrate that the proposed algorithm outperforms the benchmark method.
• ### Topological $R$PdBi half-Heusler semimetals: a new family of non-centrosymmetric magnetic superconductors(1501.04096)

June 8, 2015 cond-mat.supr-con
We report superconductivity and magnetism in a new family of topological semimetals, the ternary half Heusler compounds $R$PdBi ($R$ : rare earth). In this series, tuning of the rare earth $f$-electron component allows for simultaneous control of both lattice density via lanthanide contraction, as well as the strength of magnetic interaction via de Gennes scaling, allowing for a unique tuning of both the normal state band inversion strength, superconducting pairing and magnetically ordered ground states. Antiferromagnetism with ordering vector (0.5,0.5,0.5) occurs below a Ne\'eel temperature that scales with de Gennes factor $dG$, while a superconducting transition is simultaneously linearly suppressed. With superconductivity appearing in a system with non-centrosymmetric crystallographic symmetry, the possibility of spin-triplet Cooper pairing with non-trivial topology analogous to that predicted for the normal state electronic structure provides a unique and rich opportunity to realize both predicted and new exotic excitations in topological materials.
• ### Iteration Complexity Analysis of Block Coordinate Descent Methods(1310.6957)

April 28, 2015 stat.ME, math.OC
In this paper, we provide a unified iteration complexity analysis for a family of general block coordinate descent (BCD) methods, covering popular methods such as the block coordinate gradient descent (BCGD) and the block coordinate proximal gradient (BCPG), under various different coordinate update rules. We unify these algorithms under the so-called Block Successive Upper-bound Minimization (BSUM) framework, and show that for a broad class of multi-block nonsmooth convex problems, all algorithms covered by the BSUM framework achieve a global sublinear iteration complexity of $O(1/r)$, where r is the iteration index. Moreover, for the case of block coordinate minimization (BCM) where each block is minimized exactly, we establish the sublinear convergence rate of $O(1/r)$ without per block strong convexity assumption. Further, we show that when there are only two blocks of variables, a special BSUM algorithm with Gauss-Seidel rule can be accelerated to achieve an improved rate of $O(1/r^2)$.
• ### Joint Power Splitting and Secure Beamforming Design in the Wireless-powered Untrusted Relay Networks(1504.00770)

April 3, 2015 cs.IT, math.IT
In this work, we maximize the secrecy rate of the wireless-powered untrusted relay network by jointly designing power splitting (PS) ratio and relay beamforming with the proposed global optimal algorithm (GOA) and local optimal algorithm (LOA). Different from the literature, artificial noise (AN) sent by the destination not only degrades the channel condition of the eavesdropper to improve the secrecy rate, but also becomes a new source of energy powering the untrusted relay based on PS. Hence, it is of high economic benefits and efficiency to take advantage of AN compared with the literature. Simulation results show that LOA can achieve satisfactory secrecy rate performance compared with that of GOA, but with less computation time.
• ### High-temperature superconductivity stabilized by electron-hole interband coupling in collapsed tetragonal phase of KFe2As2 under high pressure(1501.02822)

We report a high-pressure study of simultaneous low-temperature electrical resistivity and Hall effect measurements on high quality single-crystalline KFe2As2 using designer diamond anvil cell techniques with applied pressures up to 33 GPa. In the low pressure regime, we show that the superconducting transition temperature T_c finds a maximum onset value of 7 K near 2 GPa, in contrast to previous reports that find a minimum T_c and reversal of pressure dependence at this pressure. Upon applying higher pressures, this T_c is diminished until a sudden drastic enhancement occurs coincident with a first-order structural phase transition into a collapsed tetragonal phase. The appearance of a distinct superconducting phase above 13 GPa is also accompanied by a sudden reversal of dominant charge carrier sign, from hole- to electron-like, which agrees with our band calculations predicting the emergence of an electron pocket and diminishment of hole pockets upon Fermi surface reconstruction. Our results suggest the high-temperature superconducting phase in KFe2As2 is substantially enhanced by the presence of nested electron and hole pockets, providing the key ingredient of high-T_c superconductivity in iron pnictide superconductors.
• ### Multi-Agent Distributed Optimization via Inexact Consensus ADMM(1402.6065)

Sept. 11, 2014 math.OC, cs.SY
Multi-agent distributed consensus optimization problems arise in many signal processing applications. Recently, the alternating direction method of multipliers (ADMM) has been used for solving this family of problems. ADMM based distributed optimization method is shown to have faster convergence rate compared with classic methods based on consensus subgradient, but can be computationally expensive, especially for problems with complicated structures or large dimensions. In this paper, we propose low-complexity algorithms that can reduce the overall computational cost of consensus ADMM by an order of magnitude for certain large-scale problems. Central to the proposed algorithms is the use of an inexact step for each ADMM update, which enables the agents to perform cheap computation at each iteration. Our convergence analyses show that the proposed methods converge well under some convexity assumptions. Numerical results show that the proposed algorithms offer considerably lower computational complexity than the standard ADMM based distributed optimization methods.
• ### A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization(1401.7079)

Jan. 28, 2014 math.OC
Consider the problem of minimizing the sum of a smooth convex function and a separable nonsmooth convex function subject to linear coupling constraints. Problems of this form arise in many contemporary applications including signal processing, wireless networking and smart grid provisioning. Motivated by the huge size of these applications, we propose a new class of first order primal-dual algorithms called the block successive upper-bound minimization method of multipliers (BSUM-M) to solve this family of problems. The BSUM-M updates the primal variable blocks successively by minimizing locally tight upper-bounds of the augmented Lagrangian of the original problem, followed by a gradient type update for the dual variable in closed form. We show that under certain regularity conditions, and when the primal block variables are updated in either a deterministic or a random fashion, the BSUM-M converges to the set of optimal solutions. Moreover, in the absence of linear constraints, we show that the BSUM-M, which reduces to the block successive upper-bound minimization (BSUM) method, is capable of linear convergence without strong convexity.
• ### Outage Constrained Robust Secure Transmission for MISO Wiretap Channels(1310.7158)

Oct. 27, 2013 cs.IT, math.IT
In this paper we consider the robust secure beamformer design for MISO wiretap channels. Assume that the eavesdroppers' channels are only partially available at the transmitter, we seek to maximize the secrecy rate under the transmit power and secrecy rate outage probability constraint. The outage probability constraint requires that the secrecy rate exceeds certain threshold with high probability. Therefore including such constraint in the design naturally ensures the desired robustness. Unfortunately, the presence of the probabilistic constraints makes the problem non-convex and hence difficult to solve. In this paper, we investigate the outage probability constrained secrecy rate maximization problem using a novel two-step approach. Under a wide range of uncertainty models, our developed algorithms can obtain high-quality solutions, sometimes even exact global solutions, for the robust secure beamformer design problem. Simulation results are presented to verify the effectiveness and robustness of the proposed algorithms.
• ### Solving Multiple-Block Separable Convex Minimization Problems Using Two-Block Alternating Direction Method of Multipliers(1308.5294)

Aug. 24, 2013 cs.NA, math.OC
In this paper, we consider solving multiple-block separable convex minimization problems using alternating direction method of multipliers (ADMM). Motivated by the fact that the existing convergence theory for ADMM is mostly limited to the two-block case, we analyze in this paper, both theoretically and numerically, a new strategy that first transforms a multi-block problem into an equivalent two-block problem (either in the primal domain or in the dual domain) and then solves it using the standard two-block ADMM. In particular, we derive convergence results for this two-block ADMM approach to solve multi-block separable convex minimization problems, including an improved O(1/\epsilon) iteration complexity result. Moreover, we compare the numerical efficiency of this approach with the standard multi-block ADMM on several separable convex minimization problems which include basis pursuit, robust principal component analysis and latent variable Gaussian graphical model selection. The numerical results show that the multiple-block ADMM, although lacks theoretical convergence guarantees, typically outperforms two-block ADMMs.
• ### Quasiparticle interference of C2-symmetric surface states in LaOFeAs parent compound(1008.2642)

We present scanning tunneling microscopy studies of the LaOFeAs parent compound of iron pnictide superconductors. Topographic imaging reveals two types of atomically flat surfaces, corresponding to the exposed LaO layer and FeAs layer respectively. On one type of surface, we observe strong standing wave patterns induced by quasiparticle interference of two-dimensional surface states. The distribution of scattering wavevectors exhibits pronounced two-fold symmetry, consistent with the nematic electronic structure found in the Ca(Fe1-xCox)2As2 parent state.