More Like this

1. Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels

   Malach, Eran; Kamath, Pritish; Abbe, Emmanuel; Srebro, Nathan (July 2021, Proceedings of Machine Learning Research)

   null (Ed.)

   We study the relative power of learning with gradient descent on differentiable models, such as neural networks, versus using the corresponding tangent kernels. We show that under certain conditions, gradient descent achieves small error only if a related tangent kernel method achieves a non-trivial advantage over random guessing (a.k.a. weak learning), though this advantage might be very small even when gradient descent can achieve arbitrarily high accuracy. Complementing this, we show that without these conditions, gradient descent can in fact learn with small error even when no kernel method, in particular using the tangent kernel, can achieve a non-trivial advantage over random guessing. 

   more » « less
2. A Chebyshev Locally Optimal Block Preconditioned Conjugate Gradient Method for Product and Standard Symmetric Eigenvalue Problems

   https://doi.org/10.1137/23M1566017  

   Zhang, Tianqi; Xue, Fei (November 2024, SIAM Journal on Matrix Analysis and Applications)

   The discretized Bethe-Salpeter eigenvalue (BSE) problem arises in many body physics and quantum chemistry. Discretization leads to an {\color{black}algebraic} eigenvalue problem involving a matrix $$H\in \mathbb{C}^{2n\times 2n}$$ with a Hamiltonian-like structure. With proper transformations, {\color{black}the real BSE eigenproblem of form I and the complex BSE eigenproblem of form II} can be transformed into real product eigenvalue problems of order $$n$$ and $2n$, respectively. We propose a new variant of the Locally Optimal Block Preconditioned Conjugate Gradient (LOBPCG) {\color{black}enhanced with polynomial filters} to improve the robustness and effectiveness of a few well-known algorithms for computing the lowest eigenvalues of the product eigenproblems. {\color{black}Furthermore, our proposed method can be easily employed to solve large sparse standard symmetric eigenvalue problems.} We show that our ideal locally optimal algorithm delivers Rayleigh quotient approximation to the desired lowest eigenvalue that satisfies a global quasi-optimality, which is similar to the global optimality of the preconditioned conjugate gradient method for the iterative solution of a symmetric positive definite linear system. The robustness and efficiency of {\color{black}our proposed method} is illustrated by numerical experiments. 

   more » « less
3. Profiling Pareto Front With Multi-Objective Stein Variational Gradient Descent

   Xingchao Liu; Xin Tong; Qiang Liu (January 2021, Advances in neural information processing systems)

   Finding diverse and representative Pareto solutions from the Pareto front is a key challenge in multi-objective optimization (MOO). In this work, we propose a novel gradient-based algorithm for profiling Pareto front by using Stein variational gradient descent (SVGD). We also provide a counterpart of our method based on Langevin dynamics. Our methods iteratively update a set of points in a parallel fashion to push them towards the Pareto front using multiple gradient descent, while encouraging the diversity between the particles by using the repulsive force mechanism in SVGD, or diffusion noise in Langevin dynamics. Compared with existing gradient-based methods that require predefined preference functions, our method can work efficiently in high dimensional problems, and can obtain more diverse solutions evenly distributed in the Pareto front. Moreover, our methods are theoretically guaranteed to converge to the Pareto front. We demonstrate the effectiveness of our method, especially the SVGD algorithm, through extensive experiments, showing its superiority over existing gradient-based algorithms. 

   more » « less
4. Accelerated primal-dual methods for convex-strongly-concave saddle point problems

   Khalafi, Mohammad; Boob, Digvijay (July 2023, Proceedings of Machine Learning Research)

   We investigate a primal-dual (PD) method for the saddle point problem (SPP) that uses a linear approximation of the primal function instead of the standard proximal step, resulting in a linearized PD (LPD) method. For convex-strongly concave SPP, we observe that the LPD method has a suboptimal dependence on the Lipschitz constant of the primal function. To fix this issue, we combine features of Accelerated Gradient Descent with the LPD method resulting in a single-loop Accelerated Linearized Primal-Dual (ALPD) method. ALPD method achieves the optimal gradient complexity when the SPP has a semi-linear coupling function. We also present an inexact ALPD method for SPPs with a general nonlinear coupling function that maintains the optimal gradient evaluations of the primal parts and significantly improves the gradient evaluations of the coupling term compared to the ALPD method. We verify our findings with numerical experiments. 

   more » « less
5. A mean-field analysis of two-player zero-sum games

   Domingo-Enrich, Carles; Jelassi, S; Mensch, A; Rotskoff, G; Bruna, J (December 2020, Advances in neural information processing systems)

   null (Ed.)

   Finding Nash equilibria in two-player zero-sum continuous games is a central problem in machine learning, e.g. for training both GANs and robust models. The existence of pure Nash equilibria requires strong conditions which are not typically met in practice. Mixed Nash equilibria exist in greater generality and may be found using mirror descent. Yet this approach does not scale to high dimensions. To address this limitation, we parametrize mixed strategies as mixtures of particles, whose positions and weights are updated using gradient descent-ascent. We study this dynamics as an interacting gradient flow over measure spaces endowed with the Wasserstein-Fisher-Rao metric. We establish global convergence to an approximate equilibrium for the related Langevin gradient-ascent dynamic. We prove a law of large numbers that relates particle dynamics to mean-field dynamics. Our method identifies mixed equilibria in high dimensions and is demonstrably effective for training mixtures of GANs. 

   more » « less