BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Robert M. Freund

Robert M. Freund appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCMachine Learningphysics.comp-phphysics.opticsComputationmath-phmath.MPmath.STStatistics Theory

Catalog footprint

What is connected

9works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

9 published item(s)

preprint2022arXiv

Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization

We propose a novel Stochastic Frank-Wolfe (a.k.a. conditional gradient) algorithm for constrained smooth finite-sum minimization with a generalized linear prediction/structure. This class of problems includes empirical risk minimization with sparse, low-rank, or other structured constraints. The proposed method is simple to implement, does not require step-size tuning, and has a constant per-iteration cost that is independent of the dataset size. Furthermore, as a byproduct of the method we obtain a stochastic estimator of the Frank-Wolfe gap that can be used as a stopping criterion. Depending on the setting, the proposed method matches or improves on the best computational guarantees for Stochastic Frank-Wolfe algorithms. Benchmarks on several datasets highlight different regimes in which the proposed method exhibits a faster empirical convergence than related methods. Finally, we provide an implementation of all considered methods in an open-source package.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

New Computational Guarantees for Solving Convex Optimization Problems with First Order Methods, via a Function Growth Condition Measure

Motivated by recent work of Renegar, we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem $f^* = \min_{x \in Q} f(x)$, where we presume knowledge of a strict lower bound $f_{\mathrm{slb}} < f^*$. [Indeed, $f_{\mathrm{slb}}$ is naturally known when optimizing many loss functions in statistics and machine learning (least-squares, logistic loss, exponential loss, total variation loss, etc.) as well as in Renegar's transformed version of the standard conic optimization problem; in all these cases one has $f_{\mathrm{slb}} = 0 < f^*$.] We introduce a new functional measure called the growth constant $G$ for $f(\cdot)$, that measures how quickly the level sets of $f(\cdot)$ grow relative to the function value, and that plays a fundamental role in the complexity analysis. When $f(\cdot)$ is non-smooth, we present new computational guarantees for the Subgradient Descent Method and for smoothing methods, that can improve existing computational guarantees in several ways, most notably when the initial iterate $x^0$ is far from the optimal solution set. When $f(\cdot)$ is smooth, we present a scheme for periodically restarting the Accelerated Gradient Method that can also improve existing computational guarantees when $x^0$ is far from the optimal solution set, and in the presence of added structure we present a scheme using parametrically increased smoothing that further improves the associated computational guarantees.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A New Perspective on Boosting in Linear Regression via Subgradient Optimization and Relatives

In this paper we analyze boosting algorithms in linear regression from a new perspective: that of modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression, namely the incremental forward stagewise algorithm (FS$_\varepsilon$) and least squares boosting (LS-Boost($\varepsilon$)), can be viewed as subgradient descent to minimize the loss function defined as the maximum absolute correlation between the features and residuals. We also propose a modification of FS$_\varepsilon$ that yields an algorithm for the Lasso, and that may be easily extended to an algorithm that computes the Lasso path for different values of the regularization parameter. Furthermore, we show that these new algorithms for the Lasso may also be interpreted as the same master algorithm (subgradient descent), applied to a regularized version of the maximum absolute correlation loss function. We derive novel, comprehensive computational guarantees for several boosting algorithms in linear regression (including LS-Boost($\varepsilon$) and FS$_\varepsilon$) by using techniques of modern first-order methods in convex optimization. Our computational guarantees inform us about the statistical properties of boosting algorithms. In particular they provide, for the first time, a precise theoretical description of the amount of data-fidelity and regularization imparted by running a boosting algorithm with a prespecified learning rate for a fixed but arbitrary number of iterations, for any dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion

Motivated principally by the low-rank matrix completion problem, we present an extension of the Frank-Wolfe method that is designed to induce near-optimal solutions on low-dimensional faces of the feasible region. This is accomplished by a new approach to generating ``in-face" directions at each iteration, as well as through new choice rules for selecting between in-face and ``regular" Frank-Wolfe steps. Our framework for generating in-face directions generalizes the notion of away-steps introduced by Wolfe. In particular, the in-face directions always keep the next iterate within the minimal face containing the current iterate. We present computational guarantees for the new method that trade off efficiency in computing near-optimal solutions with upper bounds on the dimension of minimal faces of iterates. We apply the new method to the matrix completion problem, where low-dimensional faces correspond to low-rank matrices. We present computational results that demonstrate the effectiveness of our methodological approach at producing nearly-optimal solutions of very low rank. On both artificial and real datasets, we demonstrate significant speed-ups in computing very low-rank nearly-optimal solutions as compared to either the Frank-Wolfe method or its traditional away-step variant.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fabrication-Adaptive Optimization, with an Application to Photonic Crystal Design

It is often the case that the computed optimal solution of an optimization problem cannot be implemented directly, irrespective of data accuracy, due to either (i) technological limitations (such as physical tolerances of machines or processes), (ii) the deliberate simplification of a model to keep it tractable (by ignoring certain types of constraints that pose computational difficulties), and/or (iii) human factors (getting people to "do" the optimal solution). Motivated by this observation, we present a modeling paradigm called "fabrication-adaptive optimization" for treating issues of implementation/fabrication. We develop computationally-focused theory and algorithms, and we present computational results for incorporating considerations of implementation/fabrication into constrained optimization problems that arise in photonic crystal design. The fabrication-adaptive optimization framework stems from the robust regularization of a function. When the feasible region is not a normed space (as typically encountered in application settings), the fabrication-adaptive optimization framework typically yields a non-convex optimization problem. (In the special case where the feasible region is a finite-dimensional normed space, we show that fabrication-adaptive optimization can be re-cast as an instance of modern robust optimization.) We study a variety of problems with special structures on functions, feasible regions, and norms, for which computation is tractable, and develop an algorithmic scheme for solving these problems in spite of the challenges of non-convexity. We apply our methodology to compute fabrication-adaptive designs of two-dimensional photonic crystals with a variety of prescribed features.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

New Analysis and Results for the Frank-Wolfe Method

We present new results for the Frank-Wolfe method (also known as the conditional gradient method). We derive computational guarantees for arbitrary step-size sequences, which are then applied to various step-size rules, including simple averaging and constant step-sizes. We also develop step-size rules and computational guarantees that depend naturally on the warm-start quality of the initial (and subsequent) iterates. Our results include computational guarantees for both duality/bound gaps and the so-called FW gaps. Lastly, we present complexity bounds in the presence of approximate computation of gradients and/or linear optimization subproblem solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Robust topology optimization of three-dimensional photonic-crystal band-gap structures

We perform full 3D topology optimization (in which "every voxel" of the unit cell is a degree of freedom) of photonic-crystal structures in order to find optimal omnidirectional band gaps for various symmetry groups, including fcc (including diamond), bcc, and simple-cubic lattices. Even without imposing the constraints of any fabrication process, the resulting optimal gaps are only slightly larger than previous hand designs, suggesting that current photonic crystals are nearly optimal in this respect. However, optimization can discover new structures, e.g. a new fcc structure with the same symmetry but slightly larger gap than the well known inverse opal, which may offer new degrees of freedom to future fabrication technologies. Furthermore, our band-gap optimization is an illustration of a computational approach to 3D dispersion engineering which is applicable to many other problems in optics, based on a novel semidefinite-program formulation for nonconvex eigenvalue optimization combined with other techniques such as a simple approach to impose symmetry constraints. We also demonstrate a technique for \emph{robust} topology optimization, in which some uncertainty is included in each voxel and we optimize the worst-case gap, and we show that the resulting band gaps have increased robustness to systematic fabrication errors.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

AdaBoost and Forward Stagewise Regression are First-Order Convex Optimization Methods

Boosting methods are highly popular and effective supervised learning methods which combine weak learners into a single accurate model with good statistical performance. In this paper, we analyze two well-known boosting methods, AdaBoost and Incremental Forward Stagewise Regression (FS$_\varepsilon$), by establishing their precise connections to the Mirror Descent algorithm, which is a first-order method in convex optimization. As a consequence of these connections we obtain novel computational guarantees for these boosting methods. In particular, we characterize convergence bounds of AdaBoost, related to both the margin and log-exponential loss function, for any step-size sequence. Furthermore, this paper presents, for the first time, precise computational complexity results for FS$_\varepsilon$.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Band Gap Optimization of Two-Dimensional Photonic Crystals Using Semidefinite Programming and Subspace Methods

In this paper, we consider the optimal design of photonic crystal band structures for two-dimensional square lattices. The mathematical formulation of the band gap optimization problem leads to an infinite-dimensional Hermitian eigenvalue optimization problem parametrized by the dielectric material and the wave vector. To make the problem tractable, the original eigenvalue problem is discretized using the finite element method into a series of finite-dimensional eigenvalue problems for multiple values of the wave vector parameter. The resulting optimization problem is large-scale and non-convex, with low regularity and non-differentiable objective. By restricting to appropriate eigenspaces, we reduce the large-scale non-convex optimization problem via reparametrization to a sequence of small-scale convex semidefinite programs (SDPs) for which modern SDP solvers can be efficiently applied. Numerical results are presented for both transverse magnetic (TM) and transverse electric (TE) polarizations at several frequency bands. The optimized structures exhibit patterns which go far beyond typical physical intuition on periodic media design.

0 citations0 reviewsNo code linkedOpen access