The densest subgraph problem in a graph (\dsg), in the simplest
form, is the following. Given an undirected graph $G=(V,E)$ find a
subset $S \subseteq V$ of vertices that maximizes the ratio
$|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints
in $S$. \dsg and several of its variants are well-studied in theory
and practice and have many applications in data mining and network
analysis. In this paper we study fast algorithms and structural
aspects of \dsg via the lens of \emph{supermodularity}.
For this we consider the densest supermodular subset problem (\dssp):
given a non-negative supermodular function $f: 2^V
\rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$.
For \dsg we describe a simple flow-based algorithm that outputs a
$(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time
where $m$ is the number of edges. Our algorithm is the first to have
a near-linear dependence on $m$ and $1/\eps$ and improves previous
methods based on an LP relaxation. It generalizes to hypergraphs, and
also yields a faster algorithm for directed \dsg.
Greedy peeling algorithms have been very popular for \dsg and
several variants due to their efficiency, empirical performance, and
worst-case approximation guarantees. We describe a simple peeling
algorithm for \dssp and analyze its approximation guarantee in a
fashion that unifies several existing results. Boob et
al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling
algorithm for \dsg which appears to work very well in practice, and
made a conjecture about its convergence to optimality. We
affirmatively answer their conjecture, and in fact prove that a
natural generalization of their algorithm converges to a
$(1-\eps)$-approximation for \emph{any} supermodular function $f$;
the key to our proof is to consider an LP formulation that is
derived via the \Lovasz extension of a supermodular function. For
\dsg the bound on the number of iterations we prove is $O(\frac{\Delta
\ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is
the maximum degree and $\lambda^*$ is the optimum value. Our work suggests
that iterative peeling can be an effective heuristic for
several objectives considered in the literature.
Finally, we show that the $2$-approximation for densest-at-least-$k$
subgraph \cite{ks-09} extends to the supermodular setting. We also
give a unified analysis of the peeling algorithm for this problem, and
via this analysis derive an approximation guarantee for a
generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave
function $g$.
more »
« less
On the Local Minima of the Empirical Risk
Population risk is always of primary interest in machine learning; however, learning algorithms only have access to the empirical risk. Even for applications with nonconvex nonsmooth losses (such as modern deep networks), the population risk is generally significantly more well-behaved from an optimization point of view than the empirical risk. In particular, sampling can create many spurious local minima. We consider a general framework which aims to optimize a smooth nonconvex function F (population risk) given only access to an approximation f (empirical risk) that is pointwise close to F (i.e., ||F − f||_\infty ≤ ν). Our objective is to find the \eps-approximate local minima of the underlying function F while avoiding the shallow local minima—arising because of the tolerance ν—which exist only in f. We propose a simple algorithm based on stochastic gradient descent
(SGD) on a smoothed version of f that is guaranteed to achieve our goal as long as ν ≤ O(\eps^{1.5}/d). We also provide an almost matching lower bound showing that our algorithm achieves optimal error tolerance ν among all algorithms making a polynomial number of queries of f. As a concrete example, we show that our results can be directly used to give sample complexities for learning a ReLU unit.
more »
« less
- Award ID(s):
- 1704656
- NSF-PAR ID:
- 10090514
- Date Published:
- Journal Name:
- Advances in neural information processing systems
- ISSN:
- 1049-5258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Continual (sequential) training and multitask (simultaneous) training are often attempting to solve the same overall objective: to find a solution that performs well on all considered tasks. The main difference is in the training regimes, where continual learning can only have access to one task at a time, which for neural networks typically leads to catastrophic forgetting. That is, the solution found for a subsequent task does not perform well on the previous ones anymore. However, the relationship between the different minima that the two training regimes arrive at is not well understood. What sets them apart? Is there a local structure that could explain the difference in performance achieved by the two different schemes? Motivated by recent work showing that different minima of the same task are typically connected by very simple curves of low error, we investigate whether multitask and continual solutions are similarly connected. We empirically find that indeed such connectivity can be reliably achieved and, more interestingly, it can be done by a linear path, conditioned on having the same initialization for both. We thoroughly analyze this observation and discuss its significance for the continual learning process. Furthermore, we exploit this finding to propose an effective algorithm that constrains the sequentially learned minima to behave as the multitask solution. We show that our method outperforms several state of the art continual learning algorithms on various vision benchmarks.more » « less
-
Training activation quantized neural networks involves minimizing a piecewise constant function whose gradient vanishes almost everywhere, which is undesirable for the standard back-propagation or chain rule. An empirical way around this issue is to use a straight-through estimator (STE) (Bengio et al., 2013) in the backward pass only, so that the “gradient” through the modified chain rule becomes non-trivial. Since this unusual “gradient” is certainly not the gradient of loss function, the following question arises: why searching in its negative direction minimizes the training loss? In this paper, we provide the theoretical justification of the concept of STE by answering this question. We consider the problem of learning a two-linear-layer network with binarized ReLU activation and Gaussian input data. We shall refer to the unusual “gradient” given by the STE-modifed chain rule as coarse gradient. The choice of STE is not unique. We prove that if the STE is properly chosen, the expected coarse gradient correlates positively with the population gradient (not available for the training), and its negation is a descent direction for minimizing the population loss. We further show the associated coarse gradient descent algorithm converges to a critical point of the population loss minimization problem. Moreover, we show that a poor choice of STE leads to instability of the training algorithm near certain local minima, which is verified with CIFAR-10 experiments.more » « less
-
Estimating the normalizing constant of an unnormalized probability distribution has important applications in computer science, statistical physics, machine learning, and statistics. In this work, we consider the problem of estimating the normalizing constant to within a multiplication factor of 1 ± ε for a μ-strongly convex and L-smooth function f, given query access to f(x) and ∇f(x). We give both algorithms and lowerbounds for this problem. Using an annealing algorithm combined with a multilevel Monte Carlo method based on underdamped Langevin dynamics, we show that O(d^{4/3}/\eps^2) queries to ∇f are sufficient. Moreover, we provide an information theoretic lowerbound, showing that at least d^{1-o(1)}/\eps^{2-o(1)} queries are necessary. This provides a first nontrivial lowerbound for the problem.more » « less
-
Tucker decomposition is a popular technique for many data analysis and machine learning applications. Finding a Tucker decomposition is a nonconvex optimization problem. As the scale of the problems increases, local search algorithms such as stochastic gradient descent have become popular in practice. In this paper, we characterize the optimization landscape of the Tucker decomposition problem. In particular, we show that if the tensor has an exact Tucker decomposition, for a standard nonconvex objective of Tucker decomposition, all local minima are also globally optimal. We also give a local search algorithm that can nd an approximate local (and global) optimal solution in polynomial time.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
