Francesco Rinaldi

Beyond Local Influence: Improved Bounds, Exact Models and Efficient Algorithms for Component-Based Diffusion in Networks

Categories Combinatorial Optimization, Network Optimization Tags , ,

Diffusion in networks is often modeled as a local neighbor-based process: a node becomes active as a result of influence exerted by its active neighbors. However, in many technological and communication settings, adoption is driven not only by local influence, but by access to sufficiently large active connected regions. This paper studies such component-based diffusion … Read more

Breaking the Odd Cycle: Regularization and First-Order Optimization for the Maximum s-Plex Problem

Categories Network Optimization, Nonlinear Optimization Tags , , ,

Building on a new regularized continuous formulation which avoids spurious solutions of the maximum s-plex problem, we develop a tailored block-coordinate first-order method that combines away-step Frank-Wolfe updates on the standard simplex with linear optimization over the fractional b-matching polytope. We establish finite stabilization of the auxiliary variables, convergence to stationary points, and finite support … Read more

Constrained Variable Projection for Structured Problems

Categories Bilevel Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

Variable projection is a classical technique for separable nonlinear least-squares problems, in which variables that enter linearly are eliminated exactly, yielding a reduced nonlinear problem. By expressing this framework as a particular instance of a broader class of bilevel optimization problems, we develop a constrained variable-projection framework for data-science models, where the remaining variables are … Read more

Extrapolation-based Direct Search for Nonsmooth Stochastic Zeroth-Order Optimization

Categories Nonlinear Optimization, Nonsmooth Optimization, Stochastic Programming Tags , ,

We propose and analyze a stochastic direct-search method for unconstrained zeroth-order minimization of locally Lipschitz, possibly nonsmooth, objectives. The method combines random polling directions with a stochastic extrapolating line search based on a sufficient-decrease test of order \(p\). Under conditional accuracy assumptions on the stochastic estimates, which can be verified for mean-zero finite-higher-moment oracle noise … Read more

The Maximum Clique Problem under Adversarial Uncertainty: a min-max approach

Categories Nonlinear Optimization, Nonsmooth Optimization, Other Topics Tags , , ,

We analyze the problem of identifying large cliques in graphs that are affected by adversarial uncertainty. More specifically, we consider a new formulation, namely the adversarial maximum clique problem, which extends the classical maximum-clique problem to graphs with edges strategically perturbed by an adversary. The proposed mathematical model is thus formulated as a two-player zero-sum … Read more

Fast and Simple Multiclass Data Segmentation: An Eigendecomposition and Projection-Free Approach

Categories Data Science Algorithms, Data Science Applications, Nonlinear Optimization

Graph-based machine learning has seen an increased interest over the last decade with many connections to other fields of applied mathematics. Learning based on partial differential equations, such as the phase-field Allen-Cahn equation, allows efficient handling of semi-supervised learning approaches on graphs. The numerical solution of the graph Allen-Cahn equation via a convexity splitting or … Read more

Sequential test sampling for stochastic derivative-free optimization

Categories Nonlinear Optimization Tags , , ,

In many derivative-free optimization algorithms, a sufficient decrease condition decides whether to accept a trial step in each iteration. This condition typically requires that the potential objective function value decrease of the trial step, i.e., the true reduction in the objective function value that would be achieved by moving from the current point to the … Read more

Sequential test sampling for stochastic derivative-free optimization

Categories Nonlinear Optimization Tags , , ,

In many derivative-free optimization algorithms, a sufficient decrease condition decides whether to accept a trial step in each iteration. This condition typically requires that the potential objective function value decrease of the trial step, i.e., the true reduction in the objective function value that would be achieved by moving from the current point to the … Read more

Probabilistic Iterative Hard Thresholding for Sparse Learning

Categories Nonlinear Optimization, Stochastic Programming Tags , ,

For statistical modeling wherein the data regime is unfavorable in terms of dimensionality relative to the sample size, finding hidden sparsity in the ground truth can be critical in formulating an accurate statistical model. The so-called “l0 norm”, which counts the number of non-zero components in a vector, is a strong reliable mechanism of enforcing … Read more

Inexact Direct-Search Methods for Bilevel Optimization Problems

Categories Nonlinear Optimization, Nonsmooth Optimization, Optimization in Data Science

In this work, we introduce new direct search schemes for the solution of bilevel optimization (BO) problems. Our methods rely on a fixed accuracy black box oracle for the lower-level problem, and deal both with smooth and potentially nonsmooth true objectives. We thus analyze for the first time in the literature direct search schemes in … Read more