Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

The matrix completion problem seeks to recover a $d\times d$ ground truth matrix of low rank $r\ll d$ from observations of its individual elements. Realworld matrix completion is often a hugescale optimization problem, with $d$ so large that even the simplest fulldimension vector operations with $O(d)$ time complexity become prohibitively expensive. Stochastic gradient descent (SGD) is one of the few algorithms capable of solving matrix completion on a huge scale, and can also naturally handle streaming data over an evolving ground truth. Unfortunately, SGD experiences a dramatic slowdown when the underlying ground truth is illconditioned; it requires at least $O(\kappa\log(1/\epsilon))$ iterations to get $\epsilon$close to ground truth matrix with condition number $\kappa$. In this paper, we propose a preconditioned version of SGD that preserves all the favorable practical qualities of SGD for hugescale online optimization while also making it agnostic to $\kappa$. For a symmetric ground truth and the Root Mean Square Error (RMSE) loss, we prove that the preconditioned SGD converges to $\epsilon$accuracy in $O(\log(1/\epsilon))$ iterations, with a rapid linear convergence rate as if the ground truth were perfectly conditioned with $\kappa=1$. In our numerical experiments, we observe a similar acceleration for illconditioned matrix completion under the 1bit crossentropymore »

In practical instances of nonconvex matrix factorization, the rank of the true solution r^{\star} is often unknown, so the rank rof the model can be overspecified as r>r^{\star}. This overparameterized regime of matrix factorization significantly slows down the convergence of local search algorithms, from a linear rate with r=r^{\star} to a sublinear rate when r>r^{\star}. We propose an inexpensive preconditioner for the matrix sensing variant of nonconvex matrix factorization that restores the convergence rate of gradient descent back to linear, even in the overparameterized case, while also making it agnostic to possible illconditioning in the ground truth. Classical gradient descent in a neighborhood of the solution slows down due to the need for the model matrix factor to become singular. Our key result is that this singularity can be corrected by \ell_{2} regularization with a specific range of values for the damping parameter. In fact, a good damping parameter can be inexpensively estimated from the current iterate. The resulting algorithm, which we call preconditioned gradient descent or PrecGD, is stable under noise, and converges linearly to an information theoretically optimal error bound. Our numerical experiments find that PrecGD works equally well in restoring the linear convergence of other variants ofmore »

Training generative models, such as GANs, on a target domain containing limited examples (e.g., 10) can easily result in overfitting. In this work, we seek to utilize a large source domain for pretraining and transfer the diversity information from source to target. We propose to preserve the relative similarities and differences between instances in the source via a novel crossdomain distance consistency loss. To further reduce overfitting, we present an anchorbased strategy to encourage different levels of realism over different regions in the latent space. With extensive results in both photorealistic and nonphotorealistic domains, we demonstrate qualitatively and quantitatively that our fewshot model automatically discovers correspondences between source and target domains and generates more diverse and realistic images than previous methods.

This article establishes sufficient conditions for the uniqueness of AC power flow solutions via the monotonic relationship between real power flow and the phase angle difference. More specifically, we prove that the PΘ power flow problem has at most one solution for any acyclic or GSP graph. In addition, for arbitrary cyclic power networks, we show that multiple distinct solutions cannot exist under the assumption that angle differences across the lines are bounded by some limit related to the maximal girth of the network. In these cases, a vector of voltage phase angles can be uniquely determined (up to an absolute phase shift) given a vector of real power injections within the realizable range. The implication of this result for the classical power flow analysis is that under the conditions specified above, the problem has a unique physically realizable solution if the phasor voltage magnitudes are fixed. We also introduce a seriesparallel operator and show that this operator obtains a reduced and easiertoanalyze model for the power system without changing the uniqueness of power flow solutions.

Vedaldi A., Bischof H. (Ed.)