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. Convergence analysis of the Fast Subspace Descent method for convex optimization problems

   https://doi.org/10.1090/mcom/3526  

   Chen, Long; Hu, Xiaozhe; Wise, Steven M. (April 2020, Mathematics of computation)

   null (Ed.)

   The full approximation storage (FAS) scheme is a widely used multigrid method for nonlinear problems. In this paper, a new framework to design and analyze FAS-like schemes for convex optimization problems is developed. The new method, the fast subspace descent (FASD) scheme, which generalizes classical FAS, can be recast as an inexact version of nonlinear multigrid methods based on space decomposition and subspace correction. The local problem in each subspace can be simplified to be linear and one gradient descent iteration (with an appropriate step size) is enough to ensure a global linear (geometric) convergence of FASD for convex optimization problems. 

   more » « less
3. 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
4. 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
5. 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